betaFeedback

WorksComputer Science

The Power and Limits of Money Burning in Bilateral Trade

Abstract

We study the power of money burning in bilateral trade. In this problem, a seller owns an indivisible item, a buyer would like to acquire it, and each of these two traders has a private value for the item and the values are sampled from independent distributions. We ask whether the traders can benefit from a mechanism that burns money, that is, one that charges the buyer more than it pays the seller, so that neither trader enjoys the difference (money burnt is a loss for the traders). Is it possible that the traders will ever be better off if the trade mechanism can burn money? For Bayesian incentive-compatible mechanisms and for deterministic dominant-strategy incentive-compatible (DSIC) mechanisms, it is known that money burning is always a waste and can only hurt the traders. Maybe surprisingly, we show that once a DSIC mechanism can use randomization, money burning can significantly benefit the traders, and the gain of each of them can be arbitrarily large. In contrast, we show that the power of DSIC randomized mechanisms that burn money is still very limited in the sense that they cannot guarantee any constant fraction of the first-best gains-from-trade.

Introduction

We study the power of money burning to improve efficiency in the classical bilateral-trade problem. In the bilateral-trade problem, a seller owns an indivisible item, and a buyer would like to acquire it. The seller and buyer privately know their respective non-negative values, vsv_s and vbv_b, for the item; these values are drawn from independent distributions. A mechanism elicits reports of these values, decides the probability with which the item is traded, and determines the price that the buyer pays the seller when there is trade.

Traders are assumed to act strategically, aiming to maximize their expected utilities. Because the traders are strategic, analyzing the outcome of a mechanism requires understanding the traders’ behavior. The literature considers two approaches. In the first, the traders are assumed to play a Bayes–Nash equilibrium, and by the revelation principle it is without loss to consider direct mechanisms in which truthful reporting is a Bayes–Nash equilibrium (Bayesian incentive-compatible, or BIC, mechanisms) [69, 9, 10, 67, 38]. The second considers dominant-strategy incentive-compatible mechanisms [11, 26, 12, 57, 34, 63, 49], which impose a stronger requirement than Bayes–Nash equilibrium. We start with a discussion of Bayesian incentive-compatible mechanisms, and move to dominant-strategy incentive-compatible mechanisms later in this introduction. As usual in mechanism design, traders’ participation is voluntary, so a mechanism must be individually rational (IR), ensuring traders are better off participating. As all mechanisms we consider are required to be IR, we sometimes omit stating this requirement explicitly.

If the traders’ values were public, efficiency (or social-welfare maximization) would require trade whenever vb>vsv_b > v_s. This efficient allocation rule is called the first-best. Myerson and Satterthwaite [69] showed that, under mild conditions, no BIC, interim IR mechanism implements the first-best.5

The first-best cannot be implemented, but can truthful mechanisms “come close” to it? To measure that, the literature considers two benchmarks: social welfare and gains-from-trade. For a valuation profile, the social welfare is the value of the trader that ends up with the item: the seller’s value if he keeps the item, and the buyer’s value if the item is traded. The gains-from-trade objective measures the improvement in social welfare relative to the no-trade outcome (in which the seller keeps the item): trade creates gains of vb−vsv_b-v_s, while no trade creates no gains. The social welfare and gains-from-trade of a truthful mechanism are the expectations of these quantities over the traders’ values and the mechanism’s internal randomness. Given the Myerson and Satterthwaite [69] impossibility result, the literature focuses on approximating these benchmarks: maximizing the mechanism’s guaranteed fraction of the corresponding expectations under the first-best.

Approximating gains-from-trade is harder than approximating social welfare: any approximation to gains-from-trade implies the same approximation to social welfare, while any impossibility for social welfare implies the same impossibility for gains-from-trade. For gains-from-trade, BIC mechanisms obtain a constant approximation to the first-best [38, 44]. These results, as well as the line of work in computer science on the approximation guarantees of bilateral-trade mechanisms [11, 16, 26, 12, 57, 34, 63, 49, 55, 64], which we discuss later in this section, consider mechanisms in which the buyer’s entire payment is transferred to the seller.

The bilateral-trade problem as presented so far, and as defined by Myerson and Satterthwaite [69], inherently assumes this property: the amount of money the buyer pays is exactly equal to the amount of money the seller receives. This property is called strong budget balance (SBB), and in the literature it is also often referred to simply as budget balance. However, nothing in the problem itself requires this property. The requirement which captures the inability of the mechanism to finance the trade is the weaker condition of “no deficit”: the amount of money the buyer pays must be at least the amount of money the seller receives, so that no outside subsidy is needed. This weaker requirement is called weak budget balance (WBB), or no deficit.

