Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade

Chris Schwiegelshohn; Federico Fusco; Paul D\"utting; Simone Di Gregorio

REVIEW 1 major objections 4 minor 2 cited by

Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves a broker can learn the best incentive-compatible bilateral-trade mechanism with only $\tilde{O}(\sqrt{T})$ regret.

desk verdict A promising and important paper whose main stochastic upper bound rests on a false telescoping identity in Lemma 9; the lower bounds and problem setup are solid. read the letter →

arxiv 2509.22563 v1 pith:BQY4LQ6Z submitted 2025-09-26 cs.GT cs.LG

Simone Di Gregorio , Paul Dütting , Federico Fusco , Chris Schwiegelshohn This is my paper · ORCID

classification cs.GTcs.LG MSC 91B2668Q32

keywords bilateraltraderegretminimizationprofitmaximizationmechanismdesignMyersonpaymentschainingstochasticonlinelearningjointadsproblem

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how much regret a broker incurs when running repeated bilateral trades without knowing the distribution over seller and buyer valuations. It establishes that a polynomial-time algorithm, Simplify-the-Best-Mechanism, achieves $\tilde{O}(\sqrt{T})$ regret against the best dominant-strategy incentive-compatible and individually rational mechanism in hindsight, and that $\Omega(\sqrt{T})$ regret is unavoidable, so the rate is tight up to log factors. In the adversarial setting, where all valuations are fixed in advance, no algorithm can have sublinear regret even when measured against a constant fraction of optimal profit. The same analysis improves the regret bound for the joint ads problem from $O(T^{3/4})$ to $\tilde{O}(\sqrt{T})$. A sympathetic reader should care because the benchmark is a complex nonparametric mechanism, not a single fixed price, and uniform convergence over all mechanisms is provably impossible.

What carries the argument

The argument rests on the geometric characterization of mechanisms: a DSIC and IR mechanism is exactly a monotone allocation region in the unit square with Myerson payments, so learning a mechanism reduces to learning its boundary curve. The empirical best mechanism on any finite sample is shown to coincide with a complete path on the point-based grid induced by the samples, making the offline step a shortest-path computation. The algorithm then simplifies that empirical optimum onto a uniform $\varepsilon$-grid. The load-bearing device is a chaining analysis over approximating sequences $\phi_h(M)$ of increasingly coarse simplified mechanisms, together with a local dichotomy (Proposition 5): at each refinement level, either the expected profit gain is large, or the second moment of the profit difference is small; unprofitable branches are discarded from the target net. This breaks the uniformity barrier while keeping concentration for mechanisms that can actually win.

What would settle it

Find a finite set of valuation pairs $S$ and a monotone allocation region whose total empirical profit exceeds the profit of every complete path on the point-based grid $G_S$; that would disprove Theorem 1 and with it the algorithm's offline step. Alternatively, exhibit a distribution and a mechanism $M$ whose simplified $\varepsilon$-mechanism fails Proposition 2, e.g., where $\operatorname{profit}(M,v)-\operatorname{profit}(M^\varepsilon,v)>2\varepsilon$ for some valuation $v$ in the allocation region.

Watch

Extended reading notes

Core claim

The central discovery is that despite the nonparametric benchmark and the impossibility of uniform convergence over all DSIC and IR mechanisms, the minimax stochastic regret for profit-maximizing bilateral trade is $\tilde{\Theta}(\sqrt{T})$. The paper proves an upper bound of $C\sqrt{T\log^3 T}$ for Simplify-the-Best-Mechanism and a matching $\Omega(\sqrt{T})$ lower bound, obtained by embedding the two-expert hard instance into valuation distributions whose optimal mechanisms are well separated. Against an oblivious adversarial valuation sequence, the paper proves a stronger impossibility: no algorithm achieves sublinear regret even with respect to a $2/3+\varepsilon$ fraction of optimal profit. As a corollary of the chaining machinery, the joint ads problem inherits an $\tilde{O}(\sqrt{T})$ regret bound, closing the gap to its lower bound.

Load-bearing premise

The load-bearing premise is that the best incentive-compatible, individually rational mechanism on any finite set of observed valuation pairs is exactly a certain monotone boundary path drawn through those samples, with payments fixed by the Myerson formula; if that geometric representation failed, the empirical-optimum step, the simplification, and the chaining bound would all collapse.

Editorial extensions

If this is right

