Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location

References

• [1] Alon N, Feldman M, Procaccia AD, Tennenholtz M (2010) Strategyproof approximation of the minimax on networks. Math. Oper. Res. 35(3):513–526.Link, Google Scholar
• [2] Antoniadis A, Gouleakis T, Kleer P, Kolev P (2020) Secretary and online matching problems with machine learned advice. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems (Curran Associates Inc., Red Hook, NY), 7933–7944.Google Scholar
• [3] Azar Y, Panigrahi D, Touitou N (2022) Online graph algorithms with predictions. Naor J(S), Buchbinder N, eds. Proc. Thirty-Third Annu. ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 35–66.Google Scholar
• [4] Bamas E, Maggiori A, Svensson O (2020) The primal-dual method for learning augmented algorithms. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems (Curran Associates Inc., Red Hook, NY), 20083–20094.Google Scholar
• [5] Banerjee S, Gkatzelis V, Gorokh A, Jin B (2022) Online Nash social welfare maximization with predictions. Naor J(S), Buchbinder N, eds. Proc. 2022 ACM-SIAM Sympos. Discrete Algorithms SODA 2022 (Society for Industrial and Applied Mathematics, Philadelphia), 1–19.Google Scholar
• [6] Chan H, Filos-Ratsikas A, Li B, Li M, Wang C (2021) Mechanism design for facility location problems: A survey. Zhou ZH, ed. Proc. Thirtieth Internat. Joint Conf. Artificial Intelligence IJCAI-21 (International Joint Conferences on Artificial Intelligence Organization, California), 4356–4365.Google Scholar
• [7] Dütting P, Lattanzi S, Paes Leme R, Vassilvitskii S (2021) Secretaries with advice. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 409–429.Google Scholar
• [8] El-Mhamdi EM, Farhadkhani S, Guerraoui R, Hoang LN (2023) On the strategyproofness of the geometric median. Ruiz F, Dy J, van de Meent J-M, eds. Proc. 26th Internat. Conf. Artificial Intelligence Statist. (PMLR, New York), 2603–2640.Google Scholar
• [9] Escoffier B, Gourves L, Thang NK, Pascual F, Spanjaard O (2011) Strategy-proof mechanisms for facility location games with many facilities. Brafman RI, Roberts FS, Tsoukiàs A, eds. ADT 2011 Internat. Conf. Algorithmic Decision Theory (Springer, Berlin, Heidelberg), 67–81.Google Scholar
• [10] Feldman M, Wilf Y (2013) Strategyproof facility location and the least squares objective. Proc. Fourteenth ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 873–890.Google Scholar
• [11] Fotakis D, Tzamos C (2014) On the power of deterministic mechanisms for facility location games. ACM Trans. Econom. Comput. 2(4):1–37.Crossref, Google Scholar
• [12] Fotakis D, Tzamos C (2016) Strategyproof facility location for concave cost functions. Algorithmica 76(1):143–167.Crossref, Google Scholar
• [13] Fotakis D, Gergatsouli E, Gouleakis T, Patris N (2021) Learning augmented online facility location. Preprint, submitted July 17, https://arxiv.org/abs/2107.08277.Google Scholar
• [14] Goel S, Hann-Caruthers W (2023) Optimality of the coordinate-wise median mechanism for strategyproof facility location in two dimensions. Soc. Choice Welfare 61:11–34.Crossref, Google Scholar
• [15] Im S, Kumar R, Montazer Qaem M, Purohit M (2021) Online knapsack with frequency predictions. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY), 2733–2743.Google Scholar
• [16] Jiang SHC, Liu E, Lyu Y, Tang ZG, Zhang Y (2022) Online facility location with predictions. Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [17] Lykouris T, Vassilvtiskii S (2018) Competitive caching with machine learned advice. Internat. Conf. Machine Learn. (PMLR, New York), 3296–3305.Google Scholar
• [18] Medina AM, Vassilvitskii S (2017) Revenue optimization with approximate bid predictions. Proc. 31st Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 1856–1864.Google Scholar
• [19] Meir R (2019) Strategyproof facility location for three agents on a circle. Fotakis D, Markakis E, eds. SAGT 2019 Internat. Sympos. Algorithmic Game Theory (Springer, Cham, Switzerland), 18–33.Google Scholar
• [20] Mitzenmacher M, Vassilvitskii S (2022) Algorithms with predictions. Commun. ACM 65(7):33–35.Crossref, Google Scholar
• [21] Moulin H (1980) On strategy-proofness and single peakedness. Public Choice 35(4):437–455.Crossref, Google Scholar
• [22] Peters H, van der Stel H, Storcken T (1993) Range convexity, continuity, and strategy-proofness of voting schemes. ZOR Methods Model. Oper. Res. 38(2):213–229.Crossref, Google Scholar
• [23] Procaccia AD, Tennenholtz M (2013) Approximate mechanism design without money. ACM Trans. Economics Comput. 1(4):18:1–18:26.Crossref, Google Scholar
• [24] Procaccia AD, Wajc D, Zhang H (2018) Approximation-variance tradeoffs in facility location games. McIlraith SA, Weinberger KQ, eds. Proc. Thirty-Second AAAI Conf. Artificial Intelligence AAAI-18 30th Innovative Appl. Artificial Intelligence IAAI-18 8th AAAI Sympos. Ed. Advances Artificial Intelligence EAAI-18 (AAAI Press, Washington, DC), 1185–1192.Google Scholar
• [25] Purohit M, Svitkina Z, Kumar R (2018) Improving online algorithms via ML predictions. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, NY), 9684–9693.Google Scholar
• [26] Roughgarden T, ed. (2021) Beyond the Worst-Case Analysis of Algorithms (Cambridge University Press, Cambridge, UK).Google Scholar
• [27] Serafino P, Ventre C (2016) Heterogeneous facility location without money. Theoretical Comput. Sci. 636:27–46.Crossref, Google Scholar
• [28] Walsh T (2020) Strategy proof mechanisms for facility location in Euclidean and Manhattan space. Preprint, submitted September 17, https://arxiv.org/abs/2009.07983.Google Scholar
• [29] Xu C, Lu P (2022) Mechanism design with predictions. Raedt LD, ed. IJCAI’22 31st Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence Organization, California), 571–577.Google Scholar