Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions

• URL: http://arxiv.org/abs/2406.03674v3
• Date: Wed, 23 Jul 2025 21:09:41 GMT
• Title: Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
• Authors: Negin Golrezaei, Sourav Sahoo,
• Abstract summary: We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a value-maximizing buyer.<n>We introduce the notion of safe bidding strategies as those that satisfy the RoI constraints irrespective of competing bids.<n>We show that these strategies satisfy a mild no-overbidding condition, depend only on the valuation curve of the bidder, and the bidder can focus on a finite subset without loss of generality.
• Score: 4.089889918897877
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a value-maximizing buyer. The buyer aims to maximize their cumulative value over $T$ rounds while adhering to per-round return-on-investment (RoI) constraints in a strategic (or adversarial) environment. Using an $m$-uniform bidding format, the buyer submits $m$ bid-quantity pairs $(b_i, q_i)$ to demand $q_i$ units at bid $b_i$, with $m \ll M$ in practice, where $M$ denotes the maximum demand of the buyer. We introduce the notion of safe bidding strategies as those that satisfy the RoI constraints irrespective of competing bids. Despite the stringent requirement, we show that these strategies satisfy a mild no-overbidding condition, depend only on the valuation curve of the bidder, and the bidder can focus on a finite subset without loss of generality. Though the subset size is $O(M^m)$, we design a polynomial-time learning algorithm that achieves sublinear regret, both in full-information and bandit settings, relative to the hindsight-optimal safe strategy. We assess the robustness of safe strategies against the hindsight-optimal strategy from a richer class. We define the richness ratio $\alpha \in (0,1]$ as the minimum ratio of the value of the optimal safe strategy to that of the optimal strategy from richer class and construct hard instances showing the tightness of $\alpha$. Our algorithm achieves $\alpha$-approximate sublinear regret against these stronger benchmarks. Simulations on semi-synthetic auction data show that empirical richness ratios significantly outperform the theoretical worst-case bounds. The proposed safe strategies and learning algorithm extend naturally to more nuanced buyer and competitor models.

Related papers

• Learning to Lead: Incentivizing Strategic Agents in the Dark [50.93875404941184]
  We study an online learning version of the generalized principal-agent model.<n>We develop the first provably sample-efficient algorithm for this challenging setting.<n>We establish a near optimal $tildeO(sqrtT) $ regret bound for learning the principal's optimal policy.
  arXiv  Detail & Related papers  (2025-06-10T04:25:04Z)
• Best of Both Worlds: Regret Minimization versus Minimax Play [57.68976579579758]
  We show that our results allow us to guarantee to risk at most $O(1)$ loss while being able to gain $Omega(T)$ from exploitable opponents.
  arXiv  Detail & Related papers  (2025-02-17T11:04:01Z)
• Learning to Bid in Non-Stationary Repeated First-Price Auctions [20.933903777434086]
  First-price auctions have gained significant traction in digital advertising markets.<n> determining an optimal bidding strategy in first-price auctions is more complex.<n>We introduce two metrics to quantify the regularity of the bidding sequence.
  arXiv  Detail & Related papers  (2025-01-23T03:53:27Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM)<n>We study a model within this domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary.<n>We propose an algorithm namely robust contextual dueling bandits (RCDB), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
  Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning. We propose a novel concave formulation for pure-strategy bidding in first-price auctions, and use it to analyze natural Gradient-Ascent-based algorithms for this problem.
  arXiv  Detail & Related papers  (2024-02-12T01:33:33Z)
• Contextual Dynamic Pricing with Strategic Buyers [93.97401997137564]
  We study the contextual dynamic pricing problem with strategic buyers. Seller does not observe the buyer's true feature, but a manipulated feature according to buyers' strategic behavior. We propose a strategic dynamic pricing policy that incorporates the buyers' strategic behavior into the online learning to maximize the seller's cumulative revenue.
  arXiv  Detail & Related papers  (2023-07-08T23:06:42Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  We study risk-sensitive Reinforcement Learning (RL), focusing on the objective of Conditional Value at Risk (CVaR) with risk tolerance $tau$. We show the minimax CVaR regret rate is $Omega(sqrttau-1AK)$, where $A$ is the number of actions and $K$ is the number of episodes. We show that our algorithm achieves the optimal regret of $widetilde O(tau-1sqrtSAK)$ under a continuity assumption and in general attains a near
  arXiv  Detail & Related papers  (2023-02-07T02:22:31Z)
• Autoregressive Bandits [58.46584210388307]
  We propose a novel online learning setting, Autoregressive Bandits, in which the observed reward is governed by an autoregressive process of order $k$. We show that, under mild assumptions on the reward process, the optimal policy can be conveniently computed. We then devise a new optimistic regret minimization algorithm, namely, AutoRegressive Upper Confidence Bound (AR-UCB), that suffers sublinear regret of order $widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G
  arXiv  Detail & Related papers  (2022-12-12T21:37:36Z)
• Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus [48.34563955829649]
  We propose a strategy-wise concentration principle which builds a confidence interval for the joint strategy. For two-player zero-sum Markov games, by exploiting the convexity of the strategy-wise bonus, we propose an efficient algorithm. All of our algorithms can naturally take a pre-specified strategy class $Pi$ as input and output a strategy close to the best strategy in $Pi$.
  arXiv  Detail & Related papers  (2022-06-01T00:18:15Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  We casting online learning problems in which a decision maker wants to maximize their expected reward without violating a finite set of $m$m resource constraints. Our framework allows the decision maker to handle its evidence flexibility and costoretic functions.
  arXiv  Detail & Related papers  (2022-02-28T12:10:48Z)
• Stochastic Strategic Patient Buyers: Revenue maximization using posted prices [40.698164629357066]
  We consider a seller faced with buyers which have the ability to delay their decision. Each buyer's type is composed of value and patience, and it is sampled i.i.d. from a distribution. We characterize both the optimal pure strategy of the seller and the buyer's best response strategy to any seller's mixed strategy.
  arXiv  Detail & Related papers  (2022-02-12T21:11:31Z)
• Fast Rate Learning in Stochastic First Price Bidding [0.0]
  First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. We show how to achieve significantly lower regret when the opponents' maximal bid distribution is known. Our algorithms converge much faster than alternatives proposed in the literature for various bid distributions.
  arXiv  Detail & Related papers  (2021-07-05T07:48:52Z)
• Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
  We develop efficient sequential bidding strategies for repeated auctions. We provide the first parametric lower bound for this problem. We propose more explainable strategies which are reminiscent of the Explore Then Commit bandit algorithm.
  arXiv  Detail & Related papers  (2020-11-10T12:45:02Z)
• Risk-Sensitive Reinforcement Learning: Near-Optimal Risk-Sample Tradeoff in Regret [115.85354306623368]
  We study risk-sensitive reinforcement learning in episodic Markov decision processes with unknown transition kernels. We propose two provably efficient model-free algorithms, Risk-Sensitive Value Iteration (RSVI) and Risk-Sensitive Q-learning (RSQ) We prove that RSVI attains an $tildeObig(lambda(|beta| H2) cdot sqrtH3 S2AT big)$ regret, while RSQ attains an $tildeObig(lambda
  arXiv  Detail & Related papers  (2020-06-22T19:28:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.