The minimax regret rate for profit maximization in stochastic bilateral trade is $\tilde{\Theta}(\sqrt{T})$, so the benchmark of the best DSIC/IR mechanism is learnable at the same rate as simple fixed-price benchmarks.
The offline sample complexity of an $\varepsilon$-optimal mechanism is $\Theta(1/\varepsilon^2)$ up to log factors: roughly $1/\varepsilon^2$ samples are both sufficient and necessary.
In the adversarial model, no-regret is impossible; even a $2/3+\varepsilon$ approximation of optimal profit cannot be learned with sublinear regret.
The joint ads problem admits an $\tilde{O}(\sqrt{T})$ regret bound, improving the prior $O(T^{3/4})$ and matching the known lower bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same branch-and-bound and chaining pattern might transfer to other mechanism-design problems whose optimal mechanisms have a monotone geometric boundary but whose full mechanism class resists uniform convergence, such as multi-dimensional screening with monotone allocation regions.
The lower-bound construction suggests that smoothed or corrupted stochastic adversaries, rather than fully adversarial ones, are the natural next testbed: the hard instance is a needle that disappears under any fixed discretization, so a smooth adversary would likely make no-regret feasible.
One testable extension is to compute the target net's empirical Rademacher complexity on real platform data and compare its realized regret to the $\sqrt{T}$ bound; the theory predicts concentration only for profitable chains, so low-profit mechanisms should show unstable estimates without hurting overall regret.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear [Colleague],

Short version: this is a genuinely interesting paper on a hard problem, but the main stochastic upper bound has a gap I'm fairly confident about, in Lemma 9. I'd send it to a serious referee, but the proof as written doesn't establish the sqrt(T) regret.

What's new: the benchmark is the best DSIC/IR mechanism rather than a fixed price, which is the right target for profit. The chaining-based approach is original and the paper is honest about the impossibility of uniform convergence. The lower bound in Section 5 (both stochastic and adversarial) looks sound. The structural reduction to monotone regions with Myerson payments is standard but well presented.

The problem: Lemma 9 in Section 4.4 asserts that for every M in the target net, phi_H(M)=M, where phi_H is the epsilon-simplification. That's false when M's boundary has a corner whose x- or y-coordinate is a sample value not on the uniform epsilon-grid. Simplification records only intersections of partial M with G_epsilon and diagonal points, so it replaces such corners with a staircase through the nearest grid node. The telescoping sum then omits the difference profit(M,p)-profit(phi_H(M),p). That difference is not O(epsilon) in absolute value; it can be a constant. Lemma 9 is the bridge from the chaining lemmas to Theorem 3, so Theorem 3 and hence Theorem 4 are not proven as written. This looks repairable--for instance, by redefining the target net to contain only simplified mechanisms, or by adding an explicit error term--but the submitted text doesn't do it.

Minor: the joint ads result is only sketched as "follows verbatim," which is thinner than the rest.

Bottom line: the paper deserves a full review, because the problem is important and the approach is worth fixing. But the current version is conditional at best; the main theorem should not be taken as established until Lemma 9 is addressed. I'd want to see a revision before citing the upper bound.

Referee Report

1 major / 4 minor

Summary. The paper studies repeated bilateral trade where a broker proposes a DSIC and IR mechanism at each round and seeks to maximize profit. The benchmark is the best incentive-compatible and individually rational mechanism in hindsight, rather than the best fixed price. In the stochastic i.i.d. setting, the authors propose Simplify-the-Best-Mechanism and claim a regret bound of O(sqrt(T log^3 T)), complemented by an Omega(sqrt(T)) lower bound. In the adversarial setting they prove a linear lower bound even for a (3/2 - eps)-regret benchmark. They also adapt the technique to the joint ads problem, improving an earlier O(T^{3/4}) regret to O(sqrt(T)) up to log factors. The technical machinery combines a geometric characterization of DSIC/IR mechanisms via monotone allocation regions and Myerson payments, a reduction of the empirical best mechanism to a shortest-path problem, a uniform-grid simplification procedure, and a chaining analysis over data-dependent nets.

Significance. If the main stochastic bound is made fully rigorous, this is a substantial contribution: it is the first nearly tight regret result for profit maximization in bilateral trade against a non-parametric benchmark, and it overcomes a genuine impossibility of uniform convergence via a chaining argument with explicit constants. The paper also contains a polynomial-time algorithm, a clean stochastic lower bound via a two-expert embedding, an adversarial lower bound following and reproving the Aggarwal et al. construction, and a nontrivial application to joint ads. The presentation is largely self-contained, and the structural characterization of mechanisms is clearly stated and proved. However, the main upper bound currently rests on an incorrect identity in the chaining argument, so the central claim is not established as written.

