Chapter 4Mechanism DesignHonesty is the best policy - when there is money in it.Mark TwainIn order for a preference aggregator to choose a good outcome, she needs to be provided with theagents’ (relevant) preferences. Usually, the only way of learning these preferences is by having theagents report them. Unfortunately, in settings where the agents are self-interested, they will reportthese preferences truthfully if and only if it is in their best interest to do so. Thus, the preferenceaggregator has the difficult task of not only choosing good outcomes for the given preferences, butalso choosing outcomes in such a way that agents will not have any incentive to misreport theirpreferences. This is the topic of mechanism design, and the resulting outcome selection functionsare called mechanisms.This chapter gives an introduction to some basic concepts and results in mechanism design.In Section 4.1, we review basic concepts in mechanism design (although discussions of the game-theoretic justifications for this particular framework, in particular the revelation principle, will bepostponed to Chapter 7). In Section 4.2, we review the famous and widely-studied Vickrey-Clarke-Groves mechanisms and their properties. In Section 4.3, we briefly review some other positiveresults (mechanisms that achieve particular properties), while in Section 4.4, we briefly reviewsome key impossibility results (combinations of properties that no mechanism can achieve).4.1 Basic conceptsIf all of the agents’ preferences were public knowledge, there would be no need for mechanismdesign—all that would need to be done is solve the outcome optimization problem. Techniquesfrom mechanism design are useful and necessary only in settings in which agents’ have privateinformation about their preferences. Formally, we say that each agent i has a privately known typeθithat corresponds to that agent’s private information, and we denote by Θithe space of all of agenti’s possible types. In general, it is possible to have private information that has implications for howother agents value outcomes—for example, one agent may privately know that the painting that isbeing auctioned is a forgery, which would be relevant to other agents that may not know this [Itoet al., 2002, 2003, 2004]. In this dissertation, as is most commonly done in the mechanism design9596CHAPTER 4. MECHANISM DESIGNliterature, we will only consider private information about the agent’s own preferences (which is themost common type of private information). We model these preferences by saying that each agenti has a utility function ui: Θi× O → R, where ui(θi, o) gives the agent’s utility for outcome owhen the agent has type θi. The utility function uiis common knowledge, but it is still impossiblefor other agents to precisely assess agent i’s utility for a given outcome o without knowing agent i’stype. For example, in an auction for a single item, an agent’s type θicould be simply that agent’svaluation for the item. Then, the agent’s utility for an outcome in which he receives the item willbe θi(not counting any payments to be made by the agent), and the utility is 0 otherwise. Hence,the utility function is common knowledge, but one still needs to know the agent’s type to assess theagent’s utility for (some) outcomes.A direct-revelation mechanism asks each agent to report its private information, and chooses anoutcome based on this (and potentially some random bits). It will generally be convenient not toconsider payments imposed by the mechanism as part of the outcome, so that the mechanism alsoneeds to specify payments to be made by/to agents. Formally:Definition 16• A deterministic direct-revelation mechanism without payments consists of an outcome selec-tion function o : Θ1× . . . × Θn→ O.• A randomized direct-revelation mechanism without payments consists of a distribution selec-tion function p : Θ1× . . . × Θn→ ∆(O), where ∆(O) is the set of probability distributionsover O.• A deterministic direct-revelation mechanism with payments consists of an outcome selectionfunction o : Θ1× . . . × Θn→ O and for each agent i, a payment selection function πi:Θ1× . . . × Θn→ R, where πi(θ1, . . . , θn) gives the payment made by agent i when thereported types are θ1, . . . , θn.• A randomized direct-revelation mechanism with payments consists of a distribution selectionfunction p : Θ1× . . . × Θn→ ∆(O), and for each agent i, a payment selection functionπi: Θ1× . . . × Θn→ R.In some settings, it makes sense to think of an agent’s type θias being drawn from a (commonlyknown) prior distribution over Θi. In this case, while each agent still only knows its own type, eachagent can use the commonly known prior to make probabilistic assessments of what the others willreport.So, what makes for a good mechanism? Typically, there is an objective function that the designerwants to maximize. One common objective is social welfare (the sum of the agents’ utilities withrespect to their true, not reported, types), but there are many others—for example, the designermay wish to maximize revenue (the sum of the agents’ payments). However, there are certainconstraints on what the designer can do. For example, it would not be reasonable for the designerto specify that a losing bidder in an auction should pay the designer a large sum: if so, the bidderwould simply not participate in the auction. We next present constraints, called participation orindividual rationality (IR) constraints, that prevent this. Before we do so, we note that we willassume quasilinear preferences when payments are involved.4.1. BASIC CONCEPTS97Definition 17 An agent i has quasilinear preferences if the agent’s utility function can be written asui(θi, o) − πi.We are now ready to present the IR constraints.Definition 18 Individual rationality (IR) is defined as follows.• A deterministic mechanism is ex post IR if for any agent i, and any type vector (θ1, . . . , θn) ∈Θ1× . . . × Θn, we have ui(θi, o(θ1, . . . , θn)) − πi(θ1, . . . , θn) ≥ 0.A randomized mechanism is ex post IR if for any agent i, and any type vector (θ1, . . . , θn) ∈Θ1× . . . × Θn, we have Eo|θ1,..,θn[ui(θi, o) − πi(θ1, .., θn)] ≥ 0.• A deterministic mechanism is ex interim IR if for any agent i, and any type θi∈ Θi, we haveE(θ1,..,θi−1,θi+1,..,θn)|θi[ui(θi, o(θ1, .., θn))
View Full Document
Unlocking...