Discrepancy And Fair Division For Non-Additive Valuations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912596375896064 |
|---|---|
| author | la Tour, Max Dupre Fujii, Kaito |
| author_facet | la Tour, Max Dupre Fujii, Kaito |
| contents | We extend the notion of combinatorial discrepancy to \emph{non-additive} functions. Our main result is an upper bound of $O(\sqrt{n \log(nk)})$ on the non-additive $k$-color discrepancy when $k$ is a prime power. We demonstrate two applications of this result to problems in fair division. First, we establish a bound for a consensus halving problem, where fairness is measured by the minimum number of items that must be transferred between the two parts to eliminate envy. Second, we improve the upper bound on the total subsidy required to achieve an envy-free allocation when the number of agents is a prime power, obtaining an $O(n \sqrt{n \log n})$ bound. This constitutes the first known subquadratic guarantee in this setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16802 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Discrepancy And Fair Division For Non-Additive Valuations la Tour, Max Dupre Fujii, Kaito Computer Science and Game Theory Discrete Mathematics We extend the notion of combinatorial discrepancy to \emph{non-additive} functions. Our main result is an upper bound of $O(\sqrt{n \log(nk)})$ on the non-additive $k$-color discrepancy when $k$ is a prime power. We demonstrate two applications of this result to problems in fair division. First, we establish a bound for a consensus halving problem, where fairness is measured by the minimum number of items that must be transferred between the two parts to eliminate envy. Second, we improve the upper bound on the total subsidy required to achieve an envy-free allocation when the number of agents is a prime power, obtaining an $O(n \sqrt{n \log n})$ bound. This constitutes the first known subquadratic guarantee in this setting. |
| title | Discrepancy And Fair Division For Non-Additive Valuations |
| topic | Computer Science and Game Theory Discrete Mathematics |
| url | https://arxiv.org/abs/2509.16802 |