major comments (1)

[Section 4.4, Lemma 9] The identity phi_H(M) = M, used to justify the telescoping decomposition of profit(M,p), is false for a general mechanism M in the data-dependent net M_eps^{S(I\J),S'(J)}. For example, take eps = 1/2 and a sample point (0.25,0.75). The complete path (0,0.5) -> (0.25,0.5) -> (0.25,0.75) -> (1,0.75) -> (1,1) belongs to M_eps^{S(I)}, but its simplification replaces the corner (0.25,0.75) with the staircase (0.25,0.5) -> (0.5,0.5) -> (0.5,0.75). Thus phi_H(M) is a different mechanism and profit(M,p) is not equal to profit(phi_H(M),p) pointwise. The omitted residual can have either sign and can be of constant size, so it cannot be absorbed into the 38eps term without an additional Gaussian-complexity argument. Since Lemma 9 is used to prove Lemma 12 and Theorem 3, and Theorem 3 is invoked in Equation (17) of Theorem 4, the main O(sqrt(T log^3 T)) regret bound is not established as written. The gap may be repairable by redefining the target net to consist of simplified mechanisms or by adding a further eps-level error, but the submitted proof does not contain that repair.

minor comments (4)

[Lemma 3] The proof says that a point in the allocation region belongs to exactly two edges, 'a vertical edge e and a vertical one e-prime'; the second should be a horizontal edge.
[Algorithm pseudocode, Section 4.1] The displayed formula for the precision parameter, eps_t = 200 sqrt(log^3 T / t - 1), is ambiguous; it should state clearly whether the -1 is inside or outside the square root, e.g., eps_t = 200 sqrt(log^3 T / (t-1)).
[Appendix D, Theorem 12] The statement of the multiplicative Chernoff bound appears to have a formatting issue: the exponent in part (ii) should be written with explicit parentheses so that the role of t and E[X] is unambiguous.
[Appendix E] The text refers to 'Section E from Aggarwal et al. [2024]'; the cross-reference should identify the appendix of the present paper rather than the cited paper.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the main near-tight bound is proved from first principles; only non-load-bearing self-citations to Aggarwal et al. remain.

full rationale

Score 2 reflects the only self-citation-related caveat; no circular derivation is present. The central chain is self-contained: Proposition 1 characterizes DSIC/IR mechanisms and is proved in Appendix A; Theorem 1 and Corollary 1 reduce empirical optimization to a shortest-path problem on the point-induced grid; the simplification procedure and Propositions 2-5 are proved from the definitions; Theorem 2's membership proof uses empirical optimality plus concentration; Theorem 3's chaining proof (Lemmas 5-12) uses ghost samples, symmetrization, Rademacher/Gaussian comparison, and the candidate-variance dichotomy, none of which imports the regret bound as an input. No parameter is fitted to data and later called a prediction: the precision ε_t=200 sqrt(log^3 T/t) is set in advance and the bound is derived, not tuned to the benchmark. Self-citations to Aggarwal et al. [2024] (overlapping authors Duetting and Fusco) occur for the ε-simple construction, for the adversarial auxiliary sequence, and for the joint-ads Ω(√T) lower bound; the last is used only to state tightness of the joint-ads corollary, while the bilateral trade lower bound is proved as Theorem 5 and the auxiliary sequence is reproved in Section E. These self-citations do not carry the main derivation, so the paper has at most a minor, non-load-bearing self-citation issue. The possible proof gap around 'φ_H(M)=M' in Lemma 9 is a correctness concern, not a circular input-output reduction, and does not change this verdict.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data; all constants in the analysis are explicit and universal. The central claim rests on the standard DSIC/IR mechanism characterization, the i.i.d. stochastic model, standard concentration inequalities, and the self-contained hard-instance sequence for the adversarial lower bound. No new entities are postulated.

assumptions (5)

standard math DSIC and IR mechanisms are exactly characterized by monotone allocation regions with Myerson payments (Proposition 1).
Standard mechanism-design theorem (Myerson 1981; Myerson-Satterthwaite 1983), proved self-contained in Appendix A. It reduces learning the mechanism to learning a monotone allocation region, the basis of the grid shortest-path search.
domain assumption In the stochastic setting, buyer-seller valuation pairs are drawn i.i.d. from a fixed unknown distribution; correlation between the two agents is allowed.
This is the model for the main positive result (Theorem 4). The adversarial lower bound (Theorem 6) shows the result fails without this stochastic structure, so the i.i.d. assumption is load-bearing.
domain assumption In the adversarial setting, the full sequence of valuations is chosen upfront by an oblivious adversary.
The negative result in Theorem 6 is stated against this adversary. The paper does not treat adaptive adversaries, so the impossibility claim is specific to this model.
standard math Multiplicative Chernoff-Hoeffding bounds (Theorem 12) and the maximal Gaussian inequality (Lemma 8) are valid and applicable.
These concentration tools are imported from the literature (Dubhashi and Panconesi 2009; Talagrand 2014); Lemma 8 is proved in the text, Theorem 12 is restated in Appendix D.
standard math The auxiliary sequence construction underlying the adversarial hard instance (a_t, b_t recursion) produces valuations in [0,1]^2 and admits a separating threshold tau.
The construction is taken from Aggarwal et al. [2024] and is reproved in Appendix E via geometric series bounds; it provides the two-point action space that makes the quadratic lower bound work.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade." pith.science (2026). https://pith.science/paper/BQY4LQ6Z

@misc{pith2026250922563,
  author       = {Pith},
  title        = {Pith review of: Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BQY4LQ6Z}},
  note         = {Machine review of arXiv:2509.22563}
}

