Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods
<|reference_start|>Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods: 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.<|reference_end|>
@article{bu2024best-of-both-worlds,
    title={Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods},
    author={Xiaolin Bu, Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao},
    journal={arXiv preprint arXiv:2410.06877},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06877},
    primaryClass={cs.GT}
}