Under WBB, the buyer’s payment may exceed the amount the seller receives. Neither trader enjoys this difference: the buyer pays it, but the seller does not receive it. Hence, when only the traders are counted, as is common in economics, this difference is lost, and we view it as money burned by the mechanism [37, 67]. The sum of the buyer’s and seller’s utilities is called the traders’ utility; in the literature on bilateral trade, this objective is also called aggregate welfare or total welfare [37, 67]. Its improvement relative to no trade is called the traders’ surplus. Thus, traders’ utility is social welfare minus the money burned, and traders’ surplus is gains-from-trade minus the money burned. One can alternatively consider the benchmarks in which the mechanism itself is considered part of the society (so the money it collects is counted). This gives rise to the social-welfare and gains-from-trade benchmarks, defined above. Under SBB, no money is burned, so the two pairs of benchmarks coincide.

When the goal is the first-best itself, SBB is without loss: the first-best leaves no room for waste, since any part of the buyer’s payment that the seller does not receive is lost to both traders. Thus, a mechanism that attains the first-best in terms of the traders’ utility must be SBB. This argument no longer applies when aiming to approximate the first-best, rather than getting it exactly. Burning money seems inherently wasteful, as the money burnt is not given to the traders. Can the traders ever be better off when the mechanism can burn money? If so, how much better can the approximation be?

Is the restriction to SBB then benign? For BIC and interim IR mechanisms with independent values, it is: a reduction [18, 10, 67] converts any ex-ante WBB mechanism into an ex-post SBB one without reducing the traders’ expected utility.6 The reduction keeps the allocation rule and only changes the payments, so money burning gives BIC mechanisms no new allocation rules. Thus, for BIC mechanisms, the picture is essentially complete: money burning is always a waste. Additionally, strongly budget-balanced BIC mechanisms already provide a constant approximation to the first-best gains-from-trade [38, 44], and therefore to the first-best social welfare as well.

In this paper we focus on the power of money burning for dominant-strategy incentive-compatible (DSIC) bilateral trade mechanisms. In such a mechanism, truthful reporting maximizes each trader’s expected utility, regardless of the other trader’s report (the expectation is only over the mechanism’s internal randomness). This makes these mechanisms more robust, but this robustness comes at a cost. No deterministic SBB DSIC mechanism guarantees any constant approximation [11] to the first-best gains-from-trade. It was shown that every randomized mechanism with these properties is a distribution over posted prices [53 ČP16], and for any distributions of values, some single posted price in its support performs at least as well. Hence, from an approximation point of view, randomization does not help such mechanisms, and this impossibility extends to randomized mechanisms with the same properties. For social welfare, deterministic, DSIC mechanisms do provide constant approximations [11, 26, 12, 57, 34, 63, 49 LSD⁺26, 55].

Here as well, all these mechanisms are SBB.7 For DSIC mechanisms, however, no reduction like that of [18, 10, 67] for BIC mechanisms is known, and whether money burning can help these mechanisms has remained open. In this work, we study the power of money burning in DSIC mechanisms, focusing on the traders’ utility and the traders’ surplus (although we give results for all four benchmarks). We focus on the following questions.

Main Question. For dominant-strategy incentive-compatible trade mechanisms with independent values, can money burning improve the traders’ surplus and the traders’ utility? If so, to what extent? Can the improvement be so large as to approximate the first-best?

As discussed above, money burning is useless for BIC mechanisms. Moreover, for DSIC mechanisms that are restricted to be deterministic, money burning is also useless: the optimal WBB mechanism for maximizing the traders’ utility can always be chosen to be SBB [37]. As money burning is useless for deterministic mechanisms, it is also useless for any randomized mechanism that is a distribution over deterministic mechanisms that each individually satisfies these properties (DSIC and WBB).

This observation might suggest that money burning also cannot help randomized mechanisms. However, not every randomized WBB DSIC mechanism is necessarily a distribution over deterministic mechanisms that each satisfies these properties. In algorithmic game theory, this is the distinction between universally truthful and truthful-in-expectation. Under SBB, the characterization in [53 ČP16] implies that every truthful-in-expectation mechanism can be implemented as a universally truthful one, with SBB and IR holding ex-post, so it is natural to ask whether the same holds under WBB. If that is the case, then money burning is useless even for randomized DSIC mechanisms.

