1 of 37

Non-clairvoyant Dynamic Mechanism Design

Vahab Mirrokni, Renato Paes Leme, Pingzhong Tang, Song Zuo

Google research Tsinghua university

May 2018

songzuo.z@gmail.com

2 of 37

Outlines

  • Dynamic auctions
  • Non-clairvoyance
  • Bank account mechanism
  • Main results & some proofs

​

3 of 37

Auction

 

 

information

 

 

actions

Requirements:

 

 

Goal: maximize

revenue

4 of 37

Dynamic Setting

Day 1

Day 3

Day 2

Day 4

v~U[0, 2]

v~U[0, 4]

v~U[0, 6]

v~U[0, 4]

Same type, different items

5 of 37

Dynamic Auction (Clairvoyant)

Day 1

Day 3

Day 2

Day 4

 

 

 

 

report

private

 

 

 

 

 

 

 

 

outcome

 

 

 

 

6 of 37

Dynamic Auction (Clairvoyant)

Day 1

Day 3

Day 2

Day 4

 

 

 

 

outcome

 

 

 

 

Requirements:

 

 

 

 

7 of 37

Dynamic Auction (Clairvoyant)

Day 1

Day 3

Day 2

Day 4

 

 

 

 

outcome

 

 

 

 

 

 

 

 

8 of 37

Dynamic Auction (Non-clairvoyant)

Day 1

Day 3

Day 2

Day 4

 

 

 

 

report

private

 

 

 

 

 

 

 

 

outcome

 

 

 

 

?

?

?

clairvoyant outcome

 

 

 

 

9 of 37

Static vs. Clairvoyant vs. Non-clairvoyant

​

Static

Clairvoyant

Non-clairvoyant

Outcomes

​

​

​

Revenue

0

[Papadimitriou et al. 2016]

1

[1/5, 1/2]

This paper

Optimal Auction

[Myerson 1981]

[Ashlagi et al. 2016]

This paper

Open?

10 of 37

Results overview

​

Simple Format

High Revenue

Buyer Flexibility

Optimality

Efficient Computation

Forecast-free

Static Auctions

YES

NO

YES

Arbitrarily large gap

YES

T-free

YES

Contracts

NO

Maybe YES

NO

N/A

Unknown

NO

Dynamic Auctions

NO

YES

Maybe YES

YES

Unknown (exponential?)

NO

Bank Account Mechanisms

YES

YES

YES

YES

somehow YES

FPTAS poly(T)

NO

Non-Clairvoyant BAMs

YES

YES

YES

2 upper bound

Unknown

YES

Constructed BAMs

YES

YES

YES

3-approx / 5-approx

Closed-form /

T-free

YES

11 of 37

Motivation

12 of 37

Dynamic Environment: Model

  • Seller has a sequence of items to sell to buyers.
  • Items arrive over time.
    • Each period, one item for sale.
    • The item will be destroyed, if not sold.
  • Unknown actual value until the t-th period.
    • Stage-wise independent, commonly known priors.
    • Additive valuation.
  • Seller's allocation rule and payment rule could depend on past periods.

13 of 37

Dynamic Environment: Application

  • Seller has a sequence of items to sell to buyers.
  • Items arrive over time.
    • Each period, one item for sale.
    • The item will be destroyed, if not sold.
  • Unknown actual value until the t-th period.
    • Stage-wise independent, commonly known priors.
    • Additive valuation.
  • Seller's allocation rule and payment rule could depend on past periods.

Google sells ad impressions to advertisers.

Impressions may come from users' searches on search engines.

- Arrive over time, destroyed immediately if not sold.

The value of each impression varies with (at least) the user's information (location, time, age, gender, cookies, etc.).

Currently, the auctions are rarely conducted dynamically.

14 of 37

Non-clairvoyance: importance

  1. In practice, the seller (Google) cannot predict the type of the next item (impression).

​

  • More importantly, even if the seller could predict the types, the buyers might not trust the seller’s prediction. (Common knowledge assumption violated)

15 of 37

Bank Account Mechanism

16 of 37

Bank Account Mechanism

  •  

16

Theorem: every dynamic auction is “isomorphic” to a bank account mechanism.

No loss of generality by restricting to bank account mechanisms

17 of 37

Bank Account Mechanism

  •  

18 of 37

How & Why it works?

  • How:
    • Bank account as a summary of the history
    • Buyers put their surplus into their bank accounts
    • Unspent balances will be returned
    • Spent = E[utility with discounts] – E[utility without discounts]
  • Why:
    • Increasing the efficiency of the allocation, higher social welfare
    • Buyer utilities not increase
    • Therefore, revenue = social welfare – buyer utilities, increases

