Information Technology Reference
In-Depth Information
≤
i
t
i
(
θ
)
<
.Weanalyzea
general multiagent flow problem, and show that for every
>
0 we can create a
strategy-resistant, allocatively ecient, and
-budget-balanced mechanism. This
result indicates that at least for some domains, it is possible to use the fact that
agents have computational limitations and are not unboundedly rational, so as
to construct mechanisms with beneficial properties.
want). A mechanism is
-budget-balanced if 0
2
Related Work
The main focus of research on bounded-rational mechanism design is on the prob-
lems that computational complexity poses for mechanism designers. Relatively
little research has been dedicated to
using
the bounded-rationality of realistic
agents to build better mechanisms. This approach was taken in [3] (building on
the work in [4]), which used computational complexity to show that common
voting protocols are hard to manipulate. A similar approach was taken in [5],
where coalition games were analyzed. It was shown there that manipulating a
marginal-contribution based value distribution scheme, similar to the standard
solution of the Shapley value [6], is an NP-complete problem. [7] considered
coalitions among computationally bounded agents. It suggested some bounded
rational concepts for coalition games, and indicated that computational complex-
ity considerations may lead us to extend the set of acceptable stable solutions.
[8] analyzed VCG auctions, and showed that manipulating VCG auctions us-
ing false name bids is NP-hard; it also analyzed approximate VCG auctions. [9]
showed that using an approximation method to find the optimal allocation in
combinatorial auctions can lead to the loss of strategy-proofness.
3
Preliminaries
In this article, we propose an alternative to VCG mechanisms in quasi-linear
domains. In such domains, we have a set
I
of agents. The mechanism needs to
choose one of a set of possible alternatives
K
. Each agent reports a type
θ
i
∈
Θ
i
to the mechanism. This type represents the agent's preferences over the different
alternatives in
K
. Each agent has a different valuation of the mechanism's chosen
alternative
k
K
,
v
i
(
k, θ
i
). The mechanism chooses the outcome according to a
choice rule
k
:
Θ
1
×
∈
K
. Each agent is also required to make a payment
p
i
to the mechanism. The mechanism chooses the payment of each agent accord-
ing to a payment rule
t
i
:
Θ
1
×
...
×
Θ
I
→
IR. If the agents have quasi-linear utility
functions, then the agents have utility
u
i
(
k, p
i
,θ
i
)=
v
i
(
k, θ
i
)
Θ
I
→
p
i
. An agent might
not report its true type, but can choose a type to report to the mechanism. Thus,
agent
i
(
A
i
)reportsatype
θ
i
=
s
i
(
θ
i
), according to its own strategy.
−
3.1 Groves and VCG Mechanisms
In Groves mechanisms, the mechanism's choice rule given the reported types
θ
=(
θ
1
, ..., θ
I
) maximizes the sum of the agents' utilities, according to their
reported types:
