Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Trade-off Curve

References

• Aleksandrov M, Walsh T (2019) Monotone and online fair division. Joint German/Austrian Conf. Artificial Intelligence (Springer), 60–75.Google Scholar
• Aleksandrov M, Walsh T (2020) Online fair division: A survey. 34th AAAI Conf. Artificial Intelligence (AAAI Press), 13557–13562.Google Scholar
• Aleksandrov MD, Aziz H, Gaspers S, Walsh T (2015) Online fair division: Analysing a food bank problem. 24th Internat. Joint Conf. Artificial Intelligence.Google Scholar
• Alkaabneh F, Diabat A, Gao HO (2020) A unified framework for efficient, effective, and fair resource allocation by food banks using an approximate dynamic programming approach. Omega 100:102300.Crossref, Google Scholar
• Azar Y, Buchbinder N, Jain K (2010) How to allocate goods in an online market? Eur. Sympos. Algorithms (Springer), 51–62.Google Scholar
• Aziz H, Schlotter I, Walsh T (2016) Control of fair division. Kambhampati S, ed. Proc. 25th Internat. Joint Conf. Artificial Intelligence (IJCAI/AAAI Press), 67–73.Google Scholar
• Banerjee S, Gkatzelis V, Gorokh A, Jin B (2020) Online Nash social welfare maximization via promised utilities. Preprint, submitted August 20, https://arxiv.org/abs/2008.03564.Google Scholar
• Bansal N, Jiang H, Singla S, Sinha M (2020) Online vector balancing and geometric discrepancy. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput., 1139–1152.Google Scholar
• Bateni M, Chen Y, Ciocan DF, Mirrokni V (2022) Fair resource allocation in a volatile marketplace. Oper. Res. 70(1):288–308.Link, Google Scholar
• Bauer L (2020) About 14 million children in the US are not getting enough to eat. Brookings Online (July 9), https://www.brookings.edu/blog/up-front/2020/07/09/about-14-million-children-in-the-us-are-not-getting-enough-to-eat/.Google Scholar
• Benade G, Kazachkov AM, Procaccia AD, Psomas CA (2018) How to make envy vanish over time. Proc. 2018 ACM Conf. Econom. Comput., 593–610.Google Scholar
• Berry AC (1941) The accuracy of the Gaussian approximation to the sum of independent variates. Trans. Amer. Math. Soc. 49(1):122–136.Crossref, Google Scholar
• Bertsekas D (2012) Dynamic Programming and Optimal Control, vol. 1 (Athena Scientific, Nashua, NH).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 (2022) On the fair division of a random object. Management Sci. 68(2):1174–1194.Link, Google Scholar
• Brams SJ, Taylor AD (1995) An envy-free cake division protocol. Amer. Math. Monthly 102(1):9–18.Crossref, Google Scholar
• Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press).Crossref, Google Scholar
• Chung KM, Lam H, Liu Z, Mitzenmacher M (2012) Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. 29th Internat. Sympos. Theoret. Aspects Comput. Sci.Google Scholar
• Cole R, Gkatzelis V, Goel G (2013) Mechanism design for fair division: Allocating divisible items without payments. Proc. 14th ACM Conf. Electronic Commerce, 251–268.Google Scholar
• Devanur NR, Papadimitriou CH, Saberi A, Vazirani VV (2002) Market equilibrium via a primal-dual-type algorithm. Proc. 43rd Annual IEEE Sympos. Foundations Comput. Sci. (IEEE), 389–395.Google Scholar
• Donahue K, Kleinberg J (2020) Fairness and utilization in allocating resources with uncertain demand. Proc. 2020 Conf. Fairness Accountability Transparency, 658–668.Google Scholar
• Eisenberg E (1961) Aggregation of utility functions. Management Sci. 7(4):337–350.Link, Google Scholar
• Eisenhandler O, Tzur M (2019) The humanitarian pickup and distribution problem. Oper. Res. 67(1):10–32.Link, Google Scholar
• Elzayn H, Jabbari S, Jung C, Kearns M, Neel S, Roth A, Schutzman Z (2019) Fair algorithms for learning in allocation problems. Proc. Conf. Fairness Accountability Transparency, 170–179.Google Scholar
• Friedman E, Psomas CA, Vardi S (2015) Dynamic fair division with minimal disruptions. Proc. 16th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 697–713.Google Scholar
• Friedman E, Psomas CA, Vardi S (2017) Controlled dynamic fair division. Proc. 2017 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 461–478.Google Scholar
• Gerding EH, Perez-Diaz A, Aziz H, Gaspers S, Marcu A, Mattei N, Walsh T (2019) Fair online allocation of perishable goods and its application to electric vehicle charging. Proc. 28th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization), 5569–5575.Google Scholar
• Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (2011) Dominant resource fairness: Fair allocation of multiple resource types. NSDI, vol. 11, 24.Google Scholar
• He J, Procaccia AD, Psomas A, Zeng D (2019) Achieving a fairer future by changing the past. Proc. 28th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization), 343–349.Google Scholar
• Jaberi-Douraki M, Moghadas SM (2014) Optimal control of vaccination dynamics during an influenza epidemic. Math. Biosciences Engrg. 11(5):1045–1063.Crossref, Google Scholar
• Kalinowski T, Narodytska N, Walsh T (2013) A social welfare optimal sequential allocation procedure. 23rd Internat. Joint Conf. Artificial Intelligence.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
• Kleinberg J, Mullainathan S, Raghavan M (2016) Inherent trade-offs in the fair determination of risk scores. Preprint, submitted September 19, https://arxiv.org/abs/1609.05807.Google Scholar
• Kulish N (2020) “Never seen anything like it”: Cars line up for miles at food banks. The New York Times Online (April 8), https://www.nytimes.com/2020/04/08/business/economy/coronavirus-food-banks.html.Google Scholar
• Lien RW, Iravani SM, Smilowitz KR (2014) Sequential resource allocation for nonprofit operations. Oper. Res. 62(2):301–317.Link, Google Scholar
• Lupkin S (2020) How feds decide on remdesivir shipments to states remains mysterious. NPR Online (August 19), https://www.npr.org/sections/health-shots/2020/08/19/903946857/how-feds-decide-on-remdesivir-shipments-to-states-remains-mysterious.Google Scholar
• Manshadi V, Niazadeh R, Rodilitz S (2021) Fair dynamic rationing. Preprint, submitted February 2, https://dx.doi.org/10.2139/ssrn.3775895.Google Scholar
• Mattei N, Saffidine A, Walsh T (2017) Mechanisms for online organ matching. Proc. 26th Internat. Joint Conf. Artificial Intelligence, 345–351.Google Scholar
• Mattei N, Saffidine A, Walsh T (2018) Fairness in deceased organ matching. Proc. 2018 AAAI/ACM Conf. AI Ethics Society, 236–242.Google Scholar
• Moulin H (2004) Fair Division and Collective Welfare (MIT Press, Cambridge, MA).Google Scholar
• Nisan N, Roughgarden T, Tardos É, Vazirani VV, eds. (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Orgut IS, Brock LG III, Davis LB, Ivy JS, Jiang S, Morgan SD, Uzsoy R, Hale C, Middleton E (2016) Achieving equity, effectiveness, and efficiency in food bank operations: Strategies for feeding America with implications for global hunger relief. Advances in Managing Humanitarian Operations (Springer), 229–256.Crossref, Google Scholar
• Procaccia AD (2013) Cake cutting: Not just child’s play. Comm. ACM. 56(7):78–87.Crossref, Google Scholar
• Sengul Orgut I, Ivy J, Uzsoy R (2017) Modeling for the equitable and effective distribution of food donations under stochastic receiving capacities. IISE Trans. 49(6):567–578.Crossref, Google Scholar
• Shadmi E, Chen Y, Dourado I, Faran-Perach I, Furler J, Hangoma P, Hanvoravongchai P, et al. (2020) Health equity and COVID-19: Global perspectives. Internat. J. Equity Health 19(1):1–16.Crossref, Google Scholar
• Sugden R (1984) Is fairness good? A critique of Varian’s theory of fairness. Nous 18(3):505–511.Crossref, Google Scholar
• Varian HR (1974) Equity, envy, and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• Varian HR (1976) Two problems in the theory of fairness. J. Public Econom. 5(3–4):249–260.Crossref, Google Scholar
• Vera A, Banerjee S (2019) The Bayesian prophet: A low-regret framework for online decision making. Performance Evaluation Rev. 47(1):81–82.Crossref, Google Scholar
• Walsh T (2011) Online cake cutting. Internat. Conf. Algorithmic Decision Theory (Springer), 292–305.Google Scholar
• Yi M, Marathe A (2015) Fairness vs. efficiency of vaccine allocation strategies. Value Health 18(2):278–283.Crossref, Google Scholar
• Zeng D, Psomas A (2020) Fairness-efficiency tradeoffs in dynamic fair division. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 911–912.Google Scholar