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.