4 papers
Constant Weighted Maximin Share Approximations for Chores
Bo Li, Fangxiao Wang, Shiji Xing
We study the fair allocation of indivisible chores among agents with asymmetric weights. Among the various fairness notions, weighted maximin share (WMMS) stands out as particularl…
Approximate Maximin Share with Subjective Divisibility: Beating the 1/2 Barrier
Xiaohui Bei, Ke Ding, Bo Li +1
Maximin share (MMS) stands out as a central notion in fair resource allocation. It is known that exact MMS fairness is not always attainable, especially when agents differ along tw…
Approximate Envy-Free Allocations up to any Goods
Aris Filos-Ratsikas, Georgios Kalantzis, Fangxiao Wang
We study the problem of finding approximate envy-free allocations up to any goods (-EFkX), when agents have additive values over goods in a bundle. As our main result, we s…
When is Truthfully Allocating Chores no Harder than Goods?
Bo Li, Biaoshuai Tao, Fangxiao Wang +3
We study the problem of fairly and efficiently allocating a set of items among strategic agents with additive valuations, where items are either all indivisible or all divisible. W…