Regularized Online Allocation Problems: Fairness and Beyond

References

• Agrawal S, Devanur NR (2015) Fast algorithms for online stochastic convex programming. Proc. Twenty-Sixth Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ‘15 (Society for Industrial and Applied Mathematics, Philadelphia), 1405–1424.Google Scholar
• Agrawal S, Devanur NR, Li L (2016) An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. Feldman V, Rakhlin A, Shamir O, eds. 29th Annual Conf. Learning Theory (PMLR, New York), 4–18.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
• Agrawal S, Zadimoghaddam M, Mirrokni V (2018) Proportional allocation: Simple, distributed, and diverse matching with high entropy. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn. (PMLR, New York), 99–108.Google Scholar
• Ahmed F, Dickerson JP, Fuge M (2017) Diverse weighted bipartite b-matching. Proc. 26th Internat. Joint Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 35–41.Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stoch. Syst. 9(3):231–260.Link, Google Scholar
• Azar Y, Buchbinder N, Jain K (2010) How to allocate goods in an online market? de Berg M, Meyer U, eds. Eur. Sympos. Algorithms (Springer Berlin Heidelberg, Berlin, Heidelberg), 51–62.Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2018) Bandits with knapsacks. J. ACM 65(3):1–55.Crossref, Google Scholar
• Ball MO, Queyranne M (2009) Toward robust revenue management: Competitive analysis of online booking. Oper. Res. 57(4):950–963.Link, 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, Lu H, Mirrokni V (2020) The best of many worlds: Dual mirror descent for online allocation problems. Preprint, submitted November 18, https://doi.org/10.48550/arXiv.2011.10124.Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2021) Regularized online allocation problems: Fairness and beyond. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn. (PMLR, New York), 630–639.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
• Balseiro SR, Feldman J, Mirrokni V, Muthukrishnan S (2014) Yield optimization of display advertising with ad exchange. Management Sci. 60(12):2886–2907.Link, Google Scholar
• Bansal N, Sviridenko M (2006) The Santa Claus problem. Proc. Thirty-Eighth Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 31–40.Google Scholar
• Bateni MH, Chen Y, Ciocan D, Mirrokni V (2018) Fair resource allocation in a volatile marketplace. Preprint, submitted October 21, http://dx.doi.org/10.2139/ssrn.2789380.Google Scholar
• Bertsekas DP (2009) Convex Optimization Theory (Athena Scientific, Belmont, MA).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
• Boyd S, Boyd SP, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learn. 8(3–4):231–357.Crossref, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Arge L, Hoffmann M, Welzl E, eds. Algorithms – ESA 2007 (Springer Berlin Heidelberg, Berlin, Heidelberg), 253–264.Crossref, Google Scholar
• Cain Miller C (2015) When algorithms discriminate. New York Times (July 9), https://www.nytimes.com/2015/07/10/upshot/when-algorithms-discriminate.html.Google Scholar
• Celli A, Colini-Baldeschi R, Kroer C, Sodomka E (2021) The parity ray regularizer for pacing in auction markets. Preprint, submitted June 17, https://doi.org/10.48550/arXiv.2106.09503.Google Scholar
• Cheung WC, Lyu G, Teo CP, Wang H (2020) Online planning with offline simulation. Available at SSRN 3709882.Google Scholar
• Devanur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce, EC ‘09 (Association for Computing Machinery, New York), 71–78.Google Scholar
• Devanur NR, Jain K (2012) Online matching with concave returns. Proc. Forty-Fourth Annual ACM Sympos. Theory Comput., STOC ‘12 (Association for Computing Machinery, New York), 137–144.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2019) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM 66(1):1–41.Crossref, Google Scholar
• Dickerson JP, Sankararaman KA, Srinivasan A, Xu P (2019) Balancing relevance and diversity in online bipartite matching via submodularity. AAAI 33(November):1877–1884.Crossref, Google Scholar
• Eghbali R, Fazel M (2016) Designing smoothing functions for improved worst-case competitive ratio in online optimization. Lee D, Sugiyama M, Luxburg U, Guyon I, Garnett R, eds. Adv. Neural Inform. Processing Systems (Curran Associates, Inc., Red Hook, NY), 3287–3295.Google Scholar
• Emanuel EJ, Persad G, Upshur R, Thome B, Parker M, Glickman A, Zhang C, Boyle C, Smith M, Phillips JP (2020) Fair allocation of scarce medical resources in the time of covid-19. N Engl. J. Med. 382(21):2049–2055.Crossref, Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. DeBerg M, Meyer U, eds. Proc. 18th Annual Eur. Conf. Algorithms Part I ESA ’10 (Springer-Verlag, Berlin, Heidelberg), 182–194.Google Scholar
• Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pál M (2009) Online ad assignment with free disposal. Leonardi S, ed. Proc. 5th Internat. Workshop Internet Network Economics WINE ‘09 (Springer-Verlag, Berlin, Heidelberg), 374–385.Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3–4):157–325.Crossref, Google Scholar
• Jasin S (2015) Performance of an lp-based control for revenue management with unknown demand parameters. Oper. Res. 63(4):909–915.Link, Google Scholar
• Jenatton R, Huang J, Csiba D, Archambeau C (2016) Online optimization and regret guarantees for non-additive long-term constraints. Preprint, submitted February 17, https://arxiv.org/abs/1602.05394.Google Scholar
• Jiang J, Li X, Zhang J (2025) Online stochastic optimization with Wasserstein based non-stationarity. Management Sci. Forthcoming.Link, Google Scholar
• Jiang J, Wang S, Zhang J (2019) Achieving high individual service-levels without safety stock? Optimal rationing policy of pooled resources. Preprint, submitted August 22, http://dx.doi.org/10.2139/ssrn.3385089.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Bodlaender HL, Italiano GF, eds. Proc. Twenty-Second Annual ACM Sympos. Theory Comput. (Springer Berlin Heidelberg, Berlin, Heidelberg), 352–358.Google Scholar
• Li X, Ye Y (2021) Online linear programming: Dual convergence, new algorithms, and regret bounds. Preprint, submitted September 12, https://arxiv.org/abs/1909.05499.Google Scholar
• Li X, Sun C, Ye Y (2020) Simple and fast algorithm for binary integer and online linear programming. Preprint, submitted March 5, https://doi.org/10.48550/arXiv.2003.02513.Google Scholar
• Lien RW, Iravani SMR, Smilowitz KR (2014) Sequential resource allocation for nonprofit operations. Oper. Res. 62(2):301–317.Link, Google Scholar
• Lobos A, Grigas P, Wen Z, Lee K (2018) Optimal bidding, allocation and budget spending for a demand side platform under many auction types. Preprint, submitted May 29, https://arxiv.org/abs/1805.11645.Google Scholar
• Lykouris T, Mirrokni V, Paes Leme R (2018) Stochastic bandits robust to adversarial corruptions. Diakonikolas I, Kempe D, Henzinger M, eds. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 114–122.Google Scholar
• Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6):1787–1803.Link, Google Scholar
• Ma W, Xu P (2020) Group-level fairness maximization in online bipartite matching. Preprint, submitted November 27, https://arxiv.org/abs/2011.13908.Google Scholar
• Manshadi V, Niazadeh R, Rodilitz S (2021) Fair dynamic rationing. EC ‘21 (Association for Computing Machinery, New York), 694–695.Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoret. Comput. Sci. 8(4):265–368.Crossref, 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
• Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation (Association for Computing Machinery, New York), 1690–1701.Google Scholar
• Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking 8(5):556–567.Crossref, Google Scholar
• Nanda V, Xu P, Sankararaman KA, Dickerson J, Srinivasan A (2020) Balancing the tradeoff between profit and fairness in rideshare platforms during high-demand hours. Proc. AAAI Conf. Artificial Intelligence, vol. 34 (Association for Computing Machinery, New York), 2210–2217.Google Scholar
• Nash JF Jr (1950) The bargaining problem. Econometrica 18(2):155–162.Crossref, Google Scholar
• Tan X, Sun B, Leon-Garcia A, Wu Y, Tsang DH (2020) Mechanism design for online resource allocation: A unified approach. Abstr. 2020 SIGMETRICS/Performance Joint Internat. Conf. Measurement Modeling Comput. Systems (Association for Computing Machinery, New York), 11–12.Google Scholar
• Xu H, Li B (2013) Dynamic cloud pricing for revenue maximization. IEEE Trans. Cloud Comput. 1(2):158–171.Crossref, Google Scholar