40 citations · 134 across the 11 of their papers we have counts for
8 papers · 1 filter
A Reduction from Chores Allocation to Job Scheduling
Xin Huang, Erel Segal-Halevi
We consider allocating indivisible chores among agents with different cost functions, such that all agents receive a cost of at most a constant factor times their maximin share. Th…
On picking sequences for chores
Uriel Feige, Xin Huang
We consider the problem of allocating indivisible chores to agents with additive disvaluation (cost) functions. It is easy to show that there are picking sequences that giv…
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…
Unified Fair Allocation of Goods and Chores via Copies
Yotam Gafni, Xin Huang, Ron Lavi +1
We consider fair allocation of indivisible items in a model with goods, chores, and copies, as a unified framework for studying: (1)~the existence of EFX and other solution concept…
Computing Welfare-Maximizing Fair Allocations of Indivisible Goods
Haris Aziz, Xin Huang, Nicholas Mattei +1
We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two…
The Constrained Round Robin Algorithm for Fair and Efficient Allocation
Haris Aziz, Xin Huang, Nicholas Mattei +1
We consider a multi-agent resource allocation setting that models the assignment of papers to reviewers. A recurring issue in allocation problems is the compatibility of welfare/ef…
An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
Xin Huang, Pinyan Lu
In this paper, we consider the problem of how to fairly dividing indivisible chores among agents. The fairness measure we considered here is the maximin share. The previous…
Envy-freeness up to any item with high Nash welfare: The virtue of donating items
Ioannis Caragiannis, Nick Gravin, Xin Huang
Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to an…