座椅机构外文翻译

huan8218

Self-interested Automated Mechanism Design and
∗




Vincent Conitzer
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213, USA
conitzer@cs.cmu.edu


ABSTRACT
Often, an outcome must be chosen on the basis of the pref-
erences reported by a group of agents. The key difficulty
is that the agents may report their preferences insincerely
to make the chosen outcome more favorable to themselves.
Mechanism design is the art of designing the rules of the
game so that the agents are motivated to report their pref-
erences truthfully, and a desirable outcome is chosen. In a
recently proposed approach—called automated mechanism
design—a mechanism is computed for the preference aggre-
gation setting at hand. This has several advantages, but the
downside is that the mechanism design optimization prob-
lem needs to be solved anew each time. Unlike the earlier
work on automated mechanism design that studied a benev-




Tuomas Sandholm
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, PA 15213, USA
sandholm@cs.cmu.edu


Categories and Subject Descriptors
F.2 [Theory of Computation]: Analysis of Algorithms
and Problem Complexity; J.4 [Computer Applications]:
Social and Behavioral Sciences—Economics

General Terms
Algorithms, Economics, Theory

Keywords
Automated Mechanism Design, Combinatorial Auctions,
Revenue Maximization

olent designer, in this paper we study automated mechanism

1.

INTRODUCTION

design problems where the designer is self-interested. In this
case, the center cares only about which outcome is chosen
and what payments are made to it. The reason that the
agents’ preferences are relevant is that the center is con-
strained to making each agent at least as well off as the agent
would have been had it not participated in the mechanism.
In this setting, we show that designing optimal deterministic
mechanisms is N P-complete in two important special cases:
when the center is interested only in the payments made
to it, and when payments are not possible and the center
is interested only in the outcome chosen. We then show
how allowing for randomization in the mechanism makes
problems in this setting computationally easy. Finally, we
show that the payment-maximizing AMD problem is closely
related to an interesting variant of the optimal (revenue-
maximizing) combinatorial auction design problem, where
the bidders have “best-only” preferences. We show that
here, too, designing an optimal deterministic auction is NP-
complete, but designing an optimal randomized auction is
easy.
∗
Grant IIS-9800994, ITR IIS-0081246, and ITR IIS-0121678.



Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
EC’04, May 17–20, 2004, New York, New York, USA.
Copyright 2004 ACM 1-58113-711-0/04/0005 ...$5.00.

In multiagent settings, often an outcome must be cho-
sen on the basis of the preferences reported by a group of
agents. Such outcomes could be potential presidents, joint
plans, allocations of goods or resources, etc. The preference
aggregator generally does not know the agents’ preferences
a priori. Rather, the agents report their preferences to the
coordinator. Unfortunately, an agent may have an incentive
to misreport its preferences in order to mislead the mech-
anism into selecting an outcome that is more desirable to
the agent than the outcome that would be selected if the
agent revealed its preferences truthfully. Such manipulation
is undesirable because preference aggregation mechanisms
are tailored to aggregate preferences in a socially desirable
way, and if the agents reveal their preferences insincerely, a
socially undesirable outcome may be chosen.
Manipulability is a pervasive problem across preference
aggregation mechanisms. A seminal negative result, the
Gibbard-Satterthwaite theorem, shows that under any non-
dictatorial preference aggregation scheme, if there are at
least 3 possible outcomes, there are preferences under which
an agent is better off reporting untruthfully [10, 23]. (A
preference aggregation scheme is called dictatorial if one of
the agents dictates the outcome no matter what preferences
the other agents report.)
What the aggregator would like to do is design a prefer-
ence aggregation mechanism so that 1) the self-interested
agents are motivated to report their preferences truthfully,
and 2) the mechanism chooses an outcome that is desirable
from the perspective of some objective. This is the classic
setting of mechanism design in game theory. In this paper,
we study the case where the designer is self-interested, that
is, the designer does not directly care about how the out-





