Infinite-Dimensional Fisher Markets and Tractable Fair Division

References

• Agrawal S, Balkanski E, Mirrokni V, Sivan B (2019) Dynamic first price auctions robust to heterogeneous buyers. Preprint, submitted June 7, https://arxiv.org/abs/1906.03286.Google Scholar
• Anderson RM (1988) The second welfare theorem with nonconvex preferences. Econometrica 56(2):361–382.Crossref, Google Scholar
• Aziz H, Mackenzie S (2016) A discrete and bounded envy-free cake cutting protocol for any number of agents. Proc. IEEE 57th Annual Sympos. on Foundations of Computer Sci. (IEEE, New York), 416–427.Google Scholar
• Aziz H, Ye C (2014) Cake cutting algorithms for piecewise constant and piecewise uniform valuations. Liu T-Y, Qi Q, Ye Y, eds. Proc. Internat. Conf. on Web and Internet Econom. (Springer, Cham, Switzerland), 1–14.Google Scholar
• Balseiro SR, Gur Y (2019) Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Sci. 65(9):3952–3968.Link, Google Scholar
• Balseiro S, Kim A, Mahdian M, Mirrokni V (2021) Budget-management strategies in repeated auctions. Oper. Res. 69(3):859–876.Link, Google Scholar
• Barman S, Krishnamurthy SK, Vaish R (2018) Finding fair and efficient allocations. Proc. ACM Conf. on Econom. and Comput. (ACM, New York), 557–574.Google Scholar
• Bei X, Garg J, Hoefer M, Mehlhorn K (2019) Earning and utility limits in Fisher markets. ACM Trans. Econom. Comput. 7(2):1–35.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2019) Lectures on modern convex optimization. August 16, 2022, https://www2.isye.gatech.edu/~nemirovs/LMCOLN2022Fall.pdf.Google Scholar
• Bertsekas D (1999) Nonlinear Programming (Athena Scientific, Nashua, NH).Google Scholar
• Birnbaum B, Devanur NR, Xiao L (2011) Distributed algorithms via gradient descent for Fisher markets. Proc. 12th ACM Conf. on Electronic Commerce (ACM, New York), 127–136.Google Scholar
• Brams SJ, Taylor AD (1996) Fair Division: From Cake-Cutting to Dispute Resolution (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brams SJ, Feldman M, Lai JK, Morgenstern J, Procaccia AD (2012) On maxsum fair cake divisions. Proc. 26th AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA).Google Scholar
• Caragiannis I, Kurokawa D, Moulin H, Procaccia AD, Shah N, Wang J (2016) The unreasonable fairness of maximum Nash welfare. Proc. ACM Conf. on Econom. and Computat. (ACM, New York), 305–322.Google Scholar
• Chares R (2009) Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. PhD thesis, UCL-Université Catholique de Louvain, Ottignies-Louvain-la-Neuve, Belgium.Google Scholar
• Chen L, Ye Y, Zhang J (2007) A note on equilibrium pricing as convex optimization. Proc. Internat. Workshop on Web and Internet Econom. (Springer, Berlin), 7–16.Google Scholar
• Chen Y, Lai JK, Parkes DC, Procaccia AD (2013) Truth, justice, and cake cutting. Games Econom. Behav. 77(1):284–297.Crossref, Google Scholar
• Cheung YK, Cole R, Devanur NR (2019) Tatonnement beyond gross substitutes? Gradient descent to the rescue. Games Econom. Behav. 123(September):295–326.Google Scholar
• Cohler YJ, Lai JK, Parkes DC, Procaccia AD (2011) Optimal envy-free cake cutting. Proc. 25th AAAI Conf. on Artificial Intelligence (Association for the Advancement of Artificial Intelligence, Palo Alto, CA).Google Scholar
• Cole R, Devanur N, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2017) Convex program duality, fisher markets, and nash social welfare. Proc. ACM Conf. on Econom. and Computat. (ACM, New York), 459–460.Google Scholar
• Conitzer V, Kroer C, Sodomka E, Stier-Moses NE (2022a) Multiplicative pacing equilibria in auction markets. Oper. Res. 70(2):963–989.Link, Google Scholar
• Conitzer V, Kroer C, Panigrahi D, Schrijvers O, Stier-Moses NE, Sodomka E, Wilkens CA (2022b) Pacing equilibrium in first price auction markets. Management Sci., ePub ahead of print, April 6, https://doi.org/10.1287/mnsc.2022.4310.Link, Google Scholar
• Dahl J, Andersen ED (2022) A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization. Math. Program. 194:341–370.Google Scholar
• Day MM (1973) Normed linear spaces. Normed Linear Spaces (Springer, Berlin), 27–52.Crossref, Google Scholar
• Deng X, Qi Q, Saberi A (2012) Algorithmic solutions for envy-free cake cutting. Oper. Res. 60(6):1461–1476.Link, Google Scholar
• Deng Y, Lahaie S, Mirrokni V, Zuo S (2021) Revenue-incentive tradeoffs in dynamic reserve pricing. Proc. Internat. Conf. on Machine Learn. 2601–2610.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
• Eisenberg E (1961) Aggregation of utility functions. Management Sci. 7(4):337–350.Link, 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
• Facebook (2017) Your guide to Facebook bid strategy. Accessed February 24, 2022, https://www.facebook.com/gms_hub/share/biddingstrategyguide_final.pdf.Google Scholar
• Gao Y, Kroer C (2020) First-order methods for large-scale market equilibrium computation. Adv. Neural Inform. Processing Systems 33:21738–21750.Google Scholar
• Gao Y, Kroer C, Peysakhovich A (2021) Online market equilibrium with application to fair division. Adv. Neural Inform. Processing Systems 34:27305–27318.Google Scholar
• Garg J, Hoefer M, Mehlhorn K (2018) Approximating the Nash social welfare with budget-additive valuations. Proc. 29th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 2326–2340.Google Scholar
• Hurwicz L, Richter MK (2001) The second welfare theorem of classical welfare economics. Discussion paper, University of Minnesota Center for Economic Research, Minneapolis.Google Scholar
• Kroer C, Peysakhovich A (2019) Scalable fair division for ‘at most one’ preferences. Preprint, submitted September 24, https://arxiv.org/abs/1909.10925.Google Scholar
• Kroer C, Stier-Moses NE (2022) Market equilibrium models in large-scale Internet markets. Innovative Tech. Interface Finance Oper. II:147.Crossref, Google Scholar
• Kroer C, Peysakhovich A, Sodomka E, Stier-Moses NE (2019) Computing large market equilibria using abstractions. Preprint, submitted January 18, https://doi.org/10.1287/opre.2021.2163.Google Scholar
• Luenberger DG (1997) Optimization by Vector Space Methods (John Wiley & Sons, Hoboken, NJ).Google Scholar
• McMahan HB, Holt G, Sculley D, Young M, Ebner D, Grady J, Nie L, et al. (2013) Ad click prediction: A view from the trenches. Proc. 19th ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (ACM, New York), 1222–1230.Google Scholar
• Mosek A (2019) Mosek optimization suite. Accessed August 16, 2022, http://www.mosek.com.Google Scholar
• Nemirovski A (2004) Interior point polynomial time methods in convex programming. Accessed August 16, 2022, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.6909&rep=rep1&type=pdf.Google Scholar
• Nemirovski A, Yudin D (1976) Information-based complexity and efficient methods of convex optimization. Ekonomika i Matematicheskie Metody (Economics and the Mathematical Methods) 12:357–379.Google Scholar
• Nemirovski A, Yudin D (1977) Optimization methods adapting to problem of significant dimension. Autom. Remote Control 38(4):513–524.Google Scholar
• Nesterov Y (2009) Primal-dual subgradient methods for convex problems. Math. Programming 120(1):221–259.Crossref, Google Scholar
• Nesterov Y, Nemirovski A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Nesterov Y (2018) Lectures on Convex Optimization, vol. 137 (Springer, Berlin).Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Nocedal J, Wright S (2006) Numerical Optimization (Springer Science & Business Media, New York).Google Scholar
• Ponstein J (2004) Approaches to the Theory of Optimization, vol. 77 (Cambridge University Press, Cambridge, UK).Google Scholar
• Procaccia AD (2013) Cake cutting: Not just child’s play. Comm. ACM 56(7):78–87.Crossref, Google Scholar
• Procaccia AD (2018) Cake cutting algorithms. https://kilthub.cmu.edu/articles/journal_contribution/Cake_Cutting_Algorithms/6604007.Google Scholar
• Robertson J, Webb W (1998) Cake-Cutting Algorithms: Be Fair If You Can (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Serrano SA (2015) Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone. PhD thesis, Stanford University, Stanford, CA.Google Scholar
• Shmyrev VI (2009) An algorithm for finding equilibrium in the linear exchange model with fixed budgets. J. Appl. Industry Math. 3(4):505.Crossref, Google Scholar
• Shor NZ (1977) Cut-off method with space extension in convex programming problems. Cybernetics 13(1):94–96.Crossref, Google Scholar
• Skajaa A, Ye Y (2015) A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Programming 150(2):391–422.Crossref, Google Scholar
• Weller D (1985) Fair division of a measurable space. J. Math. Econom. 14(1):5–17.Crossref, Google Scholar
• Xiao L (2010) Dual averaging methods for regularized stochastic learning and online optimization. J. Machine Learn. Res. 11:2543–2596.Google Scholar
• Yudin D, Nemirovski A (1976) Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody (Economics and the Mathematical Methods) 12:128–142.Google Scholar
• Zhang L (2011) Proportional response dynamics in the Fisher market. Theoretical Comput. Sci. 412(24):2691–2698.Crossref, Google Scholar