Abstract

We study the efficiency ofmechanisms for allocating a divisible resource. Given scalar signals submittedby all users, such a mechanism decides the fraction of the resource that eachuser will receive and a payment that will be collected from her. Users areself-interested and aim to maximize their utility (defined as their value forthe resource fraction they receive minus their payment). Starting with theseminal work of Johari and Tsitsiklis [Operations Research, 2004], a long listof papers studied the price of anarchy (in terms of the social welfare --- thetotal users' value) of resource allocation mechanisms for a variety ofallocation and payment rules. Here, we further assume that each user has abudget constraint that invalidates strategies that yield a payment that ishigher than the user's budget. This subtle assumption (which is arguably morerealistic) constitutes the traditional price of anarchy analysis meaningless asthe set of equilibria may change drastically and their social welfare can bearbitrarily far from optimal. 

Instead, we study the price ofanarchy using the liquid welfare benchmark that measures efficiency takingbudget constraints into account. We show a tight bound of 2 on the liquid priceof anarchy of the well-known Kelly mechanism and prove that this result isessentially best possible among all multi-user resource allocation mechanisms.This comes in sharp contrast to the no-budget setting where there aremechanisms that considerably outperform Kelly in terms of social welfare andeven achieve full efficiency. In our proofs, we exploit the particularstructure of worst-case games and equilibria, which also allows us to design(nearly) optimal two-player mechanisms by solving differential equations.

Time

1月18日（周五）14:00-15:00

Speaker

Ioannis Caragiannis (ComputerScientist and Engineer; Diploma, 1996; PhD, 2002) is an Associate Professor atthe Department of Computer Engineering and Informatics of the University ofPatras, Greece.

Hisresearch interests include design and analysis of algorithms, economics andcomputation, and foundations of machine learning and artificial intelligence. 

Hehas published more than 150 papers in conference proceedings, scientificjournals, and books and has participated in basic research projects funded bythe European programmes IST/ICT FET, ESF/COST, and ESPRIT LTR and by the Greekstate. 

Currently,he is involved, as a member of its management committee, in the COST ActionsCA15210 “European network for collaboration on kidney exchange programmes (ENCKEP)”and CA16228 “European Network for Game Theory (GAMENET).” He also recentlyserved in the senior program committee of the 19th ACM Conference on Economicsand Computation (EC 2018) and the 27th International Joint Conference onArtificial Intelligence (IJCAI 2018). Ioannis Caragiannis is a member of theAssociation for Computing Machinery (ACM, SIGACT, SIGECOM), the Association forthe Advancement of Artificial Intelligence (AAAI), and the European Associationfor Theoretical Computer Science (EATCS).

Venue

信息管理与工程学院602室

上海财经大学（第三教学楼西侧）

上海市杨浦区武东路100号