come relates to the agents’ preferences, but is rather con-
cerned with its own agenda for which outcome should be
chosen, and with maximizing payments to itself. This is the
mechanism design setting most relevant to electronic com-
merce.
In the case where the mechanism designer is interested in
maximizing some notion of social welfare, the importance
of collecting the agents’ preferences is clear. It is perhaps
less obvious why they should be collected when the designer
is self-interested and hence its objective is not directly re-
lated to the agents’ preferences. The reason for this is that
often the agents’ preferences impose limits on how the de-
signer chooses the outcome and payments. The most com-
mon such constraint is that of individual rationality (IR),
which means that the mechanism cannot make any agent
worse off than the agent would have been had it not par-
ticipated in the mechanism. For instance, in the setting
of optimal auction design, the designer (auctioneer) is only
concerned with how much revenue is collected, and not per
se with how well the allocation of the good (or goods) cor-
responds to the agents’ preferences. Nevertheless, the de-
signer cannot force an agent to pay more than its valuation
for the bundle of goods allocated to it. Therefore, even a
self-interested designer will choose an outcome that makes
the agents reasonably well off. On the other hand, the de-
signer will not necessarily choose a social welfare maximiz-
ing outcome. For example, if the designer always chooses
an outcome that maximizes social welfare with respect to
the reported preferences, and forces each agent to pay the
difference between the utility it has now and the utility it
would have had if it had not participated in the mechanism,
it is easy to see that agents may have an incentive to mis-
report their preferences—and this may actually lead to less
revenue being collected. Indeed, one of the counterintuitive
results of optimal auction design theory is that sometimes
the good is allocated to nobody even when the auctioneer
has a reservation price of 0.
Classical mechanism design provides some general mech-
anisms, which, under certain assumptions, satisfy some no-
tion of nonmanipulability and maximize some objective. The
upside of these mechanisms is that they do not rely on
(even probabilistic) information about the agents’ prefer-
ences (e.g., the Vickrey-Clarke-Groves (VCG) mechanism [24,
4, 11]), or they can be easily applied to any probability
distribution over the preferences (e.g., the dAGVA mecha-
nism [8, 2], the Myerson auction [18], and the Maskin-Riley
multi-unit auction [17]). However, the general mechanisms
also have significant downsides:
• The most famous and most broadly applicable general
mechanisms, VCG and dAGVA, only maximize social
welfare. If the designer is self-interested, as is the case
in many electronic commerce settings, these mecha-
nisms do not maximize the designer’s objective.
• The general mechanisms that do focus on a self-
interested designer are only applicable in very restricted
settings—such as Myerson’s expected revenue maxi-
mizing auction for selling a single item, and Maskin
and Riley’s expected revenue maximizing auction for
selling multiple identical units of an item.
• Even in the restricted settings in which these mecha-
nisms apply, the mechanisms only allow for payment






maximization. In practice, the designer may also be
interested in the outcome per se. For example, an auc-
tioneer may care which bidder receives the item.
• It is often assumed that side payments can be used
to tailor the agents’ incentives, but this is not always
practical. For example, in barter-based electronic
marketplaces—such as Recipco, firstbarter.com,
BarterOne, and Intagio—side payments are not al-
lowed. Furthermore, among software agents, it might
be more desirable to construct mechanisms that do not
rely on the ability to make payments, because many
software agents do not have the infrastructure to make
payments.
In contrast, we follow a recent approach where the mech-
anism is designed automatically for the specific problem at
hand. This approach addresses all of the downsides listed
above. We formulate the mechanism design problem as an
optimization problem. The input is characterized by the
number of agents, the agents’ possible types (preferences),
and the aggregator’s prior distributions over the agents’
types. The output is a nonmanipulable mechanism that is
optimal with respect to some objective. This approach is
called automated mechanism design.
The automated mechanism design approach has four ad-
vantages over the classical approach of designing general
mechanisms. First, it can be used even in settings that
do not satisfy the assumptions of the classical mechanisms
(such as availability of side payments or that the objective
is social welfare). Second, it may allow one to circumvent
impossibility results (such as the Gibbard-Satterthwaite the-
orem) which state that there is no mechanism that is desir-
able across all preferences. When the mechanism is designed
for the setting at hand, it does not matter that it would
not work more generally. Third, it may yield better mech-
anisms (in terms of stronger nonmanipulability guarantees
and/or better outcomes) than classical mechanisms because
the mechanism capitalizes on the particulars of the setting
(the probabilistic information that the designer has about
the agents’ types). Given the vast amount of information
that parties have about each other today, this approach is
likely to lead to tremendous savings over classical mecha-
nisms, which largely ignore that information. For example,
imagine a company automatically creating its procurement
mechanism based on statistical knowledge about its suppli-
ers, rather than using a classical descending procurement
auction. Fourth, the burden of design is shifted from hu-
mans to a machine.
However, automated mechanism design requires the mech-
anism design optimization problem to be solved anew for
each setting. Hence its computational complexity becomes
a key issue. Previous research has studied this question for
benevolent designers—that wish to maximize, for example,
social welfare [5, 6]. In this paper we study the compu-
tational complexity of automated mechanism design in the
case of a self-interested designer. This is an important set-
ting for automated mechanism design due to the shortage
of general mechanisms in this area, and the fact that in
most e-commerce settings the designer is self-interested. We
also show that this problem is closely related to a particular
optimal (revenue-maximizing) combinatorial auction design
problem.





The rest of this paper is organized as follows. In Sec-
tion 2, we justify the focus on nonmanipulable mechanisms.
In Section 3, we define the problem we study. In Section 4,
we show that designing an optimal deterministic mechanism
is N P-complete even when the designer only cares about the
payments made to it. In Section 5, we show that designing
an optimal deterministic mechanism is also N P-complete
when payments are not possible and the designer is only in-
terested in the outcome chosen. In Section 6, we show that
an optimal randomized mechanism can be designed in poly-
nomial time even in the general case. Finally, in Section 7,
we show that for designing optimal combinatorial auctions
under best-only preferences, our results on AMD imply that
this problem is NP-complete for deterministic auctions, but
easy for randomized auctions.






