Paper: arXiv 2405.13102
Authors: Tommaso Cesari, Roberto Colomboni
Abstract
We explore brokerage between traders in an online learning framework. At any round \(t\), two traders meet to exchange an asset, provided the exchange is mutually beneficial. The broker proposes a trading price, and each trader tries to sell their asset or buy the asset from the other party, depending on whether the price is higher or lower than their private valuations. A trade happens if one trader is willing to sell and the other is willing to buy at the proposed price. Previous work provided guidance to a broker aiming at enhancing traders’ total earnings by maximizing the gain from trade, defined as the sum of the traders’ net utilities after each interaction. In contrast, we investigate how the broker should behave to maximize the trading volume, i.e., the total number of trades. We model the traders’ valuations as an i.i.d. process with an unknown distribution. If the traders’ valuations are revealed after each interaction (full-feedback), and the traders’ valuations cumulative distribution function (cdf) is continuous, we provide an algorithm achieving logarithmic regret and show its optimality up to constant factors. If only their willingness to sell or buy at the proposed price is revealed after each interaction (\(2\)-bit feedback), we provide an algorithm achieving poly-logarithmic regret when the traders’ valuations cdf is Lipschitz and show that this rate is near-optimal. We complement our results by analyzing the implications of dropping the regularity assumptions on the unknown traders’ valuations cdf. If we drop the continuous cdf assumption, the regret rate degrades to \(Θ(\sqrt{“T”})\) in the full-feedback case, where \(T\) is the time horizon. If we drop the Lipschitz cdf assumption, learning becomes impossible in the \(2\)-bit feedback case.
Complexity vs Empirical Score
- Math Complexity: 7.5/10
- Empirical Rigor: 2.0/10
- Quadrant: Lab Rats — high math complexity, limited empirical testing
Why this score: The paper is dense with advanced mathematical theory, including regret analysis, lower bounds, and algorithm design in an online learning setting, but lacks any empirical validation, backtesting, or implementation details beyond theoretical algorithms.
Research Flowchart
flowchart TD
A["Research Goal: How should a broker maximize<br>trading volume in an online learning setting?"] --> B["Model Setup"]
B --> C{"Trader Valuation CDF Type"}
C -->|"Continuous & Known"| D["Full-Feedback Setting"]
C -->|"Lipschitz & Known"| E["2-Bit Feedback Setting"]
C -->|"Discontinuous / Unknown"| F["Drop Regularity Assumptions"]
D --> G["Algorithm: Propose Prices at<br>Quantiles of Empirical CDF"]
E --> H["Algorithm: Discretize Valuations<br>& Explore-Exploit Strategy"]
F --> I["Regret increases to Θ√T or<br>Learning becomes impossible"]
G --> J["Outcome: Logarithmic Regret<br>(Optimal up to constants)"]
H --> K["Outcome: Poly-Logarithmic Regret<br>(Near-optimal)"]
I --> L["Outcome: Degraded Performance<br>No poly-log regret possible"]
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 online learning algorithms for a broker to maximize trading volume (the total number of trades) under different feedback models.
Source sentence
In contrast, we investigate how the broker should behave to maximize the trading volume, i.e., the total number of trades. 1.2 Overview of Our Contributions In the full-feedback case, if the distribution ν of the traders’ valuations has a continuous cdf, we design an algorithm (Algorithm 1) suffering O(ln T ) regret in the time horizon T (Theorem 1), and we provide a matching lower bound (Theorem 2).
Assumes 6
- Traders' valuations are drawn i.i.d. from an unknown distribution. statistical
Source sentence
We model the traders' valuations as an i.i.d. process with an unknown distribution.
- In the full‑feedback case the valuation distribution has a continuous cumulative distribution function. statistical
Source sentence
If the traders' valuations are revealed after each interaction (full-feedback), and the traders' valuations cumulative distribution function (cdf) is continuous, we provide an algorithm achieving logarithmic regret and show its optimality up to constant factors.
- In the 2‑bit feedback case the valuation distribution’s cdf is Lipschitz. statistical
Source sentence
If only their willingness to sell or buy at the proposed price is revealed after each interaction ($2$-bit feedback), we provide an algorithm achieving poly-logarithmic regret when the traders' valuations cdf is Lipschitz and show that this rate is near-optimal.
- Traders have no fixed buyer or seller roles and can sell or buy depending on the posted price. market
Source sentence
1.5 Limitations This paper investigates a setting where traders lack rigid buyer/seller roles.
Show 2 more
- The analysis focuses on an i.i.d. setting; results may not extend to non‑i.i.d. environments. model
Source sentence
Another conceivable limitation of this work is our focus on an i.i.d. setting.
- Fast regret rates rely on regularity assumptions (continuity or Lipschitzness) of the valuation cdf. statistical
Source sentence
Lastly, we obtain fast regret rates only under regularity assumptions on the cdf of the traders’ valuations.
Data
No dataset named in the text.
Costs
Not applicable
Finds 5
- With full‑feedback and a continuous cdf, the proposed algorithm achieves O(log T) regret, which is optimal up to constant factors. theoretical
Source sentence
If the traders' valuations are revealed after each interaction (full-feedback), and the traders' valuations cumulative distribution function (cdf) is continuous, we provide an algorithm achieving logarithmic regret and show its optimality up to constant factors. 1.2 Overview of Our Contributions In the full-feedback case, if the distribution ν of the traders’ valuations has a continuous cdf, we design an algorithm
- If the continuous‑cdf assumption is dropped, regret degrades to Θ(√T) in the full‑feedback case. theoretical
Source sentence
If we drop the continuous cdf assumption, the regret rate degrades to $Θ(\sqrt{T})$ in the full-feedback case, where $T$ is the time horizon.
- In the 2‑bit feedback case with a Lipschitz cdf, the binary‑search‑based algorithm attains O(log(MT)·log T) regret, which is near‑optimal up to a log T factor. theoretical
Source sentence
In contrast, we exploit the extra information provided by the 2-bit feedback and the intuition provided by Lemma 1 to devise a binary search algorithm achieving the exponentially better rate of O(ln(MT )lnT ), 3 with the additional feature of being oblivious to M. Our corresponding lower bound shows that this rate is optimal (up to a ln T factor), Interestingly, using our different reward function, we achieve an
- Removing the Lipschitz cdf assumption makes learning impossible in the 2‑bit feedback setting. negative
Source sentence
If we drop the Lipschitz cdf assumption, learning becomes impossible in the $2$-bit feedback case. If the Lipschitz cdf assumption is removed, the learning rate for both our problem and the one in [6] degrades to Θ( √ T) in the full-feedback case, and the problem becomes unlearnable in the 2-bit feedback case.
- Compared to prior work on gain‑from‑trade, the new volume‑maximization objective yields exponentially faster regret bounds under the same regularity conditions. theoretical
Source sentence
Surprisingly, in the same full-feedback case, but using our different reward function, we achieve a Θ(lnT ) regret rate even when the cdf is only continuous: in our case, the additional Lipschitz regularity does not offer any speedup once the continuity assumption is fulfilled. Interestingly, using our different reward function, we achieve an exponentially faster upper bound of O(ln(MT )lnT ), which is tight up to a ln
Checked by others
No other paper in the archive has been found to support or contradict these findings (compared with 9 related papers). Coverage is partial, so this is neither replication nor refutation.
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.