Efficient fair division with minimal sharing. (English) Zbl 1496.90088
Summary: A collection of objects, some of which are good and some of which are bad, is to be divided fairly among agents with different tastes, modeled by additive utility functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then a fair division may not exist. What is the smallest number of objects that must be shared between two or more agents to attain a fair and efficient division? In this paper, fairness is understood as proportionality or envy-freeness and efficiency as fractional Pareto-optimality. We show that, for a generic instance of the problem (all instances except a zero-measure set of degenerate problems), a fair fractionally Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time, assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where agents’ valuations are aligned for many objects.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90C27 | Combinatorial optimization |
| 90C90 | Applications of mathematical programming |
Keywords:
fair division; polynomial-time algorithm; discrete objects; fractional Pareto-optimality; envy-freeness; proportional fairnessReferences:
| [1] | Abdulkadiroglu A, Sonmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689.Crossref, Google Scholar · Zbl 1019.91016 · doi:10.2307/2998580 |
| [2] | Aleksandrov M (2020) Jealousy-freeness and other common properties in fair division of mixed manna. Preprint, submitted May 12, https://arxiv.org/abs/ 2004.11469. Google Scholar |
| [3] | Aleksandrov M, Walsh T (2020) Two algorithms for additive and fair division of mixed manna. Schmid U, Klügl F, Wolter D eds. 43rd German Conf. Artificial Intelligence (Springer, Cham), 3-17.Google Scholar · Zbl 1520.91200 |
| [4] | Aleksandrov M, Aziz H, Gaspers S, Walsh T (2015) Online fair division: Analysing a Food Bank problem. IJCAI (United States) 15:2540-2546.Google Scholar |
| [5] | Alijani R, Farhadi M, Ghodsi M, Seddighin M, Tajik AS (2017) Envy-free mechanisms with minimum number of cuts. (AAAI, Palo Alto, CA), 312-318. Google Scholar |
| [6] | Amanatidis G, Markakis E, Nikzad A, Saberi A (2017) Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms 13(4):52.Crossref, Google Scholar · Zbl 1407.68540 · doi:10.1145/3147173 |
| [7] | Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265-290.Crossref, Google Scholar · Zbl 0055.38007 · doi:10.2307/1907353 |
| [8] | Avvakumov S, Karasev R (2021) Envy-free division using mapping degree. Mathematika 67(1):36-53.Google Scholar · Zbl 1522.51010 |
| [9] | Aziz H (2015) A note on the undercut procedure. Social Choice Welfare 45(4):723-728.Crossref, Google Scholar · Zbl 1341.91093 · doi:10.1007/s00355-015-0877-4 |
| [10] | Aziz H (2016) A generalization of the AL method for fair allocation of indivisible objects. Econom. Theory Bull. 4(2):307-324. Crossref, Google Scholar · doi:10.1007/s40505-015-0089-1 |
| [11] | Aziz H (2020) Simultaneously achieving ex-ante and ex-post fairness. Proc. Internat. Conf. on Web and Internet Econom. (Springer), 341-355.Google Scholar · Zbl 1533.91240 |
| [12] | Aziz H, Caragiannis I, Igarashi A (2018) Fair allocation of combinations of indivisible goods and chores. Preprint, submitted July 27, https://arxiv.org/abs/ 1807.10684.Google Scholar |
| [13] | Aziz H, Moulin H, Sandomirskiy F (2020) A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Oper. Res. Lett. 48(5):573-578.Crossref, Google Scholar · Zbl 1478.91091 · doi:10.1016/j.orl.2020.07.005 |
| [14] | Aziz H, Rauchecker G, Schryen G, Walsh T (2016) Approximation algorithms for max-min share allocations of indivisible chores and goods. Preprint, submitted April 5, https://arxiv.org/abs/ 1604.01435.Google Scholar |
| [15] | Babaioff M, Nisan N, Talgam-Cohen I (2019) Competitive equilibrium with generic budgets: Beyond additive. Preprint, submitted November 22, https://arxiv.org/abs/ 1911.09992.Google Scholar |
| [16] | Babaioff M, Nisan N, Talgam-Cohen I (2021) Competitive equilibrium with indivisible goods and generic budgets. Math. Oper. Res. 46(1):382-403.Link, Google Scholar · Zbl 1466.91138 |
| [17] | Barbanel JB (2005) The Geometry of Efficient Fair Division (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1071.91001 · doi:10.1017/CBO9780511546679 |
| [18] | Barbanel JB, Brams SJ (2004) Cake division with minimal cuts: Envy-free procedures for three persons, four persons, and beyond. Math. Soc. Sci. 48(3):251-269.Crossref, Google Scholar · Zbl 1080.91017 · doi:10.1016/j.mathsocsci.2004.03.006 |
| [19] | Barbanel JB, Brams SJ (2014) Two-person cake cutting: The optimal number of cuts. Math. Intelligencer 36(3):23-35.Crossref, Google Scholar · Zbl 1303.91098 · doi:10.1007/s00283-013-9442-0 |
| [20] | Barman S, Krishnamurthy SK (2017) Approximation algorithms for maximin fair division. Proc. ACM Conf. on Econom. and Comput. (ACM, New York), 647-664.Google Scholar |
| [21] | Barman S, Krishnamurthy SK (2018) On the proximity of markets with integral equilibria. Preprint, submitted November 21, https://arxiv.org/abs/ 1811.08673.Google Scholar |
| [22] | Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Proc. ACM Conf. on Econom. and Comput. (ACM, New York), 557-574.Google Scholar |
| [23] | Bei X, Li Z, Liu J, Liu S, Lu X (2020) Fair division of mixed divisible and indivisible goods. Preprint, submitted November 16, https://arxiv.org/abs/ 1911.07048.Google Scholar |
| [24] | Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J. Econom. Theory 100(2):295-328.Crossref, Google Scholar · Zbl 1134.91357 · doi:10.1006/jeth.2000.2710 |
| [25] | Bogomolnaia A, Moulin H, Sandomirskiy F (2021) On the fair division of a random object. Management Sci. 68(2):1174-1194. Google Scholar |
| [26] | Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2016) Dividing goods or bads under additive utilities. Preprint, submitted October 12, https://arxiv.org/abs/ 1608.01540.Google Scholar |
| [27] | Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2017) Competitive division of a mixed manna. Econometrica 85(6):1847-1871.Crossref, Google Scholar · Zbl 1420.91151 · doi:10.3982/ECTA14564 |
| [28] | Bouveret S, Lemaître M (2016) Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents Multi-Agent Systems 30(2):1-32.Crossref, Google Scholar · doi:10.1007/s10458-015-9287-3 |
| [29] | Brams SJ, Taylor AD (1996) Fair Division: From Cake Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 0991.91019 · doi:10.1017/CBO9780511598975 |
| [30] | Brams SJ, Taylor AD (2000) The Win-Win Solution: Guaranteeing Fair Shares to Everybody (W. W. Norton & Company).Google Scholar |
| [31] | Brams SJ, Togman JM (1996) Camp David: Was the agreement fair? Conflict Management Peace Sci. 15(1):99-112.Crossref, Google Scholar · doi:10.1177/073889429601500105 |
| [32] | Brams SJ, Kilgour DM, Klamler C (2012) The undercut procedure: An algorithm for the envy-free division of indivisible items. Social Choice Welfare 39(2-3):615-631. Google Scholar · Zbl 1287.91100 |
| [33] | Brams SJ, Kilgour DM, Klamler C (2014) Two-person fair division of indivisible items: An efficient, envy-free algorithm. Notices of the AMS 61(2):130-141.Google Scholar · Zbl 1338.91084 |
| [34] | Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1436.91001 · doi:10.1017/CBO9781107446984 |
| [35] | Branzei S, Sandomirskiy F (2022) Algorithms for competitive division of chores. Math. Oper. Res. Forthcoming. Google Scholar |
| [36] | Brustle J, Dippel J, Narayan VV, Suzuki M, Vetta A (2019) One dollar each eliminates envy. Preprint, submitted December 5, https://arxiv.org/abs/ 1912.02797.Google Scholar |
| [37] | Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061-1103.Crossref, Google Scholar · doi:10.1086/664613 |
| [38] | Budish E, Cachon GP, Kessler JB, Othman A (2016) Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Oper. Res. 65(2):314-336.Link, Google Scholar · Zbl 1366.91099 |
| [39] | Budish E, Che YK, Kojima F, Milgrom P (2013) Designing random allocation mechanisms: Theory and applications. Amer. Econom. Rev. 103(2):585-623.Crossref, Google Scholar · doi:10.1257/aer.103.2.585 |
| [40] | Caragiannis I, Ioannidis S (2020) Computing envy-freeable allocations with limited subsidies. Preprint, submitted February 6, https://arxiv.org/abs/ 2002.02789.Google Scholar · Zbl 1533.91244 |
| [41] | Caragiannis I, Gravin N, Huang X (2019a) Envy-freeness up to any item with high Nash welfare: The virtue of donating items. Proc. ACM Conf. on Econom. and Comput. (ACM, New York), 527-545.Google Scholar |
| [42] | Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2019b) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):1-32.Crossref, Google Scholar · doi:10.1145/3355902 |
| [43] | Chaudhury BR, Garg J, McGlaughlin P, Mehta R (2021) Competitive allocation of a mixed manna. Proc. ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1405-1424.Google Scholar · Zbl 07788423 |
| [44] | Cherkassky BV, Goldberg AV (1999) Negative-cycle detection algorithms. Math. Programming 85(2):277-311.Crossref, Google Scholar · Zbl 0954.90057 · doi:10.1007/s101070050058 |
| [45] | Cole R, Devanur NR, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, Fisher markets, and Nash social welfare. Proc. 2017 ACM Conf. Econom. Computation 2017 (ACM, New York), 459-460.Google Scholar |
| [46] | Crew L, Narayanan B, Spirkl S (2019) Disproportionate division. Preprint, submitted September 16, https://arxiv.org/abs/ 1909.07141.Google Scholar |
| [47] | Daniel T, Parco J (2005) Fair, efficient and envy-free bargaining: An experimental test of the Brams-Taylor adjusted winner mechanism. Group Decision Negotiation 14(3):241-264.Crossref, Google Scholar · doi:10.1007/s10726-005-1245-z |
| [48] | de Keijzer B, Bouveret S, Klos T, Zhang Y (2009) On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. Rossi F, Tsoukias A, eds. Algorithmic Decision Theory, vol. 5783 of Lecture Notes in Computer Science (Springer, Berlin), 98-110.Crossref, Google Scholar · Zbl 1260.91132 · doi:10.1007/978-3-642-04428-1_9 |
| [49] | Devanur NR, Kannan R (2008) Market equilibria in polynomial time for fixed number of goods or agents. Proc. 49th Annual IEEE Sympos. on Foundations of Comput. Sci. (IEEE, New York), 45-53.Google Scholar |
| [50] | Dickerson JP, Goldman J, Karp J, Procaccia AD, Sandholm T (2014) The computational rise and fall of fairness. Proc. 28th AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 1405-1411.Google Scholar |
| [51] | DW (2019) Enumerate all allocations of points in a simplex. Theoretical Computer Science Stack Exchange. https://cstheory.stackexchange.com/q/42496.Google Scholar |
| [52] | Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Statist. 30(1):165-168. Crossref, Google Scholar · Zbl 0087.13805 · doi:10.1214/aoms/1177706369 |
| [53] | Freeman R, Shah N, Vaish R (2020) Best of both worlds: Ex-ante and ex-post fairness in resource allocation. Proc. 21st ACM Conf. on Econom. and Comput. (ACM, New York), 21-22.Google Scholar |
| [54] | Gal YK, Mash M, Procaccia AD, Zick Y (2017) Which is the fairest (rent division) of them all? J. ACM 64(6):39.Crossref, Google Scholar · Zbl 1427.91144 · doi:10.1145/3131361 |
| [55] | Garg J, McGlaughlin P (2020) Computing competitive equilibria with mixed manna. Proc. 19th Internat. Conf. on Autonomous Agents and MultiAgent Systems (ACM, New York), 420-428.Google Scholar |
| [56] | Garg J, Végh LA (2019) A strongly polynomial algorithm for linear exchange markets. Proc. 51st Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 54-65.Google Scholar · Zbl 1437.91210 |
| [57] | Garg J, McGlaughlin P, Taki S (2018) Approximating maximin share allocations. Proc. 2nd Sympos. on Simplicity in Algorithms (Schloss Dagstuhl, Germany), 20:1-20:11.Google Scholar · Zbl 07902023 |
| [58] | Ghodsi M, HajiAghayi M, Seddighin M, Seddighin S, Yami H(2018) Fair allocation of indivisible goods: Improvements and generalizations. Proc. ACM Conf. on Econom. and Comput. (ACM, New York), 539-556.Google Scholar |
| [59] | Goldberg PW, Hollender A, Igarashi A, Manurangsi P, Suksompong W (2020) Consensus halving for sets of items. Preprint, submitted July 14, https://arxiv.org/abs/ 2007.06754.Google Scholar |
| [60] | Goldman J, Procaccia AD (2015) Spliddit: Unleashing fair division algorithms. SIGecom Exchange 13(2):41-46.Crossref, Google Scholar · doi:10.1145/2728732.2728738 |
| [61] | Halpern D, Shah N (2019) Fair division with subsidy. Proc. Internat. Sympos. Algorithmic Game Theory (Springer), 374-389.Google Scholar · Zbl 1431.91184 |
| [62] | Hosseini H, Sikdar S, Vaish R, Wang H, Xia L (2020) Fair division through information withholding. Proc. Conf. AAAI Artificial Intelligence (ACM, New York), 34:2014-2021.Crossref, Google Scholar · doi:10.1609/aaai.v34i02.5573 |
| [63] | Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Political Econom. 87(2):293-314.Crossref, Google Scholar · doi:10.1086/260757 |
| [64] | Kesten O, Ünver MU (2015) A theory of school-choice lotteries. Theoretical Econom. 10(2):543-595.Crossref, Google Scholar · Zbl 1395.91345 · doi:10.3982/TE1558 |
| [65] | Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Proc. 5th ACM Conf. on Electronic Commerce (ACM, New York), 125-131.Google Scholar |
| [66] | Manurangsi P, Suksompong W (2017) Asymptotic existence of fair divisions for groups. Math. Social Sci. 89:100-108.Crossref, Google Scholar · Zbl 1415.91182 · doi:10.1016/j.mathsocsci.2017.05.006 |
| [67] | Massoud TG (2000) Fair division, adjusted winner procedure (AW), and the Israeli-Palestinian conflict. J. Conflict Resolution 44(3):333-358.Crossref, Google Scholar · doi:10.1177/0022002700044003003 |
| [68] | Meunier F, Zerbib S (2019) Envy-free cake division without assuming the players prefer nonempty pieces. Preprint, submitted April 2, https://arxiv.org/abs/ 1804.00449.Google Scholar · Zbl 1432.91067 |
| [69] | Misra N, Sethia A (2021) Fair division is hard even for amicable agents. Proc. 47th Internat. Conf. on Current Trends in Theory and Practice of Comput. Sci. (Springer Nature, Cham, Switzerland), 421-430.Google Scholar · Zbl 1492.91160 |
| [70] | Moitra A, O’Donnell R (2011) Pareto optimal solutions for smoothed analysts. Proc. 43rd Annual ACM Sympos. on Theory of Comput. (ACM, New York), 225-234.Google Scholar · Zbl 1288.68133 |
| [71] | Moulin H (2004) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Google Scholar |
| [72] | Moulin H (2019) Fair division in the Internet age. Annu. Rev. Econom. 11:407-441.Crossref, Google Scholar · doi:10.1146/annurev-economics-080218-025559 |
| [73] | Negishi T (1960) Welfare economics and existence of an equilibrium for a competitive economy. Metroeconomica 12(2-3):92-97.Crossref, Google Scholar · Zbl 0104.38403 · doi:10.1111/j.1467-999X.1960.tb00275.x |
| [74] | Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic Game Theory. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar · Zbl 1130.91005 · doi:10.1017/CBO9780511800481 |
| [75] | Nizri A (2021) Private communication with Amnon Nizri, a real-estate appraiser. Google Scholar |
| [76] | Oh H, Procaccia AD, Suksompong W (2019) Fairly allocating many goods with few queries. Proc. Conf. AAAI Artificial Intelligence (AAAI, Palo Alto, CA), 33:2141-2148.Crossref, Google Scholar · doi:10.1609/aaai.v33i01.33012141 |
| [77] | Orlin JB (2010) Improved algorithms for computing fisher’s market clearing prices: Computing fisher’s market clearing prices. Proc. 42nd ACM Sympos. on Theory of Comput (ACM, New York), 291-300.Google Scholar · Zbl 1293.68152 |
| [78] | Pazner EA, Schmeidler D (1978) Egalitarian equivalent allocations: A new concept of economic equity. Quart. J. Econom. 92(4):671-687.Crossref, Google Scholar · doi:10.2307/1883182 |
| [79] | Plaut B, Roughgarden T (2018) Almost envy-freeness with general valuations. Proc. 29th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 2584-2603.Google Scholar · Zbl 1403.91215 |
| [80] | Procaccia AD, Wang J, Kurokawa D (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):1-27.Crossref, Google Scholar · Zbl 1410.91314 · doi:10.1145/3140756 |
| [81] | Reijnierse JH, Potters JA (1998) On finding an envy-free pareto-optimal division. Math. Programming 83(1):291-311.Crossref, Google Scholar · Zbl 0920.90144 · doi:10.1007/BF02680564 |
| [82] | Schneider G, Krämer US (2004) The limitations of fair division. J. Conflict Resolution 48(4):506-524.Crossref, Google Scholar · doi:10.1177/0022002704266148 |
| [83] | Seddighin M, Farhadi M, Ghodsi M, Alijani R, Tajik AS (2018) Expand the shares together: Envy-free mechanisms with a small number of cuts. Algorithmica 1-28.Google Scholar |
| [84] | Segal-Halevi E (2018) Fairly dividing a cake after some parts were burnt in the oven. Proc. 17th Internat. Conf. on Autonomous Agents and MultiAgent Systems (IFAAMAS), 1276-1284.Google Scholar |
| [85] | Segal-Halevi E (2019a) Cake-cutting with different entitlements: How many cuts are needed? J. Math. Analysis Appl. 480(1):123382.Crossref, Google Scholar · Zbl 1426.91149 · doi:10.1016/j.jmaa.2019.123382 |
| [86] | Segal-Halevi E (2019b) Fair division with bounded sharing. Preprint, submitted December 1, https://arxiv.org/abs/ 1912.00459.Google Scholar |
| [87] | Segal-Halevi E (2020) Competitive equilibrium for almost all incomes: Existence and fairness. Auton. Agent. Multi Agent Systems 34(1):1-50. Google Scholar |
| [88] | Shishido H, Zeng DZ (1999) Mark-choose-cut algorithms for fair and strongly fair division. Group Decision Negotiation 8(2):125-137.Crossref, Google Scholar · doi:10.1023/A:1008620404353 |
| [89] | Su FE (1999) Rental harmony: Sperner’s lemma in fair division. Amer. Math. Monthly 106(10):930-942.Crossref, Google Scholar · Zbl 1010.05077 · doi:10.2307/2589747 |
| [90] | Thomson W (2011) Fair allocation rules. Handbook of Social Choice and Welfare, vol. 2 (Elsevier, New York), 393-506.Crossref, Google Scholar · doi:10.1016/S0169-7218(10)00021-3 |
| [91] | Varian HR (1974) Equity, envy, and efficiency. J. Econom. Theory. 9(1):63-91Crossref, Google Scholar · doi:10.1016/0022-0531(74)90075-1 |
| [92] | Varian HR (1976) Two problems in the theory of fairness. J. Public Econom. 5(3-4):249-260.Crossref, Google Scholar · doi:10.1016/0047-2727(76)90018-9 |
| [93] | Webb WA (1997) How to cut a cake fairly using a minimal number of cuts. Discrete Appl. Math. 74(2):183-190.Crossref, Google Scholar · Zbl 0876.90100 · doi:10.1016/S0166-218X(96)00032-7 |
| [94] | Wilson SJ (1998) Fair division using linear programming. Working paper, Department of Mathematics, Iowa State University, Ames, IA.Google Scholar |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
