Free disposal
In various parts of economics, the term free disposal implies that resources can be discarded without any cost. For example, a fair division setting with free disposal is a setting where some resources have to be divided fairly, but some of the resources may be left undivided, discarded or donated.
Examples of situations with free disposal are allocation of food, clothes jewels etc. Examples of situations without free disposal are:
- Chore division - since all chores must be done.
- Allocation of land with an old structure - since the structure may have to be destructed, and destruction is costly.
- Allocation of an old car - since the car may have to be carried away to used cars garage, and moving it may be costly.
- Allocation of shares in a firm that may have debts - since the firm cannot be disposed of without paying its debts first.
The free disposal assumption may be useful for several reasons:
- It enables truthful cake-cutting algorithms:[1][2] The option to discard some of the cake gives the players an incentive to reveal their true valuations.
- It enables fast envy-free cake-cutting algorithms,[3][4] and more economically-efficient envy-free allocations:[5] Discarding some of the cake helps to reduce envy.
- It enables online assignment algorithms.[6]
References
[edit]- ^ Chen, Yiling; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013-01-01). "Truth, justice, and cake cutting" (PDF). Games and Economic Behavior. 77 (1): 284–297. doi:10.1016/j.geb.2012.10.009. ISSN 0899-8256.
- ^ Bei, Xiaohui; Huzhang, Guangda; Suksompong, Warut (2020). "Truthful fair division without free disposal". Social Choice and Welfare. 55 (3): 523–545. arXiv:1804.06923. doi:10.1007/s00355-020-01256-0. PMC 7497335. PMID 33005068.
- ^ Segal-Halevi, Erel; Hassidim, Avinatan; Aumann, Yonatan (2016). "Waste Makes Haste". ACM Transactions on Algorithms. 13: 1–32. arXiv:1511.02599. doi:10.1145/2988232. S2CID 11358086.
- ^ Aziz, Haris; MacKenzie, Simon (2016). "A discrete and bounded envy-free cake cutting protocol for any number of agents". FOCS 2016. arXiv:1604.03655. Bibcode:2016arXiv160403655A.
- ^ Arzi, Orit; Aumann, Yonatan; Dombb, Yair (2016-04-01). "Toss one's cake, and eat it too: partial divisions can improve social welfare in cake cutting". Social Choice and Welfare. 46 (4): 933–954. doi:10.1007/s00355-015-0943-y. ISSN 1432-217X. S2CID 29132296.
- ^ Feldman, Jon; Korula, Nitish; Mirrokni, Vahab; Muthukrishnan, S.; Pál, Martin (2009). "Online Ad Assignment with Free Disposal". In Leonardi, Stefano (ed.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 5929. Springer Berlin Heidelberg. pp. 374–385. doi:10.1007/978-3-642-10841-9_34. ISBN 978-3-642-10841-9.