CS代考 Algorithmic Game Theory and Applications

Algorithmic Game Theory and Applications
Lecture 17:
A first look at Auctions and Mechanism Design: Auctions as Games, Bayesian Games, Vickrey auctions

Copyright By PowCoder代写 加微信 powcoder

Food for thought: sponsored search auctions
How should advertisement slots on your Google search page be auctioned? You may have already heard that Google uses a so-called
“Generalized Second Price Auction” mechanism to do this.
But why do they do so? Is there any “better” way?
What does “better” actually mean? What is the goal of the auctioneer? How should other (electronic) auctions be conducted?
More generally, how should we design games when our goal is to compel selfish players to behave in a desired way (e.g., a “socially optimal” way, or “truthfully”). This is the topic of Mechanism Design.
Auction theory and Mechanism Design are rich and vast subdisciplines of game/economic theory. We can not do them adequate justice. We briefly explore them in remaining lectures, focusing on algorithmic aspects. Some reference reading: Chapters 9, 11, 12, 13, & 28 of AGT book.
Lecture 17 2 / 10

Auctions as games
Consider one formulation of a single-item, sealed-bid, auction as a game:
Each of n bidders is a player.
Each player i has a valuation, vi ∈ R, for the item being auctioned.
if the outcome is: player i wins the item and pays price pr, then the payoff to player i, is
ui(outcome):=vi −pr
and all other players j ̸= i get payoff 0: uj (outcome) := 0.
Let us require that the auctioneer must set up the rules of the auction so that they satisfy the following reasonable constraints: given (sealed) bids (b1 , . . . , bn ), one of the highest bidders must win, and must pay a price pr such that 0 ≤ pr ≤ maxi bi .
Question: What rule should the auctioneer employ, so that for each player i , bidding their “true valuation” vi (i.e., letting bi := vi ) is a dominant strategy?
Lecture 17 3 / 10

Vickrey auctions
In a Vickrey auction, a.k.a., second-price, sealed bid auction, a highest bidder, j , whose bid is bj = maxi bi , gets the item, but pays the second highest bid price: pr = maxi ̸=j bi .
Bidding their true valuation, vi , i.e., letting bi := vi , is a (weakly) dominant strategy in this game for all players i.
Let us prove this on the board. (We actually prove something stronger.)
Note: there is something very fishy/unsatisfactory about our formulation so far of an auction as a complete information game: player i normally does not know the valuation vj of other players j ̸= i. But if viewed as a complete information game, then every player knows every one else’s valuation. This is totally unrealistic!
We need a better game-theoretic model for settings like auctions.
Lecture 17 4 / 10

Bayesian Games (Games of Incomplete Information) [Harsanyi,’67,’68] A Bayesian Game, G = (N, (Ai)i∈N, (Ti)i∈N, (ui)i∈N, p), has:
A (finite) set N = {1,…,n} of players.
A (finite1) set Ai of actions for each player i ∈ N.
A (finite1) set of possible types, Ti, for each player i ∈ N. A payoff (utility) function, for each player i ∈ N:
ui :A1 ×…×An ×T1 ×…×Tn →R A (joint) probability distribution over types:
p : T1 × . . . × Tn → [0, 1] where, letting T = T1 × . . . × Tn, we must have:
p(t1,…,tn) = 1 (t1 ,…,tn )∈T
p is sometimes called a common prior.
1We can and do often remove the finiteness assumption on the type/action spaces, e.g., letting Ti be a closed interval [a, b] ⊆ R.
Lecture 17 5 / 10