All prior work that we have discussed above seems to indicate that, for independent distributions, money burning is useless. Our Main Question asks whether this is indeed the case for DSIC (randomized) mechanisms.

Our Results

Our work answers the Main Question. First, we show that for randomized dominant-strategy incentive-compatible mechanisms, money burning can substantially improve the traders’ outcome: mechanisms that burn money can outperform strongly budget-balanced mechanisms in maximizing the traders’ surplus, and their advantage can be arbitrarily large, even for each trader separately. Motivated by this gap, we also consider correlated values, and strengthen the result of [SV18] by showing an unbounded separation not only for the traders’ surplus, but even for the traders’ utility. These positive results are presented in § 1.1.1. On the negative side, we present impossibility results for first-best approximations, showing that even with money burning, DSIC mechanisms are not very powerful. Specifically, they cannot guarantee a constant approximation to the first-best traders’ surplus, and, for correlated values, to the first-best traders’ utility. These two impossibility results hold even if we ignore the fact that some money is burnt by the mechanism, and count it towards the gains-from-trade or the social welfare. These negative results are presented in § 1.1.2.

The Advantages of Money Burning

We demonstrate the power of money burning for randomized DSIC mechanisms. We prove that the traders’ surplus (the improvement in the traders’ utilities relative to no trade) of money burning mechanisms can be arbitrarily larger than that of any strongly budget-balanced mechanism, even for each trader separately.

Notation. For a truthful mechanism M\mathcal{M} and independent seller and buyer distributions Fs\mathcal{F}_s and Fb\mathcal{F}_b, we write TUM(Fs×Fb)\mathrm{TU}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) and TSM(Fs×Fb)\mathrm{TS}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) for the expected traders’ utility and traders’ surplus, respectively, under mechanism M\mathcal{M} when the agents’ values are sampled according to these distributions. These quantities are equal to the expected social welfare and gains-from-trade, respectively, minus the expected money burned (the expected difference between the buyer’s payment and the amount the seller receives).

Theorem 1. For every ε>0\varepsilon> 0, there are independent seller and buyer distributions Fs\mathcal{F}_s and Fb\mathcal{F}_b and a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism MWBB\mathcal{M}^{\mathrm{WBB}} such that, for every dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism MSBB\mathcal{M}^{\mathrm{SBB}}, it holds that

ε⋅TSMWBB(Fs×Fb)>TSMSBB(Fs×Fb).\varepsilon\cdot\mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_s \times\mathcal{F}_b) > \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}_s \times\mathcal{F}_b).

Moreover, the same gap holds for each trader separately: ε\varepsilon times the expected surplus of each trader under MWBB\mathcal{M}^{\mathrm{WBB}} is larger than the expected surplus of that trader under MSBB\mathcal{M}^{\mathrm{SBB}}.

Note that this strong separation holds even though we do not credit the WBB mechanism for the money burnt. The separation for each trader separately follows since our construction is symmetric between the two traders (Remark 4.7). Thus, each trader might be arbitrarily better off by money burning (the gain for one is not due to a loss for the other). Observe that a separation for independent distributions immediately implies the same separation for correlated values.

We next move to consider the traders’ utility. An unbounded separation does not hold for the traders’ utility under independent values, because fixed-price mechanisms already guarantee a constant approximation to the first-best [11, 26, 12, 57, 34, 63, 49]. Does such a constant approximation hold for correlated distributions, or is there a strong separation for this general case? We show that for correlated values, there is a strong separation for the traders’ utility as well.

For a joint distribution F\mathcal{F} over the agents’ values, we write TUM(F)\mathrm{TU}_{\mathcal{M}}(\mathcal{F}) for the expected traders’ utility under mechanism M\mathcal{M} when the agents’ values are sampled according to F\mathcal{F}.

Theorem 2. For every ε>0\varepsilon> 0, there is a joint distribution F\mathcal{F} and a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism MWBB\mathcal{M}^{\mathrm{WBB}} such that, for every dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism MSBB\mathcal{M}^{\mathrm{SBB}}, it holds that

ε⋅TUMWBB(F)>TUMSBB(F).\varepsilon\cdot\mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) > \mathrm{TU}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}).

Table 1 summarizes how much money burning can help the traders, for each class of mechanisms and each type of prior.

MechanismValuesTraders’ Utility: IndependentTraders’ Utility: CorrelatedTraders’ Surplus: IndependentTraders’ Surplus: Correlated
Deterministic DSIC11111111
[37]
General DSIC>1>1 (new)∞\infty (new)∞\infty (new)∞\infty (new)
≤1.355\le1.355
[55, 64]

