Learning to Coordinate Bidders in Non-Truthful Auctions

• URL: http://arxiv.org/abs/2507.02801v1
• Date: Thu, 03 Jul 2025 17:03:14 GMT
• Title: Learning to Coordinate Bidders in Non-Truthful Auctions
• Authors: Hu Fu, Tao Lin,
• Abstract summary: We study the complexity of learning Bayes correlated equilibria in non-truthful auctions.<n>We prove that the BCEs can be learned with a number $tilde O(fracnvareps2)$ of samples from bidders' value.
• Score: 6.3923058661534276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In non-truthful auctions such as first-price and all-pay auctions, the independent strategic behaviors of bidders, with the corresponding equilibrium notion -- Bayes Nash equilibria -- are notoriously difficult to characterize and can cause undesirable outcomes. An alternative approach to designing better auction systems is to coordinate the bidders: let a mediator make incentive-compatible recommendations of correlated bidding strategies to the bidders, namely, implementing a Bayes correlated equilibrium (BCE). The implementation of BCE, however, requires knowledge of the distribution of bidders' private valuations, which is often unavailable. We initiate the study of the sample complexity of learning Bayes correlated equilibria in non-truthful auctions. We prove that the BCEs in a large class of non-truthful auctions, including first-price and all-pay auctions, can be learned with a polynomial number $\tilde O(\frac{n}{\varepsilon^2})$ of samples from the bidders' value distributions. Our technique is a reduction to the problem of estimating bidders' expected utility from samples, combined with an analysis of the pseudo-dimension of the class of all monotone bidding strategies of bidders.

Related papers

• Conformalized Strategy-Proof Auctions [19.750369749595734]
  Strategy-proofness is crucial as it ensures that buyers are incentivized to bid their true valuations.<n>We propose a formulation of statistical strategy-proofness auction mechanism.<n>We develop an auction acceptance rule that leverages regret predictions to guarantee that the data-driven auction mechanism meets the statistical strategy-proofness requirement with high probability.
  arXiv  Detail & Related papers  (2024-05-20T13:39:58Z)
• Towards Distribution-Agnostic Generalized Category Discovery [51.52673017664908]
  Data imbalance and open-ended distribution are intrinsic characteristics of the real visual world. We propose a Self-Balanced Co-Advice contrastive framework (BaCon) BaCon consists of a contrastive-learning branch and a pseudo-labeling branch, working collaboratively to provide interactive supervision to resolve the DA-GCD task.
  arXiv  Detail & Related papers  (2023-10-02T17:39:58Z)
• Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
  We study the problem of bidding strategies in pay-as-bid (PAB) auctions from the perspective of single bidder. We show that a utility trick enables a time algorithm to solve the offline problem where competing bids are known in advance. We also present additional findings on the characterization of PAB equilibria.
  arXiv  Detail & Related papers  (2023-07-27T20:49:28Z)
• Advancing Ad Auction Realism: Practical Insights & Modeling Implications [2.8413290300628313]
  This paper shows that one can still gain useful insight into modern ad auctions by modeling advertisers as agents governed by an adversarial bandit algorithm. We find that soft floors yield lower revenues than suitably chosen reserve prices, even restricting attention to a single query.
  arXiv  Detail & Related papers  (2023-07-21T17:45:28Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  We study a game between autobidding algorithms that compete in an online advertising platform.<n>We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
  arXiv  Detail & Related papers  (2023-01-30T21:59:30Z)
• Provable Unrestricted Adversarial Training without Compromise with Generalizability [44.02361569894942]
  Adversarial training (AT) is widely considered as the most promising strategy to defend against adversarial attacks. The existing AT methods often achieve adversarial robustness at the expense of standard generalizability. We propose a novel AT approach called Provable Unrestricted Adversarial Training (PUAT)
  arXiv  Detail & Related papers  (2023-01-22T07:45:51Z)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  We study reserve price optimization in multi-phase second price auctions. From the seller's perspective, we need to efficiently explore the environment in the presence of potentially nontruthful bidders. Third, the seller's per-step revenue is unknown, nonlinear, and cannot even be directly observed from the environment.
  arXiv  Detail & Related papers  (2022-10-19T03:49:05Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• Multi-Stage Decentralized Matching Markets: Uncertain Preferences and Strategic Behaviors [91.3755431537592]
  This article develops a framework for learning optimal strategies in real-world matching markets. We show that there exists a welfare-versus-fairness trade-off that is characterized by the uncertainty level of acceptance. We prove that participants can be better off with multi-stage matching compared to single-stage matching.
  arXiv  Detail & Related papers  (2021-02-13T19:25:52Z)
• A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling [19.453243313852557]
  Empirical Revenue Maximization (ERM) is one of the most important price learning algorithms in auction design. We generalize the definition of an incentive-awareness measure proposed by Lavi et al to quantify the reduction of ERM's outputted price due to a change of $mge 1$ out of $N$ input samples. We construct an efficient, approximately incentive-compatible, and revenue-optimal learning algorithm using ERM in repeated auctions against non-myopic bidders, and show approximate group incentive-compatibility in uniform-price auctions.
  arXiv  Detail & Related papers  (2020-10-12T08:20:35Z)
• Learning Utilities and Equilibria in Non-Truthful Auctions [11.682943354386868]
  We show that $tilde O(n / epsilon2)$ samples from the prior with $n$ agents suffice for an algorithm to learn the interim utilities for all bidding strategies. We also consider a setting where agents must pay a search cost to discover their own types.
  arXiv  Detail & Related papers  (2020-07-03T14:44:33Z)
• Foreseeing the Benefits of Incidental Supervision [83.08441990812636]
  This paper studies whether we can, in a single framework, quantify the benefits of various types of incidental signals for a given target task without going through experiments. We propose a unified PAC-Bayesian motivated informativeness measure, PABI, that characterizes the uncertainty reduction provided by incidental supervision signals.
  arXiv  Detail & Related papers  (2020-06-09T20:59:42Z)

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.