Saar Cohen

ConferencePosterExtended Abstract

Near-Optimal Online Resource Allocation in the Random-Order Model

Saar Cohen and Noa Agmon

Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems AAMAS 2024, pp. 2219–2221

Abstract

We study the problem of allocating either divisible or indivisible items (goods or chores) among a set of agents, where the items arrive online, one at a time. Each agent's non-negative value for an item is set by an adversary upon the item's arrival. Our focus is on a unifying algorithmic framework for finding online allocations that treats both fairness and economic efficiency. For this sake, we aim to optimize the generalized means of agents' received values, covering a spectrum of welfare functions including average utilitarian welfare and egalitarian welfare. In the traditional adversarial model, where items arrive in an arbitrary order, no algorithm can give a decent approximation to welfare in the worst case. To escape from this strong lower bound, we consider the random-order model, where items arrive in a uniformly random order. This model provides us with a major breakthrough: we devise algorithms that guarantee a nearly-optimal competitive ratio for certain welfare functions, if the welfare obtained by the optimal allocation is sufficiently large. We prove that our results are almost tight: if the optimal solution's welfare is strictly below a certain threshold, then no nearly-optimal algorithm exists, even in the random-order model.

Cite

Saar Cohen and Noa Agmon. Near-Optimal Online Resource Allocation in the Random-Order Model (Extended Abstract). In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 2219–2221, 2024.

@inproceedings{cohen2024near,
  title     = {{Near-Optimal Online Resource Allocation in the Random-Order Model ({Extended Abstract})}},
  author    = {Saar Cohen and Noa Agmon},
  booktitle = {Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems},
  pages     = {2219--2221},
  year      = {2024},
  doi       = {10.65109/koyf1641}
}

Related work