Table 1. Each entry is the largest possible ratio between the best WBB mechanism and the best SBB mechanism. Entries marked (new) are our results, and arrows point from a result to an entry that follows from it. For deterministic DSIC mechanisms, the entries for correlated values follow from Proposition 3.7. For general DSIC mechanisms, the unbounded gap in traders’ surplus for correlated values follows from the unbounded gap for independent values. The gap in traders’ surplus for independent values also implies a gap in traders’ utility, since traders’ utility is the traders’ surplus plus the seller’s expected value, which is the same under both mechanisms (see Appendix § 7.15 for more details). This gap can be much smaller, but is strictly larger than one. The upper bound of 1.355 holds since a fixed price obtains approximately a 0.738024 ≈11.355\approx\frac{1}{1.355} fraction of the first-best social welfare. Finding the exact ratio is an open problem.

The intuition behind this immense gap lies in the structural rigidity of SBB mechanisms. Every SBB DSIC mechanism is a distribution over posted prices. A posted price requires both agents to face the same price, which depends on neither report, limiting the mechanism’s ability to trade the item at disjoint valuation profiles. WBB decouples the buyer’s and seller’s prices, allowing the mechanism to trade at multiple disjoint profiles with high probability (at the cost of burning money at intermediate profiles). Randomization is necessary for this: if a deterministic mechanism trades at two disjoint profiles, it also trades at the profile with the lower seller value and the higher buyer value, and there the buyer pays less than the seller receives, so WBB fails (see Proposition 3.7). Randomized mechanisms can avoid this deficit, at the cost of trading with probability less than 1 at the two disjoint profiles, as we explain in § 1.2. We show how to chain such profiles to generate unbounded relative gains in expected traders’ surplus.

The Limitations of Weak Budget Balance Mechanisms

We have seen that DSIC mechanisms that burn money can be unboundedly more powerful than strongly budget-balanced mechanisms. Moreover, on the distributions used in Theorem 1 and Theorem 2, our WBB mechanism obtains a constant fraction of the first-best. This raises the natural question of whether money burning is powerful enough to overcome the known barriers to approximating the first-best with SBB DSIC mechanisms. Our next results show a sharp limit: even weakly budget-balanced DSIC mechanisms cannot guarantee a constant approximation to the first-best traders’ surplus (for independent priors) or the first-best traders’ utility (for correlated priors). These impossibilities hold even if we ignore the fact that some money is burnt by the mechanism, and count it towards the gains-from-trade or the social welfare.

Notation. For a truthful mechanism M\mathcal{M} and a prior F\mathcal{F} over the agents’ values, we write SW⁡M(F)\operatorname{SW}_{\mathcal{M}}(\mathcal{F}) and GFT⁡M(F)\operatorname{GFT}_{\mathcal{M}}(\mathcal{F}) for the expected social welfare and gains-from-trade, respectively, under mechanism M\mathcal{M} when the agents’ values are sampled according to F\mathcal{F}. Unlike the traders’ utility and surplus, these quantities do not subtract the money burned by the mechanism, and thus depend only on the allocation rule.

We write SWOPT(F)\mathrm{SW}_{OPT}(\mathcal{F}) and GFTOPT(F)\mathrm{GFT}_{OPT}(\mathcal{F}) for the expected social welfare and gains-from-trade of the first-best, which trades whenever vb>vsv_b > v_s.

Theorem 3 (limitations of weak budget balance). The following statements hold:

  1. For every ε>0\varepsilon> 0, there are independent seller and buyer distributions Fs\mathcal{F}_s and Fb\mathcal{F}_b such that every dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism MWBB\mathcal{M}^{\mathrm{WBB}} satisfies

TSMWBB(Fs×Fb)≤GFTMWBB(Fs×Fb)<ε⋅GFTOPT(Fs×Fb).\mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_s \times\mathcal{F}_b) \le\mathrm{GFT}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_s \times\mathcal{F}_b) < \varepsilon\cdot\mathrm{GFT}_{OPT}(\mathcal{F}_s \times\mathcal{F}_b).
  1. For every ε>0\varepsilon> 0, there is a joint distribution F\mathcal{F} such that every dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism MWBB\mathcal{M}^{\mathrm{WBB}} satisfies

TUMWBB(F)≤SWMWBB(F)<ε⋅SWOPT(F).\mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) \le\mathrm{SW}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) < \varepsilon\cdot\mathrm{SW}_{OPT}(\mathcal{F}).

