Complexity of Pricing and Auctions in Economic Sciences
Noam Nisan
Complexity of Pricing
Noam Nisan
Hebrew University
Noam Nisan
C
i
r
c
a
2
0
0
4
L
e
n
s
o
f
C
o
m
p
u
t
a
t
i
o
n
o
n
t
h
e
S
c
i
e
n
c
e
s
-
-
A
w
o
r
k
s
h
o
p
o
r
g
a
n
i
z
e
d
b
y
A
v
i
W
i
g
d
e
r
s
o
n
2
0
1
4
Complexity in Economics
Noam Nisan
Complexity in Economics
C
l
a
s
s
i
c
a
l
E
c
o
n
o
m
i
c
s
E
c
o
n
o
m
i
c
s
a
n
d
C
o
m
p
u
t
a
t
i
o
n
Noam Nisan
Optimization Perspective
S
i
m
p
l
i
c
i
t
y
C
o
m
p
l
e
x
i
t
y
Noam Nisan
Ad auctions
Noam Nisan
Spectrum Auctions
Noam Nisan
Cloud Computing
Noam Nisan
Our Setting
Noam Nisan
Selling independent items
A seller has
n
items for sale.
There is a single buyer that has
private
value
v
i
for each item
i
.
T
h
e
b
u
y
e
r
’
s
v
a
l
u
e
i
s
s
i
m
p
l
y
a
d
d
i
t
i
v
e
o
v
e
r
t
h
e
i
t
e
m
s
.
T
h
e
s
e
l
l
e
r
’
s
p
a
r
t
i
a
l
k
n
o
w
l
e
d
g
e
i
s
c
a
p
t
u
r
e
d
b
y
i
n
d
e
p
e
n
d
e
n
t
p
r
i
o
r
d
i
s
t
r
i
b
u
t
i
o
n
s
F
i
o
n
v
i
.
How does the seller maximize his
(expected) revenue?
Noam Nisan
Noam Nisan
Single Item case: monopolist pricing
Buyer has value
v
distributed according to
F
.
Seller knows
F
but
not
v
and
wants to maximize expected revenue.
Sell at price
p
Revenue =
p
Pr
v~F
[v≥p]
Seller maximizes for
p
v
F
p
Noam Nisan
Single Item case: can we do better?
Is there a better way?
Interactive protocol
Randomization
…
T
h
e
o
r
e
m
(
M
y
e
r
s
o
n
)
:
N
o
.
There are other protocols
They can all be put into a clean canonical form
Offer a menu of (
Pr[win], price
)
Revenue maximizing one still uses
simple pricing
Generalizes to multiple bidders (“optimal auctions”)
v
F
…
…
Noam Nisan
Selling Two Items
One seller
One buyer
Values for the two items (
v, u)
are
(independently) distributed according to
F, G
.
Value for bundle is
additive
C
h
a
l
l
e
n
g
e
:
f
i
n
d
t
h
e
r
e
v
e
n
u
e
-
m
a
x
i
m
i
z
i
n
g
s
e
l
l
i
n
g
m
e
c
h
a
n
i
s
m
.
Surely, just sell each item optimally…
Example:
item values are IID uniformly on {1,2}Selling a single item:
optimal revenue = 1
Price=1
Pr[buy]=1
Revenue=1
Price=2
Pr[buy]=1/2
Revenue=1
Noam Nisan
Surely, just sell each item optimally…
Example:
item values are IID uniformly on {1,2}Selling a single item:
optimal revenue = 1
Price=1
Pr[buy]=1
Revenue=1
Price=2
Pr[buy]=1/2
Revenue=1
Selling both items:
you can get revenue > 2!
Price bundle at 3
Pr[buy]=3/4
Revenue = 2.25
Noam Nisan
Other Examples
IID Uniform on {0,1}Selling each item separately is better than bundling
IID uniform on {0,1,2}Buy any single item for $2 or both for $3
IID uniform on [0,1]
Manelli-Vincent 2006
Buy any single item for $X or both for $Y
Uniform on {1, 2} × uniform on {1, 3} Daskalakis-Deckelbaum-Tzamos 2014
Buy (Item 1 & 50%-lottery for item 2) for $2.5, or both (surely) for $4
Beta(3,3) × Beta(3,4)
Daskalakis-Deckelbaum-Tzamos 2013
Choose between infinitely many possible lotteries (each with its price)
Noam Nisan
Optimal Multi-item Auctions
May be complex
May be randomized
May have infinitely many outcomes
May be nonmonotone
Hart-Reny 2012
Increasing players’ values may
reduce
revenue
May be very hard (#P-hard) to compute
Daskalakis-Deckelbaum-Tzamos 2014
Noam Nisan
Drawbacks of Complex Auctions
Harder to analyze
Harder to represent
Harder to participate in
Harder to “tweak”
for
Designer
Implementer
Human participant
Computerized participant
Noam Nisan
How much do we lose if we
stick to simple auctions?
Noam Nisan
Simplicity vs Complexity
Qualitative measures:
Selling items separately vs. combinatorially
Selling full bundle vs. combinatorially
Selling packages additively vs. combinatorially
Selling deterministically vs. using lotteries
Quantitative Measures:
Number of “menu entries”
in auction
Hart-Nisan 2013
Number of “parameters” needed to “describe”
auction
Dughmi-Li-Nisan 2014, Morgenstern-Roughgarden 2015
Noam Nisan
Theorem:
Selling two items
separately always gives at least half of
the optimal revenue.
Hart-Nisan 2012
Noam Nisan
Noam Nisan
Proof Strategy: split the valuation space
v
u
v
<
u
u
<
v
•
An auction for
the
u
item
•
E[v]
is bounded
by
Rev(u)
Multiple Items
Revenue obtained by selling n items
separately may be a factor of
O(log n)
smaller than the optimal revenue, but no less.
Selling as a single bundle may be an
O(n)
factor smaller, but no less.
Hart-Nisan 2012, Li-Yao 2013
The better of selling separately and of selling
as a single bundle gives at least
1/6
of the
optimal revenue.
Babaioff-Immorlica-Lucier-Weinberg 2014
Noam Nisan
Menu-size Complexity
Canonical representation of any auction:
Noam Nisan
P
r
[
w
i
n
i
t
e
m
1
]
P
r
[
w
i
n
i
t
e
m
2
]
P
r
i
c
e
0% 0% 0$
0% 100% 3$
20% 30% 4$
40% 60% 10$
… … …
100% 100% 20$
M
e
n
u
C
o
m
p
l
e
x
i
t
y
=
N
u
m
b
e
r
o
f
e
n
t
r
i
e
s
M
e
n
u
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
1
-
O(1)
1/n
1
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
Theorem:
For every
n,
,
there exists
C=exp(n,
-1
)
such that auctions with menu size
at most
C
suffice for getting
(1-
)
fraction of
the optimal revenue in every
n
item auction
.
Babaioff-Gonczarowski-Nisan 2016
Noam Nisan
Noam Nisan
Proof Strategy: Core vs. Tails
Li-Yao
M
M
v
u
C
o
r
e
:
N
u
d
g
e
+
A
p
p
r
o
x
i
m
a
t
e
D
o
u
b
l
e
T
a
i
l
:
I
g
n
o
r
e
T
a
i
l
:
I
g
n
o
r
e
S
m
a
l
l
I
t
e
m
.
A
p
p
l
y
M
y
e
r
s
o
n
t
o
L
a
r
g
e
I
t
e
m
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
Theorem:
An auction that extracts at least
1-1/n
fraction of the optimal revenue from the
uniform distribution on
{0,1}n
requires
2
Ω
(n)
menu entries.
Babaioff-Gonczarowski-Nisan 2016
Noam Nisan
Proof Idea: limitations of single entry
Noam Nisan
M
e
n
u
E
n
t
r
y
A
l
l
o
c
a
t
e
i
t
e
m
s
S
*
f
o
r
p
r
i
c
e
p
*
Set
S
= {itemswith
value 1}
chooses this
menu entry
High revenue
p*≈ |S|
S
S*
S*
contains
many
S
S*
Contains their
Union
Low
revenue on union
How Complex Must Auctions Be?
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
The power of small menus
T
h
e
o
r
e
m
:
F
o
r
e
v
e
r
y
,
t
h
e
r
e
e
x
i
s
t
s
d
=
p
o
l
y
(
-
1
)
s
u
c
h
t
h
a
t
a
u
c
t
i
o
n
s
w
i
t
h
m
e
n
u
s
i
z
e
O
(
C
d
)
s
u
f
f
i
c
e
f
o
r
g
e
t
t
i
n
g
(
1
-
)
f
r
a
c
t
i
o
n
o
f
t
h
e
r
e
v
e
n
u
e
o
f
s
e
l
l
i
n
g
n
i
t
e
m
s
s
e
p
a
r
a
t
e
l
y
.
B
a
b
a
i
o
f
f
-
G
o
n
c
z
a
r
o
w
s
k
i
-
N
i
s
a
n
2
0
1
6
C
o
r
o
l
l
a
r
y
:
A
m
e
n
u
s
i
z
e
w
h
i
c
h
i
s
p
o
l
y
n
o
m
i
a
l
i
n
n
s
u
f
f
i
c
e
s
f
o
r
e
x
t
r
a
c
t
i
n
g
a
t
l
e
a
s
t
1
/
7
o
f
t
h
e
o
p
t
i
m
a
l
r
e
v
e
n
u
e
i
n
a
n
y
n
i
t
e
m
a
u
c
t
i
o
n
.
Babaioff-Immorlica-Lucier-Weinberg 2014
Noam Nisan
Auction with small menu-size
Item
i
is sold at price
t
i
and this happens with
probability
p
i
.
Noam Nisan
Don’t
sell
sell at
most one
of these
item
O(log n /
)
bundles
p
i
>> 1
Sell bundle
for price:
t(1-
)
p
i
p
i
<< 1
Sell
bundle for
price
t
O
r
d
e
r
i
t
e
m
s
b
y
i
n
c
r
e
a
s
i
n
g
v
a
l
u
e
o
f
t
V
e
r
y
h
i
g
h
V
e
r
y
l
o
w
Open Problem
Noam Nisan
M
e
n
u
S
i
z
e
R
e
v
e
n
u
e
(
a
s
f
r
a
c
t
i
o
n
o
f
O
P
T
)
1
P
o
l
y
E
x
p
F
i
n
i
t
e
I
n
f
i
n
i
t
e
1
-
1
/
n
c
1
-
O(1)
1/n
1
Noam Nisan
Explore the research work by Noam Nisan from Hebrew University on the complexity of pricing and auctions in economic sciences. The content covers various topics such as optimization, ad auctions, spectrum auctions, cloud computing, and strategies for maximizing revenue in selling independent items. Nisan's studies delve into game theory, computational economics, and the intersection of economics and computation, offering insights into revenue maximization and market mechanisms.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Complexity of Pricing Noam Nisan Hebrew University Noam Nisan
Circa 2004 Lens of Computation on the Sciences -- A workshop organized by Avi Wigderson 2014 Noam Nisan
Complexity in Economics Noam Nisan
Complexity in Economics Economics and Computation Classical Economics Noam Nisan
Optimization Perspective Simplicity Complexity Noam Nisan
Ad auctions Noam Nisan
Spectrum Auctions Noam Nisan
Cloud Computing Noam Nisan
Our Setting Noam Nisan
Selling independent items A seller has n items for sale. There is a single buyer that has private value vifor each item i. The buyer s value is simply additive over the items. The seller s partial knowledge is captured by independent prior distributions Fion vi. How does the seller maximize his (expected) revenue? Noam Nisan
Single Item case: monopolist pricing F Buyer has value v distributed according to F. v p Seller knows F but not v and wants to maximize expected revenue. Sell at price p Revenue = p Prv~F[v p] Seller maximizes for p Noam Nisan
Single Item case: can we do better? Is there a better way? Interactive protocol Randomization F v Theorem (Myerson): No. There are other protocols They can all be put into a clean canonical form Offer a menu of (Pr[win], price) Revenue maximizing one still uses simple pricing Generalizes to multiple bidders ( optimal auctions ) Noam Nisan
Selling Two Items One seller One buyer Values for the two items (v, u) are (independently) distributed according to F, G. Value for bundle is additive Challenge: find the revenue-maximizing selling mechanism. Noam Nisan
Surely, just sell each item optimally Example: item values are IID uniformly on {1,2} Selling a single item: optimal revenue = 1 Price=1 Pr[buy]=1 Revenue=1 Price=2 Pr[buy]=1/2 Revenue=1 Noam Nisan
Surely, just sell each item optimally Example: item values are IID uniformly on {1,2} Selling a single item: optimal revenue = 1 Price=1 Pr[buy]=1 Revenue=1 Price=2 Pr[buy]=1/2 Revenue=1 Selling both items: you can get revenue > 2! Price bundle at 3 Pr[buy]=3/4 Revenue = 2.25 Noam Nisan
Other Examples IID Uniform on {0,1} Selling each item separately is better than bundling IID uniform on {0,1,2} Buy any single item for $2 or both for $3 IID uniform on [0,1] Manelli-Vincent 2006 Buy any single item for $X or both for $Y Uniform on {1, 2} uniform on {1, 3} Daskalakis-Deckelbaum-Tzamos 2014 Buy (Item 1 & 50%-lottery for item 2) for $2.5, or both (surely) for $4 Beta(3,3) Beta(3,4) Daskalakis-Deckelbaum-Tzamos 2013 Choose between infinitely many possible lotteries (each with its price) Noam Nisan
Optimal Multi-item Auctions May be complex May be randomized May have infinitely many outcomes May be nonmonotone Increasing players values may reduce revenue May be very hard (#P-hard) to compute Hart-Reny 2012 Daskalakis-Deckelbaum-Tzamos 2014 Noam Nisan
Drawbacks of Complex Auctions Harder to analyze Harder to represent Harder to participate in Harder to tweak for Designer Implementer Human participant Computerized participant Noam Nisan
How much do we lose if we stick to simple auctions? Noam Nisan
Simplicity vs Complexity Qualitative measures: Selling items separately vs. combinatorially Selling full bundle vs. combinatorially Selling packages additively vs. combinatorially Selling deterministically vs. using lotteries Quantitative Measures: Number of menu entries in auction Hart-Nisan 2013 Number of parameters needed to describe auction Dughmi-Li-Nisan 2014, Morgenstern-Roughgarden 2015 Noam Nisan
Theorem: Selling two items separately always gives at least half of the optimal revenue. Hart-Nisan 2012 Noam Nisan
Proof Strategy: split the valuation space An auction for the u item E[v] is bounded by Rev(u) v u<v v<u u Noam Nisan
Multiple Items Revenue obtained by selling n items separately may be a factor of O(log n) smaller than the optimal revenue, but no less. Selling as a single bundle may be an O(n) factor smaller, but no less. Hart-Nisan 2012, Li-Yao 2013 The better of selling separately and of selling as a single bundle gives at least 1/6 of the optimal revenue. Babaioff-Immorlica-Lucier-Weinberg 2014 Noam Nisan
Menu-size Complexity Canonical representation of any auction: Menu Pr[win item 1] Pr[win item 2] Price 0% 0% 0$ 0% 100% 3$ 20% 30% 4$ 40% 60% 10$ Menu Complexity = Number of entries 100% 100% 20$ Noam Nisan
How Complex Must Auctions Be? Revenue (as fraction of OPT) Menu Size Noam Nisan
How Complex Must Auctions Be? 1 1-1/n Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
How Complex Must Auctions Be? 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
How Complex Must Auctions Be? 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
How Complex Must Auctions Be? 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
How Complex Must Auctions Be? 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
Theorem: For every n, , there exists C=exp(n, -1) such that auctions with menu size at most C suffice for getting (1- ) fraction of the optimal revenue in every n item auction. Babaioff-Gonczarowski-Nisan 2016 Noam Nisan
Proof Strategy: Core vs. Tails Li-Yao Double Tail: Ignore M Tail: Ignore Small Item. Apply Myerson to Large Item u Core: Nudge + Approximate M v Noam Nisan
How Complex Must Auctions Be? 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
Theorem: An auction that extracts at least 1-1/n fraction of the optimal revenue from the uniform distribution on {0,1}nrequires 2 (n) menu entries. Babaioff-Gonczarowski-Nisan 2016 Noam Nisan
Proof Idea: limitations of single entry Menu Entry Allocate items S* for price p* S* contains many S S* Contains their Union Low revenue on union Set S = {items with value 1} chooses this menu entry High revenue p* |S| S S* Noam Nisan
How Complex Must Auctions Be? 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
The power of small menus Theorem: For every , there exists d=poly( -1) such that auctions with menu size O(Cd) suffice for getting (1- ) fraction of the revenue of selling n items separately. Babaioff-Gonczarowski-Nisan 2016 Corollary: A menu size which is polynomial in n suffices for extracting at least 1/7 of the optimal revenue in any n item auction. Babaioff-Immorlica-Lucier-Weinberg 2014 Noam Nisan
Auction with small menu-size Item i is sold at price tiand this happens with probability pi. Order items by increasing value of t Very low Very high O(log n / ) bundles Don t sell sell at most one of these item pi>> 1 Sell bundle for price: t(1- ) pi pi<< 1 Sell bundle for price t Noam Nisan
Open Problem 1 1-1/nc Revenue (as fraction of OPT) 1- O(1) 1/n 1 Poly Exp Finite Infinite Menu Size Noam Nisan
