Online fair division: Difference between revisions
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
| Line 10: | Line 10: | ||
The online nature of the problem requires different techniques and fairness criteria than in the classic, offline fair division. |
The online nature of the problem requires different techniques and fairness criteria than in the classic, offline fair division. |
||
== Online arrival of people == |
|||
=== The party cake-cutting problem === |
|||
Walsh<ref>{{Cite journal|last=Walsh|first=Toby|date=2011|editor-last=Brafman|editor-first=Ronen I.|editor2-last=Roberts|editor2-first=Fred S.|editor3-last=Tsoukiàs|editor3-first=Alexis|title=Online Cake Cutting|url=https://link.springer.com/chapter/10.1007/978-3-642-24873-3_22|journal=Algorithmic Decision Theory|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=292–305|doi=10.1007/978-3-642-24873-3_22|isbn=978-3-642-24873-3}}</ref> studies an online variant of the [[fair cake-cutting]] problem, in which agents arrive and depart during the division process, like in a party. Well-known fair division procedures like [[divide and choose]] and [[last diminisher]] can be adapted to this setting. They obtain online forms of [[Proportional cake-cutting|proportionality]] and [[Envy-free cake-cutting|envy-freeness]]. The online version of divide-and-choose is more robust to collusion, and has better empirical performance. |
|||
== References == |
== References == |
||
Revision as of 14:17, 19 March 2021
Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made.[1] Some situations in which not all resources are availble include:
- Allocating food donations to charities (the "food bank" problem). Each donation must be allocated immediately when it arrives, before future donations arrive.
- Allocating donated blood or organs to patients. Again, each donation must be allocated immediately, and it is not known when and what future donations will be.
Some situations in which not all participants are availble include:
- Dividing a cake among people in a party. Some people come early and want to get a cake when they arrive, but other people may come later.
- Dividing the rent and rooms among tenants in a rented apartment, when one or more of them are not available during the allocation.
The online nature of the problem requires different techniques and fairness criteria than in the classic, offline fair division.
Online arrival of people
The party cake-cutting problem
Walsh[2] studies an online variant of the fair cake-cutting problem, in which agents arrive and depart during the division process, like in a party. Well-known fair division procedures like divide and choose and last diminisher can be adapted to this setting. They obtain online forms of proportionality and envy-freeness. The online version of divide-and-choose is more robust to collusion, and has better empirical performance.
References
- ^ Aleksandrov, Martin; Walsh, Toby (2020-04-03). "Online Fair Division: A Survey". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (09): 13557–13562. doi:10.1609/aaai.v34i09.7081. ISSN 2374-3468.
- ^ Walsh, Toby (2011). Brafman, Ronen I.; Roberts, Fred S.; Tsoukiàs, Alexis (eds.). "Online Cake Cutting". Algorithmic Decision Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 292–305. doi:10.1007/978-3-642-24873-3_22. ISBN 978-3-642-24873-3.