PaperlayerView exact revision on arXiv

Source-linked AI summary

Selling to a No-Regret Buyer

Mark Braverman, Jieming Mao, Jon Schneider, S. Matthew Weinberg

arXiv:1711.09176v1cs.GTcs.LGstat.ML

TL;DR

For GFP/GSP auctions, computing and playing a Bayes–Nash equilibrium is possible but unrealistic because it requires accurate priors and extensive computation. The paper analyzes repeated single-item sales with fresh values from D, comparing seller strategies against buyers using different no-regret learning algorithms and bid constraints. Mean-based buyers permit near-welfare revenue with unrestricted auctions; a modified algorithm makes the Myerson reserve optimal, while a linear program characterizes revenue for buyers who do not overbid.

  • Problem

    For GFP/GSP auctions, computing and playing a Bayes–Nash equilibrium is possible but unrealistic because it requires accurate priors and extensive computation.

    Source: §1 · p. 2

  • Method

    The paper analyzes repeated single-item sales with fresh values from D, comparing seller strategies against buyers using different no-regret learning algorithms and bid constraints.

    Source: §2 · p. 5

  • Results

    Mean-based buyers permit near-welfare revenue with unrestricted auctions; a modified algorithm makes the Myerson reserve optimal, while a linear program characterizes revenue for buyers who do not overbid.

    Source: §1 · pp. 2–3, §4 · pp. 11–12

  • Takeaways & Limitations

    Seller-optimal auctions depend on the buyer’s learning rule and whether overbidding is dominated; in the latter setting, decreasing-reserve pay-your-bid auctions attain the LP guarantee.

    Source: §1 · p. 3, §4 · p. 12

    The multi-buyer problem remains a boundary: only Theorem 3.2 extends easily, and the paper identifies clear barriers to the other results.

    Source: §4 · p. 12

Abstract

from arXiv · show