strategies and expected payoffs in Bayesian games
A pure strategy for player i is a function si : Ti → Ai .
I.e., player i knows its own type, ti , and chooses action si (ti ) ∈ Ai . (In a mixed strategy, xi , xi (ti ) is a probability distribution over Ai .)
Players’ types are chosen randomly according to (joint) distribution p. Player i knows ti ∈ Ti, but doesn’t know the type tj of players j ̸= i.
But every player “knows” the joint distribution p (this is often too strong an assumption, dubiously so, but it is useful), so each player i can compute the conditional probabilities, p(t−i | ti ), on other player’s types, given its own type ti .
The expected payoff to player i, under the pure profile
s = (s1,…,sn), when player i has type ti (which it knows) is:
Ui(s,ti) = 􏰄p(t−i | ti)ui(s1(t1),…,sn(tn),ti,t−i) t−i

Lecture 17

Bayesian Nash Equilibrium Definition
A strategy profile s = (s1, . . . , sn) is a (pure) Bayesian Nash equilibrium (BNE) if for all players i and all types ti ∈ Ti , and all strategies si′ for player i, we have: Ui(s,ti) ≥ Ui((si′;s−i),ti).
(A mixed BNE is defined similarly, by allowing players to use mixed strategies, xi, and defining expected payoffs Ui(x,ti) accordingly.)
Proposition
Every finite Bayesian Game has a mixed strategy BNE.
Follows from Nash’s Theorem. Every finite Bayesian Games can be encoded as a finite extensive form game of imperfect information: the game tree first randomly choose a subtree labeled (t1, . . . , tn), with probabilityp(t1,…,tn). Allnodesbelongingtoplayeriindifferent subtrees labeled by the same type ti ∈ Ti are in the same information set.
Lecture 17 7 / 10

Back to Vickrey auctions
Now suppose we model a sealed-bid single-item auction using a Bayesian game, with some arbitrary prior probability distribution p(v1, . . . , vn) over valuations (suppose every vi is in some finite nonnegative range [0, vmax ]). The private information of each player i is ti := vi .
Proposition
In the Vickrey (second-price, sealed-bid) auction game, with any prior p, the truth revealing profile of bids v = (v1, . . . , vn), is a weakly dominant strategy profile.
(In fact, under suitable conditions on p, v is the unique BNE of the game.)
The exact same proof as for the complete information version of the vickrey game works to show that v is a weakly dominant strategy profile. Indeed, we didn’t use the fact that the game has complete information. We didn’t even assume the players have a common prior for this!
Lecture 17 8 / 10

What about other auctions?
In first-price, sealed-bid auctions, (maximum bidder gets the item and pays pr = maxi bi ), bidding truthfully may indeed not be a dominant strategy. E.g., if player i knows (with high probability) that its valuation vi >> vj for all j ̸= i, then i will not “waste money” and will instead bid bi << vi , since it will still get the item. What implications does this have for the expected revenue of the auction? Surprisingly, it has less than you might think: Proposition If prior p is a product of i.i.d. uniform distributions over some interval [0, vmax ], then the expected revenue of the second-price and first-price sealed-bid auctions are both the same in their (unique) symmetric BNEs. This is actually a special case of a much more general result in Mechanism Design called the Revenue Equivalence Principle. (But anyway, note that one-shot revenue maximization is not always a wise goal for an auctioneer.) Lecture 17 9 / 10 The bigger picture This was our first look at Auctions (with hints of Mechanism design), in the simple setting of a single-item, sealed-bid, auction. To delve deeper into (algorithmic aspects of) Mechanism Design and auctions, we need a deeper understanding of the “bigger picture”: Starting next time, we will step back to glimpse at where all this fits in the broader scope of Economic Theory. In particular, we will briefly discuss some social choice theory, and also Market equilibria, before returning to the important VCG mechanism, which vastly generalizes the Vickrey single-item auction. Some of the topics we will discuss are beyond the scope of this AGT course, and can be properly learned, e.g., in a good Microeconomic Theory course/text (e.g., [Mas-Colell-Whinston-Green’95]). However, I feel I would be “cheating you” if I didn’t at least provide some (necessarily impressionistic) sense of the “bigger picture”. Lecture 17 10 / 10 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com