Conformalized Strategy-Proof Auctions

• URL: http://arxiv.org/abs/2405.12016v4
• Date: Mon, 10 Feb 2025 17:06:04 GMT
• Title: Conformalized Strategy-Proof Auctions
• Authors: Roy Maor Lotan, Inbal Talgam-Cohen, Yaniv Romano,
• Abstract summary: 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.
• Score: 19.750369749595734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Auctions are key for maximizing sellers' revenue and ensuring truthful bidding among buyers. Recently, an approach known as differentiable economics based on machine learning (ML) has shown promise in learning powerful auction mechanisms for multiple items and participants. However, this approach has no guarantee of strategy-proofness at test time. Strategy-proofness is crucial as it ensures that buyers are incentivized to bid their true valuations, leading to optimal and fair auction outcomes without the risk of manipulation. In this work, we propose a formulation of statistical strategy-proofness auction mechanism, ensuring that the probability of regret exceeding a predefined threshold is strictly controlled. Building upon conformal prediction techniques, 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. Our approach represents a practical middle-ground between two extremes: forcing zero-regret at the cost of significant revenue loss, and naively using ML to construct auctions with the hope of attaining low regret at test time. Numerical experiments demonstrate the necessity of the proposed method, the validity of our theoretical result, and its applicability.

Related papers

• From No-Regret to Strategically Robust Learning in Repeated Auctions [0.5076419064097732]
  We show that any no-regret learning algorithm, when fed gradient feedback with respect to the quantile representation, is strategically robust.<n>In particular, the multiplicative weights update (MWU) algorithm simultaneously achieves the optimal regret guarantee and the best-known strategic robustness guarantee.
  arXiv  Detail & Related papers  (2026-01-07T12:09:13Z)
• Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets [57.179679246370114]
  In financial applications, reinforcement learning (RL) agents are commonly trained on historical data, where their actions do not influence prices.<n>During deployment, these agents trade in live markets where their own transactions can shift asset prices, a phenomenon known as market impact.<n>Traditional robust RL approaches address this model misspecification by optimizing the worst-case performance over a set of uncertainties.<n>We develop a novel class of elliptic uncertainty sets, enabling efficient and tractable robust policy evaluation.
  arXiv  Detail & Related papers  (2025-10-22T18:22:25Z)
• PAC Apprenticeship Learning with Bayesian Active Inverse Reinforcement Learning [59.93251770120936]
  Inverse reinforcement learning (IRL) offers a promising approach to infer preferences from demonstrations.<n>We introduce PAC-EIG, an information-theoretic acquisition function that directly targets probably-approximately-correct (PAC) guarantees for the learned policy.<n>Our method maximises information gain about the regret of the apprentice policy, efficiently identifying states requiring further demonstration.
  arXiv  Detail & Related papers  (2025-08-05T17:59:56Z)
• Learning to Coordinate Bidders in Non-Truthful Auctions [9.642382646285805]
  We study the complexity of learning Bayes correlated equilibria in non-truthful auctions.<n>We prove that the set of strategic-form BCEs can be learned with a number $tilde O(fracnvarepsilon2)$ of samples of bidders' values.<n>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.
  arXiv  Detail & Related papers  (2025-07-03T17:03:14Z)
• Dynamic Reinsurance Treaty Bidding via Multi-Agent Reinforcement Learning [0.0]
  This paper develops a novel multi-agent reinforcement learning (MARL) framework for reinsurance treaty bidding.<n>MARL agents achieve up to 15% higher underwriting profit, 20% lower tail risk, and over 25% improvement in Sharpe ratios.<n>These findings suggest that MARL offers a viable path toward more transparent, adaptive, and risk-sensitive reinsurance markets.
  arXiv  Detail & Related papers  (2025-06-16T05:43:22Z)
• Shill Bidding Prevention in Decentralized Auctions Using Smart Contracts [0.0]
  This paper presents a conceptual framework that applies dynamic, behavior-based penalties to deter auction fraud using blockchain smart contracts.<n>The framework employs the proposed Bid Shill Score (BSS) to evaluate nine distinct bidding behaviors.<n>Performance evaluation shows that the system introduces only moderate gas and latency overhead, keeping transaction costs and response times within practical bounds for real-world use.
  arXiv  Detail & Related papers  (2025-05-30T22:23:29Z)
• Learning to Bid in Non-Stationary Repeated First-Price Auctions [20.933903777434086]
  First-price auctions have gained significant traction in digital advertising markets. determining an optimal bidding strategy in first-price auctions is more complex. We introduce two metrics to quantify the regularity of the bidding sequence.
  arXiv  Detail & Related papers  (2025-01-23T03:53:27Z)
• Strategic Conformal Prediction [0.66567375919026]
  When a machine learning model is deployed, its predictions can alter its environment, as better informed agents strategize to suit their own interests. We propose a new framework, Strategic Conformal Prediction, which is capable of robust uncertainty quantification in such a setting.
  arXiv  Detail & Related papers  (2024-11-03T15:06:05Z)
• Conformal Counterfactual Inference under Hidden Confounding [19.190396053530417]
  Predicting potential outcomes along with its uncertainty in a counterfactual world poses the foundamental challenge in causal inference. Existing methods that construct confidence intervals for counterfactuals either rely on the assumption of strong ignorability. We propose a novel approach based on transductive weighted conformal prediction, which provides confidence intervals for counterfactual outcomes with marginal converage guarantees.
  arXiv  Detail & Related papers  (2024-05-20T21:43:43Z)