abstract

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. We study this problem from the perspective of a broker, in a regret minimization framework. At each time step, a new seller and buyer arrive, and the broker has to propose a mechanism that is incentive-compatible and individually rational, with the goal of maximizing profit. We propose a learning algorithm that guarantees a nearly tight $\tilde{O}(\sqrt{T})$ regret in the stochastic setting when seller and buyer valuations are drawn i.i.d. from a fixed and possibly correlated unknown distribution. We further show that it is impossible to achieve sublinear regret in the non-stationary scenario where valuations are generated upfront by an adversary. Our ambitious benchmark for these results is the best incentive-compatible and individually rational mechanism. This separates us from previous works on efficiency maximization in bilateral trade, where the benchmark is a single number: the best fixed price in hindsight. A particular challenge we face is that uniform convergence for all mechanisms' profits is impossible. We overcome this difficulty via a careful chaining analysis that proves convergence for a provably near-optimal mechanism at (essentially) optimal rate. We further showcase the broader applicability of our techniques by providing nearly optimal results for the joint ads problem.

Figures

Figures reproduced from arXiv: 2509.22563 by the authors.

**Figure 2.** Visualization of approximating sequence (in red) of mechanism [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** An instance of a point-based grid, as defined in Definition 3. The points in [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Visualization of the approximation (red) of a mechanism [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]

**Figure 5.** Figure 5: Visualization of the allocation region of a joint ad mechanism. [PITH_FULL_IMAGE:figures/full_fig_p039_5.png]

**Figure 6.** Figure 6: Visualization of the proofs of Theorem 9 (left) and Theorems 10 and 11 (right). [PITH_FULL_IMAGE:figures/full_fig_p047_6.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability
cs.CL 2026-08 reject novelty 7.0 of 10

The paper introduces TCS-Bench, a 300-task proof-generation benchmark from top TCS papers, and reports frontier LLM accuracies from 30% to 68% using an automated verifier.
Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs
cs.LG 2026-07 conditional novelty 7.0 of 10

A new three-phase algorithm achieves O~(T^{7/10}) regret for two-dimensional Lipschitz CDF-dependent rewards, improving on the previous O~(T^{3/4}).

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 2 Pith papers

[3]

A tight VC-dimension analysis of clustering coresets with applications

Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight VC-dimension analysis of clustering coresets with applications. InSODA, pages 4783–4808. SIAM, 2025a. Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn. Almost optimal PAC learning for k-means. InSTOC, pages 2019–2030. ACM, 2025b. Richard Cole...

work page 2019
[6]

Learning to bid without knowing your value

Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In EC 2018, pages 505–522. ACM,

work page 2018
[8]

Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem. In COLT 2021, pages 2248–2288,

work page 2021
[12]

characterize

B Efficiency Maximization and Budget Balance In this section, we discuss the efficiency maximization version of the bilateral trade problem. Let M be a mechanism with allocation region A, the social welfare and gain from trade induced by M on agents with valuationsv s andv b are defined as follows: GFT(M,vs,vb) =1 {(vs,vb)∈A}(vb−vs) (Gain-From-Trade) SW(M...

work page 2016
[14]

left” and “right

for variables in [0,1]). Theorem 12.Let X be defined as the sum of m random variables Xi, independently distributed in [0, 1]. Let ε∈ (0, 1)and t >2eE[X] be any precision parameters, then the following inequalities hold: (i)P(X−E[X]<−εE[X])≤exp − 1 2ε2E[X] (ii)P(X >t)≤2 −t E Proof of Proposition 7 For completeness, we report here a direct proof of Section...

work page 2024
[1961]

Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. InEC 2023, page

work page 2023
[1983]

In particular, the first mechanism to achieve a constant factor approximation of the optimal gain from trade in the Bayesian setting [Deng et al., 2022] is BIC but not DSIC

hold in the more general setting where mechanisms only need to enforce incentive compatibility, individual rationality, and budget balancein expectation.These mechanisms clearly do not respect the characterization provided in Propositions 1, 8 and 9, but have also been studied. In particular, the first mechanism to achieve a constant factor approximation ...

work page 2022
[2008]

On the pseudo-dimension of nearly optimal auctions

Jamie Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. In NIPS 2015, pages 136–144,

work page 2015

Show all 14 references

[2009]

Smoothed analysis of online non- parametric auctions

Naveen Durvasula, Nika Haghtalab, and Manolis Zampetakis. Smoothed analysis of online non- parametric auctions. InEC 2023, pages 540–560. ACM,

2023
[2018]

Bandit algorithms for prophet inequality and pandora’s box

Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang. Bandit algorithms for prophet inequality and pandora’s box. InSODA 2024, pages 462–500,

2024
[2019]

Kleinberg and Frank Thomson Leighton

Robert D. Kleinberg and Frank Thomson Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. InFOCS 2003, pages 594–605. IEEE,

2003
[2021]

Optimal no-regret learning for one-sided lipschitz functions

41 Paul D¨ utting, Guru Guruganesh, Jon Schneider, and Joshua Ruizhi Wang. Optimal no-regret learning for one-sided lipschitz functions. InICML 2023, pages 8836–8850,

2023
[2022]

Online learning in online auctions

Avrim Blum, Vijay Kumar, Atri Rudra, and Felix Wu. Online learning in online auctions. InSODA 2003, pages 202–204. ACM-SIAM,

2003
[2023]

On multi-dimensional gains from trade maximization

40 Yang Cai, Kira Goldner, Steven Ma, and Mingfei Zhao. On multi-dimensional gains from trade maximization. InSODA 2021, pages 1079–1098. ACM-SIAM,

2021

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [3]

A tight VC-dimension analysis of clustering coresets with applications

Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight VC-dimension analysis of clustering coresets with applications. InSODA, pages 4783–4808. SIAM, 2025a. Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn. Almost optimal PAC learning for k-means. InSTOC, pages 2019–2030. ACM, 2025b. Richard Cole...

work page 2019

[2] [6]

Learning to bid without knowing your value

Zhe Feng, Chara Podimata, and Vasilis Syrgkanis. Learning to bid without knowing your value. In EC 2018, pages 505–522. ACM,

work page 2018

[3] [8]

Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, and Xinzhi Zhang. Generalizing complex hypotheses on product distributions: Auctions, prophet inequalities, and pandora’s problem. In COLT 2021, pages 2248–2288,

work page 2021

[4] [12]

characterize

B Efficiency Maximization and Budget Balance In this section, we discuss the efficiency maximization version of the bilateral trade problem. Let M be a mechanism with allocation region A, the social welfare and gain from trade induced by M on agents with valuationsv s andv b are defined as follows: GFT(M,vs,vb) =1 {(vs,vb)∈A}(vb−vs) (Gain-From-Trade) SW(M...

work page 2016

[5] [14]

left” and “right

for variables in [0,1]). Theorem 12.Let X be defined as the sum of m random variables Xi, independently distributed in [0, 1]. Let ε∈ (0, 1)and t >2eE[X] be any precision parameters, then the following inequalities hold: (i)P(X−E[X]<−εE[X])≤exp − 1 2ε2E[X] (ii)P(X >t)≤2 −t E Proof of Proposition 7 For completeness, we report here a direct proof of Section...

work page 2024

[6] [1961]

Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity of online contract design. InEC 2023, page

work page 2023

[7] [1983]

In particular, the first mechanism to achieve a constant factor approximation of the optimal gain from trade in the Bayesian setting [Deng et al., 2022] is BIC but not DSIC

hold in the more general setting where mechanisms only need to enforce incentive compatibility, individual rationality, and budget balancein expectation.These mechanisms clearly do not respect the characterization provided in Propositions 1, 8 and 9, but have also been studied. In particular, the first mechanism to achieve a constant factor approximation ...

work page 2022

[8] [2008]

On the pseudo-dimension of nearly optimal auctions

Jamie Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. In NIPS 2015, pages 136–144,

work page 2015