Information Technology Reference
In-Depth Information
the manipulation problem are indeed computationally intractable, we expect
agents would truthfully report their preferences. In this case, the mechanism
would choose the result maximizing the sum of agents' utilities, and we have an
allocatively-ecient mechanism.
Given some
>
0, we can make the mechanism
-budget-balanced, by choos-
ing a constant
c
=
n
(
|E|
+
|V |
)
, so that all of the agents together pay less than
.
The mechanism we have described is also individual rational. The mechanism's
calculation is tractable, and only involves a polynomial algorithm for finding the
maximal network flow. This indicates that the agents' di
culty in finding a ben-
eficial manipulation is not caused by any di
culty in simulating the mechanism,
but is instead caused by the diculty of trying exponentially many options of
untruthful declarations to the mechanism.
Therefore, in the domain of network flow, it is possible to achieve an
individually-rational, allocatively-ecient,
-budget-balanced, and strategy-
resistant mechanism. The standard VCG solution in this domain would be only
weakly budget-balanced, but strategy-proof. Impossibility results [1] and [2] in-
dicate that no direct-revelation mechanism can achieve strong budget-balance
without sacrificing either allocative-eciency or strategy-proofness. We believe
that in many cases, trading strategy-proofness for strategy-resistance is a fair
price to pay for achieving strong budget-balance.
There has been much work dedicated to overcoming the intractability of mech-
anisms, since in building a real-world mechanism we cannot assume unbounded
computation. However, if we are not willing to accept unbounded-rationality on
the
mechanism's
part, we must also consider the implications of the bounded-
rational nature of the
agents
.
We believe that strategy-proofness should not be the only criteria when con-
sidering the susceptibility of a mechanism to manipulations. In fact, we believe
it is found on one end of a
scale
of susceptibility. On the other end of this
scale are mechanisms where there exists a poly-time algorithm for finding the
optimal manipulation. Such mechanisms probably cannot be used in practice,
since they are so easy to manipulate. Between these two extremes is the re-
gion of strategy-resistant mechanisms. In this paper we have implicitly defined a
strategy-resistant mechanism as one in which it is NP-hard to find the optimal
manipulation. As we have commented above, this is a rather weak notion of
strategy resistance. A preferable solution would be one in which it is computa-
tionally intractable to find
any
manipulation. NP-hardness is not sucient for
a problem to be computationally intractable. For example, we can require the
manipulation problem to have no approximation methods, or show that most
instances of the manipulation problem are indeed hard.
In this paper we have shown that in the network flow domain, we can gain
budget-balance by giving up strategy proofness, and replacing it with our notion
of strategy-resistance. Assuming we are willing to accept strategy-resistance as
a sucient guarantee that agents would truthfully declare their types, we have
improved the results obtained by VCG for this problem.
