Prompt Mechanisms for Online Auctions

Speaker: Shahar Dobzinski

​

Joint work with Richard Cole and Lisa Fleischer

A Running Example

• A cinema in Las Vegas is presenting a daily show.
• For simplicity, assume only one tourist can watch the show each day.
• Each tourist has a different value for a ticket.
• We do not know the tourists that will come next.
• Our goal: maximize the total value of tourists that watched the show.

Val: 20

Val:10

Val: 9

Sun

Mon

Tue

Wed

Thu

Fri

Problem Definition

• m identical items are for sale, the j-th item must be allocated at time j.
• Bidder i arrives at time a_i (unknown in advance), and has a value of v_i for getting exactly one item a_i ≤ j ≤ d_i (before his departure time).
• Goal: maximize the sum of values of bidders that won some item.

The Greedy Algorithm

• The greedy algorithm: at time t, assign item t to the bidder with the highest value that is available.
• The greedy achieves a competitive ratio of 2 (Kesselman, Lotker, Mansour, Patt-Shamir, Schieber, Sviridenko)
• At least half of the optimal offline social welfare is recovered.
• What about truthfulness?
• In this talk: the only private information of bidder i is his value v_i.
• In particular, a bidder cannot lie about his arrival time a_i and departure time d_i.

Truthfulness of the Greedy Algorithm

• Theorem: The greedy algorithm is truthful (Hajiaghayi, Kleinberg, Mahdian, Parkes).
• Proof: using the following characterization:
• An algorithm for a single-parameter setting admits payments that make it truthful if and only if the algorithm is monotone.
• An algorithm is monotone if for each bidder i that wins with value v_i, bidder i also wins with value v’_i > v_i.
• The payment that a winning bidder i pays is the minimum value that he can bid and still win (the threshold value).

​

The Price of Winning

Val:10

Val:100

Val:100

Val:100

Val:9

Val: 20

Sun

Mon

Tue

Wed

Thu

Fri

Prompt Mechanisms

• Definition: A mechanism is prompt if a bidder learns his payment at the moment he wins an item. Otherwise, the mechanism is tardy.
• Why tardy mechanisms are not desired?
• Uncertainty
• How much money do I have to spend in my vacation?
• Debt Collection
• What if a bidder refuses to pay after getting the service?
• Trusted Auctioneer
• In tardy mechanisms the bidder essentially provides the auctioneer with a blank check.
• It is natural to know the price of a good the moment you buy it.

Our Results

• Theorem: There exists a prompt deterministic 2-competitive truthful mechanism for online auctions.
• Theorem: No prompt deterministic mechanism can achieve a (2-ε)-competitive ratio.

​

• We also present a randomized prompt O(1)-competitive mechanism.
• Proof involves a nice balls-and-bins question.
• We will mention later results in other models.

The Prompt 2-Competitive Deterministic Mechanism

• Prelims:
• Each Bidder is going to compete on exactly one item.
• Let the candidate for item j be the competitor on item j with the largest value.
• The Mechanism:
• On the arrival of bidder i, let him compete on the item in his window where currently the candidate bidder has the lowest value.
• On time t, allocate item t to its candidate.

The Deterministic Mechanism

9

0

20

Sun

Mon

Tue

Wed

Thu

Fri

Val:9

Val: 20

0

0

0

0

0

Val:5

Promptness and Truthfulness

• Lemma: The deterministic algorithm is prompt and truthful.
• Proof:
• Monotonicity…
• Promptness:
• Bidder i can win only one item t: the one that he is competing on.
• This item is determined on the arrival of bidder i.
• Thus, whether bidder i wins is only a function of bidders that arrive by time t.
• 🡺 If bidder i wins, we can calculate the payment of bidder i at time t.

The Competitive Ratio

• Lemma: the algorithm provides a competitive ratio of 2.
• Proof (outline):
• We will match each bidder in OPT to exactly one bidder in ALG.
• Each bidder in ALG will be associated to at most 2 bidders in OPT with lower values.
• Enough to get a 2-competitive ratio.

Proving the Competitive Ratio (cont)

• Let OPT=(o₁,…,o_m), ALG=(a₁,…,a_m).
• Fix item j. WLOG, let o₂,o₅,o₈,o₁₀ be the bidders that won some item in the optimal solution and are competing on j (by order of arrival).
• The Matching: Match o₂ to a₅, o₅ to a₈,… Match o₁₀ to a_j.
• The two properties:
• A bidder in OPT is matched to exactly one bidder in ALG.
• A bidder in ALG is associated to at most 2 bidders in OPT with lower values.

The Randomized Mechanism

• The Mechanism:
• When bidder i arrives, he competes on an item in his time window, selected uniformly at random.
• At time j conduct a second-price auction on item j, with the participation of all bidders that were selected to compete on item j.

​

• Theorem: This is a truthful prompt O(1)-competitive mechanism.

Balls and Bins

• n balls are thrown to n bins, where the i’th ball is thrown uniformly at random to the interval [a_i,d_i]. We are given that all balls can be placed in a way s.t. all bins are full. What is the expected number of full bins?

​

• 1-1/e≈0.61 of the bins if each ball can be thrown to all bins.
• Between 0.1 and 0.41 of the bins in the general case.

Summary

• Introduced prompt and tardy mechanisms.
• Showed a prompt 2-competitve deterministic mechanism.
• A prompt randomized O(1)-competitive mechanism.
• Can the analysis of the underlying balls and bins question can be improved?
• Main open question: upper and lower bounds (not necessarily prompt) when the arrival and departure time are also private information.
• Our results: a logarithmic upper bound, and a lower bound of 2.

The Lower Bound

• Theorem: No prompt deterministic mechanism can achieve a (2-ε)-competitive ratio.
• Proof: Claim that a player can win exactly one item, and that this item is determined the moment he arrives.

The Proof (cont)

• The arrival order of competitors on item j: o₂,o₅,o₈,o₁₀.
• Construction: Match o₂ to a₅, o₅ to a₈,… Match o₁₀ to a_j.
• Our two properties:
• A bidder in OPT is matched to exactly one bidder in ALG.
• A bidder in ALG is associated to at most 2 bidders in OPT with lower values:
• 2 bidders: a₅ is associated to o_2, and to the last bidder in OPT that was assigned to compete on item 5.
• Next we prove that the value of o₂ is less than the value of a₅.
• When o₅ arrives, the value of the candidate for j is less than the candidate for item 5 (o₅ competes on item j, not on item 5).
• The value of o₂ is at most the value of the candidate for j when o₅ arrives.
• The value of the candidate of item 5 can only increase over time.