Paper: arXiv 2411.13993

Authors: Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak

Abstract

We consider a sequential decision-making setting where, at every round \(t\), a market maker posts a bid price \(B_t\) and an ask price \(A_t\) to an incoming trader (the taker) with a private valuation for one unit of some asset. If the trader’s valuation is lower than the bid price, or higher than the ask price, then a trade (sell or buy) occurs. If a trade happens at round \(t\), then letting \(M_t\) be the market price (observed only at the end of round \(t\)), the maker’s utility is \(M_t - B_t\) if the maker bought the asset, and \(A_t - M_t\) if they sold it. We characterize the maker’s regret with respect to the best fixed choice of bid and ask pairs under a variety of assumptions (adversarial, i.i.d., and their variants) on the sequence of market prices and valuations. Our upper bound analysis unveils an intriguing connection relating market making to first-price auctions and dynamic pricing. Our main technical contribution is a lower bound for the i.i.d. case with Lipschitz distributions and independence between prices and valuations. The difficulty in the analysis stems from the unique structure of the reward and feedback functions, allowing an algorithm to acquire information by graduating the “cost of exploration” in an arbitrary way.

Complexity vs Empirical Score

  • Math Complexity: 8.5/10
  • Empirical Rigor: 3.0/10
  • Quadrant: Lab Rats — high math complexity, limited empirical testing

Why this score: The paper presents heavy theoretical analysis with dense mathematical formalism (online learning, regret bounds, Lipschitz distributions, lower bounds), placing it in the ‘Lab Rats’ quadrant due to high math complexity and low empirical rigor.

Research Flowchart

  flowchart TD
  A["Research Goal"] --> B["Modeling & Setup"]
  B --> C["Regret Analysis"]
  C --> D{"Assumption on<br>Market & Valuation"}
  D --> E["Adversarial Case"]
  D --> F["I.I.D. Case"]
  E --> G["Regret Bound via<br>Adversarial Dynamic Pricing"]
  F --> H["Lower Bound Derivation<br>with Lipschitz Distributions"]
  G --> I["Key Outcomes<br>Regret Bounds & Connection to<br>First-Price Auctions / Dynamic Pricing"]
  H --> I

Evidence Card

What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card

Proposes

The paper proposes an online learning algorithm for market making that posts bid and ask prices each round and achieves regret bounds by reducing the problem to repeated first‑price auctions and dynamic pricing.

Source sentence
Our contributions We study the question of market making in an online learning setup. We thus obtain an algorithm for market-making and we show in Theorem 1 that its regret can be upper bounded by the sum of the regrets of the two sub-algorithms for the two corresponding sub-problems.

Assumes 6

  • An unknown stochastic process governs the market prices and private valuations of traders. statistical
    Source sentence
    Here, trading happens in discrete time steps and an unknown stochastic process governs the prices of the asset being traded as well as the private valuations assigned to the asset by market participants (see details in Section 2).
  • The market maker offloads its position shortly after each transaction. execution
    Source sentence
    For these reasons, we focus on a setting where the market maker offloads their positions shortly after each transaction. 1.1.
  • In the i.i.d. case, market prices and takers’ valuations are independent of each other. statistical
    Source sentence
    T 2/3 Lower Bound (iid+lip+iv) In this section, we present the main result of this work, a lower bound showing that no algorithm can achieve a worst-case regret better than Ω(T 2/3) even when the sequence of market prices and takers’ valuations is i.i.d. with a smooth distribution, and market prices and takers’ valuations are independent of each other.
  • Distributions of market prices and valuations are L‑Lipschitz. statistical
    Source sentence
    Our main technical contribution is a lower bound for the i.i.d. case with Lipschitz distributions and independence between prices and valuations.
Show 2 more
  • The bid posted in the first‑price auction must not exceed the price posted in the dynamic pricing sub‑problem. model
    Source sentence
    However, in our problem we have the further constraint that the bid we propose in the first-price auction is no greater than the price we propose in the dynamic pricing problem.
  • The utility of the market maker is the sum of utilities from the first‑price auction and the dynamic pricing components. model
    Source sentence
    The idea of our meta-algorithm M3 (Algo-rithm 2) begins with the observation that the utility of the market maker is a sum of two terms that correspond to the utilities of the learner in first-price auctions and dynamic pricing, respectively.

Data

No dataset named in the text.

Costs

Not applicable The paper reports no trading or execution result.

Finds 5

  • The regret of the proposed market‑making algorithm is upper‑bounded by the sum of the regrets of the two sub‑algorithms for first‑price auctions and dynamic pricing. theoretical
    Source sentence
    We thus obtain an algorithm for market-making and we show in Theorem 1 that its regret can be upper bounded by the sum of the regrets of the two sub-algorithms for the two corresponding sub-problems.
  • A lower bound of Ω(T^{2/3}) on regret holds for any algorithm in the i.i.d. smooth setting with independent prices and valuations. theoretical
    Source sentence
    T 2/3 Lower Bound (iid+lip+iv) In this section, we present the main result of this work, a lower bound showing that no algorithm can achieve a worst-case regret better than Ω(T 2/3) even when the sequence of market prices and takers’ valuations is i.i.d. with a smooth distribution, and market prices and takers’ valuations are independent of each other.
  • All regret rates proved are optimal up to constant factors for the various problem variants. theoretical
    Source sentence
    All the rates are optimal up to constant factors. 1.2.
  • The paper establishes a connection between market making, first‑price auctions, and dynamic pricing. theoretical
    Source sentence
    Our upper bound analysis unveils an intriguing connection relating market making to first-price auctions and dynamic pricing.
  • The work initiates the study of market making under online learning and provides tight regret bounds, highlighting the role of liquidity providers. theoretical
    Source sentence
    6. Conclusions and Future Directions We initiated an investigation of market making under an online learning framework and provided tight bounds on the regret under various natural assumptions.

Checked by others

No other paper in the archive has been found to support or contradict these findings (compared with 12 related papers). Coverage is partial, so this is neither replication nor refutation.

Cited by 5 papers in the archive (3 by independent authors): Multi-Task Dynamic Pricing in Credit Market with Contextual … (extends it)

Code

No repository by the authors found in the paper.

Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.