Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements

References

• Abdel-Hamid AR, Bather JA, Trustrum GB (1982) The secretary problem with an unknown number of candidates. J. Appl. Probab. 19(3):619–630.Crossref, Google Scholar
• Agrawal S, Devanur N (2015) Fast algorithms for online stochastic convex programming. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2015) (SIAM, Philadelphia), 1405–1424.Google Scholar
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Asia Initiatives (2023) Social capital credits: The community currency for social good. Accessed May 19, 2024, https://www.asiainitiatives.org/soccs.Google Scholar
• Azar Y, Buchbinder N, Jain K (2016) How to allocate goods in an online market? Algorithmica 74(2):589–601.Crossref, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Banerjee S, Gkatzelis V, Gorokh A, Jin B (2022) Online Nash social welfare maximization with predictions. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1–19.Google Scholar
• Brainard WC, Scarf HE (2005) How to compute equilibrium prices in 1891. Amer. J. Econom. Sociol. 64(1):57–83.Crossref, Google Scholar
• Brânzei S, Gkatzelis V, Mehta R (2022) Nash social welfare approximation for strategic agents. Oper. Res. 70(1):402–415.Link, Google Scholar
• Bray RL (2019) Logarithmic regret in multisecretary and online linear programming problems with continuous valuations. Preprint, submitted December 16, https://arxiv.org/abs/1912.08917.Google Scholar
• Chen G, Li X, Ye Y (2024) Technical note—An improved analysis of LP-based control for revenue management. Oper. Res. 72(3):1124–1138.Link, Google Scholar
• Cheung YK, Cole R, Devanur N (2020) Tatonnement beyond gross substitutes? Gradient descent to the rescue. Games Econom. Behav. 123:295–326.Crossref, Google Scholar
• Cheung YK, Cole R, Tao Y (2018) Dynamics of distributed updating in Fisher markets. Proc. 2018 ACM Conf. Econom. Comput. (EC ‘18) (Association for Computing Machinery, New York), 351–368.Google Scholar
• Cole R, Devanur NR, Gkatzelis V, Jain K, Mai T, Vazirani VV, Yazdanbod S (2016) Convex program duality, Fisher markets, and Nash social welfare. Preprint, submitted September 21, https://arxiv.org/abs/1609.06654.Google Scholar
• Devanur N, Papadimitriou C, Saberi A, Vazirani V (2008) Market equilibrium via a primal–dual algorithm for a convex program. J. ACM 55(5):22:1–22:18.Crossref, 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
• Gao Y, Kroer C, Peysakhovich A (2021) Online market equilibrium with application to fair division. Preprint, submitted March 24, https://arxiv.org/abs/2103.12936.Google Scholar
• Gao W, Sun C, Xue C, Ge D, Ye Y (2024) Decoupling learning and decision-making: Breaking the O(T) barrier in online resource allocation with first-order methods. Proc. 41st Internat. Conf. Machine Learn., Proc. Machine Learn. Res., vol. 235 (PMLR, New York), 14859–14883.Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3–4):157–325.Crossref, Google Scholar
• Jain K (2007) A polynomial time algorithm for computing an Arrow–Debreu market equilibrium for linear utilities. SIAM J. Comput. 37(1):303–318.Crossref, Google Scholar
• Jalota D, Tsao M, Pavone M (2024) Catch me if you can: Combatting fraud in artificial currency based government benefits programs. Preprint, submitted February 25, https://arxiv.org/abs/2402.16162.Google Scholar
• Jalota D, Pavone M, Qi Q, Ye Y (2023) Fisher markets with linear constraints: Equilibrium properties and efficient distributed algorithms. Games Econom. Behav. 141:223–260.Crossref, Google Scholar
• Javanmard A, Nazerzadeh H (2019) Dynamic pricing in high-dimensions. J. Machine Learn. Res. 20(9):1–49.Google Scholar
• Jenatton R, Huang J, Archambeau C (2016) Adaptive algorithms for online convex optimization with long-term constraints. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., Proc. Machine Learn. Res., vol. 48 (PMLR, New York), 402–411.Google Scholar
• Ji Z, Mehta R, Telgarsky M (2018) Social welfare and profit maximization from revealed preferences. Christodoulou G, Harks T, eds. Web and Internet Economics (Springer, Cham, Switzerland), 264–281.Crossref, Google Scholar
• Joyce P (1984) The Walrasian tatonnement mechanism and information. RAND J. Econom. 15(3):416–425.Crossref, Google Scholar
• Kleinberg R, Leighton T (2003) The value of knowing a demand curve: Bounds on regret for online posted-price auctions. 44th Annual IEEE Sympos. Foundations Comput. Sci. 2003 Proc. (IEEE Computer Society, Washington, DC), 594–605.Google Scholar
• Koutsoupias E, Papadimitriou CH (2000) Beyond competitive analysis. SIAM J. Comput. 30(1):300–317.Crossref, Google Scholar
• Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• Li X, Sun C, Ye Y (2022) Simple and fast algorithm for binary integer and online linear programming. Math. Programming 200(2):831–875.Crossref, Google Scholar
• Mahdavi M, Jin R, Yang T (2012) Trading regret for efficiency: Online convex optimization with long term constraints. J. Machine Learn. Res. 13(1):2503–2528.Google Scholar
• Mao J, Leme R, Schneider J (2018) Contextual pricing for Lipschitz buyers. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Adv. Neural Inform. Processing Systems 31 (NeurIPS 2018) (Curran Associates, Inc., Red Hook, NY), 5643–5651.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22–es.Crossref, Google Scholar
• Nesterov Y, Shikhman V (2018) Computation of Fisher–Gale equilibrium by auction. J. Oper. Res. Soc. China 6(3):349–389.Crossref, Google Scholar
• Roth A, Ullman J, Wu ZS (2016) Watch and learn: Optimizing from revealed preferences feedback. Proc. 48th Annual ACM Sympos. Theory Comput. (STOC ‘16) (Association for Computing Machinery, New York), 949–962.Google Scholar
• Sinclair S, Jain G, Banerjee S, Yu CL (2022) Sequential fair allocation: Achieving the optimal envy-efficiency trade-off curve. Oper. Res. 71(5):1689–1705.Link, Google Scholar
• U.S. Department of Agriculture (2024) Supplemental Nutrition Assistance Program (SNAP). Accessed May 19, 2024, https://www.fns.usda.gov/snap/supplemental-nutrition-assistance-program.Google Scholar
• Varian H (1974) Equity, envy, and efficiency. J. Econom. Theory 9(1):63–91.Crossref, Google Scholar
• Varian H (1976) Two problems in the theory of fairness. J. Public Economics 5(3):249–260.Crossref, Google Scholar
• Vazirani VV (2007) Combinatorial algorithms for market equilibria. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 103–134.Crossref, Google Scholar
• Walras L (1954) Elements of Pure Economics: Or, the Theory of Social Wealth. Translation series (American Economic Association, Nashville, TN).Google Scholar
• Wang Z, Deng S, Ye Y (2014) Close the gaps: A learning-while-doing algorithm for single-product revenue management problems. Oper. Res. 62(2):318–331.Link, Google Scholar
• Ye Y (2008) A path to the Arrow–Debreu competitive market equilibrium. Math. Programming 111(1):315–348.Google Scholar
• Yu H, Neely M, Wei X (2017) Online convex optimization with stochastic constraints. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems (NIPS 2017), vol. 30 (Curran Associates Inc., Red Hook, NY), 1427–1437.Google Scholar
• Zhang L (2011) Proportional response dynamics in the Fisher market. Theoret. Comput. Sci. 412(24):2691–2698.Crossref, Google Scholar