On Dominant StrategyMechanisms–1–UniversiteitMaastrichtTruthful Mechanisms and Shortest PathsRudolf M¨ullerUniversiteit MaastrichtThe Netherlandsjoined work with Hongwei Gui and Rakesh V. VohraKellog School of Management, Northwestern UniversityGuest LectureFoundations of Electronic MarketplacesSeptember 22, 2005On Dominant StrategyMechanisms–2–UniversiteitMaastrichtMotivation• Given a decision problem (e.g., a combinatorial optimizationproblem)• Input: split among different agents, private information.• Output: computed by a center on basis of input reports.• Assumption: agents vary in their valuations over the chosen out-put.• Incentives to manipulate: report of wrong input might give fa-vored decision.• Question: can we introduce (side-)payments that depend on agentreports which give incentives to tell the truth?On Dominant StrategyMechanisms–3–UniversiteitMaastrichtExample: Minimum Spanning Tree• Setting: every agent owns one edge in a graph, no agent owns acut, edge lengths are private information.• Valuation: if edge is chosen, cost to operate it is equal to thelength.• Input: every agent reports his edge length.• Output: center chooses a minimum spanning tree based on thesereports, pays cost of chosen edges.• Incentivesto manipulate: higher reports increase revenue, whilethere might be still a chance to be in the minimum spanning tree.• Question: which payment should be made in order to makeagents tell the truth?On Dominant StrategyMechanisms–4–UniversiteitMaastrichtExample II: Sealed bid, single item auction• Setting: 1 item, n bidders, we want to reward the item to thebidder who values it most.• Valuation: each bidder has a private value for the item.• Input: maximum price each bidder is willing to pay.• Output: the winner of the auction, and a price he has to pay.• Incentives to manipulate: lower reports might still win, but re-sult in a lower price.• Question: which payment gives incentives to tell the truth?• Vickrey (1961): if the payment is equal to the highest loosingbid, then every bidder cannot do better than reporting his valua-tion.On Dominant StrategyMechanisms–5–UniversiteitMaastrichtMechanism Design SettingN = {1, . . . , n} set of agents.Tiset of types, ti∈ Titype of agent i, T = ×i∈NTiY set of outcomes (output)vi: Y × Ti→ R valuation of agent i for outcome y if of type ti.Notation: vi(y|ti).A social choice function: f : T → Y.A payment function: p : T → Rn.We assume (quasi-linear) utilities: agent i, if of type ti, values out-come y and payment pi:ui: Y × R × Ti→ Rui(y, pi|ti) = vi(y|ti) − piOn Dominant StrategyMechanisms–6–UniversiteitMaastrichtExample: Minimum Spanning TreeEvery agent in N = {1, . . . , n} owns an edge ei.Ti= [0, ∞) represents costs ciof operating edge eiY set of spanning treesvi(y|ci) =½−ciif ei∈ y0 elseSocial choice function: any algorithm that computes a spanningtree.A payment function: p : T → Rnrewards agents in the spanningtree.On Dominant StrategyMechanisms–7–UniversiteitMaastrichtMechanism Design Setting (II)Definition. (f, p) is dominant strategy incentive compatible if andonly if for all i, for all si, ti∈ Ti, for all t−i∈ T−i:vi(f(ti, t−i)|ti) − p(ti, t−i) ≥ vi(f(si, t−i)|ti) − p(si, t−i)Definition. f is dominant strategy incentive compatible (or imple-mentable) if and only if there exists a payment function p such that(f, p) is dominant strategy incentive compatible.Example: Choose a weight wyfor every y ∈ Γ, and a multiplier qifor every agent, then the weighted utilitarian social choice functionf(t) ∈ argmax{wy+nXi=1qivi(y|ti) | y ∈ Y }is dominant strategy incentive compatible (Vickrey (1961), Clarke(1970), Groves (1971), Roberts (1979)).On Dominant StrategyMechanisms–8–UniversiteitMaastrichtExample: VCG payment for minimum spanning treeChoose allocation rule min total cost (= max -(total cost)) and definepi(ci) = ci(yopt) + (c−i(yopt−i) − c(yopt))Interpretation: Add to declared cost the marginal increase of thecost of a minimum spanning tree if bidder i would not be present.Let y0be the solution chosen if bidder i reports c0irather than histrue type ci, and p0the payment.Note that:ui(y0, p0|ci) = −ci(y0) + (c0i(y0) + (c0−i(yopt−i) − c0(y0)))= c−i(yopt−i) − c(y0)≤ c−i(yopt−i) − c(yopt)= −ci(yopt) + (ci(yopt) + (c−i(yopt−i) − c(yopt)))= ui(yopt, p|ci)On Dominant StrategyMechanisms–9–UniversiteitMaastrichtMechanism Design Setting (III)Problems:• In many settings (e.g., combinatorial auctions) computing theweighted utilitarian s.c.f. is NP-complete or reporting the typesrequires exponential communication.• Sometimes the utilitarian s.c.f. is not in the interest of the center(e.g., task scheduling (Nisan and Ronen, 2001)).• Sometimes the center might want to modify the utilitarian so-cial choice function in order to increase revenue (e.g., optimalauctions).• Very little is known about implementable social choice functions(i.e., algorithms) for multi-dimensional type spaces.On Dominant StrategyMechanisms–10–UniversiteitMaastrichtThis presentation• Given type spaces Ti⊆ Rk, outcomes Y , valuations vi(y|ti)• Characterizef : ×i∈NTi→ Ythat are dominant strategy incentive compatible.• Approach: a construction of payments or a prove that no pay-ments exist.• Based on relation between shortest paths and negative cycles.On Dominant StrategyMechanisms–11–UniversiteitMaastrichtOutline• Introduction to Mechanism Design• Projection to the single-agent case• Allocation graphs• Necessary condition: no negative 2-cycles• Environments in which no negative 2-cycles is sufficient:– Combinatorial auctions with bounded type domains– Multi-item auctions with decreasing marginal utilitiesOn Dominant StrategyMechanisms–12–UniversiteitMaastrichtProjection to the single-agent caseGiven N, T , v, f, p.Fix agent i, and report of the other agents t−i.Define:fi(ti) = f (ti, t−i)pi(ti) = (p(ti, t−i))iFor simplicity we drop the dependence on t−iin our notation.Lemma f is dominant strategy incentive compatible if and only iffor all i ∈ N and t−i∈ T−i, fiis dominant strategy incentivecompatible (or rationalizable).On Dominant StrategyMechanisms–13–UniversiteitMaastrichtAllocation GraphFrom now on: fix i, t−i, drop i in the notation: f = fi.Define an (infinite) digraph G = (T, A), arc lengthsl(s, t) = v(f (t)|t) −