Competitive equilibrium with indivisible goods and generic budgets. (English) Zbl 1466.91138
Summary: Competitive equilibrium from equal incomes (CEEI) is a classic solution to the problem of fair and efficient allocation of goods [D. K. Foley, “Resource allocation and the public sector”, Yale Econ. Essays 7, No. 1, 45–98 (1967), H. R. Varian, “Equity, envy and efficiency”, J. Econ. Theory 9, No. 1, 63–91 (1974; doi:10.1016/0022-0531(74)90075-1)]. Every agent receives an equal budget of artificial currency with which to purchase goods, and prices match demand and supply. However, a CEEI is not guaranteed to exist when the goods are indivisible even in the simple two-agent, single-item market. Yet it is easy to see that, once the two budgets are slightly perturbed (made generic), a competitive equilibrium does exist. In this paper, we aim to extend this approach beyond the single-item case and study the existence of equilibria in markets with two agents and additive preferences over multiple items. We show that, for agents with equal budgets, making the budgets generic – by adding vanishingly small random perturbations – ensures the existence of equilibrium. We further consider agents with arbitrary nonequal budgets, representing nonequal entitlements for goods. We show that competitive equilibrium guarantees a new notion of fairness among nonequal agents and that it exists in cases of interest (such as when the agents have identical preferences) if budgets are perturbed. Our results open opportunities for future research on generic equilibrium existence and fair treatment of nonequals.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
Keywords:
market equilibrium existence; fairness; unequal entitlements; additive preferences; Fisher marketsReferences:
| [1] | [1] Alkan A, Demange G, Gale D (1991) Fair allocation of indivisible goods and criteria of justice. Econometrica 59(4):1023-1039.Crossref, Google Scholar · Zbl 0734.90026 · doi:10.2307/2938172 |
| [2] | [2] Amanatidis G, Birmpas G, Christodoulou G, Markakis E (2017) Truthful allocation mechanisms without payments: Characterization and implications on fairness. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 18th ACM Conf. Econom. Comput. (ACM, New York), 545-562.Google Scholar |
| [3] | [3] Anari N, Mai T, Oveis Gharan S, Vazirani VV (2018) Nash social welfare for indivisible items under separable, piecewise-linear concave utilities. Czumaj A, ed. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2274-2290.Google Scholar · Zbl 1403.91204 |
| [4] | [4] Arrow KJ, Debreu G (1954) Existence of equilibrium for a competitive economy. Econometrica 22(3):265-290.Crossref, Google Scholar · Zbl 0055.38007 · doi:10.2307/1907353 |
| [5] | [5] Aziz H, Gaspers S, Mackenzie S, Walsh T (2015) Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence 227:71-92.Crossref, Google Scholar · Zbl 1346.68106 · doi:10.1016/j.artint.2015.06.002 |
| [6] | [6] Aziz H, Bouveret S, Caragiannis I, Giagkousi I, Lang J (2018) Knowledge, fairness, and social constraints. McIlraith SA, Weinberger KQ, eds. Proc. 31st AAAI Conf. Artificial Intelligence, New Orleans, 4638-4645.Google Scholar |
| [7] | [7] Babaioff M, Nisan N, Talgam-Cohen I (2019) Competitive equilibrium with generic budgets: Beyond additive. Working paper, Microsoft Research, Herzliya, Israel.Google Scholar |
| [8] | [8] Babaioff M, Nisan N, Talgam-Cohen I (2019) Fair allocation through competitive equilibrium from generic incomes. Morgenstern J, Boyd D, eds. Proc. Conf. Fairness, Accountability, Transparency (ACM, New York), 180.Google Scholar |
| [9] | [9] Bogomolnaia A, Moulin H, Sandomirskiy F, Yanovskaya E (2019) Dividing bads under additive utilities. Soc. Choice Welfare 52(3):395-417.Crossref, Google Scholar · Zbl 1410.91303 · doi:10.1007/s00355-018-1157-x |
| [10] | [10] Bouveret S, Chevaleyre Y, Maudet N (2016) Fair allocation of indivisible goods. Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD, eds. Handbook of Computational Social Choice (Cambridge University Press, New York), 284-310.Crossref, Google Scholar · Zbl 1448.91132 · doi:10.1017/CBO9781107446984.013 |
| [11] | [11] Brainard WC, Scarf HE (2005) How to compute equilibrium prices in 1981. Amer. J. Econom. Sociol. 64(1):57-83.Crossref, Google Scholar · doi:10.1111/j.1536-7150.2005.00349.x |
| [12] | [12] Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press, New York).Crossref, Google Scholar · Zbl 0991.91019 · doi:10.1017/CBO9780511598975 |
| [13] | [13] Brams SJ, Jones MA, Klamler C (2008) Proportional pie-cutting. Internat. J. Game Theory 36(3):353-367.Crossref, Google Scholar · Zbl 1151.91011 · doi:10.1007/s00182-007-0108-z |
| [14] | [14] Brandt F, Conitzer V, Endriss U, Lang J, Procaccia AD (2016) Handbook of Computational Social Choice (Cambridge University Press, New York).Crossref, Google Scholar · Zbl 1436.91001 · doi:10.1017/CBO9781107446984 |
| [15] | [15] Brânzei S, Gkatzelis V, Mehta R (2017) Nash social welfare approximation for strategic agents. Proc. 18th ACM Conf. Econom. Comput., 611-628.Google Scholar |
| [16] | [16] Brânzei S, Hosseini H, Miltersen PB (2015) Characterization and computation of equilibria for indivisible goods. Proc. 8th Internat. Sympos. Algorithmic Game Theory, 244-255.Google Scholar · Zbl 1358.91069 |
| [17] | [17] Broome J (1990) Fairness. Proc. Aristotelian Soc. 91:87-101.Crossref, Google Scholar · doi:10.1093/aristotelian/91.1.87 |
| [18] | [18] 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 |
| [19] | [19] Budish E, Cantillon E (2012) The multi-unit assignment problem: Theory and evidence from course allocation at Harvard. Amer. Econom. Rev. 102(5):2237-2271.Crossref, Google Scholar · doi:10.1257/aer.102.5.2237 |
| [20] | [20] Caragiannis I, Kurokawa D, Moulin HC, Procaccia AD, Shah N, Wang J (2019) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):1-32.Google Scholar |
| [21] | [21] Chen Y, Shah N (2017) Ignorance is often bliss: Envy with incomplete information. Working paper, Harvard University, Cambridge, MA.Google Scholar |
| [22] | [22] Cole R, Gkatzelis V (2018) Approximating the Nash social welfare with indivisible items. SIAM J. Comput. 47(3):1211-1236.Crossref, Google Scholar · Zbl 1397.91302 · doi:10.1137/15M1053682 |
| [23] | [23] 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. 18th ACM Conf. Econom. Computation, 459-460.Google Scholar |
| [24] | [24] Cramton P, Gibbons R, Klemperer P (1987) Dissolving a partnership efficiently. Econometrica 55(3):615-632.Crossref, Google Scholar · Zbl 0632.90097 · doi:10.2307/1913602 |
| [25] | [25] 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. Proc. 1st Internat. Conf. Algorithmic Decision Theory, 98-110.Google Scholar · Zbl 1260.91132 |
| [26] | [26] Deng X, Papadimitriou CH, Safra S (2003) On the complexity of price equilibria. J. Comput. System Sci. 67(2):311-324.Crossref, Google Scholar · Zbl 1067.90102 · doi:10.1016/S0022-0000(03)00011-4 |
| [27] | [27] Dierker E (1971) Equilibrium analysis of exchange economies with indivisible commodities. Econometrica 39(6):997-1008.Crossref, Google Scholar · Zbl 0235.90002 · doi:10.2307/1909672 |
| [28] | [28] Echenique F, Miralles A, Zhang J (2018) Fairness and efficiency for probabilistic allocations with participation constraints. Working paper, California Institute of Technology, Pasadena.Google Scholar |
| [29] | [29] Eisenberg E (1961) Aggregation of utility functions. Management Sci. 7(4):337-350.Link, Google Scholar |
| [30] | [30] Farhadi A, Ghodsi M, Hajiaghayi MT, Lahaie S, Pennock D, Seddighin M, Seddighin S, Yami H (2019) Fair allocation of indivisible goods to asymmetric agents. J. Artificial Intelligence Res. 64(1):1-20.Crossref, Google Scholar · Zbl 1454.91104 · doi:10.1613/jair.1.11291 |
| [31] | [31] Foley DK (1967) Resource allocation and the public sector. Yale Econom. Essays 7(1):45-98.Google Scholar |
| [32] | [32] Fujishige S, Yang Z (2002) Existence of an equilibrium in a general competitive exchange economy with indivisible goods and money. Ann. Econom. Finance 3(1):135-147.Google Scholar |
| [33] | [33] Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms, 2326-2340.Google Scholar · Zbl 1403.91210 |
| [34] | [34] Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. Proc. 8th USENIX Sympos. Networked Systems Design Implementation, 305-322.Google Scholar |
| [35] | [35] Goldman J, Procaccia AD (2014) Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges 13(2):41-46.Crossref, Google Scholar · doi:10.1145/2728732.2728738 |
| [36] | [36] Gordon J, Kalinin N (2018) Private e-mail communication, August 11.Google Scholar |
| [37] | [37] Guruswami V, Hartline JD, Karlin AR, Kempe D, Kenyon C, McSherry F (2005) On profit-maximizing envy-free pricing. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1164-1173.Google Scholar · Zbl 1297.91072 |
| [38] | [38] Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):1-27.Crossref, Google Scholar · Zbl 1410.91314 · doi:10.1145/3140756 |
| [39] | [39] Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Proc. 5th ACM Conf. Econom. Comput. (ACM, New York), 125-131.Google Scholar |
| [40] | [40] Markakis E, Psomas CA (2011) On worst-case allocations in the presence of indivisible goods. Proc. 7th Internat. Workshop Internet Network Econom. (Springer, Berlin, Heidelberg), 278-289.Google Scholar |
| [41] | [41] Mas-Colell A (1977) Indivisible commodities and general equilibrium theory. J. Econom. Theory 16(2):443-456.Crossref, Google Scholar · Zbl 0402.90010 · doi:10.1016/0022-0531(77)90018-7 |
| [42] | [42] Mas-Colell A, Whinston MD, Green JR (1995) Microeconomic Theory (Oxford University Press, New York).Google Scholar · Zbl 1256.91002 |
| [43] | [43] Maskin ES (1987) On the fair allocation of indivisible goods. Feiwel G, ed. Arrow and the Foundations of the Theory of Economic Policy (MacMillan Publishing Company, London), 341-349.Crossref, Google Scholar · doi:10.1007/978-1-349-07357-3_12 |
| [44] | [44] Moulin H (1995) Cooperative Microeconomics: A Game-Theoretic Introduction (Princeton University Press, Princeton, NJ).Crossref, Google Scholar · doi:10.1515/9781400864140 |
| [45] | [45] Moulin H (2002) Axiomatic cost and surplus sharing. Arrow KJ, Sen A, Suzumura K, eds. Handbook of Social Choice and Welfare (Elsevier, Amsterdam), 289-360.Google Scholar |
| [46] | [46] Niazadeh R, Wilkens C (2016) Competitive equilibria for non-quasilinear bidders in combinatorial auctions. Proc. 12th Internat. Workshop Internet Network Econom. (Springer, Berlin, Heidelberg), 116-130.Google Scholar · Zbl 1406.91189 |
| [47] | [47] Othman A, Papadimitriou CH, Rubinstein A (2016) The complexity of fairness through equilibrium. ACM Trans. Econom. Comput. 4(4):1-19.Crossref, Google Scholar · doi:10.1145/2956583 |
| [48] | [48] Othman A, Sandholm T, Budish E (2010) Finding approximate competitive equilibria: Efficient and fair course allocation. Proc. 9th Internat. Joint Conf. Autonomous Agents Multi-Agent Systems, Toronto, Canada, 873-880.Google Scholar |
| [49] | [49] Plaut B, Roughgarden T (2018) Almost envy-freeness with general valuations. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2584-2603.Google Scholar · Zbl 1403.91215 |
| [50] | [50] Plaut B, Roughgarden T (2020) Communication complexity of discrete fair division. SIAM J. Comput. 49(1):206-243.Crossref, Google Scholar · doi:10.1137/19M1244305 |
| [51] | [51] Pratt JW, Zeckhauser RJ (1990) The fair and efficient division of the Winsor family silver. Management Sci. 36(11):1293-1301.Link, Google Scholar |
| [52] | [52] Prendergast C (2017) The allocation of food to food banks. Working paper, Chicago Booth School of Business, Chicago.Google Scholar |
| [53] | [53] Procaccia AD, Wang J (2014) Fair enough: Guaranteeing approximate maximin shares. Proc. 15th ACM Conf. Econom. Comput., 675-692.Google Scholar |
| [54] | [54] Rastogi A, Cole R (2007) Indivisible markets with good approximate equilibrium prices. Working paper, New York University, New York.Google Scholar |
| [55] | [55] Robertson J, Webb W (1998) Cake-Cutting Algorithms: Be Fair If You Can (Peters/CRC Press, Boca Raton, FL).Crossref, Google Scholar · Zbl 0939.91001 · doi:10.1201/9781439863855 |
| [56] | [56] Segal-Halevi E (2018) Competitive equilibrium for almost all incomes. Proc. 17th Internat. Joint Conf. Autonomous Agents Multi-Agent Systems, Stockholm, Sweden, 1267-1275.Google Scholar |
| [57] | [57] Shapley L, Scarf H (1974) On cores and indivisibility. J. Math. Econom. 1(1):23-37.Crossref, Google Scholar · Zbl 0281.90014 · doi:10.1016/0304-4068(74)90033-0 |
| [58] | [58] Spielman DA, Teng SH (2009) Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Comm. ACM. 52(10):76-84.Crossref, Google Scholar · doi:10.1145/1562764.1562785 |
| [59] | [59] Steinhaus H (1948) The problem of fair division. Econometrica 16(1):101-104.Google Scholar |
| [60] | [60] Svensson LG (1983) Large indivisibles: An analysis with respect to price equilibrium and fairness. Econometrica 51(4):939-954.Crossref, Google Scholar · Zbl 0526.90017 · doi:10.2307/1912044 |
| [61] | [61] Svensson LG (1984) Competitive equilibria with indivisible goods. J. Econom. 44(4):373-386.Google Scholar · Zbl 0552.90010 |
| [62] | [62] Varian HR (1974) Equity, envy and efficiency. J. Econom. Theory 9(1):63-91.Crossref, Google Scholar · doi:10.1016/0022-0531(74)90075-1 |
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.
