Information Technology Reference
In-Depth Information
k
∗
(
θ
)=
arg
max
k∈K
v
i
(
k, θ
i
)
.
(1)
i
The payment rule in Groves mechanisms is
t
i
(
θ
)=
h
i
(
θ
−i
)
v
j
(
k
∗
,θ
j
)
−
(2)
j
=
i
where
h
i
:
Θ
−i
→
IR may be any function that only depends on the reported
types of agents other than
i
. Groves mechanisms are allocatively-ecient, and
maximize the total utility of the agents. They are also strategy-proof, and for
each agent the dominant strategy is to reveal its true type (or preferences) to
the mechanism, no matter what the other agents report. Groves mechanisms are
known to be the only direct revelation mechanisms that are allocatively-ecient
and strategy-proof. Another advantage of Groves mechanisms is that in many
cases they are weakly budget-balanced:
i
t
i
(
θ
)
0.
A special case of Groves mechanisms is that of the VCG mechanism, when
h
i
(
θ
−i
)=
j
=
i
≥
v
j
(
k
−i
(
θ
−i
)
,θ
j
)
.
(3)
Under quite general settings, agents would voluntarily participate in VCG
mechanisms, and we say that under these conditions the mechanism is individual-
rational. The VCG mechanism also achieves weak budget-balance in quite gen-
eral settings.
3.2
Main Contribution of the Paper
We approach the problem of designing a mechanism for bounded rational agents
by building a mechanism for a distributed flow problem. We will demonstrate
that for this domain, we can find a mechanism that is allocatively-e
cient,
-
budget-balanced, and strategy-resistant. This means that if we assume the agents
are bounded-rational and would not try to manipulate the mechanism if such
manipulation is an NP-complete problem, they would all truthfully report their
preferences. Once the mechanism gets their true preferences, it chooses the out-
come that maximizes total utility of the agents. To achieve this truthfulness, the
mechanism requires side payments; however, the total sum of these payments
can be minimized as much as required. In other words, for every
>
0wecan
build such a strategy-resistant, allocatively-ecient mechanism, that would also
be
-budget-balanced.
We restrict ourselves to the case where maximizing the graph's flow also
maximizes the agents' total utility, since this allows us to choose a tractable
mechanism. However, although the mechanism itself performs a polynomial cal-
culation, finding the optimal manipulation for an agent remains NP-complete.
The payments we demand from the agents to the mechanism makes finding
this manipulation hard, while leaving the mechanism's calculation simple and
tractable.
