Learning Prices for Repeated Auctions with Strategic Buyers

Kareem Amin; Afshin Rostamizadeh; Umar Syed

Source-linked AI summary

Learning Prices for Repeated Auctions with Strategic Buyers

Kareem Amin, Afshin Rostamizadeh, Umar Syed

arXiv:1311.6838v1Nov 26, 2013cs.LGcs.GT

TL;DR

The paper asks how a seller can learn a buyer’s value distribution and maximize revenue when the same buyer repeatedly responds strategically to posted prices. It defines strategic regret against truthful behavior and develops learning algorithms under buyer discounting. The results show that discounting enables no-regret learning, while the regret lower bound scales with the buyer’s effective horizon and becomes linear without discounting.

Problem
Repeated posted-price auctions must learn the buyer’s value distribution while accounting for a buyer who strategically maximizes long-term surplus.
Method
The paper defines strategic regret against the best fixed price with a truthful buyer and designs seller algorithms for discounted strategic buyers.
Results
Discounted buyers permit no-regret algorithms, while any seller algorithm has strategic regret at least Ω(Tγ), which is linear without discounting.
Takeaways & Limitations
Strategic-buyer learning is feasible when the buyer values present surplus sufficiently more than distant future surplus.
Takeaways & Limitations
The analysis assumes discounted buyer surplus and, for the distributional algorithm, a smooth value distribution.

Abstract

from arXiv · show

Inspired by real-time ad exchanges for online display advertising, we consider the problem of inferring a buyer's value distribution for a good when the buyer is repeatedly interacting with a seller through a posted-price mechanism. We model the buyer as a strategic agent, whose goal is to maximize her long-term surplus, and we are interested in mechanisms that maximize the seller's long-term revenue. We define the natural notion of strategic regret --- the lost revenue as measured against a truthful (non-strategic) buyer. We present seller algorithms that are no-(strategic)-regret when the buyer discounts her future surplus --- i.e. the buyer prefers showing advertisements to users sooner rather than later. We also give a lower bound on strategic regret that increases as the buyer's discounting weakens and shows, in particular, that any seller algorithm will suffer linear strategic regret if there is no discounting.

1 Introduction

The paper studies repeated posted-price auctions where a seller learns a buyer’s value distribution while the buyer strategically maximizes long-term surplus. It defines strategic regret and shows that discounting enables no-regret learning, while weaker discounting imposes larger regret.

Motivation: Single-bidder ad exchanges reduce second-price auctions to posted-price mechanisms, making reserve-price learning central to publisher revenue.The seller offers a price, and the buyer accepts or rejects it.
Problem: The seller repeatedly posts prices while observing only accept/reject decisions, using interactions to learn the buyer’s fixed value distribution.The buyer observes both her values and distribution; the seller observes neither directly.
Strategic behavior: A buyer who rejects high prices can induce a no-regret seller to offer low prices repeatedly, even when her value is much higher.The standard no-regret benchmark can therefore be unhelpful for revenue maximization.
Strategic regret: Strategic regret compares revenue against a best fixed price facing a truthful buyer, rather than against the best price against the buyer’s strategic behavior.This benchmark can exceed the best fixed-price revenue learned against a strategic buyer.
Discounting: Discounted buyer surplus is weighted by γ_t, and the buyer horizon Tγ = Σ_t γ_t measures how strongly future surplus matters.The paper assumes the discount sequence is nonincreasing and lies in (0, 1].
Results: No-regret requires Tγ = o(T), and every seller algorithm has strategic regret at least Ω(Tγ), with linear regret when there is no discounting.The lower bound is obtained by reducing to a single-shot auction.

2 Related work

Prior work studies repeated auctions, reserve-price learning, repeated games, and adaptive-adversary regret, but this paper focuses on repeated interactions with the same strategic buyer. Its strategic-regret setting differs because the buyer’s behavior responds to the seller’s announced algorithm.

Repeated auctions: Earlier repeated-auction work considers sequential bidders with fixed, distributional, or obliviously adversarial values rather than one buyer repeatedly interacting strategically.The cited settings include posted prices and related reserve-price problems.
Strategic buyers: Electronic exchanges repeatedly encounter the same buyer, creating incentives for strategic behavior that earlier theoretical settings generally omit.Empirical work cited by the paper reports strategic behavior affecting seller revenue.
Repeated games: Related repeated-game research mainly characterizes equilibria, whereas this setting’s structure supports more efficient seller algorithms.The paper models the interaction as a nonzero-sum repeated game of incomplete information.
Adjacent learning problems: Multi-armed bandit mechanism design and incentive-compatible prediction combine learning with mechanism design but address settings distinct from this paper’s model.The cited bandit-mechanism setting involves multiple advertisers and click-through-rate estimation.
Policy regret: Policy regret accounts for adaptive adversaries but is insufficient here because an oblivious buyer strategy can yield low standard regret and high truthful-buyer benchmark regret.Thus, adaptivity-aware regret alone does not capture the paper’s strategic-buyer benchmark.

