Profit Maximization in Bilateral Trade against a Smooth Adversary

• URL: http://arxiv.org/abs/2605.12664v1
• Date: Tue, 12 May 2026 19:12:57 GMT
• Title: Profit Maximization in Bilateral Trade against a Smooth Adversary
• Abstract summary: Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good.<n>We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary.<n>We devise a learning algorithm that guarantees a $tildeO(sqrtT)$ regret bound, which is tight in the time horizon $T$ poly-logarithmic factors.
• Score: 14.182863671689836
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a $\tilde{O}(\sqrt{T})$ regret bound, which is tight in the time horizon $T$ up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight $\tilde{O}(\sqrt{T})$ regret bound for a related mechanism design model: the joint ads problem.

Related papers

• Mitigating Anchoring Bias in LLM-Based Agents for Energy-Efficient 6G Autonomous Networks [3.2715455153948256]
  This paper presents an autonomous agentic resource negotiation framework designed to enable zero-touch network slicing in 6G architectures using Large Language Model (LLM) agents.<n>We show that such agents inherently suffer from anchoring bias, rigidly adhering to initial proposals and causing severe network over-provisioning.<n>Our cognitive de-biasing successfully dismantles rigid negotiation patterns, forcing agents into active exploration to safely ride SLA boundaries and boost system energy savings up to 25%.
  arXiv  Detail & Related papers  (2026-06-05T08:29:03Z)
• Regret Minimization in Bilateral Trade With Perturbed Markets [25.375074054942434]
  We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints.<n> adversarial environments allow for no-regret learning against the best fixed-price mechanism.<n>Our algorithm maintains the worst-case $tildemathcalO(T3/4)$ regret bound relative to a per-round budget-balanced baseline.
  arXiv  Detail & Related papers  (2026-05-11T12:37:53Z)
• Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade [14.182863671689836]
  Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations.<n>We study this problem from the perspective of a broker, in a regret minimization framework.<n>We propose a learning algorithm that guarantees a nearly tight $tildeO(sqrtT)$ regret when seller and valuations are drawn.
  arXiv  Detail & Related papers  (2025-09-26T16:42:05Z)
• Competing Bandits in Decentralized Contextual Matching Markets [13.313881962771777]
  We study decentralized learning in two-sided matching markets where the demand side (aka players or agents) competes for the supply side (aka arms)<n>Motivated by the linear contextual bandit framework, we assume that for each agent, an arm-mean may be represented by a linear function of a known feature vector and an unknown (agent-specific) parameter.<n>We propose learning algorithms to identify the latent environment and obtain stable matchings simultaneously.
  arXiv  Detail & Related papers  (2024-11-18T18:08:05Z)
• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand) This problem captures, for example, situations where a merchant and a brand bid cooperatively in an auction to advertise a product, and both benefit from the ad being shown. A mechanism collects bids from the two and decides whether to allocate and which payments the two parties should make.
  arXiv  Detail & Related papers  (2024-09-12T07:59:10Z)
• Multi-Agent Imitation Learning: Value is Easy, Regret is Hard [52.31989962031179]
  We study a multi-agent imitation learning (MAIL) problem where we take the perspective of a learner attempting to coordinate a group of agents. Most prior work in MAIL essentially reduces the problem to matching the behavior of the expert within the support of the demonstrations. While doing so is sufficient to drive the value gap between the learner and the expert to zero under the assumption that agents are non-strategic, it does not guarantee to deviations by strategic agents.
  arXiv  Detail & Related papers  (2024-06-06T16:18:20Z)
• 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)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds [31.5504566292927]
  We consider a linear bandit problem involving $M$ agents that can collaborate via a central server to minimize regret. A fraction $alpha$ of these agents are adversarial and can act arbitrarily, leading to the following tension. We design new algorithms that balance the exploration-exploitation trade-off via carefully constructed robust confidence intervals.
  arXiv  Detail & Related papers  (2022-06-06T18:16:34Z)
• 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)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Online Adversarial Attacks [57.448101834579624]
  We formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases. We first rigorously analyze a deterministic variant of the online threat model. We then propose algoname, a simple yet practical algorithm yielding a provably better competitive ratio for $k=2$ over the current best single threshold algorithm.
  arXiv  Detail & Related papers  (2021-03-02T20:36:04Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

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.