Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914986710794240 |
|---|---|
| author | Bu, Xiaolin Li, Zihao Liu, Shengxin Lu, Xinhang Tao, Biaoshuai |
| author_facet | Bu, Xiaolin Li, Zihao Liu, Shengxin Lu, Xinhang Tao, Biaoshuai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06877 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods Bu, Xiaolin Li, Zihao Liu, Shengxin Lu, Xinhang Tao, Biaoshuai Computer Science and Game Theory 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. |
| title | Best-of-Both-Worlds Fair Allocation of Indivisible and Mixed Goods |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.06877 |