Information Technology Reference
In-Depth Information
Achieving Allocatively-Ecient and Strongly
Budget-Balanced Mechanisms in the Network
Flow Domain for Bounded-Rational Agents
Yoram Bachrach and Jeffrey S. Rosenschein
Hebrew University, Jerusalem, Israel
(yori, jeff)@cs.huji.ac.il
Abstract.
Vickrey-Clarke-Groves (VCG) mechanisms are a well-known
framework for finding a solution to a distributed optimization problem
in systems of self-interested agents. VCG mechanisms have received wide
attention in the AI community because they are ecient and strategy-
proof; a special case of the Groves family of mechanisms, VCG mech-
anisms are the
only
direct-revelation mechanisms that are allocatively
ecient and strategy-proof. Unfortunately, VCG mechanisms are only
weakly budget-balanced.
We consider self-interested agents in a network flow domain, and
show that in this domain, it
is
possible to design a mechanism that is
both allocatively-ecient and almost completely budget-balanced. This
is done by choosing a mechanism that is not
strategy-proof
but rather
strategy-resistant
. Instead of using the VCG mechanism, we propose a
mechanism in which finding the most beneficial manipulation is an NP-
complete problem, and the payments from the agents to the mechanism
may be minimized as much as desired. This way, the mechanism is virtu-
ally strongly budget-balanced: for any
>
0, we find a mechanism that
is
-budget-balanced.
1
Introduction
Mechanisms face the problem of finding a system-wide solution to an optimiza-
tion problem based on private information given by self-interested agents. As
mechanism designers, we want to build a mechanism that would encourage agents
to report their information truthfully, so that we can implement a desirable so-
cial choice function and maximize social welfare. A well-known solution to this
problem in the case of quasi-linear preferences is that of Groves mechanisms. A
special case of the Groves family of mechanisms are VCG mechanisms, which
are budget-balanced, allocatively-ecient and strategy-proof.
Thus, in many cases, by using VCG we get a mechanism that operates with
no outside subsidy (weakly budget-balanced) and maximizes the agents' utility.
We maximize the agents' utility by choosing the outcome that maximizes the
total utility according to the agents' reported types. Since VCG mechanisms
are strategy-proof, the agents report their true preferences, and the mechanism
maximizes their true utility. Also, VCG mechanisms are individually rational.