3 Preliminaries and Model

The model is a repeated posted-price interaction in which a seller learns from allocation decisions while a strategic buyer knows her value distribution and responds to the announced seller algorithm. Regret benchmarks revenue from the optimal fixed price against truthful behavior.

Model: A single buyer receives independent values from a fixed distribution D, while the seller posts prices without observing the realized values.Both the value and D are known to the buyer but not the seller.
Strategies: The seller’s algorithm selects each price from prior prices and allocation decisions, and is announced before the buyer chooses her strategy.The buyer’s strategy may depend on D, values, prices, and previous allocations.
Revenue: A buyer’s strategy and value distribution determine a distribution over price and allocation sequences, which determines expected seller revenue.The model permits randomized seller algorithms and buyer strategies.
Discounting: The buyer’s effective horizon is Tγ = Σ_t γ_t, and the paper’s lower bounds show that sufficiently decaying discounting is necessary for no-regret learning.The discount sequence is nonincreasing with terms in (0, 1].
Strategic buyer: The buyer is modeled as surplus-maximizing against the announced seller algorithm and distribution.B*(A, D) achieves at least as much discounted buyer surplus as any alternative strategy.
Regret: Strategic regret equals optimal fixed-price revenue against truthful acceptance minus revenue earned by the seller’s algorithm against the surplus-maximizing buyer.The benchmark is T p* Pr_{v∼D}[v ≥ p*].
No-regret: No-regret means worst-case regret is o(T), so average regret vanishes as T approaches infinity.The worst case ranges over value distributions while buyer behavior remains surplus maximizing.

4 Fixed Value Setting

For a fixed unknown buyer value, the Monotone algorithm uses decreasing prices and achieves a regret bound that supports no-regret when the buyer’s effective horizon is sufficiently smaller than the game horizon.

The Monotone algorithm starts at price 1 and decreases price by factor β whenever the fixed-value buyer rejects, otherwise leaving it unchanged.
The buyer’s optimal allocation sequence is monotonically nondecreasing, so once she accepts the offered price, she continues accepting thereafter.
The analysis characterizes the buyer’s revenue-minimizing optimal sequence when multiple surplus-maximizing allocation sequences exist.
The tuned Monotone algorithm achieves O(T^γ) regret, without requiring knowledge of the buyer’s discount parameter γ.
No-regret is possible for an unknown fixed value when T^γ = o(T), meaning the buyer’s effective horizon is more than a constant factor smaller than the square-root of the finite horizon.

5 Stochastic Value Setting

For stochastic buyer values, the Phased algorithm alternates exploration and exploitation to learn the value distribution while reducing strategic manipulation, under a continuity assumption on that distribution.

The Phased algorithm explores each finite price for a fixed number of rounds, then exploits the price with the greatest observed revenue.
Strategic buyers have no incentive to lie during exploit rounds because their decisions there do not affect future prices.
During exploration, buyers may lie to obtain better future exploit prices, so the algorithm balances exploration length against the opportunity for exploitation.
The Phased algorithm explores both to estimate revenues accurately and to dampen the buyer’s incentive to mislead the seller.
The value distribution must be K-Lipschitz so nearby prices cannot have sharply different acceptance probabilities.
With T^γ = T^c, Phased has regret ˜O(T^c), while any seller algorithm has worst-case regret at least Ω(T^c).

6 Lower Bound

The lower-bound argument reduces repeated strategic interaction to a single-shot auction and shows that seller regret must grow with the buyer’s discounting horizon. In particular, any seller algorithm faces regret of order Tγ for some buyer distribution.

Main lower bound: The repeated-auction regret is at least Ω(Tγ), where γ captures the buyer’s discounting.When Tγ = Ω(T), no-regret learning is impossible; without discounting, the seller cannot exploit information learned from prior interactions.
Interpretation: The lower bound relates repeated-auction regret to a single-shot game, leaving the seller no better off against a non-discounted buyer than under repeated single-shot mechanisms.This establishes the relevance of the single-shot impossibility result to repeated strategic interaction.
Reduction to a single-shot auction: The lower bound constructs a single-shot auction from the buyer’s discounted interaction with any seller algorithm.The construction uses the discounted empirical distribution of prices and allocations generated against surplus-maximizing buyers.
Transfer to repeated auctions: The single-shot construction is incentive compatible and rational, so its lower bound transfers to the repeated-auction setting.The proof uses surplus-maximizing buyer behavior and the fact that such a buyer can always reject every price to obtain zero surplus.

