@inproceedings{971988f8fddf4cc28bc1667b16402282,
title = "Online Nash Welfare Maximization Without Predictions",
abstract = "The maximization of Nash welfare, which equals the geometric mean of agents{\textquoteright} utilities, is widely studied because it balances efficiency and fairness in resource allocation problems. Banerjee, Gkatzelis, Gorokh, and Jin (2022) recently introduced the model of online Nash welfare maximization for T divisible items and N agents with additive utilities with predictions of each agent{\textquoteright}s utility for receiving all items. They gave online algorithms whose competitive ratios are logarithmic. We initiate the study of online Nash welfare maximization without predictions, assuming either that the agents{\textquoteright} utilities for receiving all items differ by a bounded ratio, or that their utilities for the Nash welfare maximizing allocation differ by a bounded ratio. We design online algorithms whose competitive ratios are logarithmic in the aforementioned ratios of agents{\textquoteright} utilities and the number of agents.",
keywords = "Fair division, Nash welfare, Online algorithm",
author = "Zhiyi Huang and Minming Li and Xinkai Shu and Tianze Wei",
note = "Publisher Copyright: {\textcopyright} 2024, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 19th InternationalConference on Web and Internet Economics, WINE 2023 ; Conference date: 04-12-2023 Through 08-12-2023",
year = "2024",
doi = "10.1007/978-3-031-48974-7\_23",
language = "英语",
isbn = "9783031489730",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "402--419",
editor = "Jugal Garg and Max Klimm and Yuqing Kong",
booktitle = "Web and Internet Economics - 19th International Conference, WINE 2023, Proceedings",
address = "德国",
}