2019-01-18 | Ioannis Caragiannis：The efficiency of resource allocation mechanisms for budget-constrained users
We study the efficiency of
mechanisms for allocating a divisible resource. Given scalar signals submitted
by all users, such a mechanism decides the fraction of the resource that each
user will receive and a payment that will be collected from her. Users are
self-interested and aim to maximize their utility (defined as their value for
the resource fraction they receive minus their payment). Starting with the
seminal work of Johari and Tsitsiklis [Operations Research, 2004], a long list
of papers studied the price of anarchy (in terms of the social welfare --- the
total users' value) of resource allocation mechanisms for a variety of
allocation and payment rules. Here, we further assume that each user has a
budget constraint that invalidates strategies that yield a payment that is
higher than the user's budget. This subtle assumption (which is arguably more
realistic) constitutes the traditional price of anarchy analysis meaningless as
the set of equilibria may change drastically and their social welfare can be
arbitrarily far from optimal.
Instead, we study the price of anarchy using the liquid welfare benchmark that measures efficiency taking budget constraints into account. We show a tight bound of 2 on the liquid price of anarchy of the well-known Kelly mechanism and prove that this result is essentially best possible among all multi-user resource allocation mechanisms. This comes in sharp contrast to the no-budget setting where there are mechanisms that considerably outperform Kelly in terms of social welfare and even achieve full efficiency. In our proofs, we exploit the particular structure of worst-case games and equilibria, which also allows us to design (nearly) optimal two-player mechanisms by solving differential equations.
Ioannis Caragiannis (Computer
Scientist and Engineer; Diploma, 1996; PhD, 2002) is an Associate Professor at
the Department of Computer Engineering and Informatics of the University of
research interests include design and analysis of algorithms, economics and
computation, and foundations of machine learning and artificial intelligence.
has published more than 150 papers in conference proceedings, scientific
journals, and books and has participated in basic research projects funded by
the European programmes IST/ICT FET, ESF/COST, and ESPRIT LTR and by the Greek
Currently, he is involved, as a member of its management committee, in the COST Actions CA15210 “European network for collaboration on kidney exchange programmes (ENCKEP)” and CA16228 “European Network for Game Theory (GAMENET).” He also recently served in the senior program committee of the 19th ACM Conference on Economics and Computation (EC 2018) and the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018). Ioannis Caragiannis is a member of the Association for Computing Machinery (ACM, SIGACT, SIGECOM), the Association for the Advancement of Artificial Intelligence (AAAI), and the European Association for Theoretical Computer Science (EATCS).