We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution $D$ in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a no-regret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically: - If the buyer bids according to EXP3 (or any "mean-based" learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer's valuation $D$, but somewhat unnatural as it is sometimes in the buyer's interest to overbid. - There exists a learning algorithm $\mathcal{A}$ such that if the buyer bids according to $\mathcal{A}$ then the optimal strategy for the seller is simply to post the Myerson reserve for $D$ every round. - If the buyer bids according to EXP3 (or any "mean-based" learning algorithm), but the seller is restricted to "natural" auction formats where overbidding is dominated (e.g. Generalized First-Price or Generalized Second-Price), then the optimal strategy for the seller is a pay-your-bid format with decreasing reserves over time. Moreover, the seller's optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare.

1 Introduction

The paper studies how a seller should adapt repeated sales to buyers who learn bids without fully strategic reasoning. It characterizes seller revenue across learning rules and auction constraints, and distinguishes this setting from prior auction-learning work.

1 Introduction

  • The model addresses sellers facing no-regret bidders, a behavior motivated by Bing evidence [NST15] and by the difficulty of computing equilibria without accurate priors.Each round brings a fresh value drawn from D, and the buyer learns from prior-round outcomes.Source: §1 · p. 2
  • Mean-based buyers let the seller approach expected welfare with an auction that works for every valuation distribution D.The paper reports revenue (1 − ε)T · Val(D) − o(T) for any constant ε > 0.Source: §1 · pp. 2–3
  • The near-welfare auction is unnatural: it can lure bidders into overbidding through free allocations early and high prices later.In GFP and GSP, overbidding is dominated, distinguishing those formats from the auction used for the unrestricted result.Source: §1 · p. 3
  • With a natural no-regret algorithm A, posting the Myerson reserve each round is optimal for the seller.The algorithm is a natural adaptation of EXP3, or of another existing no-regret algorithm, to this setting.Source: §1 · p. 3
  • For mean-based buyers restricted to undominated bids, a linear program characterizes optimal revenue, achieved by pay-your-bid auctions with decreasing reserves.This revenue can be unboundedly better than T · Rev(D) yet unboundedly worse than T · Val(D).Source: §1 · pp. 3–4

1.1 Related Work

  • Unlike dynamic-auction work [ADH16] [MLTZ16b] [LP17] and seller-learning work [CR14] [DHP16] [MR15] [MR16] [GN17] [CD17], this studies seller adaptation to a no-regret buyer.Related work on dynamic auctions assumes strategic buyers, while seller-learning work studies buyers who participate in one round; the paper identifies its setting as a first study of seller adaptation to a no-regret buyer.Source: §1.1 · pp. 4–5

2 Model and Preliminaries

The model combines repeated single-item sales with context-dependent no-regret bidding, then defines the learning and revenue benchmarks used to evaluate seller strategies.

2 Model and Preliminaries

  • Each round, one buyer’s value is drawn independently from known D, and the seller sets allocation and payment rules for K bid options.Seller strategies that guarantee revenue are non-adaptive; upper bounds also hold against adaptive sellers.Source: §2 · p. 5

2.1 Bandits and experts

  • Bandit learners observe rewards only for chosen bids, whereas experts learners observe rewards for all bids; no-regret means expected regret is o(T).Mean-based algorithms rarely select an arm whose cumulative reward is significantly below the best arm; examples include EXP3, Multiplicative Weights, and Follow-the-Perturbed-Leader.Source: §2.1 · p. 6

Contextual bandits

  • Because the buyer’s current value is a context, separate no-regret instances for each value yield a contextual algorithm that remains mean-based.This construction is called cont(M), and Theorem 2.5 establishes preservation of the mean-based property.Source: Contextual bandits · pp. 6–7

2.2 Welfare and monopoly revenue

  • Expected welfare is Val(D) = E[v], while Myerson revenue is the maximum fixed-price revenue, max_p p · Pr[v ≥ p].Myerson revenue is attainable by setting the corresponding reserve price.Source: §2.2 · p. 7

2.3 A final note on the model

  • The model is equivalent to a population of m fixed-value buyers, with exactly one arriving each round according to probabilities q_i.Each buyer learns without context because their value remains fixed.Source: §2.3 · p. 7

3 An Illustrative Example

The examples show how a mean-based buyer can let a seller extract more than the default reserve revenue, and how the result changes with the learning algorithm and auction format. With no overbidding, a linear program characterizes the optimal revenue; a decreasing-reserve pay-your-bid auction achieves it.

3.1 Mean-Based Learning and Arbitrary Auctions

  • (1 − ε)Val(D)T − o(T) revenue is achievable against a mean-based learner with an arbitrary auction, approaching full expected welfare.The construction is prior-independent but can rely on luring bidders into overbidding.Source: §3.1 · pp. 8–9

3.4 A Final Note on the Example

  • The examples’ overpaying behavior is still no-regret, though a more thoughtful learner can do better.Mean-based behavior can persist because the learner compares cumulative arm utilities without adapting its policy to a different value context.Source: §3.2 · p. 9, §3.4 · p. 11

3.2 Better Learning and Arbitrary Auctions

  • A buyer algorithm with no regret across lower-value contexts limits every seller strategy to Myerson revenue, matching the default reserve strategy.The construction adds virtual arms that let a buyer with value v learn as if they had a lower value v′.Source: §3.2 · p. 9

3.3 Mean-Based Learning and Critical Auctions

  • With no overbidding, MBRev(D)T ± o(T) characterizes optimal seller revenue, and decreasing cutoffs in a pay-your-bid auction achieve it.The seller’s upper bound applies to any auction; the stated construction achieves the bound against mean-based algorithms.Source: §3.3 · pp. 10–11
  • For distributions D supported on [1/H, 1], MBRev(D) is O(log log H), and there exist such distributions for which MBRev(D) is Θ(log log H).Source: §3.3 · p. 11

4 Conclusion and Future Directions

The paper studies repeated selling to a single learning buyer and characterizes seller revenue under several learning and auction conditions. It identifies multiple learning buyers as a natural extension, while noting barriers to extending the results.

4 Conclusion and Future Directions

  • For mean-based learning with no overbidding, the seller’s optimal revenue is characterized by a linear program and achieved by a pay-your-bid auction with decreasing reserves.The equal-revenue distribution truncated at H has monopoly revenue 1, expected welfare ln(H), and mean-based revenue Θ(ln(ln(H))).Source: §4 · pp. 11–12
  • Only the result for the modified learner extends easily to multiple buyers; achieving welfare-optimal revenue would require welfare maximization, which free allocation can undermine.For mean-based revenue, the natural multi-buyer LP does not make a critical-auction construction clear because its variables depend on other bidders’ actions.Source: §4 · p. 12
  • The paper leaves open how seller strategies affect buyer utility and whether buyers can benefit from using an exploitable learning strategy.The authors note that the effect on utility is not obvious outside certain corner configurations.Source: §4 · p. 12

A Good no-regret algorithms for the buyer

The appendix constructs a contextual no-regret buyer algorithm that also compares play across lower-valued contexts. This added guarantee limits seller revenue to Myerson revenue, even against adaptive strategies.

A Good no-regret algorithms for the buyer

  • Each value-specific instance learns over bid arms and virtual value arms, where choosing a lower-value arm means playing as if the buyer had that value.The construction resembles low swap-regret learning, but swaps contexts rather than actions and considers only lower-valued contexts.Source: A Good no-regret algorithms for the… · p. 15
  • The constructed buyer algorithm guarantees the seller at most Mye(D)T plus an additive regret term, even against an adaptive strategy.The construction modifies a standard no-regret algorithm with virtual actions representing lower values.Source: A Good no-regret algorithms for the… · p. 15
  • The revenue bound follows by using the buyer’s no-regret comparisons across values to construct a single-round mechanism whose revenue cannot exceed Myerson’s optimum.The proof constructs a menu from the expected allocations and payments, then invokes Myerson optimality.Source: A Good no-regret algorithms for the… · pp. 16–18

A.1 Multiple bidders

Algorithm 2 adapts a no-regret learner to multiple bidders, and against these bidders even an adaptive seller cannot exceed the revenue of the single-round Myerson auction repeated over T rounds.

A.1 Multiple bidders

  • Algorithm 2 limits even an adaptive seller to Mye(D1, D2, . . . , DB)T + o(T) revenue, the repeated single-round Myerson benchmark.The proof constructs a single-round mechanism from the dynamic auction and bounds its revenue by Myerson's optimal revenue.Source: §A.1 · pp. 18–19
  • Each bidder runs copies of a no-regret bandit learner over bid arms and value arms, using value arms to condition its learning on its current value.Algorithm 2 includes one value arm for each possible value and bid arms for menu options.Source: §A.1 · p. 19
  • The proof converts the dynamic auction's expected allocations and payments, conditional on reported values, into a single-round mechanism that is approximately incentive compatible.It then uses a transformation from approximately incentive-compatible mechanisms to Bayesian incentive-compatible ones.Source: §A.1 · p. 20

B Achieving full welfare against non-conservative buyers

Against non-conservative buyers using a mean-based algorithm, the seller can obtain revenue arbitrarily close to expected welfare by offering time-phased options. The result applies to a seller strategy that can be chosen independently of the buyer's value distribution.

B Achieving full welfare against non-conservative buyers

  • (1 − ε)Val(D)T − o(T) revenue is achievable against a non-conservative buyer running a mean-based algorithm.The guarantee holds for any constant ε > 0.Source: B Achieving full welfare against… · p. 21
  • Each option with maximum bid 1 first withholds the item, then gives it free, and finally allocates it for price 1.The durations of these three sessions vary across options; the seller can choose ρ = 1 − ε/2 and δ = ε/2 to make the strategy independent of D.Source: B Achieving full welfare against… · pp. 21–22
  • During the interval [Aj, Bj(vi)], a value-vi buyer chooses an arm in a 1-session with probability at least 1 − nγ and pays 1 each round.This follows from the mean-based condition and supports the seller's near-welfare revenue guarantee.Source: B Achieving full welfare against… · p. 23

C Optimal revenue against conservative buyers

Restricting buyers to bids no higher than their values changes the seller's problem: full-welfare extraction is no longer attainable by the described approach, but revenue above Myerson remains possible. The optimal revenue is characterized by a linear program and achieved by a repeated first-price auction with decreasing reserves.

C Optimal revenue against conservative buyers

  • The section addresses two drawbacks of full-welfare extraction: its unnatural format and its reliance on buyers considering bids above value.The proposed setting instead studies buyers constrained to bids below their current values.Source: C Optimal revenue against conservative… · p. 23
  • For conservative buyers running a mean-based algorithm, an LP characterizes optimal seller revenue, which exceeds Myerson revenue but falls short of full welfare.The setting restricts buyers to bids below their current values.Source: C Optimal revenue against conservative… · pp. 23–24
  • The optimal mechanism has the interpretation of a repeated first-price auction with gradually decreasing reserves.The auction is critical, and is also optimal among critical auctions against clever buyers.Source: C Optimal revenue against conservative… · p. 24

C.1 Characterizing the optimal revenue

For conservative mean-based buyers, the seller's optimal revenue is characterized by the mean-based revenue LP. Its solution yields a repeated option schedule that is tight against even adaptive seller strategies, under the monotonicity condition used in the analysis.

C.1 Characterizing the optimal revenue

  • For each value vi, the seller's option gives no allocation at first, then allocates at price vi − ε for the remaining xiT rounds, with xi chosen by the mean-based revenue LP.The LP's value is defined as MBRev(D), and its optimal xi values are monotone increasing in i.Source: §C.1 · p. 24
  • The seller's option schedule achieves at least (MBRev(D) − ε)T − o(T), while no strategy can exceed MBRev(D)T + o(T) against a conservative no-regret buyer.The lower bound uses a mean-based buyer; the upper bound applies to any seller strategy, including adaptive ones.Source: §C.1 · pp. 25, 27
  • The proof bounds each value type's item allocation using xi and its utility using ui, then bounds seller revenue by welfare minus buyer surplus.It compares arbitrary seller strategies to an LP upper bound before relating that bound to the mean-based revenue LP.Source: §C.1 · pp. 27–28
  • The upper-bound argument relies on monotone allocation; with non-monotone strategies, the seller can extract up to the full welfare from a conservative mean-based buyer.The appendix states that monotonicity is necessary for the bound based on Lemma C.5.Source: §C.1 · p. 29

C.2 Bounding MBRev(D)

The section places mean-based revenue between Myerson revenue and expected value, then shows that it need not approximate either benchmark within a constant factor. For bounded supports, the gaps can grow logarithmically with the support bound.

C.2 Bounding MBRev(D)

  • MBRev(D) is at most Val(D), at least Mye(D), and is not a constant-factor approximation to either benchmark in general.The section establishes these benchmark bounds directly from the revenue LP and the seller’s ability to post the Myerson price.Source: §C.2 · p. 29
  • MBRev(D) is monotone under stochastic dominance: if D dominates D′, then MBRev(D) ≥ MBRev(D′).The proof uses that the revenue expression for an increasing allocation rule is increasing in value.Source: §C.2 · p. 29
  • The gap results are developed for continuous distributions on [1, H] and extend to discrete distributions by appropriate discretization.Rescaling values preserves the multiplicative gaps while restoring support [0, 1].Source: §C.2 · pp. 29–30
  • For distributions supported on [1, H] with Mye(D) = 1, the truncated equal-revenue curve maximizes MBRev(D), which is Θ(log log H).The lower bound is Ω(log log H), and the upper bound is O(log log H).Source: §C.2 · pp. 30–31
  • The gap MBRev(D)/Mye(D) can reach Ω(log log H), while Val(D)/MBRev(D) can reach Ω(log H / log log H), and both gaps grow unboundedly.The first gap is tight for distributions supported on [1, H].Source: §C.2 · p. 32

D Mean-based learning algorithms

This appendix establishes that Multiplicative Weights, Follow-the-Perturbed-Leader, and EXP3 are mean-based no-regret algorithms. It also shows that contextualizing a mean-based algorithm preserves that property.

D Mean-based learning algorithms

  • The authors expect variants and other no-regret algorithms to be mean-based, but say these require similar proof methods.This is an expectation about extensions, not a result established for every such algorithm.Source: D Mean-based learning algorithms · p. 33
  • Multiplicative Weights, also called Hedge, chooses options proportional to their weights and updates each weight by an exponential reward factor; it is mean-based.The appendix identifies it as a full-information no-regret algorithm.Source: D Mean-based learning algorithms · p. 33
  • Follow-the-Perturbed-Leader is mean-based when its arms receive independent nonnegative exponential perturbations.The appendix states that the algorithm is γ-mean-based.Source: D Mean-based learning algorithms · pp. 33–34
  • EXP3 is mean-based while updating the chosen option’s weight using an importance-weighted reward, extending Multiplicative Weights to the bandit setting.The appendix shows EXP3 remains no-regret with ε = T^-1/4.Source: D Mean-based learning algorithms · p. 34
  • Contextualizing a mean-based experts or bandit algorithm preserves mean-based behavior, including for the contextualized versions of all three algorithms.The three named algorithms are Multiplicative Weights, Follow-the-Perturbed-Leader, and EXP3.Source: D Mean-based learning algorithms · p. 35

E Full revenue can be achieved with non-monotone strategies

A non-monotone seller strategy can approach full expected welfare against a conservative buyer using a mean-based algorithm. The construction uses multiple arms whose charges and allocation schedules vary over time.

E Full revenue can be achieved with non-monotone strategies

  • For any constant ε > 0, a non-monotone strategy with O(m^2/ε) arms earns at least (1 − ε)Val(D)T − o(T) against a conservative buyer using a γ-mean-based algorithm with γ = o(1).The theorem states the result for any constant ε > 0.Source: E Full revenue can be achieved with… · p. 35
  • The construction sets M = m/ε and provides multiple arms for each possible value, scheduling periods with zero charge and periods charging that value.Each value vi receives M − i + 1 arms, with intervals that alternate between free allocation and charging vi.Source: E Full revenue can be achieved with… · p. 36
  • During designated intervals, the matching arm has higher cumulative reward than the specified competing arms, so mean-based behavior favors it.The argument bounds the probability of selecting that arm below by 1 − Mmγ.Source: E Full revenue can be achieved with… · pp. 36–37
Loading 1711.09176v1…