Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents - Agent-Mediated Electronic Commerce - page 72

Although in VCG mechanisms the agents pay the mechanism, they never pay
more than they value the chosen outcome; the agents always have positive utility,
and voluntarily participate.
A significant disadvantage of VCG mechanisms is that they are only weakly
budget-balanced. We would in principle prefer a strongly budget-balanced mech-

anism, where the total sum of payments to the mechanism is zero: i t i ( θ )=0.
Impossibility results ([1] and [2]) show that in a quasi-linear environment, it is
impossible to achieve a mechanism that is strategy-proof, allocatively-ecient,
and strongly budget-balanced. Given this fact, we are faced with a grim future.
Giving up allocation-eciency means we would no longer maximize the sum
of agents' utilities, which was our goal in the first place. Giving up strategy-
proofness means agents may have an incentive to try and manipulate the mech-
anism by not reporting their true preferences, which may lead us to a sub-optimal
result. However, without sacrificing one of the two, we will not be able to achieve
strong budget-balance.
We propose addressing this problem by relaxing the strategy-proof require-
ment, replacing it with strategy-resistance . A mechanism is strategy-proof if the
dominant strategy of each agent is to reveal its true type to the mechanism.
Strategy-resistance only requires that even if an agent is given the reported
types of the other agents, it still faces a computationally intractable problem to
solve if it wishes to find a beneficial manipulation (i.e., report a false type to
the mechanism in order to gain higher utility). We here consider a scenario in
which it is an NP-hard problem for an agent to find a useful manipulation. NP-
hardness is a worst case notion of computational diculty, in the sense that it
only indicates that a certain problem has some hard instances. A stronger notion
of strategy-resistance could also require the manipulation problem to have no
approximation methods, or require it to be in some harder computational com-
plexity class. Also, a stronger sense of strategy resistance could require it to be
hard to find any beneficial manipulation, not just the optimal manipulation. This
paper constitutes a first step in establishing the notion of strategy-resistance.
In this paper we consider the network flow domain. In this domain, the edges
of a network flow belong to several self-interested agents. Each agent reports its
edges to the mechanism. The mechanism is then required to choose a flow from
the source vertex to the target vertex. Agents gain utility from flow units on
their edges. A reasonable choice for the mechanism would be selecting the flow
that maximizes the total flow on all of the agents' edges. In the case of a layer
graph, this can easily be done by finding the maximal flow, and we get a simple
and tractable algorithm for implementing the mechanism, assuming each of the
agents truthfully reports its subset of edges. However, in some cases it is beneficial
for these agents to hide some of their edges. A VCG mechanism to overcome this
problem would be strategy-proof, but only weakly budget-balanced.
We show that in the domain of network flow, it is possibletoachieveamecha-
nism that is strategy-resistant (and thus agents have an incentive to be truthful),
ecient when agents are truthful, and as budget-balanced as we want it to be

(i.e., we can minimize the sum of agent payments, i t i ( θ ), as much as we