Myerson's Lemma in Algorithmic Game Theory
COMP/MATH 553 Algorithmic
COMP/MATH 553 Algorithmic
Game Theory
Game Theory
Lecture 3: Myerson’s Lemma
Lecture 3: Myerson’s Lemma
Yang
Yang
Cai
Cai
Sep 10,
2014
An overview of today’s class
An overview of today’s class
Case Study: Sponsored Search Auction
Myerson’s Lemma
Back to Sponsored Search Auction
Case
Study:
Sponsored
Search
Auction
Sponsored Search Auction
k
slots for sale.
Slot
j
has click
-through-rate (CTR)
α
j
.
Bidder
i
’s value for slot
j
is
α
j
v
i
.
Sponsored Search
Auctions: Set-up
α
1
α
j
α
k
Sponsored Search Auction: Goal
(1)
DSIC. That is, truthful bidding should be a
dominant
strategy
, and never leads to negative utility.
(2) Social welfare maximization. That is, the assignment of
bidders to slots should maximize
Σv
i
x
i
,
where
x
i
now denotes the CTR of the slot to which
i
is assigned (or 0 if
i
is not assigned to a slot). Each slot can only be assigned to one bidder,
and each bidder gets only one slot.
(3)
Polynomial
running time. Remember zillions of these
auctions need to be run every day!
Sponsored Search Auction
Two things to consider: who wins what
and how much to charge?
Make the “correct” choice for only the first one is
not enough, e.g. single item auction.
Tackle this one step at a time:
1)
Assume that bidders bid truthfully. Then, how should we
assign bidders to slots so that property (2) and (3) hold?
2)
How do we set prices so that truthful is a dominant
strategy?
Sponsored Search Auction
Tackle this one step at a time:
1)
Assume that bidders bid truthfully. Then, how should we
assign bidders to slots so that property (2) and (3) hold?
Greedy Alg.
✔
1)
How do we set prices so that being truthful is a dominant
strategy?
Can we run k Vickrey auctions?
Sponsored Search Auction
NO! It’s not truthful!
Example: 3 bidders 2 slots.
v
1
=7, v
2
=6
and
v
3
=1; α
1
=1
and
α
2
=0.4.
Instead of being truthful, it’s better for
bidder 1 to bid 5 and win the second slot.
Sponsored Search Auction
Tackle this one step at a time:
1)
Assume that bidders bid truthfully. Then, how should we
assign bidders to slots so that property (2) and (3) hold?
Greedy Alg.
✔
.
1)
How do we set prices so that being truthful is a dominant
strategy?
Myerson’s Lemma!
Myerson’s Lemma
Definition:
o
n
bidders
o
Each bidder
i
has a private valuation
v
i
, its value
“per unit of stuff” that she
gets.
o
A
feasible set X. Each element of X is an n-
dimensional
vector (x
1
, x
2
, . . . , x
n
), where x
i
denotes the “amount of stuff” given to bidder
i.
Single
-dimensional Environment
Single
-dimensional Environment
Examples:
o
Single-item auction:
X is the set of 0-1 vectors that have at
most one 1
o
k units of the same items for sale: each bidder wants only
one item. X is the 0-1 vectors satisfying
Σ
i
x
i
≤ k
.
o
Sponsored search auction: X is the set of n-dimensional
vectors corresponding to assignments of bidders to slots. If
bidder
i
is assigned to slot j, then the component
x
i
equals the
CTR
α
j
of its slot.
Seal
-Bid Auction in Single-dimensional Settings
Make Two choices:
•
Allocation rule
•
Payment rule
Sealed
Sealed
-Bid Auctions:
1.
Collect bids
b=
(
b
1
, ..., b
n
)
2.
[allocation rule]
Choose a feasible allocation
x(b)
in
X
as
a
function of the bids
3.
[payment rule]
Choose payments
p(b)
as
a function of the bids
.
Two important definitions
Definition 1: (Implementable Allocation Rule) An
allocation rule
x
for a
single-dimensional environment is
implementable
if there is a
payment
rule
p
such the sealed-bid auction
(x, p)
is
DSIC
.
-
Example:
The
allocation
rule
that
gives
the
item
to
the
highest
bidder
is
implementable
-
Is
the
Greedy
allocation
rule
implementable
for
Sponsored
Search
Auctions?
-
How
about
giving
the
item
to
the
second
highest
bidder?
Lowest
bidder?
Two important definitions
Definition 2: (Monotone Allocation Rule) An
allocation rule
x
for a
single-dimensional environment is
monotone
if for every bidder
i
and
bids
b
−i
by the other bidders, the allocation
x
i
(z,b
−i
)
to
i
is
nondecreasing
in its bid z.
-
Example:
The
allocation
rule
that
gives
the
item
to
the
highest
bidder
is
monotone.
-
The
Greedy
allocation
rule
for
Sponsored
Search
Auctions is monotone.
-
Giving
the
item
to
the
second
highest
bidder or the
lowest
bidder is not
monotone.
Myerson’s Lemma
[Myerson ’81 ]
Fix a single-dimensional environment.
(a)
An allocation rule x is implementable
if and only if
it is
monotone
.
(b) If x is monotone, then there is a
unique
payment rule
such that the sealed-bid mechanism (x, p) is DSIC [assuming
the normalization that b
i
= 0 implies pi(b) = 0].
(c) The payment rule in (b) is given by an explicit formula.
Myerson’s Lemma
Corollary: The greedy allocation rule for sponsored
search is
Implementable
. Thus, there is a truthful
auction that maximizes social welfare in sponsored
search.
Myerson’s Lemma
[Myerson ’81 ]
Fix a single-dimensional environment.
(a)
An allocation rule x is implementable
if and only if
it is
monotone
.
(b) If x is monotone, then there is a
unique
payment rule such that
the sealed-bid mechanism (x, p) is DSIC [assuming the normalization
that b
i
= 0 implies pi(b) = 0].
(c) The payment rule in (b) is given by an explicit formula.
Proof: See the Board.
Myerson's Lemma is a fundamental concept in algorithmic game theory, particularly in the context of Sponsored Search Auctions. This lecture delves into the application of Myerson's Lemma to ensure truthful bidding as a dominant strategy, maximize social welfare, and maintain polynomial running time in auctions. The discussion covers the goals of DSIC, social welfare maximization, and the considerations involved in assigning bidders to slots and setting prices to incentivize truthful bidding. Various scenarios and algorithms are explored to illustrate the challenges and solutions in Sponsored Search Auctions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
COMP/MATH 553 Algorithmic Game Theory Lecture 3: Myerson s Lemma Sep 10, 2014 Yang Cai
An overview of todays class Case Study: Sponsored Search Auction Myerson s Lemma Back to Sponsored Search Auction
Case Study: Sponsored Search Auction
Sponsored Search Auctions: Set-up Bidders (advertisers) Slots Auctioneer/ Google v1 1 1 1 vi i j j n vn k k k slots for sale. Slot j has click-through-rate (CTR) j. Bidder i s value for slot j is jvi.
Sponsored Search Auction: Goal (1)DSIC. That is, truthful bidding should be a dominant strategy, and never leads to negative utility. (2) Social welfare maximization. That is, the assignment of bidders to slots should maximize vixi, where xinow denotes the CTR of the slot to which i is assigned (or 0 if i is not assigned to a slot). Each slot can only be assigned to one bidder, and each bidder gets only one slot. (3) Polynomial running time. Remember zillions of these auctions need to be run every day!
Sponsored Search Auction Two things to consider: who wins what and how much to charge? Make the correct choice for only the first one is not enough, e.g. single item auction. Tackle this one step at a time: 1) Assume that bidders bid truthfully. Then, how should we assign bidders to slots so that property (2) and (3) hold? 2) How do we set prices so that truthful is a dominant strategy?
Sponsored Search Auction Tackle this one step at a time: 1) Assume that bidders bid truthfully. Then, how should we assign bidders to slots so that property (2) and (3) hold? Greedy Alg. 1) How do we set prices so that being truthful is a dominant strategy? Can we run k Vickrey auctions?
Sponsored Search Auction NO! It s not truthful! Example: 3 bidders 2 slots. v1=7, v2=6 and v3=1; 1=1 and 2=0.4. Instead of being truthful, it s better for bidder 1 to bid 5 and win the second slot.
Sponsored Search Auction Tackle this one step at a time: 1) Assume that bidders bid truthfully. Then, how should we assign bidders to slots so that property (2) and (3) hold? Greedy Alg.. 1) How do we set prices so that being truthful is a dominant strategy? Myerson s Lemma!
Single-dimensional Environment Definition: o n bidders o Each bidder i has a private valuation vi, its value per unit of stuff that she gets. o Afeasible set X. Each element of X is an n- dimensional vector (x1, x2, . . . , xn), where xi denotes the amount of stuff given to bidder i.
Single-dimensional Environment Examples: o Single-item auction: X is the set of 0-1 vectors that have at most one 1 o k units of the same items for sale: each bidder wants only one item. X is the 0-1 vectors satisfying i xi k. o Sponsored search auction: X is the set of n-dimensional vectors corresponding to assignments of bidders to slots. If bidder i is assigned to slot j, then the component xi equals the CTR j of its slot.
Seal-Bid Auction in Single-dimensional Settings Make Two choices: Allocation rule Payment rule Sealed-Bid Auctions: 1. Collect bids b=(b1 , ..., bn) 2. [allocation rule] Choose a feasible allocation x(b) in X as a function of the bids 3. [payment rule] Choose payments p(b) as a function of the bids.
Two important definitions Definition 1: (Implementable Allocation Rule) An allocation rulex for a single-dimensional environment is implementable if there is a payment rulep such the sealed-bid auction (x, p) is DSIC. - Example: The allocation rule that gives the item to the highest bidder is implementable - Is the Greedy allocation rule implementable for Sponsored SearchAuctions? - How about giving the item to the second highest bidder? Lowest bidder?
Two important definitions Definition 2: (Monotone Allocation Rule) An allocation rule xfor a single-dimensional environment is monotone if for every bidder i and bids b i by the other bidders, the allocation xi(z,b i) to i is nondecreasing in its bid z. - Example: The allocation rule that gives the item to the highest bidder is monotone. - The Greedy allocation rule for Sponsored SearchAuctions is monotone. - Giving the item to the second highest bidder or the lowest bidder is not monotone.
Myersons Lemma [Myerson 81 ] Fix a single-dimensional environment. (a) An allocation rule x is implementable if and only if it is monotone. (b) If x is monotone, then there is a unique payment rule such that the sealed-bid mechanism (x, p) is DSIC [assuming the normalization that bi = 0 implies pi(b) = 0]. bi 0 (c) The payment rule in (b) is given by an explicit formula.
Myersons Lemma Corollary: The greedy allocation rule for sponsored search is Implementable. Thus, there is a truthful auction that maximizes social welfare in sponsored search.
Myersons Lemma [Myerson 81 ] Fix a single-dimensional environment. (a) An allocation rule x is implementable if and only if it is monotone. (b) If x is monotone, then there is a unique payment rule such that the sealed-bid mechanism (x, p) is DSIC [assuming the normalization that bi = 0 implies pi(b) = 0]. (c) The payment rule in (b) is given by an explicit formula. Proof: See the Board.