2. a probability distribution γi over Θi (in the case of
correlated types, there is a single joint distribution
γ over Θ1 × . . . × ΘN ), and
1

• An objective function whose expectation the designer
wishes to maximize.
There are many possible objective functions the designer
might have, for example, social welfare (where the designer
seeks to maximize the sum of the agents’ utilities), or the
minimum utility of any agent (where the designer seeks to
maximize the worst utility had by any agent). In both
of these cases, the designer is benevolent, because the de-
signer, in some sense, is pursuing the agents’ collective hap-
piness. However, in this paper, we focus on the case of

2.

JUSTIFYING THE FOCUS ON NONMA-

a self-interested designer. A self-interested designer cares
only about the outcome chosen (that is, the designer does

NIPULABLE MECHANISMS
Before we define the computational problem of automated
mechanism design, we should justify our focus on nonma-
nipulable mechanisms. After all, it is not immediately ob-
vious that there are no manipulable mechanisms that, even
when agents report their types strategically and hence some-
times untruthfully, still reach better outcomes (according to
whatever objective we use) than any nonmanipulable mech-
anism. This does, however, turn out to be the case: given
any mechanism, we can construct a nonmanipulable mech-
anism whose performance is identical, as follows. We build
an interface layer between the agents and the original mech-
anism. The agents report their preferences (or types) to
the interface layer; subsequently, the interface layer inputs
into the original mechanism the types that the agents would
have strategically reported to the original mechanism, if their
types were as declared to the interface layer. The resulting
outcome is the outcome of the new mechanism. Since the
interface layer acts “strategically on each agent’s behalf”,
there is never an incentive to report falsely to the interface
layer; and hence, the types reported by the interface layer
are the strategic types that would have been reported with-
out the interface layer, so the results are exactly as they
would have been with the original mechanism. This argu-
ment is known in the mechanism design literature as the rev-
elation principle [16]. (There are computational difficulties
with applying the revelation principle in large combinatorial
outcome and type spaces [7, 22]. However, because here we
focus on flatly represented outcome and type spaces, this is
not a concern here.) Given this, we can focus on truthful
mechanisms in the rest of the paper.

not care how the outcome relates to the agents’ preferences,
but rather has a fixed preference over the outcomes), and
about the net payments made by the agents, which flow to
the designer.

Definition 2. A self-interested designer has an objective
N
function given by g(o) + πi, where g : O → R indicates
i=1
the designer’s own preference over the outcomes, and πi is
the payment made by agent i. In the case where g = 0
everywhere, the designer is said to be payment maximizing.
In the case where payments are not possible, g constitutes
the objective function by itself.

We now define the kinds of mechanisms under study. By
the revelation principle, we can restrict attention to truth-
ful, direct revelation mechanisms, where agents report their
types directly and never have an incentive to misreport them.

Definition 3. We consider the following kinds of mech-
anism:
• A deterministic mechanism without payments consists
of an outcome selection function o : Θ1 × Θ2 × . . . ×
ΘN → O.
• A randomized mechanism without payments consists
of a distribution selection function p : Θ1 × Θ2 × . . . ×
ΘN → P(O), where P(O) is the set of probability dis-
tributions over O.
• A deterministic mechanism with payments consists of
an outcome selection function o : Θ1 ×Θ2 ×. . .×ΘN →

3.

DEFINITIONS

O and for each agent i, a payment selection function
πi : Θ1 × Θ2 × . . . × ΘN → R, where πi(θ1, . . . , θN )

We now formalize the automated mechanism design set-
ting.

Definition 1. In an automated mechanism design set-

gives the payment made by agent i when the reported
types are θ1, . . . , θN .

ting, we are given:

1

Though this follows standard game theory notation [16],

• a finite set of outcomes O;
• a finite set of N agents;
• for each agent i,
1. a finite set of types Θi,

the fact that the agent has both a utility function and a type
is perhaps confusing. The types encode the various possible
preferences that the agent may turn out to have, and the
agent’s type is not known to the aggregator. The utility
function is common knowledge, but because the agent’s type
is a parameter in the agent’s utility function, the aggregator
cannot know what the agent’s utility is without knowing the
agent’s type.

山鹰

顶一下，，，，

laogui8905892

好！太讲究了。

lixu1302587946

撒花撒花撒花~~太棒了~~~楼主.....我顶你。就是不能复制~~~有点郁闷~~

whw1374

dfgfghghrtyrtutyidtytyu

jinhui

有难度啊。。。

fys

中文呢？表示看不懂啊啊啊啊啊啊

XKD302

收下了，不错