Efficient Fair Division with Minimal Sharing

References

• 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
• 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
• 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
• 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
• 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
• 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
• Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290.Crossref, Google Scholar
• Avvakumov S, Karasev R (2021) Envy-free division using mapping degree. Mathematika 67(1):36–53.Google Scholar
• Aziz H (2015) A note on the undercut procedure. Social Choice Welfare 45(4):723–728.Crossref, Google Scholar
• 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
• Aziz H (2020) Simultaneously achieving ex-ante and ex-post fairness. Proc. Internat. Conf. on Web and Internet Econom. (Springer), 341–355.Google Scholar
• 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
• 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
• 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
• 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
• 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
• Barbanel JB (2005) The Geometry of Efficient Fair Division (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• 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
• Barbanel JB, Brams SJ (2014) Two-person cake cutting: The optimal number of cuts. Math. Intelligencer 36(3):23–35.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J. Econom. Theory 100(2):295–328.Crossref, Google Scholar
• Bogomolnaia A, Moulin H, Sandomirskiy F (2021) On the fair division of a random object. Management Sci. 68(2):1174–1194. Google Scholar
• 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
• Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2017) Competitive division of a mixed manna. Econometrica 85(6):1847–1871.Crossref, Google Scholar
• 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
• Brams SJ, Taylor AD (1996) Fair Division: From Cake Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brams SJ, Taylor AD (2000) The Win-Win Solution: Guaranteeing Fair Shares to Everybody (W. W. Norton & Company).Google Scholar
• Brams SJ, Togman JM (1996) Camp David: Was the agreement fair? Conflict Management Peace Sci. 15(1):99–112.Crossref, Google Scholar
• 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
• 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
• Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Branzei S, Sandomirskiy F (2022) Algorithms for competitive division of chores. Math. Oper. Res. Forthcoming. Google Scholar
• 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
• Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061–1103.Crossref, Google Scholar
• 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
• 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
• Caragiannis I, Ioannidis S (2020) Computing envy-freeable allocations with limited subsidies. Preprint, submitted February 6, https://arxiv.org/abs/ 2002.02789.Google Scholar
• 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
• 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
• 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
• Cherkassky BV, Goldberg AV (1999) Negative-cycle detection algorithms. Math. Programming 85(2):277–311.Crossref, Google Scholar
• 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
• Crew L, Narayanan B, Spirkl S (2019) Disproportionate division. Preprint, submitted September 16, https://arxiv.org/abs/ 1909.07141.Google Scholar
• 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
• 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
• 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
• 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
• DW (2019) Enumerate all allocations of points in a simplex. Theoretical Computer Science Stack Exchange. https://cstheory.stackexchange.com/q/42496.Google Scholar
• Eisenberg E, Gale D (1959) Consensus of subjective probabilities: The pari-mutuel method. Ann. Math. Statist. 30(1):165–168. Crossref, Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Goldman J, Procaccia AD (2015) Spliddit: Unleashing fair division algorithms. SIGecom Exchange 13(2):41–46.Crossref, Google Scholar
• Halpern D, Shah N (2019) Fair division with subsidy. Proc. Internat. Sympos. Algorithmic Game Theory (Springer), 374–389.Google Scholar
• 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
• Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Political Econom. 87(2):293–314.Crossref, Google Scholar
• Kesten O, Ünver MU (2015) A theory of school-choice lotteries. Theoretical Econom. 10(2):543–595.Crossref, Google Scholar
• 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
• Manurangsi P, Suksompong W (2017) Asymptotic existence of fair divisions for groups. Math. Social Sci. 89:100–108.Crossref, Google Scholar
• Massoud TG (2000) Fair division, adjusted winner procedure (AW), and the Israeli-Palestinian conflict. J. Conflict Resolution 44(3):333–358.Crossref, Google Scholar
• 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
• 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
• 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
• Moulin H (2004) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Google Scholar
• Moulin H (2019) Fair division in the Internet age. Annu. Rev. Econom. 11:407–441.Crossref, Google Scholar
• Negishi T (1960) Welfare economics and existence of an equilibrium for a competitive economy. Metroeconomica 12(2–3):92–97.Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic Game Theory. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Nizri A (2021) Private communication with Amnon Nizri, a real-estate appraiser. Google Scholar
• 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
• 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
• Pazner EA, Schmeidler D (1978) Egalitarian equivalent allocations: A new concept of economic equity. Quart. J. Econom. 92(4):671–687.Crossref, Google Scholar
• 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
• Procaccia AD, Wang J, Kurokawa D (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):1–27.Crossref, Google Scholar
• Reijnierse JH, Potters JA (1998) On finding an envy-free pareto-optimal division. Math. Programming 83(1):291–311.Crossref, Google Scholar
• Schneider G, Krämer US (2004) The limitations of fair division. J. Conflict Resolution 48(4):506–524.Crossref, Google Scholar
• 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
• 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
• Segal-Halevi E (2019a) Cake-cutting with different entitlements: How many cuts are needed? J. Math. Analysis Appl. 480(1):123382.Crossref, Google Scholar
• Segal-Halevi E (2019b) Fair division with bounded sharing. Preprint, submitted December 1, https://arxiv.org/abs/ 1912.00459.Google Scholar
• Segal-Halevi E (2020) Competitive equilibrium for almost all incomes: Existence and fairness. Auton. Agent. Multi Agent Systems 34(1):1–50. Google Scholar
• 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
• Su FE (1999) Rental harmony: Sperner’s lemma in fair division. Amer. Math. Monthly 106(10):930–942.Crossref, Google Scholar
• Thomson W (2011) Fair allocation rules. Handbook of Social Choice and Welfare, vol. 2 (Elsevier, New York), 393–506.Crossref, Google Scholar
• Varian HR (1974) Equity, envy, and efficiency. J. Econom. Theory. 9(1):63–91Crossref, Google Scholar
• Varian HR (1976) Two problems in the theory of fairness. J. Public Econom. 5(3-4):249–260.Crossref, Google Scholar
• 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
• Wilson SJ (1998) Fair division using linear programming. Working paper, Department of Mathematics, Iowa State University, Ames, IA.Google Scholar