2 citations · 4 across the 12 of their papers we have counts for
15 papers · 1 filter
The Power of Share-Based Notions in Proving Envy-Based Fairness Guarantees
Hannaneh Akrami, Uriel Feige, Ryoga Mahara +2
We study the problem of fairly allocating indivisible goods among agents with monotone valuations. We introduce a new share-based fairness notion, the residual maximin share (RMMS)…
Fair Division in a Variable Setting
Harish Chandramouleeswaran, Prajakta Nimbhorkar, Nidhi Rathi
We study fair division of indivisible items under a variable input setting, where the set of agents or items may change over time. Starting from an arbitrary allocation, the goal i…
Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously
Hannaneh Akrami, Nidhi Rathi
We study the problem of computing \emph{fair} divisions of a set of indivisible goods among agents with \emph{additive} valuations. For the past many decades, the literature has ex…
Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity
Ioannis Caragiannis, Kurt Mehlhorn, Nidhi Rathi
Serial dictatorship is a simple mechanism for coordinating agents in solving combinatorial optimization problems according to their preferences. The most representative such proble…
Epistemic EFX Allocations Exist for Monotone Valuations
Hannaneh Akrami, Nidhi Rathi
We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is…
On the complexity of Pareto-optimal and envy-free lotteries
Ioannis Caragiannis, Kristoffer Arnsfelt Hansen, Nidhi Rathi
We study the classic problem of dividing a collection of indivisible resources in a fair and efficient manner among a set of agents having varied preferences. Pareto optimality is…
Optimally Interpolating between Ex-Ante Fairness and Welfare
Mikael Møller Høgsgaard, Panagiotis Karras, Wenyue Ma +2
For the fundamental problem of allocating a set of resources among individuals with varied preferences, the quality of an allocation relates to the degree of fairness and the colle…
A Discrete and Bounded Locally Envy-Free Cake Cutting Protocol on Trees
Ganesh Ghalme, Xin Huang, Yuka Machino +1
We study the classic problem of \emph{fairly} dividing a heterogeneous and divisible resource -- modeled as a line segment and typically called as a \emph{cake} -- among $n…
New Fairness Concepts for Allocating Indivisible Items
Ioannis Caragiannis, Jugal Garg, Nidhi Rathi +2
For the fundamental problem of fairly dividing a set of indivisible items among agents, envy-freeness up to any item (EFX) and maximin fairness (MMS) are arguably the most compelli…
Envy-Free Cake Cutting with Graph Constraints
Ganesh Ghalme, Xin Huang, Nidhi Rathi
We study the classic problem of fairly dividing a heterogeneous and divisible resource -- represented by a cake, -- among agents. This work considers an interesting var…
Optimizing over Serial Dictatorships
Ioannis Caragiannis, Nidhi Rathi
Motivated by the success of the serial dictatorship mechanism in social choice settings, we explore its usefulness in tackling various combinatorial optimization problems. We do so…
Fair Cake Division Under Monotone Likelihood Ratios
Siddharth Barman, Nidhi Rathi
This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents wi…
Fair and Efficient Cake Division with Connected Pieces
Eshwar Ram Arunachaleswaran, Siddharth Barman, Rachitesh Kumar +1
The classic cake-cutting problem provides a model for addressing fair and efficient allocation of a divisible, heterogeneous resource (metaphorically, the cake) among agents with d…
Fair Division with a Secretive Agent
Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi
We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with car…
Fully Polynomial-Time Approximation Schemes for Fair Rent Division
Eshwar Ram Arunachaleswaran, Siddharth Barman, Nidhi Rathi
We study the problem of fair rent division that entails splitting the rent and allocating the rooms of an apartment among roommates (agents) in a fair manner. In this setup, a dist…