• The Pitfalls and Promise of Conformal Inference Under Adversarial Attacks [90.52808174102157]
  In safety-critical applications such as medical imaging and autonomous driving, it is imperative to maintain both high adversarial robustness to protect against potential adversarial attacks. A notable knowledge gap remains concerning the uncertainty inherent in adversarially trained models. This study investigates the uncertainty of deep learning models by examining the performance of conformal prediction (CP) in the context of standard adversarial attacks.
  arXiv  Detail & Related papers  (2024-05-14T18:05:19Z)
• Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce [6.241187362917031]
  We introduce the Conformal Online Auction Design (COAD), a novel mechanism that maximizes revenue by quantifying uncertainty in bidder values without relying on known distributions.<n>COAD incorporates both bidder and item features, using historical data to design an incentive-compatible mechanism for online auctions.<n>We demonstrate the practical effectiveness of COAD through an application to real-world eBay auction data.
  arXiv  Detail & Related papers  (2024-05-11T15:28:25Z)
• Mimicking Better by Matching the Approximate Action Distribution [48.95048003354255]
  We introduce MAAD, a novel, sample-efficient on-policy algorithm for Imitation Learning from Observations. We show that it requires considerable fewer interactions to achieve expert performance, outperforming current state-of-the-art on-policy methods.
  arXiv  Detail & Related papers  (2023-06-16T12:43:47Z)
• Robust multi-item auction design using statistical learning: Overcoming uncertainty in bidders' types distributions [6.5920927560926295]
  Our proposed approach utilizes nonparametric density estimation to accurately estimate bidders' types from historical bids. To further enhance efficiency of our mechanism, we introduce two novel strategies for query reduction. Simulation experiments conducted on both small-scale and large-scale data demonstrate that our mechanism consistently outperforms existing methods in terms of revenue design and query reduction.
  arXiv  Detail & Related papers  (2023-02-02T08:32:55Z)
• Adaptive Risk-Aware Bidding with Budget Constraint in Display Advertising [47.14651340748015]
  We propose a novel adaptive risk-aware bidding algorithm with budget constraint via reinforcement learning. We theoretically unveil the intrinsic relation between the uncertainty and the risk tendency based on value at risk (VaR)
  arXiv  Detail & Related papers  (2022-12-06T18:50:09Z)
• Conformal Off-Policy Prediction in Contextual Bandits [54.67508891852636]
  Conformal off-policy prediction can output reliable predictive intervals for the outcome under a new target policy. We provide theoretical finite-sample guarantees without making any additional assumptions beyond the standard contextual bandit setup.
  arXiv  Detail & Related papers  (2022-06-09T10:39:33Z)
• Bayesian Bilinear Neural Network for Predicting the Mid-price Dynamics in Limit-Order Book Markets [84.90242084523565]
  Traditional time-series econometric methods often appear incapable of capturing the true complexity of the multi-level interactions driving the price dynamics. By adopting a state-of-the-art second-order optimization algorithm, we train a Bayesian bilinear neural network with temporal attention. By addressing the use of predictive distributions to analyze errors and uncertainties associated with the estimated parameters and model forecasts, we thoroughly compare our Bayesian model with traditional ML alternatives.
  arXiv  Detail & Related papers  (2022-03-07T18:59:54Z)
• 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)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)
• CoinDICE: Off-Policy Confidence Interval Estimation [107.86876722777535]
  We study high-confidence behavior-agnostic off-policy evaluation in reinforcement learning. We show in a variety of benchmarks that the confidence interval estimates are tighter and more accurate than existing methods.
  arXiv  Detail & Related papers  (2020-10-22T12:39:11Z)
• ProportionNet: Balancing Fairness and Revenue for Auction Design with Deep Learning [55.76903822619047]
  We study the design of revenue-maximizing auctions with strong incentive guarantees. We extend techniques for approximating auctions using deep learning to address concerns of fairness while maintaining high revenue and strong incentive guarantees.
  arXiv  Detail & Related papers  (2020-10-13T13:54:21Z)
• A Generic Methodology for the Statistically Uniform & Comparable Evaluation of Automated Trading Platform Components [2.28438857884398]
  The proposed methodology is showcased on two automated trading platform components. Namely, price levels, a well-known trading pattern, and a novel 2-step feature extraction method. The main hypothesis was formulated to evaluate whether the selected trading pattern is suitable for use in the machine learning setting.
  arXiv  Detail & Related papers  (2020-09-21T16:17:42Z)
• Certifying Strategyproof Auction Networks [53.37051312298459]
  We focus on the RegretNet architecture, which can represent auctions with arbitrary numbers of items and participants. We propose ways to explicitly verify strategyproofness under a particular valuation profile using techniques from the neural network verification literature.
  arXiv  Detail & Related papers  (2020-06-15T20:22:48Z)
• Optimal Bidding Strategy without Exploration in Real-time Bidding [14.035270361462576]
  maximizing utility with a budget constraint is the primary goal for advertisers in real-time bidding (RTB) systems. Previous works ignore the losing auctions to alleviate the difficulty with censored states. We propose a novel practical framework using the maximum entropy principle to imitate the behavior of the true distribution observed in real-time traffic.
  arXiv  Detail & Related papers  (2020-03-31T20:43:28Z)

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.