Source-linked AI summary
Support-Dependent Regret Rates for Profit Maximization in Multilateral Trade
Francesco Bacchiocchi, Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
TL;DR
The paper studies online profit maximization in multilateral trade with unknown, finitely supported marginal valuations and arbitrary dependence across agents. It uses the support-induced candidate structure to learn prices and payments, establishing a support-dependent regret guarantee for constant dimension.
Problem
In multilateral trade with unknown joint valuations, the intermediary must learn fixed prices and payments from trade feedback when marginal supports are unknown and may be arbitrarily correlated.
Source: §1 · pp. 1–2Method
The approach exploits the finite grid induced by marginal supports and adaptively identifies useful candidate actions despite unknown support locations.
Source: §1 · p. 2, A Small Set of Candidate Solutions · p. 3Results
For constant dimension, the algorithm achieves a support-dependent regret guarantee that applies to multilateral trade with a constant number of agents.
Source: §1.1 · p. 2Takeaways & Limitations
Finite marginal supports extend support-dependent online pricing guarantees to multilateral trade, even when agents’ valuations may be correlated.
Source: §1 · p. 2The guarantee assumes each agent’s marginal valuation has finite support of size at most K, though the joint distribution may be arbitrarily correlated.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We study online profit maximization in multilateral trade, a setting that generalizes both dynamic pricing and bilateral trade. At each round, an intermediary posts prices to buyers and offers payments to sellers; trade occurs only if every agent accepts. We consider valuations drawn from an unknown joint distribution, allowing arbitrary correlation across agents, under the assumption that each agent's marginal valuation distribution has unknown support of size at most $K$. For constant dimension $d$, we design an algorithm with regret $\widetilde O(\sqrt{K^dT})$. This extends optimal support-dependent guarantees for one-dimensional dynamic pricing to the multidimensional setting of multilateral trade. At the core of our approach is a normalized zooming procedure that adapts to the local probability of trade, avoiding the excessive refinement of nearly flat regions that can arise with standard zooming.
1 Introduction
The paper studies profit maximization with fixed posted prices in multilateral trade, where valuations have unknown finite marginal supports but may be arbitrarily correlated. It extends support-dependent pricing guarantees to this setting and develops an adaptive approach to unknown support-induced candidates.
1 Introduction
- Unknown finite marginal supports may be arbitrarily correlated across agents, and learning must identify useful fixed-price actions from trade feedback.The framework includes online pricing and bilateral trade as special cases.Source: §1 · pp. 1–2
1.1 Our Contributions
- For constant dimension, the algorithm gives a support-dependent regret guarantee that also applies to multilateral trade with a constant number of agents.The paper extends support-dependent guarantees from one-dimensional pricing to multilateral trade.Source: §1.1 · p. 2, §1 · p. 2
- Known supports induce at most O(K^d) candidate grid points because trade probability is constant within each support-defined cell and the best point is its smallest corner.The challenge is that support locations, and therefore the candidate actions, are unknown.Source: §1 · p. 2, A Small Set of Candidate Solutions · p. 3
A Small Set of Candidate Solutions
- Standard zooming can over-refine low-trade-probability cells, while probability-normalized splitting adapts refinement to local trade probability.The rule balances finding accurate actions near an optimal support threshold against avoiding repeated subdivision of low-variation regions.Source: A Small Set of Candidate Solutions · pp. 3–4
A Tight Lower Bound
- A matching support-dependent lower bound makes the upper bound optimal up to logarithmic factors when K ≤ T^(1/3d), while the large-support regime remains open.The lower-bound construction uses exponentially many support-induced cells.Source: A Tight Lower Bound · p. 4
1.2 Related Work
- Related work covers gain-from-trade feedback and adversarial or stochastic guarantees, as well as contextual, fairness, and multi-buyer trade settings.These works address varying feedback models, benchmarks, and market structures.Source: §1.2 · pp. 4–5
2 Preliminaries
The preliminaries formulate the learner’s task using lower-orthant feedback and a reward determined by the action and trade probability. Finite marginal supports induce a finite grid, and multilateral trade can be represented in this formulation by reversing buyer coordinates.
2 Preliminaries
- Each round draws valuations independently from an unknown joint distribution, and the learner observes whether the valuation vector lies below the chosen action.The distribution may have dependence across coordinates.Source: §2 · p. 5
- The model assumes known reward parameters α and β, with the linear margin term g(x) bounded in [−1, 1].The passages introduce the lower-orthant CDF, mean reward, and pseudo-regret.Source: §2 · p. 5
- With finite coordinate supports, the induced grid has at most K^d points, and coordinatewise rounding maps eligible actions to grid points without reducing their mean reward.The origin is added to handle cases where the reward is negative at every grid point.Source: §2 · p. 5
A Special Case: Multilateral Trade
- Reversing buyer coordinates maps buyer acceptance to the lower-orthant condition, while seller offers already have that form, yielding a multilateral-trade representation.The represented trade occurs exactly when V ⪯ x, and profit is normalized to [−1, 1].Source: A Special Case: Multilateral Trade · p. 6
3 Why Does Standard Zooming Fail?
Standard zooming behaves well when purchase probability is constant, but rare purchases make many prices nearly optimal and can lead it to refine too many intervals. This motivates normalizing the refinement rule for probability of trade.
3 Why Does Standard Zooming Fail?
- When the high-valuation buyer appears with probability Θ(1), δ-optimal prices fit in a constant number of intervals, yielding eO(T) regret for Kleinberg et al. (2008).A purchase then occurs with constant probability at every positive price.Source: §3 · p. 6
- At probability ε, Θ(min {1/δ, 1/ε}) intervals cover δ-optimal prices, allowing the number of refined intervals to grow as large as eO(1/ε).The expected revenue at price p is εp, with suboptimality gap ε(1 −p).Source: §3 · p. 6
- The paper addresses this excessive refinement with a normalization that increases the reward function’s slope.Figure 2 illustrates why zooming fails and how normalization fixes the issue.Source: §3 · p. 6
4 Suboptimality and the support grid
The section characterizes how suboptimality relates to distance from the support grid. It uses asymmetric, direction-sensitive neighborhoods and a probability-weighted gap bound.
4 Suboptimality and the support grid
- The upper neighborhoods are asymmetric because the objective is only right-continuous and behaves differently along different coordinate directions.The neighborhood norm is adapted to g, which is globally Lipschitz but direction-dependent.Source: §4 · p. 7
- Only points above a support point in coordinatewise order count as its upper neighbors, with g(y) −g(x) bounded by ε..Source: §4 · p. 7
- Outside the ε-upper neighborhood of the support grid, the suboptimality gap is at least εF(x), and is strictly greater when F(x) > 0.The bound weights distance from the support grid by the CDF at x.Source: §4 · p. 7
5 Algorithm Description
Algorithm 1 applies zooming to an adaptive partition, selecting promising cells optimistically and refining them according to statistical uncertainty and probability-weighted geometric error. Its splitting rule also avoids unnecessary refinement along low-weight coordinates.
5 Algorithm Description
- The algorithm adaptively refines only cells that remain potentially optimal, using optimistic selection and a criterion balancing statistical uncertainty against spatial approximation error.It starts from a coarse discretization of the action space.Source: §5 · p. 7
- The partition consists of axis-aligned rectangles with lower and upper corners; cells are selected by maximizing an upper-confidence-based score.The score uses g(ℓA) and the upper confidence bound on F(uA).Source: §5 · pp. 7–8
- Only selected cells are split, so the active partition may contain different depths, while all cells at a given depth share the same side-length vector.Splitting a depth-h cell creates two children at depth h + 1.Source: Figure 3 · p. 8
- Refinement is triggered when statistical uncertainty is smaller than the probability-weighted geometric approximation error, subject to a maximum depth.When the optimum is small, an additional condition helps avoid over-splitting low-g(ℓA) cells.Source: §5 · p. 8
- The algorithm bisects the coordinate with the largest weighted side, halving that side; this rule avoids excessive refinement where coefficients are small.It is designed to remain suitable even for very small αi.Source: §5 · p. 8
- Each cell tracks its play count and mean observations, with confidence radii controlling uncertainty at its upper corner.The confidence parameter is set for a fixed horizon and confidence level.Source: §5 · p. 9
6 Algorithm Guarantees
The guarantees rely on a high-probability event controlling probability estimates, then bound how many cells can be created and aggregate their regret. Splits are confined to neighborhoods of the support grid.
6 Algorithm Guarantees
- Event E holds with probability at least 1 −δ, controlling the probability estimates used by the algorithm.The proof establishes this with Hoeffding’s inequality and a union bound over cells and sample counts.Source: §6 · p. 10
- Under event E, a cell is split only when it is near an element of G, with the neighborhood radius determined by the cell’s g-radius.Smaller cells must be closer to a support-grid element to be split.Source: §6 · p. 10
- At each depth h ≤H, at most 2 (12d + 2)^d |G| cells are ever created under event E.The proof bounds the total number of created cells by summing across depths and including the root.Source: §6 · p. 10
- The regret analysis bounds per-cell regret, uses the cell-count bound, and aggregates contributions across cells with Cauchy-Schwarz.The proof distinguishes cells below the maximum depth from cells at depth H.Source: §6 · pp. 10–11
7 A Tight Lower Bound
The section constructs hard instances to establish a support-dependent regret lower bound. It shows the upper bound is tight up to logarithmic factors when K ≤ T^(1/(3d)), while the large-support regime remains open.
7 A Tight Lower Bound
- The lower bound matches the upper bound up to logarithmic factors when K ≤ T^(1/(3d)); the optimal rate for larger supports remains open.The section also reports best known upper bounds of O~(T^(3/4)) in arbitrary dimension and O~(T^(7/10)) in two dimensions.Source: §7 · pp. 11, 13
- The lower bound holds even with d buyers and no sellers.Figure 4 depicts reference and perturbed CDFs for d = 2 and M = 3, with the perturbed cell indexed by j = (1, 1).Source: §7 · p. 12, Figure 4 · p. 12
- The alternatives preserve the feedback distribution outside their perturbed cell, so distinguishing one requires exploring that cell.The feedback divergence within the cell is O(ε^2).Source: §7 · p. 12
- The construction uses M^d disjoint cells, with a reference instance and alternatives that each improve the reward in one cell.The reference distribution gives every grid point expected reward 1/4; perturbing a cell raises its lower corner's reward by at least ε/2.Source: §7 · p. 12
A Omitted Proofs
These omitted proofs establish high-probability confidence control and bound how many cells the adaptive tree can create at each depth. They use cell geometry and proximity to a grid of reference points.
A Omitted Proofs
- Event E holds with probability at least 1 − δ, using concentration bounds over cells and sample counts.The proof applies Hoeffding’s inequality and a union bound.Source: A Omitted Proofs · p. 16
- At each depth h ≤ H, at most 2(12d + 2)^d |G| cells are created under event E.The proof bounds split cells with g(ℓ_A) ≥ 0 by their possible upper corners near grid points; cells with g(ℓ_A) < 0 are not selected.Source: A Omitted Proofs · pp. 17–18
- After at most d bisections, every weighted side is at most half the previous maximum, supporting the depth-wise cell-count argument.The split coordinate is chosen using side lengths, and ties are broken deterministically.Source: A Omitted Proofs · p. 17
B Proof of Theorem 7.1
The proof builds a reference distribution on a grid, then perturbs probability mass within one of many disjoint cells. A change-of-measure argument turns these alternatives into a regret lower bound.
B Proof of Theorem 7.1
- The reference distribution assigns expected reward 1/4 to every grid point, while no action has a larger mean reward.The support is an equally spaced grid in [0, 1/2]^d plus the all-ones point.Source: B Proof of Theorem 7.1 · pp. 18–20
- The construction has M^d disjoint cells and marginal support size M + 2; the lower bound holds even when the learner knows the common support.The learner does not know which perturbed instance generates the observations.Source: B Proof of Theorem 7.1 · pp. 19–20
- Each perturbed instance raises the expected reward at its cell’s lower corner by at least ε/2, while actions outside that cell have reward at most 1/4.The CDF changes by ε on the perturbed cell and agrees with the reference CDF elsewhere.Source: B Proof of Theorem 7.1 · pp. 19–20
- For K ≥ 4 with T < 2^(3d), taking M = 2 in Equation (20) gives the lower bound Reg_T ≥ γ_d T/(8·2^d).For K ≥ 4 and T ≥ 2^(3d), choose M = min{K−2, floor(T^(1/(3d)))}; this satisfies 2 ≤ M ≤ K−2 and M^(3d) ≤ T.Source: B Proof of Theorem 7.1 · p. 21
B.1 Proof of the Lemmas
The appendix verifies that the constructed reference and perturbed distributions are valid and establishes their CDF behavior. It also develops the divergence comparison used in the lower-bound proof.
B.1 Proof of the Lemmas
- The reference probabilities define a discrete distribution supported exactly on V.The proof checks that the probabilities sum to one and are positive at every point in V.Source: §B.1 · pp. 23–24
- For each cell perturbation, the modified probabilities define a distribution on V, and its CDF differs from the reference CDF only inside that cell.The CDF increases by ε within the perturbed cell.Source: §B.1 · pp. 24–25
- The proof defines kl(a, b) as the Bernoulli KL divergence and uses a bound on that divergence in its comparison of interaction laws.The cited passage identifies the divergence decomposition used in the argument; the Bernoulli divergence is upper-bounded in the subsequent proof.Source: §B.1 · p. 26