-
Uddannelse
Find uddannelse
Studievejledning
Kvalitet
- Forskning
-
Samarbejde
Virksomheder
Kommuner og regioner
Gymnasier
Myndigheder
-
Om AU
Organisation
Kontakt
Om AU
- Organisation
- Ledelse
- Strategi
- AU i tal
- AU's historie
- Internationalt samarbejde
- Bæredygtighed
- Campus 2.0
- Diversitet og ligestilling
- Ledige stillinger
- Presse
- Kontakt
Beyond Cake Cutting: Allocating Homogeneous Divisible Goods
Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review
- Ioannis Caragiannis
- Vasilis Gkatzelis, Drexel University ,
- Alexandros Psomas, Purdue University ,
- Daniel Schoepflin, Drexel University
The problem of fair division known as “cake cutting” has been the focus of multiple papers spanning several decades. The most prominent problem in this line of work has been to bound the query complexity of computing an envy-free outcome in the Robertson-Webb query model. However, the root of this problem's complexity is somewhat artificial: the agents' values are assumed to be additive across different pieces of the “cake” but infinitely complicated within each piece. This is unrealistic in most of the motivating examples, where the cake represents a finite collection of homogeneous goods. We address this issue by introducing a fair division model that more accurately captures these applications: the value that an agent gains from a given good depends only on the amount of the good they receive, yet it can be an arbitrary function of this amount, allowing the agents to express preferences that go beyond standard cake cutting. In this model, we study the query complexity of computing allocations that are not just envy-free, but also approximately Pareto optimal among all envy-free allocations. Using a novel flow-based approach, we show that we can encode the ex-post feasibility of randomized allocations via a polynomial number of constraints, which reduces our problem to solving a linear program.
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) |
| Antal sider | 9 |
| Forlag | International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) |
| Udgivelsesår | 2022 |
| Sider | 208-216 |
| ISBN (Elektronisk) | 9781713854333 |
| Status | Udgivet - 2022 |
| Begivenhed | 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 - Auckland, Virtual, New Zealand Varighed: 9 maj 2022 → 13 maj 2022 |
Konference
| Konference | 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022 |
|---|---|
| Land | New Zealand |
| By | Auckland, Virtual |
| Periode | 09/05/2022 → 13/05/2022 |
| Serietitel | Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS |
|---|---|
| Vol/bind | 1 |
| ISSN | 1548-8403 |
Bibliografisk note
Funding Information:
The second author was supported in part by an NSF CAREER award CCF-2047907 and NSF grant CCF-2008280. The third author was supported in part by a Google Research Scholar Award. The fourth author was supported in part by NSF grants CCF-2008280 and CCF-1755955. Part of this work was done while the last three authors were visiting the Simons Institute for the Theory of Computing.
Publisher Copyright:
© 2022 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved
Se relationer på Aarhus Universitet Citationsformater
ID: 306852149