1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Economics
  4. Volume 11, 2019
  5. Article

Annual Review of Economics

Volume 11, 2019

Fair Division in the Internet Age

Abstract

Fair division, a key concern in the design of many social institutions, has for 70 years been the subject of interdisciplinary research at the interface of mathematics, economics, and game theory. Motivated by the proliferation of moneyless transactions on the internet, the computer science community has recently taken a deep interest in fairness principles and practical division rules. The resulting literature brings a fresh concern for computational simplicity (scalable rules) and realistic implementation. In this review of the most salient fair division results of the past 30 years, I concentrate on division rules with the best potential for practical implementation. The critical design parameter is the message space that the agents must use to report their individual preferences. A simple preference domain is key both to realistic implementation and to the existence of division rules with strong normative and incentive properties. I discuss successively the one-dimensional single-peaked domain, Leontief utilities, ordinal ranking, dichotomous preferences, and additive utilities. Some of the theoretical results in the latter domain are already implemented in the user-friendly SPLIDDIT platform ().

Keyword(s): bads, competitive division, egalitarian division, envy free, fair share, goods, JEL D63, JEL D70, manna, preference domains
Loading

Article metrics loading...

/content/journals/10.1146/annurev-economics-080218-025559
2019-08-02
2024-04-25
Loading full text...

Full text loading...

/deliver/fulltext/economics/11/1/annurev-economics-080218-025559.html?itemId=/content/journals/10.1146/annurev-economics-080218-025559&mimeType=html&fmt=ahah