18

19 of 37

(Static) Second Price Auction

Single buyer example:

​

v~U[0, 2]

v~U[0, 4]

v~U[0, 6]

value

v=3

v=0.08

v=5

Myerson reserves

2

1

3

deal

no deal

deal

Static Auction

Revenue = 2 + 0 + 3 = 5

20 of 37

(Dynamic) Bank Account Mechanism

Single buyer example:

​

v~U[0, 2]

v~U[0, 4]

v~U[0, 6]

value

v=3

v=0.08

v=5

dynamic

reserves

2

0

2.4

Dynamic Auction

Revenue = 0 + 2 + 0.75 + 0 + 0.33 + 2.4 = 5.48

bank account balance

b=0

b=0-0+1=1

b=1-0.75+0.08

=0.33

charge

balance

0

0.75

0.33

21 of 37

Why these magic numbers?

  •  

22 of 37

(Dynamic) Bank Account Mechanism

Single buyer example:

​

v~U[0, 2]

v~U[0, 4]

v~U[0, 6]

value

v=3

v=0.08

v=5

dynamic

reserves

2

0

2.4

Dynamic Auction

Revenue = 0 + 2 + 0.75 + 0 + 0.33 + 2.4 = 5.48

bank account balance

b=0

b=0-0+1=1

b=1-0.75+0.08

=0.33

charge

balance

0

0.75

0.33

23 of 37

Why these magic numbers?

  •  

24 of 37

Why these magic numbers?

  •  

25 of 37

Why these magic numbers?

  •  

 

 

26 of 37

From the example

  • Key message: the buyers are indifferent to the balance
  • The single buyer example naturally extends to multi-buyer cases.
  • Auction format (during each period) not limited to second price auctions (with reserves).

27 of 37

Revenue Approximation for Non-clairvoyant Mechanisms

  • Theorem: No non-clairvoyant is a better-than-2 approximation to the optimal revenue of clairvoyant.

​

  • Theorem (multi-buyer): There is a non-clairvoyant is (i) a 5-apprximation to the optimal revenue of clairvoyant and (ii) can be constructed efficiently.

​

  • Theorem (single-buyer): 5-approx -> 3-approx

28 of 37

3-approx for single-buyer cases

29 of 37

Recall: Bank Account Mechanism

  •  

30 of 37

3-approximation Bank Account Mechanism

  •  

 

31 of 37

Proof of 3-approx

  •  

32 of 37

Proof of 3-approx

  •  

33 of 37

Proof of 3-approx

  •  

Myerson’s auction

Give-for-free & increase balance

Greedy charge & post a price

34 of 37

5-approximation Bank Account Mechanism (multi-buyer)

  •  

 

 

Second price auction

 

 

for the winner

35 of 37

Summary

  • Dynamic auctions & non-clairvoyance (~online)
  • Bank account mechanism
    • Simple structure, representative
  • Non-clairvoyant bank account mechanism
    • 5-approx for multi-buyer (3-approx for single-buyer)
    • no better-than-2
  • +Application in ad auctions

36 of 37

Applications in ad auctions

  • [Mirrokni et al. 2018] Dynamic second price auction
    • SPA with dynamic reserves managed via bank accounts
    • Can be easily constructed from any given SPAwR
  • Evaluates the revenue & welfare on real data
    • Deal with the empirical prior distributions
    • Introduce measures on dynamic IC guarantees
    • Show significant improvements, +17% rev, +5% wel

37 of 37

Thanks for your attention!

  • Ashlagi, Itai, Constantinos Daskalakis, and Nima Haghpanah. “Sequential Mechanisms with ex-post Participation Guarantees.” Proceedings of the seventeenth ACM conference on Economics and computation. ACM, 2016.
  • Mirrokni, Vahab, Renato Paes Leme, Pingzhong Tang, and Song Zuo. “Dynamic auctions with bank accounts.” Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). (2016).
  • Mirrokni, Vahab, Renato Paes Leme, Pingzhong Tang, and Song Zuo. “Non-clairvoyant dynamic mechanism design.” EC (2018) https://ssrn.com/abstract=2873701.
  • Mirrokni, Vahab, Renato Paes Leme, Rita Ren, and Song Zuo. “Dynamic Mechanism Design in the Field.” WWW (2018).
  • Papadimitriou, Christos, George Pierrakosm, Christos-Alexandros Psomas, and Aviad Rubinstein. “On the complexity of dynamic mechanism design.” Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2016.