7 Conclusion

The paper studies revenue-maximizing learning in repeated posted-price auctions with strategic buyers. It shows that discounting enables no-regret learning relative to truthful buyers, while lower bounds establish that this assumption is necessary.

The paper analyzes revenue-maximizing algorithms for repeated posted-price auctions with strategic buyers.
When buyers value present inventory more than inventory in the distant future, no-regret learning against truthful-buyer revenue is possible.
Lower bounds show that buyer discounting is necessary for no-regret learning in this setting.

A.1 Proof of Lemma 1

The proof analyzes optimal acceptance sequences under geometrically changing prices and derives a contradiction from exchanging acceptance decisions. Monotonicity of an auxiliary function completes the argument.

The proof selects an optimal acceptance sequence whose last acceptance occurs as late as possible.
If the buyer’s surplus at the last accepted price is nonnegative, moving acceptance one round later preserves surplus and contradicts maximality.
If that surplus is negative, exchanging acceptance decisions at later rounds yields two incompatible surplus inequalities.
The auxiliary function g(β) = β^(k−1) + β − β^k is non-decreasing for β < 1 and satisfies g(β) ≤ g(1) = 1.

A.2 Proof of Lemma 2

The proof compares the discounted surplus from beginning acceptance at adjacent rounds. After algebraic rearrangement, it shows that earlier acceptance yields greater surplus under the relevant condition.

For any t > dβ,γ, rearranging the defining inequality yields a bound involving β^t(1 + (1 − β)Tγ) < v.
Substituting β^t(1 − β) = (v − β^(t+1)) − (v − β^t) enables the proof to gather adjacent-round surplus terms.
The resulting inequality says that surplus from starting acceptance at round t + 1 exceeds surplus from starting at round t + 2.

A.3 Proof of Corollary 1

The proof establishes logarithmic inequalities and applies them to derive Corollary 1 under the condition T ≥ 1.

Lemma 5 proves x ≥ log(1 + x) for x ≥ 0 and x ≤ 2 log(1 + x) for 0 ≤ x ≤ 1.
The first inequality follows from the exponential-series bound e^x ≥ 1 + x for nonnegative x.
For 0 ≤ x ≤ 1, the proof bounds finite even-order Taylor approximations and takes their limit to obtain 2 log(1 + x) ≥ x.
The corollary proof invokes Lemma 5 and uses T ≥ 1 before substituting the earlier bound involving cβ,γ.

B Upper Bound on Regret of Phased

The Phased algorithm explores prices in phases, selects the empirically best price for exploitation, and controls strategic misreporting through concentration and surplus arguments.

Algorithm and proof strategy: The analysis seeks to show that the optimal price p∗ maximizes observed revenue with high probability after sufficiently many phases.Failure can arise from atypical realized values or buyer untruthfulness; the proof separately controls these events.
Concentration and strategic behavior: Lemma 6 gives a 1 − 2T^-1 probability event controlling empirical revenue estimates for every fixed price and sufficiently large phase.
Concentration and strategic behavior: If another price’s observed revenue exceeds that of p∗ during a good event, Lemma 7 implies that the buyer must have produced many λ-lies.A λ-lie is an acceptance below p − λ or a rejection above p + λ.
Concentration and strategic behavior: Lemma 8 bounds the probability that a surplus-maximizing buyer produces at least Cδ λ-lies for a fixed price and phase by δ.The proof compares the strategic buyer with an alternative that becomes truthful from the current phase onward.
Algorithm and proof strategy: The algorithm uses phased exploration and exploitation, offering the price maximizing observed revenue throughout each phase’s exploit rounds.The proof allows the final phase to be partial and bounds regret through exploration rounds and the probability of selecting a nonoptimal price.
Regret bound: Combining concentration, lie bounds, phase growth, and discounting yields the theorem’s regret upper bound.The proof treats separately the regimes γT ≥ 1/2 and γT ≤ 1/2, using the trivial regret bound in the first case.

C.2 Proof of Lemma 4

The proof relates discounted surplus to undiscounted surplus by induction, then uses the revenue–surplus–value identity to derive the lemma’s bound.

The proof defines discounted surplus, undiscounted surplus, and total value, with revenue plus undiscounted surplus equal to total value.
A surplus-maximizing buyer has nonnegative continuation surplus because she could stop accepting from any round onward.
Induction establishes sur(t, T) ≤ γ^t udsur(t, T) for every round t.The inductive step uses nonnegative future undiscounted surplus and the monotonicity γ^t ≥ γ^(t+1).
Applying the bound at t = 1 and γ^1 ≤ 1, together with the value decomposition, proves the lemma.