Literature Cited

  1. Abdulkadiroglu A, Sőnmez T 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66:689–701
     [Google Scholar]
  2. Aumann RJ, Maschler M 1985. Game theoretic analysis of a bankruptcy problem from the Talmud. J. Econ. Theory 36:2195–213
     [Google Scholar]
  3. Aumann Y, Dombb Y 2010. The efficiency of fair division with connected pieces. Internet and Network Economics A Saberi26–37 Berlin: Springer
     [Google Scholar]
  4. Aziz A, McKenzie S 2016. A discrete and bounded envy-free cake cutting protocol for any number of agents. Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 9–11 Oct416–27 New Brunswick, NJ: IEEE
     [Google Scholar]
  5. Aziz H, Caragianis I, Igarashi A, Walsh T 2018. Fair allocation of combinations of indivisible goods and chores. arXiv:1807.10684 [cs.GT]
    [Google Scholar]
  6. Aziz H, Rauchecker G, Schryen G, Walsh T 2017. Algorithms for max-min share fair allocation of indivisible chores. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)335–41 Menlo Park, CA: AAAI
     [Google Scholar]
  7. Babaioff M, Nisan N, Talgam-Cohen I 2017. Competitive equilibria with indivisible goods and generic budgets. arXiv:1703.08150 [cs.GT]
    [Google Scholar]
  8. Barbera S, Jackson M, Neme A 1997. Strategy-proof allotment rules. Games Econ. Behav. 18:GA970511
     [Google Scholar]
  9. Barman S, Krishnamurthy SK, Vaish R 2018. Finding fair and efficient allocations. Proceedings of the 2018 ACM Conference on Economics and Computation (EC ‘18), June 18–22557–74 New York: ACM
     [Google Scholar]
  10. Berliant M, Dunz K, Thomson W 1992. On the fair division of a heterogeneous commodity. J. Math. Econ. 21:201–16
     [Google Scholar]
  11. Bochet O, Ilkilic R, Moulin H 2013. Egalitarianism under earmark constraints. J. Econ. Theory 148:535–62
     [Google Scholar]
  12. Bochet O, Ilkilic R, Moulin H, Sethuraman J 2012. Balancing supply and demand under bilateral constraints. Theor. Econ. 7:3395–424
     [Google Scholar]
  13. Bogomolnaia A 2015. Random assignment: redefining the serial rule. J. Econ. Theory 158:A308–31
     [Google Scholar]
  14. Bogomolnaia A, Heo EJ 2012. Probabilistic assignment of objects: characterizing the serial rule. J. Econ. Theory 147:52072–82
     [Google Scholar]
  15. Bogomolnaia A, Moulin H 2001. A new solution to the random assignment problem. J. Econ. Theory 100:295–328
     [Google Scholar]
  16. Bogomolnaia A, Moulin H 2002. A simple random assignment problem with a unique solution. Econ. Theory 19:298–317
     [Google Scholar]
  17. Bogomolnaia A, Moulin H 2004. Random matching under dichotomous preferences. Econometrica 72:257–79
     [Google Scholar]
  18. Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaia E 2017. Competitive division of a mixed manna. Econometrica 85:61847–71
     [Google Scholar]
  19. Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaia E 2019. Dividing bads under additive utilities. Soc. Choice Welf. 52:3395–417
     [Google Scholar]
  20. Bouveret S, Lang J 2008. Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity. J. Artif. Intel. Res. 32:525–64
     [Google Scholar]
  21. Brams SJ, Taylor AD 1995. An envy-free cake division protocol. Am. Math. Mon. 102:19–18
     [Google Scholar]
  22. Brams SJ, Taylor AD 1996. Fair Division: From Cake-Cutting to Dispute Resolution Cambridge, UK: Cambridge Univ. Press
  23. Branzei S 2015. A note on envy-free cake cutting with polynomial valuations. Inf. Proc. Lett. 115:293–95
     [Google Scholar]
  24. Budish E 2011. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Political Econ. 119:61061–103
     [Google Scholar]
  25. Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J 2016. The unreasonable fairness of maximum Nash welfare. Proceedings of the 2016 ACM Conference on Economics and Computation (EC'16)305–22 New York: ACM
     [Google Scholar]
  26. Che YK, Kojima F 2010. Asymptotic equivalence of probabilistic serial and random priority mechanisms. Econometrica 78:51625–72
     [Google Scholar]
  27. Ching S 1994. An alternative characterization of the uniform rule. Soc. Choice Welf. 40:57–60
     [Google Scholar]
  28. Chipman JS 1974. Homothetic preferences and aggregation. J. Econ. Theory 8:26–38
     [Google Scholar]
  29. Cole R, Devanur NR, Gkatzelis V, Jain K, Mai T 2017. Convex program duality, Fisher markets, and Nash social welfare. Proceedings of the 2017 ACM Conference on Economics and Computation (EC ‘17)459–60 New York: ACM
     [Google Scholar]
  30. Cole R, Gkatzelis V 2015. Approximating the Nash social welfare with indivisible items. Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC)371–80 New York: ACM
     [Google Scholar]
  31. Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV 2008. Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55:22
     [Google Scholar]
  32. Dubins LE, Spanier EH 1961. How to cut a cake fairly. Am. Math. Mon. 68:1–17
     [Google Scholar]
  33. Dutta B, Ray D 1989. A concept of egalitarianism under participation constraints. Econometrica 59:615–36
     [Google Scholar]
  34. Dworkin R 1981a. What is equality? Part I: equality of welfare. Phil. Public Aff. 10:185–246
     [Google Scholar]
  35. Dworkin R 1981b. What is equality? Part II: equality of resources. Phil. Public Aff. 10:283–345
     [Google Scholar]
  36. Eisenberg E, Gale D 1959. Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Stat. 30:1165–68
     [Google Scholar]
  37. Fleurbaey M 1996. Théories Economiques de la Justice Paris: Economica
  38. Foley D 1967. Resource allocation and the public sector. Yale Econ. Essays 7:45–98
     [Google Scholar]
  39. Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I 2011. Dominant resource fairness: fair allocation of multiple resource types. Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI)24–37 Berkeley, CA: USENIX
     [Google Scholar]
  40. Goldman J, Procaccia AD 2014. Spliddit: unleashing fair division algorithms. SIGecom Exch. 13:241–46
     [Google Scholar]
  41. Guo M, Conitzer V 2007. Worst case optimal redistribution of VCG payments. Proceedings of the 8th ACM Conference on Electronic Commerce (EC ‘07), San Diego, CA30–39 New York: ACM
     [Google Scholar]
  42. Hashimoto T, Hirata D, Kesten O, Kurino M, Unver U 2014. Two axiomatic approaches to the probabilistic serial mechanism. Theor. Econ. 9:1253–77
     [Google Scholar]
  43. Hurwicz L 1978. On the interaction between information and incentives in organizations. Communication and Control in Society K Krippendorff123–47 New York: Sci. Publ.
     [Google Scholar]
  44. Hylland A, Zeckhauser R 1979. The efficient allocations of individuals to positions. J. Political Econ. 87:293–314
     [Google Scholar]
  45. Kalai E, Smorodinsky M 1975. Other solutions to Nash's bargaining problem. Econometrica 43:3513–18
     [Google Scholar]
  46. Katta AK, Sethuraman J 2006. A solution to the random assignment problem on the full preference domain. J. Econ. Theory 131:1231–50
     [Google Scholar]
  47. Kurokawa D, Lai JK, Procaccia AD 2013. How to cut a cake before the party ends. Proceedings of the 27th AAAI Conference on Artificial Intelligence555–61 New York: ACM
     [Google Scholar]
  48. Kurokawa D, Procaccia AD, Shah N 2015. Leximin allocations in the real world. Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC ‘15), Portland, OR, June 15–19345–62 New York: ACM
     [Google Scholar]
  49. Kurokawa D, Procaccia AD, Wang J 2016. When can the maximin share guarantee be guaranteed. Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI)523–29 Menlo Park, CA: AAAI
     [Google Scholar]
  50. Lee E 2017. APX-hardness of maximizing Nash social welfare with indivisible items. Inf. Proc. Lett. 122:17–20
     [Google Scholar]
  51. Li J, Xue J 2013. Egalitarian division under Leontief preferences. Econ. Theory 54:3597–622
     [Google Scholar]
  52. Li S 2017. Obviously strategy-proof mechanisms. Am. Econ. Rev. 107:3257–87
     [Google Scholar]
  53. Manurangsi P, Suksompong W 2018. When do envy-free allocations exist. arXiv:1811.01630 [cs.GT]
    [Google Scholar]
  54. Markakis E 2017. Approximation algorithms and hardness results for fair division. Trends in Computational Social Choice U Endriss231–48 AI Access
    [Google Scholar]
  55. Mas-Colell A 1992. Equilibrium theory with possibly sated preferences. Equilibrium and Dynamics: Essays in Honor of David Gale M Majumdar201–13 New York: St. Martin's Press
     [Google Scholar]
  56. Mas-Colell A, Whinston MD, Green JR 1995. Microeconomic Theory Oxford, UK: Oxford Univ. Press
  57. Maskin E 1999. Nash equilibrium and welfare optimality. Rev. Econ. Stud. 66:83–114
     [Google Scholar]
  58. McLennan A 2018. Efficient disposal equilibria of pseudomarkets Unpublished manuscript, Univ. Queensland, Aust.
  59. Moulin H 1988. Axioms of Cooperative Decision Making Cambridge, UK: Cambridge Univ. Press
  60. Moulin H 1992. An application of the Shapley value to fair division with money. Econometrica 60:1331–49
     [Google Scholar]
  61. Moulin H 1995. Cooperative Microeconomics: A Game-Theoretic Introduction Princeton, NJ: Princeton Univ. Press
  62. Moulin H 1999. Rationing a commodity along fixed paths. J. Econ. Theory 84:41–72
     [Google Scholar]
  63. Moulin H 2009. Almost budget-balanced VCG mechanisms to assign multiple objects. J. Econ. Theory 144:196–119
     [Google Scholar]
  64. Moulin H 2017. One-dimensional mechanism design. Theor. Econ. 12:2587–619
     [Google Scholar]
  65. Moulin H, Thomson W 1988. Can everyone benefit from growth? Two difficulties. J. Math. Econ. 17:339–45
     [Google Scholar]
  66. Nash J 1950. The bargaining problem. Econometrica 18:2155–62
     [Google Scholar]
  67. Nicolo A 2004. Efficiency and truthfulness with Leontief preferences: a note on two-agent, two-good economies. Rev. Econ. Des. 8:373–82
     [Google Scholar]
  68. O'Neill B 1982. A problem of rights arbitration in the Talmud. Math. Soc. Sci. 2:345–71
     [Google Scholar]
  69. Orlin JB 2010. Improved algorithms for computing Fisher's market clearing prices. Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC ‘10)291–300 New York: ACM
     [Google Scholar]
  70. Pazner E, Schmeidler D 1978. Egalitarian equivalent allocations: a new concept of economic equity. Q. J. Econ. 92:4671–87
     [Google Scholar]
  71. Plaut B, Roughgarden T 2018. Almost envy-freeness with general valuations. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ‘18), New Orleans, LA, 7–10 Jan.2584–603 New York: ACM
     [Google Scholar]
  72. Pratt JW, Zeckhauser RJ 1990. The fair and efficient division of the Winsor family silver. Manag. Sci. 36:1293–301
     [Google Scholar]
  73. Procaccia AD 2013. Cake cutting: not just child's play. Commun. ACM 56:778–87
     [Google Scholar]
  74. Procaccia AD, Wang J 2014. Fair enough: guaranteeing approximate maximin shares. Proceedings of the 14th ACM Conference on Economics and Computation (EC ‘14)675–92 New York: ACM
     [Google Scholar]
  75. Pycia M, Troyan P 2018. Obvious dominance and random priority Unpublished manuscript, Univ. Zurich
  76. Rawls J 1971. A Theory of Justice Cambridge, MA: Harvard Univ. Press
  77. Robertson JM, Webb WA 1998. Cake Cutting Algorithms: Be Fair If You Can Natick, MA: AK Peters
  78. Roemer J 1996. Theories of Distributive Justice Cambridge, MA: Harvard Univ. Press
  79. Roth AE, Sönmez T, Ünver MU 2004. Kidney exchange. Q. J. Econ. 119:2457–88
     [Google Scholar]
  80. Schummer J 1997. Strategy-proofness versus efficiency on restricted domains of exchange economies. Soc. Choice Welf. 14:47–56
     [Google Scholar]
  81. Segal-Halevi E, Nitzan S, Hassidim A, Aumann Y 2017. Fair and square: cake-cutting in two dimensions. J. Math. Econ. 70:1–28
     [Google Scholar]
  82. Segal-Halevi E, Sziklai B 2018. Monotonicity and competitive equilibrium in cake-cutting. Econ. Theory. https://doi.org/10.1007/s00199-018-1128-6
     [Crossref] [Google Scholar]
  83. Sen A 1970. Collective Choice and Social Welfare San Francisco: Holden Day
  84. Sprumont Y 1991. The division problem with single-peaked preferences: a characterization of the uniform allocation rule. Econometrica 59:509–19
     [Google Scholar]
  85. Steinhaus H 1948. The problem of fair division. Econometrica 16:101–4
     [Google Scholar]
  86. Steinhaus H 1949. Sur la division pragmatique. Econometrica 17:315–19
     [Google Scholar]
  87. Su FE 1999. Rental harmony: Sperner's lemma in fair division. Am. Math. Mon. 10:930–42
     [Google Scholar]
  88. Thomson W 1983. The fair division of a fixed supply among a growing population. Math. Oper. Res. 8:319–26
     [Google Scholar]
  89. Thomson W 2019. The Theory of Fair Allocation Princeton, NJ: Princeton Univ. Press In press
  90. Varian H 1974. Equity, envy and efficiency. J. Econ. Theory 9:63–91
     [Google Scholar]
  91. Zhou L 1991. Inefficiency of strategy-proof allocation mechanisms for pure exchange economies. Soc. Choice Welf. 8:247–57
     [Google Scholar]
/content/journals/10.1146/annurev-economics-080218-025559
Loading
  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error