TY - GEN
T1 - Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods
AU - Bu, Xiaolin
AU - Li, Zihao
AU - Liu, Shengxin
AU - Lu, Xinhang
AU - Tao, Biaoshuai
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.
PY - 2026
Y1 - 2026
N2 - We study the problem of fairly allocating either a set of indivisible goods or a set of mixed divisible and indivisible goods (i.e., mixed goods) to agents with additive utilities, taking the best-of-both-worlds perspective of guaranteeing fairness properties both ex-ante and ex-post. The ex-post fairness notions considered in this paper are relaxations of envy-freeness, specifically, EFX for indivisible-goods allocation, and EFM for mixed-goods allocation. For two agents, we show that there is a polynomial-time randomized algorithm that achieves ex-ante envy-freeness and ex-post EFX / EFM simultaneously. For n agents with bi-valued utilities, we show there exist randomized allocations that are (i) ex-ante proportional and ex-post EFM, and (ii) ex-ante envy-free, ex-post EFX, and ex-post fractionally Pareto optimal.
AB - We study the problem of fairly allocating either a set of indivisible goods or a set of mixed divisible and indivisible goods (i.e., mixed goods) to agents with additive utilities, taking the best-of-both-worlds perspective of guaranteeing fairness properties both ex-ante and ex-post. The ex-post fairness notions considered in this paper are relaxations of envy-freeness, specifically, EFX for indivisible-goods allocation, and EFM for mixed-goods allocation. For two agents, we show that there is a polynomial-time randomized algorithm that achieves ex-ante envy-freeness and ex-post EFX / EFM simultaneously. For n agents with bi-valued utilities, we show there exist randomized allocations that are (i) ex-ante proportional and ex-post EFM, and (ii) ex-ante envy-free, ex-post EFX, and ex-post fractionally Pareto optimal.
KW - Fair division
KW - Indivisible goods
KW - Mixed goods
KW - Randomization and approximation
UR - https://www.scopus.com/pages/publications/105027210322
U2 - 10.1007/978-3-032-08560-3_16
DO - 10.1007/978-3-032-08560-3_16
M3 - 会议稿件
AN - SCOPUS:105027210322
SN - 9783032085597
T3 - Lecture Notes in Computer Science
SP - 277
EP - 294
BT - Web and Internet Economics - 20th International Conference, WINE 2024, Proceedings
A2 - Mavronicolas, Marios
A2 - Qi, Qi
A2 - Schoenebeck, Grant
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th International Conference on Web and Internet Economics, WINE 2024
Y2 - 2 December 2024 through 5 December 2024
ER -