Double Auctions with Two-sided Bandit Feedback

• URL: http://arxiv.org/abs/2208.06536v2
• Date: Mon, 10 Jul 2023 04:50:53 GMT
• Title: Double Auctions with Two-sided Bandit Feedback
• Authors: Soumya Basu and Abishek Sankararaman
• Abstract summary: Double Auction enables decentralized transfer of goods between multiple buyers and sellers. We show with confidence bound based bidding, and Average Pricing' there is an efficient price discovery among the participants. Our paper is the first to provide decentralized learning algorithms in a two-sided market where emphboth sides have uncertain preference that need to be learned.
• Score: 11.334374665364214
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Double Auction enables decentralized transfer of goods between multiple buyers and sellers, thus underpinning functioning of many online marketplaces. Buyers and sellers compete in these markets through bidding, but do not often know their own valuation a-priori. As the allocation and pricing happens through bids, the profitability of participants, hence sustainability of such markets, depends crucially on learning respective valuations through repeated interactions. We initiate the study of Double Auction markets under bandit feedback on both buyers' and sellers' side. We show with confidence bound based bidding, and `Average Pricing' there is an efficient price discovery among the participants. In particular, the regret on combined valuation of the buyers and the sellers -- a.k.a. the social regret -- is $O(\log(T)/\Delta)$ in $T$ rounds, where $\Delta$ is the minimum price gap. Moreover, the buyers and sellers exchanging goods attain $O(\sqrt{T})$ regret, individually. The buyers and sellers who do not benefit from exchange in turn only experience $O(\log{T}/ \Delta)$ regret individually in $T$ rounds. We augment our upper bound by showing that $\omega(\sqrt{T})$ individual regret, and $\omega(\log{T})$ social regret is unattainable in certain Double Auction markets. Our paper is the first to provide decentralized learning algorithms in a two-sided market where \emph{both sides have uncertain preference} that need to be learned.

Related papers

• Fair Online Bilateral Trade [20.243000364933472]
  We present a complete characterization of the regret for fair gain from trade when, after each interaction, the platform only learns whether each trader accepted the current price. We conclude by providing tight regret bounds when, after each interaction, the platform is allowed to observe the true traders' valuations.
  arXiv  Detail & Related papers  (2024-05-22T18:49:11Z)
• Bandit Sequential Posted Pricing via Half-Concavity [12.373936155910934]
  We study sequential posted pricing in the bandit learning model. In each round the seller posts $n$ prices for the $n$ buyers and the first buyer with a valuation higher than the price takes the item. Our main results obtain nearly-optimal regret bounds for single-item sequential posted pricing.
  arXiv  Detail & Related papers  (2023-12-20T06:34:15Z)
• An Online Learning Theory of Brokerage [3.8059763597999012]
  We investigate brokerage between traders from an online learning perspective. Unlike other bilateral trade problems already studied, we focus on the case where there are no designated buyer and seller roles. We show that the optimal rate degrades to $sqrtT$ in the first case, and the problem becomes unlearnable in the second.
  arXiv  Detail & Related papers  (2023-10-18T17:01:32Z)
• Identifying key players in dark web marketplaces [58.720142291102135]
  This paper aims to identify the key players in Bitcoin transaction networks linked to dark markets. We show that a large fraction of the traded volume is concentrated in a small group of elite market participants. Our findings suggest that understanding the behavior of key players in dark web marketplaces is critical to effectively disrupting illegal activities.
  arXiv  Detail & Related papers  (2023-06-15T20:30:43Z)
• Improving Language Model Negotiation with Self-Play and In-Context Learning from AI Feedback [97.54519989641388]
  We study whether multiple large language models (LLMs) can autonomously improve each other in a negotiation game by playing, reflecting, and criticizing. Only a subset of the language models we consider can self-play and improve the deal price from AI feedback.
  arXiv  Detail & Related papers  (2023-05-17T11:55:32Z)
• Repeated Bilateral Trade Against a Smoothed Adversary [5.939280057673226]
  We study repeated bilateral trade where an adaptive $sigma$-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models.
  arXiv  Detail & Related papers  (2023-02-21T16:30:10Z)
• Uniswap Liquidity Provision: An Online Learning Approach [49.145538162253594]
  Decentralized Exchanges (DEXs) are new types of marketplaces leveraging technology. One such DEX, Uniswap v3, allows liquidity providers to allocate funds more efficiently by specifying an active price interval for their funds. This introduces the problem of finding an optimal strategy for choosing price intervals. We formalize this problem as an online learning problem with non-stochastic rewards.
  arXiv  Detail & Related papers  (2023-02-01T17:21:40Z)
• 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. 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)
• 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)
• Bilateral Trade: A Regret Minimization Perspective [5.031063690574698]
  We cast the bilateral trade problem in a regret minimization framework over $T$ rounds of seller/buyer interactions. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different feedback models and private valuations.
  arXiv  Detail & Related papers  (2021-09-08T22:11:48Z)
• Bandit Learning in Decentralized Matching Markets [82.39061186055775]
  We study two-sided matching markets in which one side of the market (the players) does not have a priori knowledge about its preferences for the other side (the arms) and is required to learn its preferences from experience. This model extends the standard multi-armed bandit framework to a decentralized multiple player setting with competition. We show that the algorithm is incentive compatible whenever the arms' preferences are shared, but not necessarily so when preferences are fully general.
  arXiv  Detail & Related papers  (2020-12-14T08:58:07Z)

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.