Avrim Blum 15-451/651 Algorithms 11/26/13 Mechanism design (aka incentive-aware algorithms) (aka "inverse game theory") * How to give away a printer * The Vickrey Auction * Social Welfare, incentive-compatibility * The VCG (Vickrey-Clarke-Groves) mechanism =========================================================================== Today we're going to talk about an area called "mechanism design", also sometimes called "incentive-aware algorithms" or "inverse game theory". But rather than start with the big picture, let's start with an example. How to give away a printer? =========================== Say the department has spare printer, and wants to give to whoever can make the most use of it. To make this formal, let's say there are n people, and assume each person i has some value v_i >= 0 (called their "private value") on getting the printer, and 0 on not getting it. We'll assume everyone knows their own v_i. What we want to do is to give the printer to the person with the highest v_i. So, one option is we ask each person for their own v_i and we then compute the argmax (the i for which v_i is maximum). Can anyone see any potential problems with this? The problem is people might lie ("mis-report" is the formal term) because they want the printer. So, let's assume one more thing, which is that we have (the department has) the ability to charge people money, and that the utility of person i for getting item and paying $p is v_i - p. (Definition of "utility" is: the thing that people/players want to maximize. If there are probabilities, then we assume they want to maximize expected utility. But everything today will be deterministic.) To be clear: while we are giving the department the ability to charge money, it's goal isn't to make money but just to use this to help in getting the printer to the right person. What about asking people how much they would pay (ask each person i to write down a bid b_i) and then give the printer to the person who bids the highest, charging them that amount. Any potential problems with this? Here is something interesting called a Vickrey auction: Vickrey auction =============== - ask everyone each person i to report the value of the printer to them (let's call this their "bid" b_i). - give to i = argmax_j b_j. (the person of highest reported value). - charge that person the *second-highest* bid. Claim: Vickrey is "dominant-strategy truthful" aka "incentive-compatible". Specifically, for any player i, for any vector of bids of the other players (call this b_{-i}), we have: u_i(Vickrey(v_i,b_{-i})) >= u_i(Vickrey(v_i',b_{-i})) [Notation: given a vector v, will write v_{-i} as the vector removing the ith component, and "(x,v_{-i})" as the vector v with the ith component replaced by x.] In other words: even if you knew what all the other bids were, and got to choose what to bid based on those, you would still be best off (have highest utility) bidding your true value on the printer. Proof: Can anyone see why? Proof: Consider player i and let p be the highest bid among everyone else. Case 1: v_i > p. In this case, if player i announces truthfully then it gets the item and pays p and has positive utility. Any other v_i' either will produce the same outcome or will result in someone else getting the item, for a utility of 0. Case 2: v_i = p. Then doesn't matter. Utility=0 no matter what. Case 3: v_i < p. In this case, announcing truthfully, player i doesn't get the item and has utility 0. Any other v_i' will either have the same outcome or else (if v_i'>p) will give him the item at a cost of p, yielding negative utility. Another way to think of it: Vickrey is like a system that bids for you, up to a maximum bid of whatever you tell it, in an ascending auction where prices go up by tiny epsilons. Initially everyone is in the game and then they drop out as their maximum bids are reached. In this game, you would want to give v_i as your maximum bid (there is no advantage to dropping out early, and no reason to continue past v_i). So, Vickrey is incentive-compatible and (assuming everyone bids their valuations, which they should because of IC) gets the printer to the person of highest value. What about two printers? ======================= What if the dept has two printers? - Could do one Vickrey auction after another. Equivalently, take in the bids, give to the highest bidder at a price equal to the 2nd-highest bid, and give to 2nd-highest bidder at a price equal to the 3rd highest bid. Does this work (is it incentive-compatible)? Why not? - How about giving the printers to the top 2 bidders at the 3rd-highest price? Does this work? Yes! Why? If you don't get a printer, would you regret your decision and want to raise your bid? No. If you do get a printer, you have no way of lowering the price you paid, and are happier than (at least as happy as) if you lowered your bid below the 3rd highest and didn't get the printer. Def: the *social welfare* of an outcome is the sum of valuations v_i on the outcome that occurs. (Or you can think of as the sum of utilities, if you also put the utility of the "center" into the picture ("center" = the department, in this case) so the money cancels out). Then what we showed is that the above procedure (a) is incentive-compatible and (b) maximizes social welfare if everyone bids truthfully (which they might as well do, by (a)). BTW, in economics, they say a procedure is "efficient" if it maximizes social welfare, but we won't use that terminology here for obvious reasons... So, you can think of this as "inverse game theory" because we are designing the rules of the game so that if people act in their own interest, an outcome that we want will occur. More general scenarios ====================== What if the department has two printers but one is nicer than the other? Or maybe some things that go together (like pairs of shoes, where it would be weird to bid on an individual shoe) or dorm rooms where you might care not only about the room you get but maybe you also would prefer a room near to someone else in the same classes you could study with? The amazing thing is the Vickrey auction can be generalized to essentially any setting where you have payments and the players have what are called "quasi-linear utilities". This will be the Vickrey-Clarke-Groves, or VCG, mechanism. Let's now define the general setup formally. The formal setup ================ We have n players and a set of alternatives A (will also call them "outcomes" or "allocations"), such as who gets the printers or what the assignment of students to dorm rooms is. Can be arbitrarily complicated (we're not going to be worried about running time here). Each player i has a valuation *function* v_i:A -> Reals. We assume *quasi-linear utilities*: Utility for alternative a in A and paying a payment p is v_i(a)-p. It's called "quasi-linear" because it is linear in money, even if it might be some weird function over the alternatives. E.g., if we have multiple items we are allocating, the utility does not have to be additive over the items you get (maybe you need several together to build a product or maybe two printers isn't much better than one, and it even can depend on what other people get!) but you are assumed to be linear in money. A "direct revelation mechanism" is a function that takes in a sequence v = (v_1,...,v_n) of valuation functions, and selects an alternative a in A, along with a vector p of payments. Will be convenient to split into two functions: f(v)=a and p(v) = vector of payments. Will use p_i(v) to denote payment of player i. A mechanism (f,p) is *incentive-compatible* if for every v = (v_1,...,v_n), every i, every v_i', then: v_i(f(v)) - p_i(v) >= v_i(f(v_i', v_{-i})) - p_i(v_i',v_{-i}). I.e., misreporting can never help. Here is the amazing thing: there exists a mechanism, called VCG, that in this very general setting is both (a) incentive compatible and (b) produces the alternative/allocation maximizing social welfare if everyone reports truthfully (which they should, due to (a)). Basic idea: design payments so that everyone wants to optimize what we want to optimize, namely social welfare. A couple versions. Start with the simplest to analyze: VCG version 1 ============= Given vector of reported valuation functions v, * let f(v) be the allocation that maximizes social welfare wrt v. I.e., f(v)= argmax_{a in A} sum_j v_j(a). * pay each player i an amount equal to the sum of everyone else's reported valuations. I.e., p_i(v) = - sum_{j != i} v_j(f(v)). Suppose player i reports truthfully. Then its utility will be v_i(f(v)) + sum_{j != i} v_j(f(v)) = max_a sum_j v_j(a) (by the definition of f(v)) = max social welfare if everyone reported truthfully. Suppose instead player i reports v_i'. Call the resulting vector v'. Then player i's utility will be: v_i(f(v')) + sum_{j != i} v_j(f(v')) = sum_j v_j(f(v')) <= max_a sum_j v_j(a). Problems with version 1: If you think of this as an auction, a big problem is this requires the auctioneer to give money to the bidders! E.g, in the case of the printer, it corresponds to giving the top guy the printer for free, and pay everyone else the amount the top guy valued it. That way everyone gets a utility equal to what the top guy got. However, notice that if we add to each p_i(v) something that depends on v_{-i} only (and not influenced at all by v_i) then it is just a constant as far as player i is concerned and so still incentive-compatible. VCG - general version ===================== * Let h_i be any function over v_{-i} for each i=1..n. Given vector of reported valuation functions v, * let f(v) be the allocation that maximizes social welfare wrt v. I.e., f(v) = argmax_a sum_j v_j(a). * let p_i(v) = h_i(v_{-i}) - sum_{j != i} v_j(f(v)). As we just argued, this is incentive-compatible too. Now, there is a specific set of h_i's that have the nice properties that (a) the center is never paying the bidders/players, and (b) on the other hand, assuming the v_i's themselves are non-negative, no player gets negative utility -- this is called "individual rationality" (e.g., if we're allocating goods and people's valuations depend only on what they get, then among other things this implies that people who don't get anything don't have to pay anything). This set of h_i's is called the "Clarke pivot rule": h_i(v_{-i}) = max_a sum_{j !=i} v_j(a) = max_a v_{-i}(a). VCG - standard version ===================== Given vector of reported valuation functions v, * let f(v) be the allocation that maximizes social welfare wrt v. I.e., f(v) = argmax_a sum_j v_j(a). * let p_i(v) = max_a[v_{-i}(a)] - v_{-i}(f(v)) In other words, you charge each player i an amount equal to how much less happy they make everyone else. This is often called "charging them their externality". - Why does this satisfy (a) p_i(v)>=0? Ans: because 1st term is a max. - Why does this satisfy (b) individual rationality? Ans: Utility of player i = max_a[v(a)] - max_a[v_{-i}(a)]. Can't be negative since one option in the first max is to use the allocation a' from the second max. You get v_i(a') + [second term] - [second term] >=0. What does this look like for the case of the single printer? - Everyone who doesn't get the printer pays nothing (both terms are equal to the maximum guy's value) - The person who gets the printer pays the second-highest valuation (since the sum of everyone else's valuations went from the second-highest valuation down to zero.) So it reduces to the Vickrey auction in that case.