Fair and Efficient Online Allocations

References

• 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. Artificial Intelligence (IJCAI) (AAAI Press, Palo Alto, CA), 2540–2546.Google Scholar
• Alon N, Spencer JH (2000) The Probabilistic Method, 2nd ed. (Wiley, New York).Crossref, Google Scholar
• Armony M, Ward AR (2010) Fair dynamic routing in large-scale heterogeneous server systems. Oper. Res. 58(3):624–637.Link, Google Scholar
• Arrow KJ, Intriligator M, eds. (1982) Handbook of Mathematical Economics (North-Holland, Amsterdam).Google Scholar
• Balseiro S, Lu H, Mirrokni V (2021) Regularized online allocation problems: Fairness and beyond. Meila M, Zhang T, eds. Internat. Conf. Machine Learn. (PMLR, Cambridge, MA), 630–639.Google Scholar
• Bansal N, Jiang H, Singla S, Sinha M (2020) Online vector balancing and geometric discrepancy. Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, eds. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 1139–1152.Google Scholar
• Barbanel JB (2005) The Geometry of Efficient Fair Division (Cambridge University Press, Cambridge, UK).Crossref, 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. Web Internet Econom. 16th Internat. Conf. WINE 2020 (Springer, Cham, Switzerland), 356–369.Google Scholar
• Bateni MH, Chen Y, Ciocan DF, Mirrokni V (2022) Fair resource allocation in a volatile marketplace. Oper. Res. 70(1):288–308.Link, Google Scholar
• Bei X, Lu X, Manurangsi P, Suksompong W (2021) The price of fairness for indivisible goods. Theory Comput. Systems 65(7):1069–1093.Crossref, Google Scholar
• Benadè JG, Kazachkov AM, Psomas CA, Procaccia AD (2018) How to make envy vanish over time. Elkind E, Vohra R, Tardos E, eds. Proc. 19th ACM Conf. Econom. Comput. (EC) (ACM, New York), 593–610.Google Scholar
• Bernstein S (1946) The Theory of Probabilities (Gastehizdat Publishing House, Moscow).Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2011) The price of fairness. Oper. Res. 59(1):17–31.Link, Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2012) On the efficiency-fairness trade-off. Management Sci. 58(12):2234–2250.Link, Google Scholar
• Bertsimas D, Farias VF, Trichakis N (2013) Fairness, efficiency, and flexibility in organ allocation for kidney transplantation. Oper. Res. 61(1):73–87.Link, Google Scholar
• Bogomolnaia A, Moulin H, Sandomirskiy F (2021) On the fair division of a random object. Management Sci. 68(2):1174–1194.Link, Google Scholar
• Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, 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
• Butler M, Williams HP (2002) Fairness vs. efficiency in charging for the use of common facilities. J. Oper. Res. Soc. 53(12):1324–1329.Crossref, Google Scholar
• Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M (2009) The efficiency of fair division. Leonardi S, ed. Proc. 5th Conf. Web Internet Econom. (WINE) (Springer, Berlin, Heidelberg, Germany), 475–482.Google Scholar
• Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2016) Conitzer V, Bergemann D, Chen Y, eds. The unreasonable fairness of maximum Nash product. Proc. 17th ACM Conf. Econom. Comput. (EC) (ACM, New York), 305–322.Google Scholar
• Chaudhury BR, Cheung YK, Garg J, Garg N, Hoefer M, Mehlhorn K (2018) On fair division for indivisible items. Ganguly S, Pandya P, eds. 38th IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (FSTTCS 2018) (Schloss Dagstuhl, Wadern, Germany), 25:1–25:17.Google Scholar
• Cole R, Gkatzelis V (2015) Approximating the Nash social welfare with indivisible items. Servedio R, Rubinfeld R, eds. Proc. 47th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 371–380.Google Scholar
• Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV (2008) Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5):1–18.Crossref, Google Scholar
• Dickerson JP, Goldman JR, Karp J, Procaccia AD, Sandholm T (2014) The computational rise and fall of fairness. Brodley CE, Stone P, eds. Proc. Twenty-Eighth AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 1405–1411.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
• Foley D (1967) Resource allocation and the public sector. Yale Econom. Essays 7:45–98.Google Scholar
• Freeman R, Zahedi SM, Conitzer V, Lee BC (2018) Dynamic proportional sharing: A game-theoretic approach. Chaintreau A, Wierman A, Akella A, eds. Proc. ACM Measurement Anal. Comput. Systems., vol. 2 (ACM, New York), 1–36.Google Scholar
• Friedman E, Psomas CA, Vardi S (2015) Dynamic fair division with minimal disruptions. Roughgarden T, Feldman M, Schwarz M, eds. Proc. Sixteenth ACM Conf. Econom. Comput. (ACM, New York), 697–713.Google Scholar
• Friedman E, Psomas CA, Vardi S (2017) Controlled dynamic fair division. Daskalakis D, Babaioff M, Moulin H, eds. Proc. 2017 ACM Conf. Econom. Comput. (ACM, New York), 461–478.Google Scholar
• Gal Y, Mash M, Procaccia AD, Zick Y (2017) Which is the fairest (rent division) of them all? Sierra C, ed. Proc. 26th Internat. Joint Conf. Artificial Intelligence (IJCAI, Marina del Rey, CA), 4841–4843.Google Scholar
• Gao Y, Peysakhovich A, Kroer C (2021) Online market equilibrium with application to fair division. Adv. Neural Inform. Processing Systems 34:27305–27318.Google Scholar
• Garg J, Végh LA (2019) A strongly polynomial algorithm for linear exchange markets. Charikar M, Cohen E, eds. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 54–65.Google Scholar
• Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Czumaj A, ed. Proc. Twenty-Ninth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA), 2326–2340.Google Scholar
• Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. Andersen DG Ratnasamy S, eds. Proc. 8th USENIX Conf. Networked Systems Design Implementation (NSDI) (USENIX Association, Berkeley, CA), 24–37.Google Scholar
• Gkatzelis V, Psomas A, Tan X (2021) Fair and efficient online allocations with normalized valuations. Yang Q, Leyton-Brown K, Mausam, eds. Proc. 35th AAAI Conf. Artificial Intelligence (AAAI) No. 6 (AAAI Press, Palo Alto, CA), 5440–5447.Google Scholar
• He J, Procaccia AD, Psomas C, Zeng D (2019) Achieving a fairer future by changing the past. Kraus S, ed. Proc. 28th Internat. Joint Conf. Artificial Intelligence (IJCAI) (IJCAI, Marina del Rey, CA), 343–349.Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Crossref, Google Scholar
• Kash I, Procaccia AD, Shah N (2014) No agent left behind: Dynamic fair division of multiple resources. J. Artificial Intelligence Res. 51:579–603.Crossref, Google Scholar
• Kurokawa D, Procaccia AD, Wang J (2016) When can the maximin share guarantee be guaranteed? Schuurmans D, ed. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI), (AAAI Press, Palo Alto, CA), 523–529.Google Scholar
• Lee MK, Kusbit D, Kahng A, Kim JT, Yuan X, Chan A, See D, et al. (2019) WeBuildAI: Participatory framework for algorithmic governance. Lampinen A, Gergle D, Shamma DA, eds. Proc. ACM Human Comput. Interaction 3:1–35.Crossref, Google Scholar
• Li B, Li W, Li Y (2018) Dynamic fair division problem with general valuations. Proc. 27th Internat. Joint Conf. Artificial Intelligence (ACM, New York), 375–381.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. Econom. Comput. (EC) (ACM, New York), 125–131.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Miller HE, Pierskalla WP, Rath GJ (1976) Nurse scheduling using mathematical programming. Oper. Res. 24(5):857–870.Link, Google Scholar
• Narayan VV, Suzuki M, Vetta A (2021) Two birds with one stone: Fairness and welfare via transfers. Caragiannis I, Hansen KA, eds. Proc. Algorithmic Game Theory 14th Internat. Sympos. SAGT 2021 (Springer, Cham, Switzerland), 376–390.Google Scholar
• Orlin JB (2010) Improved algorithms for computing Fisher’s market clearing prices. Mitzenmacher M, Schulman LJ, eds. Proc. Forty-Second ACM Sympos. Theory Comput. (ACM, New York), 291–300.Google Scholar
• Procaccia AD (2016) Cake cutting algorithms. Brandt F, Conitzer V, Endress U, Lang J, Procaccia AD, eds. Handbook of Computational Social Choice (Cambridge University Press, Cambridge, UK), 311–330.Crossref, Google Scholar
• Ruhe G, Fruhwirth B (1990) ε-optimality for bicriteria programs and its application to minimum cost flows. Computing 44(1):21–34.Crossref, Google Scholar
• Sanders P (1996) On the competitive analysis of randomized static load balancing. Rajasekaran S, ed. Proc. 1st Workshop Randomized Parallel Algorithms (RANDOM).Google Scholar
• Su FE (1999) Rental harmony: Sperner’s lemma in fair division. Amer. Math. Monthly 106(10):930–942.Crossref, Google Scholar
• Su X, Zenios SA (2006) Recipient choice can address the efficiency-equity trade-off in kidney transplantation: A mechanism design model. Management Sci. 52(11):1647–1660.Link, Google Scholar
• Vardi S, Psomas A, Friedman E (2022) Dynamic fair resource division. Math. Oper. Res. 47(2):945–968.Link, Google Scholar
• Varian H (1974) Equity, envy and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• Walsh T (2011) Online cake cutting. Perny P, Pirlot M, Tsoukiís A, eds. Proc. 3rd Internat. Conf. Algorithmic Decision Theory (ADT) (Springer-Verlag, Berlin, Heidelberg), 292–305.Google Scholar