Comparing the Fairness of Recursively Balanced Picking Sequences
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917157320785920 |
|---|---|
| author | Celine, Karen Frilya Suksompong, Warut Yuen, Sheung Man |
| author_facet | Celine, Karen Frilya Suksompong, Warut Yuen, Sheung Man |
| contents | Picking sequences are well-established methods for allocating indivisible goods. Among the various picking sequences, recursively balanced picking sequences -- whereby each agent picks one good in every round -- are notable for guaranteeing allocations that satisfy envy-freeness up to one good. In this paper, we compare the fairness of different recursively balanced picking sequences using two key measures. Firstly, we demonstrate that all such sequences have the same price in terms of egalitarian welfare relative to other picking sequences. Secondly, we characterize the approximate maximin share (MMS) guarantees of these sequences. In particular, we show that compensating the agent who picks last in the first round by letting her pick first in every subsequent round yields the best MMS guarantee. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17604 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Comparing the Fairness of Recursively Balanced Picking Sequences Celine, Karen Frilya Suksompong, Warut Yuen, Sheung Man Computer Science and Game Theory Picking sequences are well-established methods for allocating indivisible goods. Among the various picking sequences, recursively balanced picking sequences -- whereby each agent picks one good in every round -- are notable for guaranteeing allocations that satisfy envy-freeness up to one good. In this paper, we compare the fairness of different recursively balanced picking sequences using two key measures. Firstly, we demonstrate that all such sequences have the same price in terms of egalitarian welfare relative to other picking sequences. Secondly, we characterize the approximate maximin share (MMS) guarantees of these sequences. In particular, we show that compensating the agent who picks last in the first round by letting her pick first in every subsequent round yields the best MMS guarantee. |
| title | Comparing the Fairness of Recursively Balanced Picking Sequences |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2512.17604 |