For independent values, no SBB DSIC mechanism guarantees a constant fraction of the first-best gains-from-trade [11]. The first statement extends this impossibility to WBB DSIC mechanisms. For correlated values, no SBB mechanism in which both traders have a dominant strategy guarantees a constant approximation to first-best social welfare [39]. The second statement shows that allowing the DSIC mechanism to be only WBB does not overcome this barrier. Table 2 places these results in the context of the literature.

MechanismValuesSocial WelfareGains-from-Trade
IndependentCorrelatedIndependentCorrelated
WBB BICYesYesYes?
SBB BICYesYes [39]Yes [38]No [RW24]
WBB DSICYesNo (new)No (new)No
SBB DSICYes [11]No [39]No [11]No

Table 2. Can the first-best be approximated to within a constant factor?

These impossibilities clarify the scope of our positive results. Money burning DSIC mechanisms can be arbitrarily more powerful than SBB DSIC mechanisms, but allowing the mechanism to be only WBB is not enough to overcome the fundamental gap between DSIC mechanisms and the first-best, even if we ignore the fact that some money is burnt by the mechanism, and count it towards the social welfare or the gains-from-trade.

Our Technique: The Advantages of Money Burning

We now describe the main ideas behind Theorem 1 and Theorem 2, which show that DSIC mechanisms that are weakly budget-balanced can obtain unboundedly better outcomes than strongly budget-balanced ones: arbitrarily more traders’ surplus when the values are independent, and arbitrarily more traders’ utility when the values may be correlated. We first identify a limitation of SBB DSIC mechanisms, explain why randomization is needed to overcome it, and then describe a WBB DSIC mechanism that overcomes it. We then explain why this mechanism also leaves the traders a large surplus, and finally describe the distributions on which the separations hold. The full details are in § 4.

A limitation of strongly budget-balanced mechanisms. It was shown that every SBB DSIC mechanism is a distribution over posted prices [53 CP16]: at a profile (vs,vb)(v_s, v_b), it trades only if its random price falls in [vs,vb][v_s, v_b]. Hence, if pp is its price and xSBBx^{\mathrm{SBB}} its allocation rule, then for any profiles (vs(1),vb(1)),…,(vs(m),vb(m))(v_s^{(1)}, v_b^{(1)}), \ldots, (v_s^{(m)}, v_b^{(m)}) whose intervals [vs(j),vb(j)][v_s^{(j)}, v_b^{(j)}] are pairwise disjoint,

∑j=1mxSBB(vs(j),vb(j))≤∑j=1mPr⁡[p∈[vs(j),vb(j)]]≤1.\sum_{j=1}^{m} x^{\mathrm{SBB}}(v_s^{(j)}, v_b^{(j)}) \le\sum_{j=1}^{m} \Pr\left[p \in[v_s^{(j)}, v_b^{(j)}]\right] \le1.

Table 2: Each entry says whether the mechanisms in that row can guarantee a constant fraction of the first-best. Entries marked (new) are our results, and arrows point from a result to an entry that follows from it. Every SBB mechanism is also WBB, and every DSIC mechanism is also BIC, so the positive result for SBB DSIC mechanisms with independent values also holds for WBB DSIC and BIC mechanisms. For BIC mechanisms, the IR requirement is of interim IR, and WBB and SBB are pointwise (see Footnote 2). A two-sided arrow means that each of the two entries implies the other, and ⋆\star means that this is due to the reduction of [18, 10, 67]. An impossibility for independent values also holds for correlated values. For the positive results with independent values, we cite the first constant approximation, later works improved the constants (see § 2). In this work our focus is on DSIC mechanisms. For BIC mechanisms, SBB mechanisms already guarantee a constant fraction of the first-best in all entries except for the gains-from-trade with correlated values. Whether money burning can help to approximate the first-best in this case is an interesting open question.

Thus, if almost all of the first-best gains-from-trade comes from these mm profiles and each profile contributes the same amount, a strongly budget-balanced mechanism obtains at most about a 1/m1/m fraction of the first-best gains-from-trade. Our WBB mechanism trades with probability more than 1/21/2 at many such profiles simultaneously, and therefore obtains at least about half of the first-best gains-from-trade on such distributions.

