4 papers · 1 filter
A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations
Xin Huang, Shengwei Zhou
We study maximin share (MMS) allocations of indivisible goods under nonnegative additive valuations. We give a strongly polynomial-time algorithm that allocates to every agent a bu…
Whoever Said Money Won't Solve All Your Problems? Weighted Envy-free Allocation with Subsidy
Noga Klein Elmalem, Haris Aziz, Rica Gonen +7
We explore solutions for fairly allocating indivisible items among agents assigned weights representing their entitlements. Our fairness goal is weighted-envy-freeness (WEF), where…
Improved Maximin Share Approximations for Chores by Bin Packing
Jugal Garg, Xin Huang, Erel Segal-Halevi
We study fair division of indivisible chores among agents with additive cost functions using the popular fairness notion of maximin share (MMS). Since MMS allocations do not al…
Weighted Envy-free Allocation with Subsidy
Haris Aziz, Xin Huang, Kei Kimura +4
We consider the problem of fair allocation of indivisible items with subsidies when agents have weighted entitlements. After highlighting several important differences from the unw…