Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation

References

• Abdulkadiroğlu A, Sönmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689–701.Crossref, Google Scholar
• Akbarpour M, Nikzad A (2020) Approximate random allocation mechanisms. Rev. Econom. Stud. 87(6):2473–2510.Crossref, Google Scholar
• Aleksandrov M, Aziz H, Gaspers S, Walsh T (2015) Online fair division: Analysing a food bank problem. Yang Q, Wooldridge M, eds. Proc. 24th Internat. Joint Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 2540–2546.Google Scholar
• Alon N (1987) Splitting necklaces. Adv. Math. 63(3):247–253.Crossref, Google Scholar
• Aziz H, Ye C (2014) Cake cutting algorithms for piecewise constant and piecewise uniform valuations. Liu TY, Qi Q, Ye Y, eds. Proc. 10th Internat. Conf. on Web and Internet Econom. (Springer, Berlin), 1–14.Google Scholar
• Aziz H (2019) A probabilistic approach to voting, allocation, matching, and coalition formation. The Future of Economic Design (Springer, Berlin), 45–50.Crossref, Google Scholar
• Aziz H (2020) Simultaneously achieving ex-ante and ex-post fairness. Chen X, Gravin N, Hoefer M, Mehta R, eds. Proc. 16th Internat. Conf. on Web and Internet Econom. (Springer, Berlin), 341–355.Google Scholar
• Babaioff M, Ezra T, Feige U (2022) On best-of-both-worlds fair-share allocations. Hansen KA, Liu TX, Malekian A, eds. 18th Internat. Conf. Web Internet Econom. (Springer, Berlin), 237–255.Google Scholar
• Barman S, Krishnamurthy S (2019) On the proximity of markets with integral equilibria. Hentenryck PV, Zhou Z-H, eds. Proc. 33rd AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 1748–1755.Google Scholar
• Barman S, Bhaskar U, Shah N (2020) Optimal bounds on the price of fairness for indivisible goods. Chen X, Gravin N, Hoefer M, Mehta R, eds. Proc. 16th Conf. on Web and Internet Econom. (Springer, Berlin), 356–369.Google Scholar
• Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Elkind E, Vohra R, Tardos E, eds. Proc. 19th Conf. on Econom. and Comput. (ACM, New York), 557–574.Google Scholar
• Bei X, Lu X, Manurangsi P, Suksompong W (2021) The price of fairness for indivisible goods. Theory Comput. Systems 65:1069–1093.Crossref, Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. Oper. Res. 59(1):17–31.Link, Google Scholar
• Birkhoff G (1946) Three observations on linear algebra. Universidad Nacional Tucumán Rev. A 5:147–151.Google Scholar
• Bogomolnaia A, Moulin H (2001) A new solution to the random assignment problem. J. Econom. Theory 100:295–328.Crossref, Google Scholar
• 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, Cambridge, United Kingdom), 284–310.Crossref, Google Scholar
• Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brandt F, Conitzer V, Endress U, Lang J, Procaccia AD, eds. (2016) Handbook of Computational Social Choice (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• Brustle J, Dippel J, Narayan V, Suzuki M, Vetta A (2020) One dollar each eliminates envy. Ostrovsky M, Procaccia A, Biro P, Hartline J, eds. Proc. 21st ACM Conf. on Econom. and Comput (ACM, New York), 23–39.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, Che Y-K, Kojima F, Milgrom P (2013) Designing random allocation mechanisms: Theory and applications. Amer. Econom. Rev. 103(2):585–623.Crossref, Google Scholar
• Caragiannis I, Kanellopoulos P, Kyropoulou M (2021) On interim envy-free allocation lotteries. Chawla S, Echenique F, Biro P, Sodomka E, eds. Proc. 22nd ACM Conf. on Econom. and Comput. (ACM, New York), 264–284.Google Scholar
• Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M (2012) The efficiency of fair division. Theory Comput. Systems 50(4):589–610.Crossref, Google Scholar
• Caragiannis I, Kurokawa D, Moulin H, Procaccia A, Shah N, Wang J (2019) The unreasonable fairness of maximum Nash welfare. ACM Trans. Econom. Comput. 7(3):1–32.Crossref, Google Scholar
• Cechlárová K, Dobos J, Pillárová E (2013) On the existence of equitable cake divisions. Informs Sci. 228:239–245.Crossref, Google Scholar
• Chen Y, Sönmez T (2002) Improving efficiency of on-campus housing: An experimental study. Amer. Econom. Rev. 92(5):1669–1686.Crossref, Google Scholar
• Conitzer V, Freeman R, Shah N (2017) Fair public decision making. Babaioff M, Moulin H, Daskalakis C, eds. Proc. 18th ACM Conf. on Econom. and Comput. (ACM, New York), 629–646.Google Scholar
• Conitzer V, Freeman R, Shah N, Vaughan J (2019) Group fairness for the allocation of indivisible goods. Hentenryck PV, Zhou Z-H, eds. Proc. 33rd AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 1853–1860.Google Scholar
• Dubins L, Spanier E (1961) How to cut a cake fairly. Amer. Math. Monthly 68(1):1–17.Crossref, Google Scholar
• Foley D (1967) Resource allocation and the public sector. Yale Econom. Essays 7:45–98.Google Scholar
• Freeman R, Shah N, Vaish R (2020) Best of both worlds: Ex-ante and ex-post fairness in resource allocation. Ostrovsky M, Procaccia A, Biro P, Hartline J, eds. Proc. 21st ACM Conf. on Econom. and Comput. (ACM, New York), 21–22.Google Scholar
• Freeman R, Sikdar S, Vaish R, Xia L (2019) Equitable allocations of indivisible goods. Kraus S, ed. Proc. 28th Internat. Joint Conf. on Artificial Intelligence (International Joint Conferences on Artificial Intelligence, California), 280–286.Google Scholar
• Gajdos T, Tallon J (2002) Fairness under uncertainty. Econom. Bull. 4(18):1–7.Google Scholar
• Gamow G, Stern M (1958) Puzzle-Math (Viking Press).Google Scholar
• Gourvès L, Monnot J, Tlilane L (2014) Near fairness in matroids. Schaub T, Friedrich G, O’Sullivan B, eds. Proc. 21st Eur. Conf. on Artificial Intelligence (IOS Press, Amsterdam), 393–398.Google Scholar
• Halpern D, Procaccia AD, Psomas A, Shah N (2020) Fair division with binary valuations: One rule to rule them all. Chen X, Gravin N, Hoefer M, Mehta R, eds. Proc. 16th Internat. Conf. on Web and Internet Econom. (Springer, Berlin), 370–383.Google Scholar
• Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Political Econom. 87(2):293–314.Crossref, Google Scholar
• Johnson DM, Dulmage A, Mendelsohn N (1960) On an algorithm of G. Birkhoff concerning doubly stochastic matrices. Canadian Math. Bull. 3(3):237–242.Crossref, Google Scholar
• Katta A-K, Sethuraman J (2006) A solution to the random assignment problem on the full preference domain. J. Econom. Theory 131(1):231–250.Crossref, Google Scholar
• Kojima F (2009) Random assignment of multiple indivisible objects. Math. Social Sci. 57(1):134–142.Crossref, Google Scholar
• Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. Breese J, Feigenbaum J, Seltzer M, eds. Proc. 6th ACM Conf. on Electronic Commerce (ACM, New York), 125–131.Google Scholar
• Matoušek J, Björner A, Ziegler GM, et al. (2003) Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry (Springer, Berlin).Google Scholar
• Moulin H (2003) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Crossref, Google Scholar
• Nesterov A (2017) Fairness and efficiency in strategy-proof object allocation mechanisms. J. Econom. Theory 170:145–168.Crossref, Google Scholar
• Orlin J (2010) Improved algorithms for computing Fisher’s market clearing prices. Schulman LJ, ed. Proc. 42nd ACM Sympos. on Theory of Comput. (ACM, New York), 291–300.Google Scholar
• Plummer MD, Lovász L (1986) Matching Theory (Elsevier, New York).Google Scholar
• Steinhaus H (1948) The problem of fair division. Econometrica 16:101–104.Google Scholar
• Varian H (1974) Equity, envy and efficiency. J. Econom. Theory 9:63–91.Crossref, Google Scholar
• Végh L (2016) A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM J. Comput. 45(5):1729–1761.Crossref, Google Scholar
• von Neumann J (1953) A certain zero-sum two-person game equivalent to the optimal assignment problem. Kuhn W, Tucker AW, eds. Contributions to the Theory of Games, vol. 2 (Princeton University Press, Princeton, NJ), 5–12.Crossref, Google Scholar