Why randomization is needed. WBB lets the buyer’s price and the seller’s price differ, and each can depend on the other trader’s report. The question is whether this lets a mechanism trade with substantial probability at many profiles whose intervals are disjoint. For deterministic mechanisms it does not (Proposition 3.7, essentially [37]), and the following example shows why. Take two agents’ profiles (s1,b1)(s_1, b_1) and (s2,b2)(s_2, b_2) with b1<s2b_1 < s_2, so no posted price trades at both, and suppose a deterministic WBB DSIC mechanism trades at both. By monotonicity, it also trades at (s1,b2)(s_1, b_2). There, the buyer faces the same price as at (s1,b1)(s_1, b_1), since the seller’s report is the same, so this price is at most b1b_1. Similarly, the seller faces the same price as at (s2,b2)(s_2, b_2), so it is at least s2s_2. Since b1<s2b_1 < s_2, the buyer pays less than the seller receives, which violates WBB.

References

  1. [1]Manuel Amador and Kyle Bagwell. Money burning in the theory of delegation. Games and Economic Behavior, 121:382–412, 2020.DOI
  2. [2]Gagan Aggarwal, Ashwinkumar Badanidiyuru, Paul Dütting, and Federico Fusco. Selling joint ads: A regret minimization perspective. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), 2024.DOI
  3. [3]Yossi Azar, Amos Fiat, and Federico Fusco. An α-regret analysis of adversarial bilateral trade. Artificial Intelligence, 337:104231, 2024.DOI
  4. [4]Martin J. Bailey. The demand revealing process: To distribute the surplus. Public Choice, 91(2):107–126, 1997.DOI
  5. [5]François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, and Roberto Colomboni. Fair online bilateral trade. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
  6. [6]Nataša Bolić, Tommaso Cesari, and Roberto Colomboni. An online learning theory of brokerage. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024.
  7. [7]François Bachoc, Tommaso Cesari, and Roberto Colomboni. A tight regret analysis of non-parametric repeated contextual brokerage. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2025.arxiv.org/abs/2503.02646
  8. [8]Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Federico Fusco. No-regret learning in bilateral trade via global budget balance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024.
  9. [9]Moshe Babaioff, Yang Cai, Yannai A. Gonczarowski, and Mingfei Zhao. The best of both worlds: Asymptotically efficient mechanisms with a guarantee on the expected gains-from-trade. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 373, New York, NY, USA, 2018. Association for Computing Machinery.
  10. [10]Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC ’17, pages 589–590, New York, NY, USA, 2017. Association for Computing Machinery.arxiv.org/abs/1706.04637
  11. [11]Liad Blumrosen and Shahar Dobzinski. Reallocation mechanisms. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC ’14, page 617, New York, NY, USA, 2014. Association for Computing Machinery.
  12. [12]Liad Blumrosen and Shahar Dobzinski. (Almost) efficient mechanisms for bilateral trading. Games and Economic Behavior, 130:369–383, 2021.arxiv.org/abs/1604.04876
  13. [13]Moshe Babaioff, Shahar Dobzinski, and Ron Kupfer. A note on the gains from trade of the random-offerer mechanism, 2021. arXiv:2111.07790.arxiv.org/abs/2111.07790
  14. [14]Moshe Babaioff, Amitai Frey, and Noam Nisan. Learning to maximize gains from trade in small markets. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), 2024.
  15. [15]Xiaohui Bei, Bo Li, Wenhao Wu, and Shengwei Zhou. Second-best gains from trade in matching markets, 2026. arXiv:2609.18724.arxiv.org/abs/2609.18724
  16. [16]Liad Blumrosen and Yehonatan Mizrahi. Approximating gains-from-trade in bilateral trading. In Yang Cai and Adrian Vetta, editors, Web and Internet Economics, pages 400–413, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.DOI
  17. [17]Moshe Babaioff and Noam Nisan. Concurrent auctions across the supply chain. Journal of Artificial Intelligence Research, 21:595–629, 2004.
  18. [18]Tilman Börgers and Peter Norman. A note on budget balance under interim participation constraints: the case of independent types. Economic Theory, 39(3):477–489, 2009.DOI
  19. [19]Moshe Babaioff, Noam Nisan, and Elan Pavlov. Mechanisms for a spatially distributed market. Games and Economic Behavior, 66(2):660–684, 2009.
  20. [20]Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, and Kangning Wang. Approximating gains-from-trade in matching markets. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC), 2026.
  21. [21]Moshe Babaioff and William E. Walsh. Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation. Decision Support Systems, 39(1):123–149, 2005.
  22. [22]Xiaohui Bei, Wenhao Wu, and Shengwei Zhou. The power of simple mechanisms: A tight e-approximation for gains from trade in matching markets, 2026. arXiv:2609.37997.arxiv.org/abs/2609.37997
  23. [23]Ruggiero Cavallo. Optimal decision-making with minimal waste: Strategyproof redistribution of VCG payments. In Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems, pages 882–889, 2006.DOI
  24. [24]Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 49(1):171–203, 2024.
  25. [25]Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Regret analysis of bilateral trade with a smoothed adversary. Journal of Machine Learning Research, 25(234):1–36, 2024.
  26. [26]Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, pages 1424–1443, USA, 2016. Society for Industrial and Applied Mathematics.
  27. [27]Tommaso Cesari and Roberto Colomboni. An online learning theory of trading-volume maximization. In International Conference on Learning Representations (ICLR), 2025.
  28. [29]Yang Cai, Kira Goldner, Steven Ma, and Mingfei Zhao. On multi-dimensional gains from trade maximization. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1079–1098, 2021.arxiv.org/abs/2007.13934
  29. [30]Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. Tight regret bounds for fixed-price bilateral trade. In Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 374 of LIPICs, pages 57:1–57:21, 2026.arxiv.org/abs/2504.04349
  30. [32]Daniele Condorelli. What money can’t buy: Efficient mechanism design with costly signals. Games and Economic Behavior, 75:613–624, 2012.DOI
  31. [34]Yang Cai and Jinzhao Wu. On the optimal fixed-price mechanism in bilateral trade. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 737–750, New York, NY, USA, 2023. Association for Computing Machinery.arxiv.org/abs/2301.05167
  32. [35]Geoffroy de Clippel, Victor Naroditskiy, Maria Polukarov, Amy Greenwald, and Nicholas R. Jennings. Destroy to save. Games and Economic Behavior, 86:392–404, 2014.
  33. [36]Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, and Thodoris Tsilivis. Bilateral trade with interdependent values: Information vs. approximation. In Proceedings of the 26th ACM Conference on Economics and Computation, pages 641–665. Association for Computing Machinery, 2025.DOI
  34. [37]Moritz Drexl and Andreas Kleiner. Optimal private good allocation: The case for a balanced budget. Games and Economic Behavior, 94:169–181, 2015.DOI
  35. [38]Yuan Deng, Jieming Mao, Balasubramanian Sivan, and Kangning Wang. Approximately efficient bilateral trade. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 718–721, New York, NY, USA, 2022. Association for Computing Machinery.
  36. [39]Shahar Dobzinski and Ariel Shaulker. Bilateral trade with correlated values. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024. Association for Computing Machinery, 2024.arxiv.org/abs/2308.09964
  37. [40]Shahar Dobzinski and Ariel Shaulker. Welfare maximization in bilateral trade: Improved approximation guarantees beyond the fixed price barrier, 2026. arXiv:2606.04890.arxiv.org/abs/2606.04890
  38. [41]Tomer Ezra, Aadityan Ganesh, and Aviad Rubinstein. Welfare approximation in multilateral trade, 2026. arXiv:2608.11351.arxiv.org/abs/2608.11351
  39. [42]Tomer Ezra, Daniel Schoepflin, and Ariel Shaulker. Multi-parameter mechanisms for consumer surplus maximization. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.arxiv.org/abs/2402.16972
  40. [43]Tomer Ezra. Money burning mechanism design: From welfare to surplus, 2026. arXiv:2608.01693.arxiv.org/abs/2608.01693
  41. [44]Yumou Fei. Improved approximation to first-best gains-from-trade. In Kristoffer Arnsfelt Hansen, Tracy Xiao Liu, and Azarakhsh Malekian, editors, Web and Internet Economics, pages 204–218, Cham, 2022. Springer International Publishing.arxiv.org/abs/2205.00140
  42. [45]Dimitris Fotakis, Dimitris Tsipras, Christos Tzamos, and Emmanouil Zampetakis. Efficient money burning in general domains. Theory of Computing Systems, 59(4):619–640, 2016.
  43. [46]Solenne Gaucher, Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Vianney Perchet. Feature-based online bilateral trade. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2405.18183
  44. [47]Mingyu Guo and Vincent Conitzer. Better redistribution with inefficient allocation in multi-unit auctions with unit demand. In Proceedings of the 9th ACM Conference on Electronic Commerce, pages 210–219, 2008.
  45. [48]Mingyu Guo and Vincent Conitzer. Worst-case optimal redistribution of VCG payments in multi-unit auctions. Games and Economic Behavior, 67(1):69–98, 2009.
  46. [49]Giordano Giambartolomei and Bart de Keijzer. On the approximation ratio of optimal fixed-price mechanisms for single and multi-unit bilateral trade. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 16946–16953, 2026.
  47. [50]Kira Goldner and Taylor Lundy. Multidimensional Bayesian utility maximization: Tight approximations to welfare. In Advances in Neural Information Processing Systems (NeurIPS), 2025.arxiv.org/abs/2402.12340
  48. [51]Kira Goldner, Taylor Lundy, and Thodoris Tsilivis. A constant-factor approximation to multidimensional consumer utility, 2026. arXiv:2610.10516.arxiv.org/abs/2610.10516
  49. [52]Kira Goldner, Divyarthi Mohan, and Thodoris Tsilivis. Knowing who, not how much: Learning-augmented mechanisms for consumer utility maximization. In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026.
  50. [53]Kathleen M Hagerty and William P Rogerson. Robust trading mechanisms. Journal of Economic Theory, 42(1):94–107, 1987.DOI
  51. [54]Jason D. Hartline and Tim Roughgarden. Optimal mechanism design and money burning. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pages 75–84, 2008.DOI
  52. [55]Tao Jiang, Minbo Gao, and Shaowei Cai. The exact approximation ratio of the optimal fixed-price mechanism in bilateral trade, 2026. arXiv:2609.27878.arxiv.org/abs/2609.27878
  53. [56]Sunghyeon Jo. Tighter bounds for the random-offerer mechanism in bilateral trade, 2026. arXiv:2607.13959.arxiv.org/abs/2607.13959
  54. [57]Zi Yang Kang, Francisco Pernice, and Jan Vondrák. Fixed-price approximations in bilateral trade. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2964–2985, Philadelphia, PA, 2022. Society for Industrial and Applied Mathematics.arxiv.org/abs/2107.14327
  55. [58]Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Better regret rates in bilateral trade via sublinear budget violation, 2025. arXiv:2507.11419.arxiv.org/abs/2507.11419
  56. [59]Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Online two-sided markets: Many buyers enhance learning. In Advances in Neural Information Processing Systems (NeurIPS), 2025. arXiv:2503.01529.arxiv.org/abs/2503.01529
  57. [60]Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi. Regret minimization in bilateral trade with perturbed markets, 2026. arXiv:2605.10475.arxiv.org/abs/2605.10475
  58. [61]Zhengyang Liu, Ying Qin, Zeyu Ren, and Zihe Wang. Second-best bilateral trade is 1/2 efficient, 2026. arXiv:2606.03849.arxiv.org/abs/2606.03849
  59. [62]Zhengyang Liu, Ying Qin, and Zihe Wang. Sharp second-best welfare in bilateral and matching markets, 2026. arXiv:2609.37366.arxiv.org/abs/2609.37366
  60. [63]Zhengyang Liu, Zeyu Ren, and Zihe Wang. Improved approximation ratios of fixed-price mechanisms in bilateral trades. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 751–760, New York, NY, USA, 2023. Association for Computing Machinery.arxiv.org/abs/2303.15711
  61. [64]Tingyi Lin, Yichen Shi, Ke Dong, JiaZhuo Li, Shawn Yu, and Huanxi Zhang. The exact welfare guarantee of fixed-price bilateral trade, 2026. arXiv:2609.35888.arxiv.org/abs/2609.35888
  62. [65]R. Preston McAfee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434–450, 1992.
  63. [66]R. Preston McAfee. The gains from trade under fixed price mechanisms. Applied Economics Research Bulletin, 1(1):1–10, 2008.
  64. [67]Mihai Manea and Eric Maskin. Withholding and damage in Bayesian trade mechanisms. Games and Economic Behavior, 142:243–265, 2023.DOI
  65. [68]Hervé Moulin. Almost budget-balanced VCG mechanisms to assign multiple objects. Journal of Economic Theory, 144(1):96–119, 2009.DOI
  66. [69]Roger B. Myerson and Mark A. Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 29(2):265–281, 1983.DOI
  67. [70]Aviad Rubinstein, Xizhi Tan, and Zixin Zhou. Approximately efficient multidimensional bilateral trade. In Proceedings of the 67th IEEE Symposium on Foundations of Computer Science (FOCS), 2026. arXiv:2609.02872.arxiv.org/abs/2609.02872

Paper details

vlnc:W_n7t5gka9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Codex, Claude, AI tools

View statement
Looking for related papers…
Contents