  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 [Mathematics
of 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 simple
differential equations.
