Algorithmic Game Theory and Applications
Lecture 19:
Auctions and Mechanism Design III: Matching Markets, unit-demand auctions, and VCG; and a Formal Framework of Mechanism Design
Copyright By PowCoder代写 加微信 powcoder
Matching markets: multi-item unit-demand auctions
(Now start thinking of, e.g., Google’s Sponsored Search Auctions.)
A set B of n bidders (Advertisers);
A set Q, of k items (Advertisement slots on your Google page).
Each bidder wants to buy at most one item (at most one ad on a web page),
i.e., each bidder has unit demand.
Each bidder i ∈ B has a valuation, vi,j ≥ 0, for each item j.
Each item j has a reserve price, rj ≥ 0, below which it won’t be sold.
A (feasible) price vector is any vector p ≥ r.
At prices p, the demand set of bidder i is
Di(p):={j ∈Q |vi,j −pj =maxj′∈Q(vi,j′ −pj′)≥0}.
The payoff (utility), ui , to a bidder i who gets item j and pays pj is ui = vi,j − pj. (And ui = 0 if bidder i gets nothing.)
() Lecture 19 2 / 20
Market equilibrium in matching markets
A partial matching, μ, is a partial one-to-one function from B to Q. A price vector p, together with a partial matching μ, is called a
Market price equilibrium, (p, μ), if:
For all matched i ∈ B, μ(i) ∈ Di(p).
If i ∈ B is unmatched in μ, then either Di (p) = ∅ or for all j ∈ Di (p), vi,j −pj =0.
For any unmatched item j ̸∈ μ(B), pj = rj.
Theorem ([Shapley-Shubik,1971])
1 A market equilibrium always exists.
2 The set P of market equilibrium price vectors p form a lattice in Rk≥0.
The least element of this price lattice has very special properties.
(For maximizing revenue, sellers would prefer the greatest element, but…)
() Lecture 19 3 / 20
Computing market equilibrium: an ascending price auction
[Demange-Gale-Sotomayor,1986]
1 Assume (only for simplicity) that valuations vi,j are all integers.
2 Set the initial price vector, p0, to the reserve prices, p0 := r.
3 At round t, when current prices are pt, each bidder i declares their demand set, Di(pt).
4 Does there exist an overdemanded set of items, S ⊆ Q, i.e., where 0<|S|<|{i∈B|∅≠ Di(pt)⊆S}|?Ifnot,STOP:ByHall’s theorem, a market equilibrium at prices pt exists (and a corresponding matching can be found by maximum matching).
5 If so, find a minimal over-demanded set S; ∀ j ∈ S let pt+1 := pt + 1; jj
∀k∈Q\S,letpt+1 :=pt;lett:=t+1;gotostep3. kk
Theorem ([DGS’86])
This auction algorithm always finds a market equilibrium. Moreover, the
equilibrium it finds is the least price equilibrium.
() Lecture 19 4 / 20
Some algorithmic considerations
Can we compute this auction outcome efficiently? Yes. We can compute (minimal) over-demanded sets in P-time.
We don’t need to increment prices by 1 in each iteration.
(We can raise all prices in the over-demanded set until the demand set of one of the respective bidders enlarges beyond S.)
It turns out that this is essentially isomorphic to the Primal-Dual Hungarian Algorithm for finding a maximum-weight matching in a weighted bipartite graph [Kuhn’55], which runs in P-time.
() Lecture 19 5 / 20
More lovely facts about this lovely auction
As we said, the DGS auction always computes the minimum price equilibrium, p∗.
In fact, it turns out that the payments, p∗, are precisely the VCG payments!
Therefore, the mechanism is incentive compatible, and for every bidder it is a dominant strategy to specify its true valuations.
Moreover, this mechanism is even group strategy-proof, meaning that no strict subset of bidders who can collude have an incentive to misrepresent their true valuations.
() Lecture 19 6 / 20
Generalized Second Price (GSP) auctions
The GSP auction looks somewhat similar to Vickrey’s second-price auction.
1 Assume there are k advertisement slots on the web page.
We assume there is a preference total ordering on the advertisement slots 1,...,k: all bidders prefer slot 1 to 2, slot 2 to 3, etc.
(It can be assumed (for simplicity) that associated with each slot j is a clickthrough rate, αj, and that for j < j′, we have αj ≥ αj′.)
2 Each advertiser i, chooses a single bid value, bi ∈ R≥0. (This is a bid associated with a click on their ad.)
3 The advertisers are ordered (from highest to smallest) based on their bid bi. Let b(j) denote the bid that is ranked j’th.
4 If advertiser i is ranked j < k, then it gets its ad in position j, and pays, per click, b(j+1), the bid by the advertiser in position j + 1.
5 If there are fewer bidders than slots, then the advertiser in the last position pays a reserve price r (per click).
() Lecture 19 7 / 20
What are the incentive properties of the GSP auction?
It is not quite VCG (but it is related).
Given equivalent bids by all bidders, GSP payments are at least as high (or higher) than VCG.
Truth telling is not a dominant strategy under GSP.
But ([Edelman-Ostrovsky-Schwarz’07],[Varian’07]) if bidding is modeled as a repeated game, then it is argued bids will eventually reach an locally envy-free equilibrium. Such equilibria of the GSP auction map directly to market equilibria of a matching market.
Thus, we again have a lattice structure to price equilibria, and there is a minimum equilibrium in which payoffs correspond precisely to VCG. (But it is not a dominant strategy of GSP, just one equilibrium.)
If we end up at any other equilibrium, the revenue of the seller is higher than VCG. (Not bad for Google.)
() Lecture 19 8 / 20
Complications: budget limits
In actual GSP ad auctions, bidders are asked to submit not just a value bid saying how much they value a clickthrough, but also a budget limit, which specifies the maximum they are willing to actually pay (which may be strictly less).
This creates a discontinuity in the player’s utility function, and in fact (in degenerate cases), market equilibria need not exist.
However, when bids and budgets satisfy certain basic non-degeneracy conditions: (1) market equilibria do exist, (2) the DGS auction algorithm works, and finds incentive compatible prices and allocations.
() Lecture 19 9 / 20
A formal framework for mechanism design
Formally, the input to a mechanism design problem can be specified by giving three things:
An environment, E, in which the game designer operates.
A choice function, f , which describes the designer’s preferred
outcomes in the given environment.
A solution concept, Sol, which describes the kinds of strategy profiles of games (such as their (Bayes) ) which will be considered “solutions” in which the desired choice function should be implemented.
We describe each of these three inputs separately, using single-item auctions as a running example to illustrate each concept.
Once this is done, we will be able to state the mechanism design problem more formally.
() Lecture 19 10 / 20
environments
An environment, E = (N,C,Θ,u,p,M), consists of: A set N = {1,...,n} of players.
A set C of “outcomes”.
auction example: C = {(i, pr) ∈ N × R≥0}, where outcome (i, pr) means player i wins and pays pr.
A cartesian product Θ = Θ1 ×Θ2 ×...×Θn, of types where each Θi is a set of possible types for player i.
We assume that the type θi ∈ Θi of player i determines its “utility
function” over outcomes. So, we have ui : Θi × C → R.
auction example: ′ 0 if i ̸= i′ ui(vi,(i,pr))= vi−pr ifi=i′
Note: the “type”, vi , of player i determines its utility function, ui .
p : Θ → [0, 1] is a common prior joint distribution on types of players. M is a set of “Mechanisms”... Question: What is a Mechanism?
() Lecture 19 11 / 20
What is a Mechanism?
Each Mechanism, M ∈ M, has the form M = (A1,...,An,g), where Ai isasetofactionsforplayeri,andg:A1×...×An→C,isa outcome function from strategy profiles to outcomes.
auction example: the action sets Ai are the possible bids that each player i could bid, and g gives a function that maps a profile of bids to an “outcome” of who wins the item and at what price. Such outcome functions can be constrained by the definition of the set M. For example, we may only allow top bidders to get the item, and we may ask for at most the maximum bid price to be paid by whoever gets the item.
Note that a mechanism M = (A1,...,An,g) ∈ M together with an environment E, gives a full description of a (Bayesian) game,
ΓM,E =(N,A,u ̃,Θ,p),wherethepayofffunctionu ̃i :A×Θi →Rfor player i is now given by: u ̃i(a1,...,an,θi) := ui(g(a1,...,an),θi).
Note: A (pure) strategy for player i in this Bayesian setting is a function
si : Θi → Ai , i.e., a function from its types to its actions.
() Lecture 19 12 / 20
choice functions
Given an environment E, a choice function f :Θ→2C
specifies what set of outcomes the designer would prefer if it knew exactly what type (i.e., what utility (payoff) function) each player has.
single-item auction example: the choice function of the designer could be, e.g., to give the item to a person who values it most:
f(v1,...,vn) = {(i,pr) | i ∈ argmaxvi′} i′
() Lecture 19 13 / 20
solution concepts
We lastly need the notion of a solution concept, which specifies what kind of solutions of a game we are trying to implement the choice function in. Such solutions might be, e.g., (Bayes) , or more strong conditions such as a Dominant Strategies Equilibrium.
Given an environment E, a solution concept is given by a mapping Sol, whose domain is M × Θ, and such that for each mechanism
M = (A1,...,An,g) and each tuple θ = (θ1,...,θn) of types, Sol((A1,...,An,g),θ) ∈ 2S, where S = S1 ×...×Sn, and where
Si ={si :Θi →Ai}isthestrategysetofplayeri.
auction example: in the auction example we may wish to implement the choice in dominant strategies. In this setting, we ask that Sol(M,θ) be the set of strategy combinations (s1, . . . , sn) such that each si : Θi → Ai is a dominant strategy for player i in the (Bayesian) game ΓM,E.
() Lecture 19 14 / 20
finally: the mechanism design problem statement
The mechanism design problem can now be stated as follows:
Given environment E = (N,C,Θ,u,p,M), a choice function f, and a solution concept Sol, find a mechanism
M = (A1,...,An,g) ∈ M such that for all tuples θ ∈ Θ of types, Sol(M, θ) is a non-empty set, and for all s ∈ Sol(M, θ), g(s(θ)) ∈ f (θ).
If such a mechanism M exists, we say M Sol-implements choice function f in environment E. We then also say f is Sol-implementable in E.
of mechanism design. See books [Mas-Colell-Whinston-Green’95,Osborne-Rubinstein’94].
Note: As already indicated by the Gibbard-Satterthwaite Theorem, in some environments, some social choice functions, such as truth revelation, are not (dominant-strategy)-implementable.
A result that is at first surprising, called the “Revelation Principle”, says that everything that is dominant-strategy implementable can in fact be
implemented as a truth revelation dominant strategy.
() Lecture 19 15 / 20
The Revelation Principle
Let Dom be the solution concept where s = (s1, . . . , sn) ∈ Dom(M, θ) if and only if for every player i, si : θi → Ai is a dominant strategy in ΓM,E. Such a profile s is called a dominant strategy equilibrium (DSE) of ΓM,E. Similarly, define BNE to be the solution concept where s ∈ BNE(M,θ) iff s is a Bayesian Nash Equilibrium of ΓM,E.
In environment E = (N,C,Θ,u,p,M), a mechanism M is called a direct revelation mechanism if M = (Θ1,...,Θn,g). I.e., players’ strategies
si : Θi → Θi amount to “announcing” their type. Players can lie, but.....
Theorem (Revelation Principle)
Suppose f is Dom-implemented (BNE-implemented, respectively) by
M = (A1,...,An,g) in environment E = (N,C,Θ,u,p,M).
Then in environment (N,C,Θ,u,p,M′), where M′ consists of all direct revelation mechanisms, there is some M′ = (Θ1,...,Θn,g′) ∈ M′ such that for all θ ∈ Θ, s∗ ∈ Dom(M′, θ) (respectively s∗ ∈ BNE(M′, θ)), where si∗(θi) = θi for all i. And, ∃s ∈ Dom(M,θ), (∃s ∈ BNE(M,θ), respectively), such that ∀θ ∈ Θ, g′(s∗(θ)) = g(s(θ)) ∈ f (θ).
() Lecture 19 16 / 20
interpreting the revelation principle
The revelation principle (RP), for now restricted to the dominant-strategy case, says that if a mechanism M Dom-implements a choice function f then there is another mechanism M′ which Dom-implements f , where each player revealing their true type is a DSE in ΓM′,E. We then say M′ truthfully Dom-implements f .
(An analogous version can be stated for implementation in BNE.)
Note the contrast to the Gibbard-Satterthwaite Theorem, which says that there is no non-dictatorial social choice function for player’s preferences among 3 or more alternatives for which “truth revealing” is implementable by dominant strategies.
() Lecture 19 17 / 20
proof of the revelation principle
Let’s prove it in the case of dominant strategy implementation.
Suppose that some indirect mechanism M = (A1,...,An,g), Dom-implements f .
Suppose s′ = (s1′ , . . . , sn′ ) is a dominant strategy profile in the game ΓM,E , where si′ : Θi → Ai .
In other words, each player i will prefer to play si′(θi) if his type is θi, regardless of what the other strategies s−i of other players are.
Now we create a direct revelation mechanism M′ = (Θ1,...,Θn,g′) by using a mediator.
The mediator says to each player i: “If you tell me your type, and if you say your type is θi then I will play strategy si′(θi) for you.”
Clearly, since si′ was dominant for M, telling the truth, θi, will be dominant for the new direct revelation mechanism M′, and it will implement the same choice function f .
() Lecture 19 18 / 20
In the Algorithmic Mechanism Design problem, we will additionally want to insist that functions like the outcome function g : A1 × . . . × An → C of the mechanism M = (A1,...,An,g) that implements f should be efficiently computable; but importantly, it is often necessary to adjust the choice function f to allow more outcomes (e.g., not necessarily optimal outcomes, but perhaps only approximately optimal ones), in order to allow efficient computability (and maintain implementability).
() Lecture 19 19 / 20
(hope you enjoyed the course)
() Lecture 19 20 / 20
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com