Efficient Allocation of Free Stuff
We study online matching settings with selfish agents when everything is free. Inconsiderate agents break ties arbitrarily amongst equal maximal value available choices, even if the maximal value is equal to zero. Even for the simplest case of zero/one valuations, where agents arrive online in an arbitrary order, and agents are restricted to taking at most one item, the resulting social welfare may be negligible for a deterministic algorithm. This may be surprising when contrasted with the 1/2 approximation of the greedy algorithm, analogous to this setting, except that agents are considerate (i.e., they don't take zero-valued items).
We overcome this challenge by introducing a new class of algorithms, which we refer to as prioritization algorithms. We show that upgrading a random subset of the agents to "business class" already improves the approximation to a constant. For more general valuations, we achieve a constant approximation using log n priority classes, when the valuations are known in advance. We extend these results to settings where agents have additive valuations and are restricted to taking up to some q items. Our results are tight up to a constant.
This work appeared in AAMAS 2019 and is joint work with Allan Borodin, Michal Feldman, Amos Fiat and Kineret Segal.
Yossi Azar is a Professor in the Blavatnik School Computer Science at Tel-Aviv university. He received his PhD from Tel-Aviv University in 1989. He spent several years at Stanford, DEC and IBM in California and joined Tel-Aviv university in 1994. From 2002 to 2004, Yossi was the chair of the department of Computer Science and from 2011 to 2014 he was the head of the school of Computer Science at Tel Aviv university. From 2006 until 2009 he was on extended sabbatical in Microsoft Research in Redmond as a visiting principal researcher. His research interests include design and analysis of discrete algorithms, especially related to online and approximations algorithms and algorithmic game theory. He coauthored over 100 papers, served on various conference program committees and advised various graduate students.