Dynamic Fair Division with Partial Information

References

• Abramowitz B, Anshelevich E (2018) Utilitarians without utilities: Maximizing social welfare for graph problems using only ordinal preferences. Proc. 32nd AAAI Conf. Artificial Intelligence (AAAI-18), 894–901.Google Scholar
• Aleksandrov MD, Aziz H, Gaspers S, Walsh T (2015) Online fair division: Analysing a food bank problem. Qiang Yang Q, Wooldridge MJ, eds. Proc. 24th Internat. Joint Conf. Artificial Intelligence (IJCAI 2015) (AAAI Press, Palo Alto, CA), 2540–2546.Google Scholar
• Altmann SM (2023) Choice, welfare, and market design: An empirical investigation of Feeding America’s choice system. Working paper, Wadham College, University of Oxford, Oxford, UK.Google Scholar
• Amanatidis G, Birmpas G, Markakis E (2016) On truthful mechanisms for maximin share allocations. Brewka G, ed. Proc. 25th Internat. Joint Conf. Artificial Intelligence (IJCAI ‘16) (AAAI Press, Washington, DC), 31–37.Google Scholar
• Anshelevich E, Sekar S (2016) Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI), 390–396.Google Scholar
• Anshelevich E, Zhu W (2019) Tradeoffs between information and ordinal approximation for bipartite matching. Theory Comput. Systems 63(7):1499–1530.Crossref, Google Scholar
• Anshelevich E, Filos-Ratsikas A, Shah N, Voudouris AA (2021) Distortion in social choice problems: The first 15 years and beyond. Zhou ZH, ed. Proc. 30th Internat. Joint Conf. Artificial Intelligence (IJCAI) (ijcai.org, San Mateo County, CA), 4294–4301.Google Scholar
• Anshelevich E, Bhardwaj O, Elkind E, Postl J, Skowron P (2018) Approximating optimal social choice under metric preferences. Artificial Intelligence 264:27–51.Crossref, Google Scholar
• 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
• Bai Y, Gölz P (2022) Envy-free and pareto-optimal allocations for agents with asymmetric random valuations. De Raedt L, ed. Proc. 31st Internat. Joint Conf. Artificial Intelligence (IJCAI) (ijcai.org, San Mateo County, CA), 53–59.Google Scholar
• Barman S, Khan A, Maiti A (2022) Universal and tight online algorithms for generalized-mean welfare. Honavar V, Spaan MTJ, eds. Proc. 36th AAAI Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 4793–4800.Google Scholar
• Baumeister D, Bouveret S, Lang J, Nguyen NT, Nguyen TT, Rothe J, Saffidine A (2017) Positional scoring-based allocation of indivisible goods. Autonomous Agents Multi-agent Systems 31(3):628–655.Crossref, Google Scholar
• Benade G, Kazachkov AM, Procaccia AD, Psomas CA (2018) How to make envy vanish over time. Tardos É, Elkind E, Vohra R, eds. Proc. 10th ACM Conf. Econom. Comput. (EC) (ACM, New York), 593–610.Google Scholar
• Benade G, Nath S, Procaccia AD, Shah N (2021) Preference elicitation for participatory budgeting. Management Sci. 67(5):2813–2827.Link, 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
• Boutilier C, Caragiannis I, Haber S, Lu T, Procaccia AD, Sheffet O (2015) Optimal social choice functions: A utilitarian view. Artificial Intelligence 227:190–213.Crossref, Google Scholar
• Bouveret S, Endriss U, Lang J (2010) Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods. Coelho H, Studer R, Wooldridge MJ, eds. Proc. 19th Eur. Conf. Artificial Intelligence (ECAI) (IOS Press, Amsterdam), 387–392.Google Scholar
• Caragiannis I, Nath S, Procaccia AD, Shah N (2017) Subset selection via implicit utilitarian voting. J. Artificial Intelligence Res. 58:123–152.Crossref, Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Charikar M, Ramakrishnan P, Wang K, Wu H (2024) Breaking the metric voting distortion barrier. Proc. 35th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1621–1640.Google Scholar
• Dhangwatnotai P, Roughgarden T, Yan Q (2010) Revenue maximization with a single sample. Proc. 11th ACM Conf. Econom. Comput. (EC) (ACM, New York), 129–138.Google Scholar
• Dickerson JP, Goldman J, Karp J, Procaccia AD, Sandholm T (2014) The computational rise and fall of fairness. Brodley CE, Stone P, eds. Proc. 28th AAAI Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 1405–1411.Google Scholar
• Dvoretzky A, Kiefer J, Wolfowitz J (1956) Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Statist. 27(3):642–669.Crossref, Google Scholar
• Ehsani S, Hajiaghayi M, Kesselheim T, Singla S (2018) Prophet secretary for combinatorial auctions and matroids. Proc. 29th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 700–714.Google Scholar
• Filos-Ratsikas A, Frederiksen SKS, Zhang J (2014) Social welfare in one-sided matchings: Random priority and beyond. Lavi R, ed. Proc. 7th Internat. Sympos. Algorithmic Game Theory (SAGT) (Springer, Berlin, Heidelberg), 1–12.Google Scholar
• Friedman E, Psomas CA, Vardi S (2015) Dynamic fair division with minimal disruptions. Proc. 16th ACM Conf. Econom. Comput. (EC) (ACM, New York), 697–713.Google Scholar
• Friedman E, Psomas CA, Vardi S (2017) Controlled dynamic fair division. Proc. 18th ACM Conf. Econom. Comput. (EC) (ACM, New York), 461–478.Google Scholar
• Gentle JE (2009) Computational Statistics (Springer, New York).Crossref, Google Scholar
• Gkatzelis V, Halpern D, Shah N (2020) Resolving the optimal metric distortion conjecture. Irani S, ed. Proc. 61st Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 1427–1438.Google Scholar
• Gkatzelis V, Psomas A, Tan X (2021) Fair and efficient online allocations with normalized valuations. Leyton-Brown K, Mausam, eds. Proc. 35th AAAI Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 5440–5447.Google Scholar
• Goel A, Krishnaswamy AK, Munagala K (2017) Metric distortion of social choice rules: Lower bounds and fairness properties. Daskalakis C, Babaioff M, Moulin H, eds. Proc. 18th ACM Conf. Econom. Comput. (EC) (ACM, New York), 287–304.Google Scholar
• Gorokh A, Banerjee S, Iyer K (2021) From monetary to nonmonetary mechanism design via artificial currencies. Math. Oper. Res. 46(3):835–855.Link, Google Scholar
• Halpern D, Shah N (2021) Fair and efficient resource allocation with partial information. Zhou Z, ed. Proc. 30th Internat. Joint Conf. Artificial Intelligence (IJCAI) (ijcai.org, San Mateo County, CA), 5456–5463.Google Scholar
• He J, Procaccia AD, Psomas A, Zeng D (2019) Achieving a fairer future by changing the past. Kraus S, ed. Proc. 28th Internat. Joint Conf. Artificial Intelligence (IJCAI) (ijcai.org, San Mateo County, CA), 343–349.Google Scholar
• Hoi SC, Sahoo D, Lu J, Zhao P (2021) Online learning: A comprehensive survey. Neurocomputing 459:249–289.Crossref, Google Scholar
• Ikeda K, Kita H, Kobayashi S (2001) Failure of Pareto-based MOEAs: Does non-dominated really mean near to optimal? Proc. 2001 Congress Evolutionary Comput., vol. 2 (IEEE, New York), 957–962.Google Scholar
• Immorlica N, Singla S, Waggoner B (2020) Prophet inequalities with linear correlations and augmentations. Proc. 21st ACM Conf. Econom. Comput. (EC) (ACM, New York), 159–185.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
• Kempe D (2020) Communication, distortion, and randomness in metric voting. Conitzer V, Sha F, eds. Proc. 34th AAAI Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 2087–2094.Google Scholar
• Kizilkaya FE, Kempe D (2022) Plurality veto: A simple voting rule achieving optimal metric distortion. Proc. 31st Internat. Joint Conf. Artificial Intelligence (IJCAI) (ijcai.org, San Mateo County, CA), 349–355.Google Scholar
• Kroer C, Peysakhovich A, Sodomka E, Stier-Moses NE (2021) Computing large market equilibria using abstractions. Oper. Res. 70(1):329–351.Link, Google Scholar
• Kurokawa D, Procaccia AD, Wang J (2016) When can the maximin share guarantee be guaranteed? Schuurmans D, Wellman MP, eds. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI) (AAAI Press, Palo Alto, CA), 523–529.Google Scholar
• Leung S, Lui E, Pass R (2015) Voting with coarse beliefs. Proc. 6th Innovations Theoret. Comput. Sci. Conf. (ITCS) (ACM, New York), 61.Google Scholar
• Mandal D, Shah N, Woodruff DP (2020) Optimal communication-distortion tradeoff in voting. Biró P, Hartline JD, Ostrovsky M, Procaccia AD, eds. Proc. 21st ACM Conf. Econom. Comput. (EC) (ACM, New York), 795–813.Google Scholar
• Manurangsi P, Suksompong W (2021) Closing gaps in asymptotic fair division. SIAM J. Discrete Math. 35(2):668–706.Crossref, Google Scholar
• Massart P (1990) The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Probab. 18(3):1269–1283.Crossref, Google Scholar
• MEANS database (2023) Organization website and FAQs. https://meansdatabase.org/.Google Scholar
• Munagala K, Wang K (2019) Improved metric distortion for deterministic social choice rules. Karlin AR, Immorlica N, Johari R, eds. Proc. 20th ACM Conf. Econom. Comput. (EC) (ACM, New York), 245–262.Google Scholar
• Nguyen NT, Nguyen TT, Rothe J (2017) Approximate solutions to max-min fair and proportionally fair allocations of indivisible goods. Larson K, Winikoff M, Das S, Durfee EH, eds. Proc. 16th Internat. Conf. Autonomous Agents Multi-agent Systems (AAMAS) (ACM, New York), 262–271.Google Scholar
• Prendergast C (2017) How food banks use markets to feed the poor. J. Econom. Perspect. 31(4):145–162.Crossref, Google Scholar
• Prendergast C (2022) The allocation of food to food banks. J. Political Econom. 130(8):1993–2017.Crossref, Google Scholar
• Procaccia AD, Rosenschein JS (2006) The distortion of cardinal preferences in voting. Klusch M, Rovatsos M, Payne TR, eds. Proc. 10th Internat. Workshop Cooperative Inform. Agents (CIA) (Springer, Berlin, Heidelberg), 317–331.Google Scholar
• Robbins L (1938) Interpersonal comparisons of utility: A comment. Econom. J. (London) 48(192):635–641.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
• Shi ZR, Lizarondo L, Fang F (2021) A recommender system for crowdsourcing food rescue platforms. Leskovec J, Grobelnik M, Najork M, Tang J, Zia L, eds. Proc. Web Conf. 2021 (ACM, New York), 857–865.Google Scholar
• Sinclair SR, Banerjee S, Yu CL (2022) Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve. SIGMETRICS Performance Evaluation Rev. 50(1):95–96.Crossref, Google Scholar
• Vardi S, Psomas A, Friedman E (2022) Dynamic fair resource division. Math. Oper. Res. 47(2):945–968.Link, Google Scholar
• Wilson R (1985) Game-Theoretic Analyses of Trading Processes (Defense Technical Information Center, Fort Belvoir, VA).Google Scholar
• Zeng D, Psomas A (2020) Fairness-efficiency tradeoffs in dynamic fair division. Proc. 21st ACM Conf. Econom. Comput. (EC) (ACM, New York), 911–912.Google Scholar