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, v s v_s v s and v b v_b v 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 v b > v s v_b > v_s v 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 v b − v s v_b-v_s v 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} M and independent seller and buyer distributions F s \mathcal{F}_s F s and F b \mathcal{F}_b F b , we write T U M ( F s × F b ) \mathrm{TU}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) TU M ( F s × F b ) and T S M ( F s × F b ) \mathrm{TS}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) TS M ( F s × F b ) for the expected traders’ utility and traders’ surplus, respectively, under mechanism M \mathcal{M} 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 ε > 0 , there are independent seller and buyer distributions F s \mathcal{F}_s F s and F b \mathcal{F}_b F b and a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB such that, for every dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB , it holds that
ε ⋅ T S M W B B ( F s × F b ) > T S M S B B ( F s × F b ) . \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). ε ⋅ TS M WBB ( F s × F b ) > TS M SBB ( F s × F b ) . Moreover, the same gap holds for each trader separately: ε \varepsilon ε times the expected surplus of each trader under M W B B \mathcal{M}^{\mathrm{WBB}} M WBB is larger than the expected surplus of that trader under M S B B \mathcal{M}^{\mathrm{SBB}} M 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} F over the agents’ values, we write T U M ( F ) \mathrm{TU}_{\mathcal{M}}(\mathcal{F}) TU M ( F ) for the expected traders’ utility under mechanism M \mathcal{M} M when the agents’ values are sampled according to F \mathcal{F} F .
Theorem 2. For every ε > 0 \varepsilon> 0 ε > 0 , there is a joint distribution F \mathcal{F} F and a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB such that, for every dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB , it holds that
ε ⋅ T U M W B B ( F ) > T U M S B B ( F ) . \varepsilon\cdot\mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) > \mathrm{TU}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}). ε ⋅ TU M WBB ( F ) > TU M SBB ( F ) .
Table 1 summarizes how much money burning can help the traders, for each class of mechanisms and each type of prior.
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 ≈ 1 1.355 \approx\frac{1}{1.355} ≈ 1.355 1 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} M and a prior F \mathcal{F} F over the agents’ values, we write SW M ( F ) \operatorname{SW}_{\mathcal{M}}(\mathcal{F}) SW M ( F ) and GFT M ( F ) \operatorname{GFT}_{\mathcal{M}}(\mathcal{F}) GFT M ( F ) for the expected social welfare and gains-from-trade, respectively, under mechanism M \mathcal{M} M when the agents’ values are sampled according to F \mathcal{F} 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 S W O P T ( F ) \mathrm{SW}_{OPT}(\mathcal{F}) SW O P T ( F ) and G F T O P T ( F ) \mathrm{GFT}_{OPT}(\mathcal{F}) GFT O P T ( F ) for the expected social welfare and gains-from-trade of the first-best, which trades whenever v b > v s v_b > v_s v b > v s .
Theorem 3 (limitations of weak budget balance). The following statements hold:
For every ε > 0 \varepsilon> 0 ε > 0 , there are independent seller and buyer distributions F s \mathcal{F}_s F s and F b \mathcal{F}_b F b such that every dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB satisfies
T S M W B B ( F s × F b ) ≤ G F T M W B B ( F s × F b ) < ε ⋅ G F T O P T ( F s × F b ) . \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). TS M WBB ( F s × F b ) ≤ GFT M WBB ( F s × F b ) < ε ⋅ GFT O P T ( F s × F b ) . For every ε > 0 \varepsilon> 0 ε > 0 , there is a joint distribution F \mathcal{F} F such that every dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB satisfies
T U M W B B ( F ) ≤ S W M W B B ( F ) < ε ⋅ S W O P T ( 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}). TU M WBB ( F ) ≤ SW M WBB ( F ) < ε ⋅ SW O P T ( 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.
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 ( v s , v b ) (v_s, v_b) ( v s , v b ) , it trades only if its random price falls in [ v s , v b ] [v_s, v_b] [ v s , v b ] . Hence, if p p p is its price and x S B B x^{\mathrm{SBB}} x SBB its allocation rule, then for any profiles ( v s ( 1 ) , v b ( 1 ) ) , … , ( v s ( m ) , v b ( m ) ) (v_s^{(1)}, v_b^{(1)}), \ldots, (v_s^{(m)}, v_b^{(m)}) ( v s ( 1 ) , v b ( 1 ) ) , … , ( v s ( m ) , v b ( m ) ) whose intervals [ v s ( j ) , v b ( j ) ] [v_s^{(j)}, v_b^{(j)}] [ v s ( j ) , v b ( j ) ] are pairwise disjoint,
∑ j = 1 m x S B B ( v s ( j ) , v b ( j ) ) ≤ ∑ j = 1 m Pr [ p ∈ [ v s ( j ) , v b ( 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. j = 1 ∑ m x SBB ( v s ( j ) , v b ( j ) ) ≤ j = 1 ∑ m Pr [ p ∈ [ v s ( j ) , v b ( j ) ] ] ≤ 1.
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 m m m profiles and each profile contributes the same amount, a strongly budget-balanced mechanism obtains at most about a 1 / m 1/m 1/ m fraction of the first-best gains-from-trade. Our WBB mechanism trades with probability more than 1 / 2 1/2 1/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 ( s 1 , b 1 ) (s_1, b_1) ( s 1 , b 1 ) and ( s 2 , b 2 ) (s_2, b_2) ( s 2 , b 2 ) with b 1 < s 2 b_1 < s_2 b 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 ( s 1 , b 2 ) (s_1, b_2) ( s 1 , b 2 ) . There, the buyer faces the same price as at ( s 1 , b 1 ) (s_1, b_1) ( s 1 , b 1 ) , since the seller’s report is the same, so this price is at most b 1 b_1 b 1 . Similarly, the seller faces the same price as at ( s 2 , b 2 ) (s_2, b_2) ( s 2 , b 2 ) , so it is at least s 2 s_2 s 2 . Since b 1 < s 2 b_1 < s_2 b 1 < s 2 , the buyer pays less than the seller receives, which violates WBB.
Randomization resolves this. To see how, suppose the mechanism trades with probability more than 1 / 2 1/2 1/2 at both ( s 1 , b 1 ) (s_1, b_1) ( s 1 , b 1 ) and ( s 2 , b 2 ) (s_2, b_2) ( s 2 , b 2 ) , which no lottery over posted prices can do, since its trade probabilities at these two profiles sum to at most one. For simplicity of the argument, take both probabilities to be the same x > 1 / 2 x > 1/2 x > 1/2 .8 Suppose also that it trades with a higher probability y > x y > x y > x at ( s 1 , b 2 ) (s_1,b_2) ( s 1 , b 2 ) . Think of the trade at ( s 1 , b 2 ) (s_1,b_2) ( s 1 , b 2 ) as two parts: a part with probability x x x , which the buyer would also get at ( s 1 , b 1 ) (s_1,b_1) ( s 1 , b 1 ) and the seller would also get at ( s 2 , b 2 ) (s_2,b_2) ( s 2 , b 2 ) , and an extra part with probability y − x y-x y − x . By Myerson’s lemma, the buyer pays price b 1 b_1 b 1 on the first part and b 2 b_2 b 2 on the extra part, while the seller receives s 2 s_2 s 2 on the first part and s 1 s_1 s 1 on the extra part. The first part still runs a deficit of ( s 2 − b 1 ) x (s_2-b_1)x ( s 2 − b 1 ) x , but the extra part brings in ( b 2 − s 1 ) ( y − x ) (b_2-s_1)(y-x) ( b 2 − s 1 ) ( y − x ) , which covers it when the gap s 2 − b 1 s_2-b_1 s 2 − b 1 is small compared to b 2 − s 1 b_2-s_1 b 2 − s 1 . A deterministic mechanism cannot do this, since it already trades with probability one at ( s 1 , b 1 ) (s_1,b_1) ( s 1 , b 1 ) and ( s 2 , b 2 ) (s_2,b_2) ( s 2 , b 2 ) , so x = 1 x=1 x = 1 , and since y y y cannot exceed one, there is no extra part to cover the deficit. This is exactly the violation of WBB in the deterministic example above.
This two-profile argument is the basic building block of our construction. We build a grid and apply this argument repeatedly along the profiles between consecutive grid points: these profiles have disjoint intervals, every two adjacent ones play the roles of ( s 1 , b 1 ) (s_1,b_1) ( s 1 , b 1 ) and ( s 2 , b 2 ) (s_2,b_2) ( s 2 , b 2 ) as described above, and the profile with the seller value of the first and the buyer value of the second plays the role of ( s 1 , b 2 ) (s_1,b_2) ( s 1 , b 2 ) . Each step requires a slightly higher trade probability than the previous one, and if each increase is small, the trade probability does not exceed 1 1 1 , even after many steps. We next describe the grid and the mechanism in detail.
The construction. The mechanism is defined by a grid 0 = q 0 < ⋯ < q n = 1 0=q_0<\cdots<q_n=1 0 = q 0 < ⋯ < q n = 1 and a small τ > 0 \tau>0 τ > 0 . Each interior grid point q i q_i q i defines a seller threshold s i = q i + τ s_i=q_i+\tau s i = q i + τ slightly above it and a buyer threshold b i = q i − τ b_i=q_i-\tau b i = q i − τ slightly below it. The mechanism rounds the seller’s report up to the nearest seller threshold and the buyer’s report down to the nearest buyer threshold, and it trades only if the buyer’s rounded index is strictly above the seller’s rounded index. We call the difference between the two rounded indices the level of the profile. The trade probability depends only on the level: at level d ≥ 1 d\geq1 d ≥ 1 it is Γ − ( n − d ) \Gamma^{-(n-d)} Γ − ( n − d ) for a growth factor Γ > 1 \Gamma>1 Γ > 1 , so moving up one level, by increasing the buyer’s rounded index or decreasing the seller’s rounded index by one, multiplies the trade probability by Γ \Gamma Γ , and at the top level the trade probability is 1 1 1 (see Figure 1 ). For the purpose of this discussion, we denote this allocation rule by x W B B x^{\mathrm{WBB}} x WBB . It is nondecreasing in the buyer’s value and nonincreasing in the seller’s value, so by Myerson’s lemma there are payments that make the mechanism DSIC. For a large enough growth factor, the mechanism is also WBB, and we fix such a Γ \Gamma Γ .
Figure 1. The allocation rule of Lemma 4.3, drawn to scale, for n = 4 n = 4 n = 4 , the grid ( q 0 , … , q 4 ) = ( 0 , 3 8 , 1 2 , 5 8 , 1 ) (q_0,\ldots,q_4) = (0,\frac{3}{8},\frac{1}{2},\frac{5}{8},1) ( q 0 , … , q 4 ) = ( 0 , 8 3 , 2 1 , 8 5 , 1 ) , and τ = 0.002 \tau= 0.002 τ = 0.002 , as a function of the buyer’s value. The dashed vertical lines are the buyer thresholds b i = q i − τ b_i = q_i-\tau b i = q i − τ for 1 ≤ i < n 1 \leq i < n 1 ≤ i < n , each b i b_i b i lies slightly below its grid point q i q_i q i . For this grid, Equation (18) gives the growth factor Γ ≈ 1.254 \Gamma\approx1.254 Γ ≈ 1.254 . Each curve corresponds to all seller values that are rounded to the same index ι S ( v s ) \iota_S(v_s) ι S ( v s ) . Since Γ 3 ≈ 1.97 < 2 \Gamma^3 \approx1.97 < 2 Γ 3 ≈ 1.97 < 2 , every positive allocation probability is above 1 / 2 1/2 1/2 (dashed line). The levels are not evenly spaced. The black arrows show the jumps of the curve ι S ( v s ) = 0 \iota_S(v_s)=0 ι S ( v s ) = 0 at b 2 b_2 b 2 , b 3 b_3 b 3 , and b 4 b_4 b 4 , of sizes approximately 0.13, 0.16, and 0.20: each jump is Γ \Gamma Γ times the previous one. The dot labeled k i k_i k i marks the allocation probability at the profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) , whose seller and buyer values are the two endpoints of the interval K i = [ s i − 1 , b i ] K_i=[s_{i-1},b_i] K i = [ s i − 1 , b i ] . For example, if the seller’s value is 0.2 and the buyer’s value is 0.7, then the seller’s value is rounded up to s 1 s_1 s 1 , so ι S ( v s ) = 1 \iota_S(v_s)=1 ι S ( v s ) = 1 (the green curve), and the buyer’s value is rounded down to b 3 b_3 b 3 . The two rounded indices are two grid steps apart, so trade happens with probability Γ − 2 ≈ 0.64 \Gamma^{-2}\approx0.64 Γ − 2 ≈ 0.64 .
The smallest positive trade probability is at level 1 1 1 , and it is Γ − ( n − 1 ) \Gamma^{-(n-1)} Γ − ( n − 1 ) . The growth factor depends on the grid, and when we apply the construction, we carefully choose the grid so that Γ n − 1 < 2 \Gamma^{n-1}<2 Γ n − 1 < 2 (Definition 4.4 gives a sufficient condition), and hence every positive trade probability is more than 1 / 2 1/2 1/2 . In particular, consider the profiles
( s 0 , b 1 ) , ( s 1 , b 2 ) , … , ( s n − 1 , b n ) . (s_0,b_1),\ (s_1,b_2),\ \ldots,\ (s_{n-1},b_n). ( s 0 , b 1 ) , ( s 1 , b 2 ) , … , ( s n − 1 , b n ) .
At the profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) , the seller’s rounded index is i − 1 i-1 i − 1 and the buyer’s rounded index is i i i , so all these profiles are at level 1 1 1 , and for a small enough τ \tau τ , their intervals [ s i − 1 , b i ] [s_{i-1},b_i] [ s i − 1 , b i ] are pairwise disjoint. Hence, the trade probabilities of every SBB DSIC mechanism at these profiles sum to at most one, while our WBB DSIC mechanism trades at each of them with probability more than 1 / 2 1/2 1/2 .
From trade probability to traders’ surplus. If we only cared about the gains from trade, which do not depend on the payments, we could stop here: as explained above, for such distributions, the difference in the trade probabilities gives an unbounded separation between the gains from trade of WBB and SBB DSIC mechanisms. However, at the profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) , the payments leave the traders with zero surplus. The payments of Myerson’s lemma charge each trader the values at which his or her trade probability jumps, and at this profile these are the thresholds themselves: the buyer pays b i ⋅ x W B B ( s i − 1 , b i ) b_i \cdot x^{\mathrm{WBB}}(s_{i-1},b_i) b i ⋅ x WBB ( s i − 1 , b i ) and the seller receives s i − 1 ⋅ x W B B ( s i − 1 , b i ) s_{i-1} \cdot x^{\mathrm{WBB}}(s_{i-1},b_i) s i − 1 ⋅ x WBB ( s i − 1 , b i ) , so the entire gain from trade is burned. To obtain a separation for the traders’ surplus, we need a more nuanced argument, which uses how the construction relates the trade probabilities at different levels.
By Myerson’s lemma, WBB at a profile ( v s , v b ) (v_s,v_b) ( v s , v b ) with x W B B ( v s , v b ) > 0 x^{\mathrm{WBB}}(v_s,v_b)>0 x WBB ( v s , v b ) > 0 is equivalent to
∫ v s v b x W B B ( v s , z ) d z + ∫ v s v b x W B B ( z , v b ) d z ≤ ( v b − v s ) x W B B ( v s , v b ) . \int_{v_s}^{v_b} x^{\mathrm{WBB}}(v_s,z)\,\mathrm{d}z+\int_{v_s}^{v_b} x^{\mathrm{WBB}}(z,v_b)\,\mathrm{d}z\leq(v_b-v_s)x^{\mathrm{WBB}}(v_s,v_b). ∫ v s v b x WBB ( v s , z ) d z + ∫ v s v b x WBB ( z , v b ) d z ≤ ( v b − v s ) x WBB ( v s , v b ) .
The left-hand side is the traders’ surplus: the first integral is the buyer’s utility and the second is the seller’s surplus. The right-hand side is the expected gain from trade at this profile. Thus, WBB says that the traders’ surplus is at most this gain, and the difference is the money burned. Apart from the profiles whose values are rounded to the same thresholds as ( v s , v b ) (v_s,v_b) ( v s , v b ) , both integrals only involve profiles at lower levels, or profiles with zero trade probability (see Figure 2 ). We therefore construct the allocation rule level by level, from the bottom up. At the level-1 profiles ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) , both integrals are zero, so the trade probabilities at level 1 can be chosen freely, and the traders’ surplus is zero. Now consider the level-2 profile ( s i − 1 , b i + 1 ) (s_{i-1},b_{i+1}) ( s i − 1 , b i + 1 ) . It plays the role of ( s 1 , b 2 ) (s_1,b_2) ( s 1 , b 2 ) in the argument above (see the paragraph “Why randomization is needed”), with the level-1 profiles ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) and ( s i , b i + 1 ) (s_i,b_{i+1}) ( s i , b i + 1 ) in the roles of ( s 1 , b 1 ) (s_1,b_1) ( s 1 , b 1 ) and ( s 2 , b 2 ) (s_2,b_2) ( s 2 , b 2 ) . The buyer’s integral covers the trade probability at level 1 for buyer values between b i b_i b i and b i + 1 b_{i+1} b i + 1 , and the seller’s integral covers the trade probability at level 1 for seller values between s i − 1 s_{i-1} s i − 1 and s i s_i s i . These two ranges together are slightly longer than b i + 1 − s i − 1 b_{i+1}-s_{i-1} b i + 1 − s i − 1 , so the trade probability at level 2 must be higher than at level 1, which is where the growth factor comes from. On the other hand, since the trade probability at level 1 is more than 1 / 2 1/2 1/2 , the traders’ surplus at this profile is more than ( b i + 1 − s i − 1 ) / 2 (b_{i+1}-s_{i-1})/2 ( b i + 1 − s i − 1 ) /2 , that is, more than half of the first-best gain from trade at this profile. The same holds at every higher level.
Figure 2. Dependence between the levels of the allocation rule, for n = 5 n = 5 n = 5 . Each cell is the rectangle of profiles with seller index ι S ( v s ) \iota_S(v_s) ι S ( v s ) (horizontal) and buyer index ι B ( v b ) \iota_B(v_b) ι B ( v b ) (vertical); cells are not drawn to scale. Gray cells have no trade. The cells on the diagonal are at level 1 (yellow): the cell labeled K i K_i K i contains the profile ( s i − 1 , b i ) (s_{i-1}, b_i) ( s i − 1 , b i ) . Darker cells are at higher levels. WBB at the cell with the solid red border involves the cells below it in its column and to its right in its row, down to level 1 (dashed), which correspond to the two integrals. (a) The level-2 cell above K 2 K_2 K 2 and K 3 K_3 K 3 is constrained by these two level-1 cells. (b) A level-3 cell is constrained by two cells at level 1 and two cells at level 2. Hence, the allocation rule is determined level by level, starting from level 1.
An SBB DSIC mechanism, in contrast, trades at the profile ( s i − 1 , b i + 1 ) (s_{i-1},b_{i+1}) ( s i − 1 , b i + 1 ) only if its price falls in [ s i − 1 , b i + 1 ] ⊆ [ q i − 1 , q i + 1 ] [s_{i-1},b_{i+1}]\subseteq[q_{i-1},q_{i+1}] [ s i − 1 , b i + 1 ] ⊆ [ q i − 1 , q i + 1 ] , so it leaves the traders at most the gain from trade times the probability of this event (Claim A.2 ). Unlike the level-1 intervals, the intervals [ q i − 1 , q i + 1 ] [q_{i-1},q_{i+1}] [ q i − 1 , q i + 1 ] overlap, but every price lies in at most three of them, so the probabilities that the price falls in them sum to at most three. Lemma 4.5 describes the distributions for which this gives an unbounded gap: if most of the first-best gains-from-trade comes from such level-2 profiles, and each i i i contributes the same amount, then our WBB DSIC mechanism obtains more than half of every contribution, while every SBB DSIC mechanism obtains, in total, only a constant number of them.
The distributions. It remains to construct distributions that satisfy the conditions of Lemma 4.5 . For independent values, the seller’s value is likely to be near a high grid point and the buyer’s value is likely to be near a low grid point. Hence, a profile in which the buyer’s grid point is more than two steps above the seller’s is unlikely, and a profile in which it is below the seller’s has no gain from trade. Thus, all but a small fraction of the first-best gains-from-trade comes from level-2 profiles. Figure 3 in § 4.2 shows the probabilities of the resulting independent distribution, and Figure 4 shows how they translate into contributions to the first-best gains-from-trade, almost all of which come from the level-2 profiles. For correlated values, we draw an index i i i and then a seller value near q i − 1 q_{i-1} q i − 1 and a buyer value near q i + 1 q_{i+1} q i + 1 , with probability inversely proportional to the gain from trade between these values, so that each i i i contributes approximately the same amount to the first-best gains-from-trade. Since the gaps of the grid grow quickly, the seller’s values are small compared to the gains from trade, so the traders’ utility is close to the traders’ surplus.
Figure 3. The support of the independent distribution F s × F b F_s \times F_b F s × F b of § 4.2 , for k = 6 k = 6 k = 6 (so n = 12 n = 12 n = 12 ) and R = 10 5 R = 10^5 R = 1 0 5 . The seller’s value is slightly above one of q 1 , q 3 , … , q 9 q_1,q_3,\ldots,q_9 q 1 , q 3 , … , q 9 , and the buyer’s value is slightly below one of q 3 , q 5 , … , q 11 q_3,q_5,\ldots,q_{11} q 3 , q 5 , … , q 11 , so the values lie in the small squares S ℓ × B r S_\ell\times B_r S ℓ × B r , and all other profiles have probability 0. The color of each square shows its probability, from blue (low) to red (high). The probabilities range from about 10 − 40 10^{-40} 1 0 − 40 to almost 1, so the color scale is logarithmic. The seller’s value is likely to be near a high grid point and the buyer’s value is likely to be near a low grid point, so the most likely squares are at the top left, above the dashed diagonal v b = v s v_b = v_s v b = v s , where v b < v s v_b < v_s v b < v s and there is no gain from trade (see Figure 4 ). The grid points are drawn evenly spaced, not to scale.
Figure 4. The contribution of each square of Figure 3 to the first-best gains-from-trade, that is, E [ ( v b − v s ) + ⋅ 1 ( v s , v b ) ∈ S ℓ × B r ] \mathbb{E}[(v_b-v_s)_+ \cdot\mathbf{1}_{(v_s,v_b)\in S_\ell\times B_r}] E [( v b − v s ) + ⋅ 1 ( v s , v b ) ∈ S ℓ × B r ] . The color of each square shows its normalized contribution, that is, its contribution divided by C C C , so a value of 1 means a contribution of C C C . The squares above the dashed diagonal v b = v s v_b=v_s v b = v s , drawn as empty gray squares, have v b < v s v_b<v_s v b < v s and contribute nothing. The squares next to the diagonal, with the seller’s value near q 2 ℓ − 1 q_{2\ell-1} q 2 ℓ − 1 and the buyer’s value near q 2 ℓ + 1 q_{2\ell+1} q 2 ℓ + 1 , are the sets R 2 ℓ − 1 R_{2\ell-1} R 2 ℓ − 1 at level 2, and each of them contributes about C C C . The other squares below the diagonal have gains from trade, but they are unlikely. We choose the probabilities (Equation (22) ) so that together they contribute at most C C C , about as much as a single set R 2 ℓ − 1 R_{2\ell-1} R 2 ℓ − 1 . As in Figure 3 , the grid points are drawn evenly spaced, not to scale.
Our Technique: The Limitations of Money Burning
We now describe the main ideas behind Theorem 3 , which shows that although DSIC mechanisms that are only weakly budget-balanced can be arbitrarily better for the agents than those that are strongly so, WBB DSIC mechanisms still cannot provide, in the worst case, a constant fraction of the first-best gains-from-trade when the values are independent, or of the first-best social welfare when the values may be correlated. Previous impossibility results [11 , 39 ] rely on the fact that every SBB DSIC mechanism is a distribution over posted prices [53 CP16] . This fails for WBB DSIC mechanisms, so we need a different approach.
We show that WBB DSIC mechanisms are inherently limited: they fail on some distributions in which almost all of the contribution to the first-best benchmark comes from the accumulated contributions of many profiles spread out over the value space, each with small gain from trade. We show that these mechanisms fail by proving that the average trade probability of every such mechanism at these profiles must be close to zero. To see why, note that to obtain a constant fraction of the first-best on such distributions, a mechanism has to trade at these profiles with substantial average probability. For WBB to hold, this forces a higher average trade probability at profiles with a larger gain from trade. After many such steps, the average trade probability exceeds 1, which is impossible (Lemma 5.4 ). For the social welfare with correlated values, a similar argument applies to profiles on a geometric grid (Lemma 5.8 ).
Organization of the paper. Section 2 discusses additional related work. Section 3 presents the model, the budget-balance requirements, the allocation and traders’ objectives, and the structural results used throughout. Section 4 explains the intuition behind our construction of WBB mechanisms, presents the construction and a separation lemma based on it, and uses them to prove the unbounded separations for the traders’ surplus under independent values and for the traders’ utility under correlated values. Section 5 shows that WBB mechanisms cannot guarantee a constant fraction of the first-best gains-from-trade under independent values, or of the first-best social welfare under correlated values. Omitted proofs are deferred to Appendix A.
Additional Related Work
Approximately efficient mechanisms. Most of the results in this literature are for independent values, and we discuss these first. Myerson and Satterthwaite [69 ] showed that no BIC and no-deficit mechanism can implement the first-best under mild conditions. This impossibility motivates the study of approximately efficient mechanisms. For gains-from-trade, [66 ] showed that when the median of the buyer’s value exceeds the median of the seller’s value, any fixed price between the two medians obtains at least half of the first-best gains-from-trade. However, [11 ] showed that without such a condition, no deterministic, SBB mechanism in which both traders have a dominant strategy guarantees a constant approximation to the first-best. This impossibility extends to randomized mechanisms with these properties, since by [53 CP16] every such randomized mechanism is a distribution over posted prices.9 To overcome this impossibility, BIC mechanisms were considered. Blumrosen and Mizrahi [16 ] showed that the seller-offering mechanism provides a constant approximation for distributions satisfying a certain condition. For general independent distributions, [10 ] showed that the random-offerer mechanism, which with probability 1/2 runs the seller-offering mechanism and with probability 1/2 the symmetric buyer-offering mechanism, obtains at least half of the second-best gains-from-trade, that is, of the gains-from-trade of the optimal SBB BIC mechanism. In a breakthrough, [38 ] proved that this mechanism also provides a constant approximation to the first-best. Subsequent works improved the approximation factor and analyzed the limitations of the random-offerer mechanism [44 , 56 , 22 , 13 , 29 CGLM26, SC26] . Recently, [61 ] showed that the second-best mechanism always obtains at least half of the first-best gains-from-trade, and that this is tight.
For social welfare, however, fixed prices suffice to give a constant approximation under independent values. A long line of work has therefore studied how well a fixed price can perform [11 , 26 , 12 , 57 , 34 , 63 , 49 ] , showing that the best fixed price always obtains approximately a 0.738024 fraction of the first-best welfare, and that this is tight [55 , 64 ] . By the posted-price characterization [53 CP16] , no randomized, SBB DSIC mechanism obtains a better ratio. When incentive compatibility is relaxed so that only one trader has a dominant strategy and the other is BIC, a better ratio is possible: the buyer-offering mechanism with a reserve price obtains a 0.746 fraction of the first-best welfare [40 ] . When incentive compatibility is relaxed further, so that both traders are only BIC, the second-best mechanism obtains approximately a 0.888 fraction of the first-best welfare, and this is tight [62 ] .
With correlated values, no SBB mechanism in which both traders have a dominant strategy guarantees a constant approximation to the first-best social welfare, while the buyer-offering mechanism, in which only the seller has a dominant strategy, obtains a ( 1 − 1 / e ) (1 - 1/e) ( 1 − 1/ e ) fraction of the first-best welfare [39 ] . For gains-from-trade, no SBB BIC mechanism guarantees a constant approximation to the first-best [RW24]. Welfare approximation was also studied for traders with interdependent values [36 ] .
Weakly budget-balanced mechanisms in bilateral trade. For B I C BIC B I C and interim IR mechanisms with independent values, money burning does not help: every ex-ante WBB mechanism can be converted into an ex-post SBB one without reducing the traders’ expected utility [18 , 10 , 67 ] . For deterministic D S I C DSIC D S I C mechanisms, money burning does not help either: the results of [37 ] imply that the allocation rule of every deterministic, WBB DSIC mechanism is pointwise dominated by that of a posted price (Proposition 3.7 ).
The work most closely related to our positive results shows that for correlated values, a weakly budget-balanced mechanism can obtain more traders’ surplus (which they call gains-from-trade) than every posted-price mechanism [SW18]. They suggest that correlation is crucial for this gain, since with independent values they found no case where their mechanisms beat posted prices, and they ask whether the optimal mechanism is indeed SBB in that case. Our results strengthen this separation in two ways. First, our separation for traders’ surplus holds even for independent distributions, while theirs uses correlated values. Second, the advantage in our separation is unbounded, also for the traders’ utility when the values are correlated, while theirs establishes a constant separation.
Manea and Maskin [67 ] also consider withholding or damaging the item in Bayesian bilateral trade with independent values. For discrete distributions, neither withholding the item from both traders nor damaging it for the buyer improves welfare. They show, however, that damaging it for the seller can sometimes be useful. Their results extend to continuous distributions under additional assumptions.
Extensions of bilateral trade. Bilateral trade has been extended to double auctions with many buyers and sellers. McAfee’s trade reduction mechanism [65 ] is a WBB DSIC double auction. It was extended to supply chains [17 , 21 ] and to spatially distributed markets [19 ] . Segal-Halevi, Hassidim, and Aumann [SHHA16] extended it to an SBB DSIC double auction. Brustle, Cai, Wu, and Zhao [10 ] obtained a constant approximation to the second-best gains-from-trade in double auctions. Babaioff, Cai, Gonczarowski, and Zhao [9 ] combined trade reduction with the random-offerer mechanism, which reduces double auctions to bilateral trade whenever the first-best has a single trade. Together with [38 ] , this gives a constant approximation to the first-best gains-from-trade in double auctions. For the social welfare, constant approximations are known as well [26 ] . The random-offerer mechanism was extended to matching markets, where it obtains a constant approximation to the first-best gains-from-trade [20 , 22 ] , and the guarantees of the second-best mechanism were extended to matching markets as well [15 , 62 ] . Bilateral trade was also extended to traders with multi-dimensional values [29 , 70 ] , to markets with one seller and two buyers [14 ] , and to trades that involve more than two agents [41 ] .
No-regret learning in bilateral trade. Bilateral trade was also studied in an online setting, where in every round the mechanism posts prices to a new seller and buyer, and the goal is to minimize the regret with respect to the best fixed price in hindsight [24 , 3 , 25 , 8 , 30 , 58 , 60 , 5 , 6 , 7 , 46 , 27 , 2 , 59 ] . Some of these works post a higher price to the buyer than to the seller, or allow the mechanism to violate budget balance in some rounds. There, this helps learning by providing more informative feedback across rounds. Each of these two prices is set independently of both traders’ reports, and each trader only decides whether to accept the price he faces. Without learning, if the buyer’s price is higher, offering both traders any common price between these two prices can only increase the probability of trade (without any impact on incentives), so posting such different prices can only be harmful.
Money burning in other settings. Money burning was previously studied in settings with one-sided private information: only the buyers have private values, while the designer, who is also the seller and owns the items, has none. The goal is to maximize the buyers’ surplus, that is, the value the buyers get from the allocation minus their payments, while the seller’s revenue does not count. This objective makes sense in settings where payments are unavailable or undesirable, such as the allocation of healthcare. The study of money-burning mechanisms for this objective, also known as the residual surplus , was introduced in [54 ] , which characterized the optimal mechanisms in single-parameter auction settings. Money burning in general domains was studied in [45 ] . For unit-demand buyers with i.i.d. values, [50 ] give mechanisms whose surplus approximates the optimal welfare, with tight bounds. A framework for designing mechanisms that maximize the surplus was given in [42 ] , and applied to unit-demand bidders, multi-unit auctions, and divisible goods, obtaining mechanisms with optimal approximation guarantees with respect to the social welfare. In general multidimensional settings, a prior-free mechanism obtains a 1 / H n 1/H_n 1/ H n fraction of the optimal welfare, and this is tight [43 ] . Unit-demand buyers with independent values were studied in [51 ] , and an online setting in [52 ] . The allocation of items when agents can signal their values only through wasteful costs was also studied in economics [32 Yo11, CK13] . Money burning was also studied for the allocation of a single item between two buyers who can exchange money, with the goal of maximizing the buyers’ surplus [SZ16]. Finally, money burning also appears in delegation settings [1 ] .
Redistribution of VCG payments. A closely related line of work studies the same objective as in the previous paragraph, the agents’ total utility, but focuses on the VCG mechanism. In allocation problems, the VCG mechanism is efficient and DSIC, but the agents’ payments go to the designer and reduce the agents’ total utility. These works redistribute as much of these payments as possible back to the agents without violating incentive compatibility, and any payment that is not redistributed is lost [4 , 23 , 48 , 68 ] . Guo and Conitzer [47 ] show that allocating inefficiently, by withholding some units, can increase the agents’ total utility, and de Clippel et al. [35 ] show that destroying items can have a similar effect.
Preliminaries
The Bilateral Trade Problem
In bilateral trade there are two agents: a seller, who initially owns one indivisible item, and a buyer. The buyer’s value for receiving the item is v b ∈ V b v_b \in V_b v b ∈ V b , and the seller’s value for keeping the item is v s ∈ V s v_s \in V_s v s ∈ V s , where the value spaces V b , V s ⊆ R ≥ 0 V_b, V_s \subseteq\mathbb{R}_{\geq0} V b , V s ⊆ R ≥ 0 are (possibly unbounded) intervals, satisfying V b = V s = V V_b = V_s = V V b = V s = V . Although both value spaces are equal, we keep separate notation for them to make clear which agent’s value each argument refers to.
The valuation profile ( v s , v b ) (v_s, v_b) ( v s , v b ) is drawn from a known joint distribution F \mathcal{F} F over V s × V b V_s \times V_b V s × V b . The values may be correlated. We denote the seller and buyer marginals of F \mathcal{F} F by F s \mathcal{F}_s F s and F b \mathcal{F}_b F b , respectively. When values are independent, F = F s × F b \mathcal{F} = \mathcal{F}_s \times\mathcal{F}_b F = F s × F b .
A randomized (direct revelation) mechanism M = ( x , p B , p S ) \mathcal{M} = (x, p_B, p_S) M = ( x , p B , p S ) consists of three measurable functions:
an allocation rule x : V s × V b → [ 0 , 1 ] x : V_s \times V_b \to[0,1] x : V s × V b → [ 0 , 1 ] , where x ( v s , v b ) x(v_s, v_b) x ( v s , v b ) is the probability of trade; and
payment rules6 ^6 6 p B , p S : V s × V b → R p_B, p_S : V_s \times V_b \to\mathbb{R} p B , p S : V s × V b → R , where p B ( v s , v b ) p_B(v_s, v_b) p B ( v s , v b ) is the expected payment made by the buyer, and p S ( v s , v b ) p_S(v_s, v_b) p S ( v s , v b ) is the expected payment that the seller receives.
A direct revelation mechanism is deterministic if it uses no internal randomness (its allocation and payments are deterministically determined). In particular, its allocation function x x x takes values in { 0 , 1 } \{0,1\} { 0 , 1 } .^7 We assume that both the seller and buyer have quasi-linear utilities and are risk neutral. That is, in a mechanism M = ( x , p B , p S ) \mathcal{M} = (x, p_B, p_S) M = ( x , p B , p S ) , for a valuation profile ( v s , v b ) ∈ V s × V b (v_s, v_b) \in V_s \times V_b ( v s , v b ) ∈ V s × V b and reports v s ′ ∈ V s v'_s \in V_s v s ′ ∈ V s and v b ′ ∈ V b v'_b \in V_b v b ′ ∈ V b , the agents’ utilities are:
u b ( v b , ( v s ′ , v b ′ ) ) = v b ⋅ x ( v s ′ , v b ′ ) − p B ( v s ′ , v b ′ ) , u_b(v_b, (v'_s, v'_b)) = v_b \cdot x(v'_s, v'_b) - p_B(v'_s, v'_b), u b ( v b , ( v s ′ , v b ′ )) = v b ⋅ x ( v s ′ , v b ′ ) − p B ( v s ′ , v b ′ ) ,
u s ( v s , ( v s ′ , v b ′ ) ) = p S ( v s ′ , v b ′ ) + v s ⋅ ( 1 − x ( v s ′ , v b ′ ) ) . u_s(v_s, (v'_s, v'_b)) = p_S(v'_s, v'_b) + v_s \cdot(1 - x(v'_s, v'_b)). u s ( v s , ( v s ′ , v b ′ )) = p S ( v s ′ , v b ′ ) + v s ⋅ ( 1 − x ( v s ′ , v b ′ )) .
Definition 3.1. A randomized mechanism M = ( x , p B , p S ) \mathcal{M} = (x, p_B, p_S) M = ( x , p B , p S ) is dominant-strategy incentive compatible (DSIC) if, for every valuation profile ( v s , v b ) ∈ V s × V b (v_s, v_b) \in V_s \times V_b ( v s , v b ) ∈ V s × V b , each agent maximizes his expected utility by reporting his actual value, regardless of the other agent’s report, where the expectation is over the mechanism’s internal randomness. That is, for every v b ′ , v b ∈ V b v'_b, v_b \in V_b v b ′ , v b ∈ V b and v s , v s ′ ∈ V s v_s, v'_s \in V_s v s , v s ′ ∈ V s ,
u b ( v b , ( v s ′ , v b ) ) ≥ u b ( v b , ( v s ′ , v b ′ ) ) (1) u_b(v_b, (v'_s, v_b)) \geq u_b(v_b, (v'_s, v'_b)) \tag*{(1)} u b ( v b , ( v s ′ , v b )) ≥ u b ( v b , ( v s ′ , v b ′ )) (1) u s ( v s , ( v s , v b ′ ) ) ≥ u s ( v s , ( v s ′ , v b ′ ) ) (2) u_s(v_s, (v_s, v'_b)) \geq u_s(v_s, (v'_s, v'_b)) \tag*{(2)} u s ( v s , ( v s , v b ′ )) ≥ u s ( v s , ( v s ′ , v b ′ )) (2)
In this paper, we only consider DSIC mechanisms, and thus by the revelation principle, we can always assume that the agents report truthfully, that is, v s ′ = v s v'_s = v_s v s ′ = v s and v b ′ = v b v'_b = v_b v b ′ = v b , and for such mechanisms we drop the reports from the utility notation:
u b ( v s , v b ) = v b ⋅ x ( v s , v b ) − p B ( v s , v b ) , (3) u_b(v_s,v_b) = v_b \cdot x(v_s,v_b) - p_B(v_s,v_b), \tag*{(3)} u b ( v s , v b ) = v b ⋅ x ( v s , v b ) − p B ( v s , v b ) , (3)
u s ( v s , v b ) = p S ( v s , v b ) + v s ⋅ ( 1 − x ( v s , v b ) ) . (4) u_s(v_s,v_b) = p_S(v_s,v_b) + v_s \cdot\left(1 - x(v_s,v_b)\right). \tag*{(4)} u s ( v s , v b ) = p S ( v s , v b ) + v s ⋅ ( 1 − x ( v s , v b ) ) . (4)
Following the standard terminology from the algorithmic mechanism-design literature, we sometimes distinguish between two classes of randomized DSIC mechanisms. The first class is of universally truthful mechanisms; such a mechanism is a distribution over deterministic DSIC mechanisms. Here, truthful reporting maximizes each agent’s utility for every realization of the mechanism’s internal randomness. The second class is truthful in expectation mechanisms. In such a mechanism truthful reporting maximizes each agent’s expected utility, where the expectation is over the mechanism’s internal randomness. This is consistent with Definition 3.1 . Thus, every universally truthful mechanism is truthful in expectation, but not necessarily vice-versa.
Definition 3.2. A randomized mechanism is individually rational (IR) if, for every valuation profile ( v s , v b ) ∈ V s × V b (v_s,v_b) \in V_s \times V_b ( v s , v b ) ∈ V s × V b , each agent’s expected utility, where the expectation is only over the mechanism’s internal randomness, is at least as large as his utility when not participating in the mechanism, under truthful reporting. Equivalently,
u b ( v s , v b ) ≥ 0 , (5) u_b(v_s,v_b) \ge0, \tag*{(5)} u b ( v s , v b ) ≥ 0 , (5) u s ( v s , v b ) ≥ v s . (6) u_s(v_s,v_b) \ge v_s. \tag*{(6)} u s ( v s , v b ) ≥ v s . (6)
As we focus on DSIC mechanisms, individual rationality requires the above inequalities to hold for every valuation profile separately: the expectation is only over the mechanism’s internal randomness. Unlike interim individual rationality in the Bayesian setting, it does not average over the other agent’s value.
Throughout this paper, unless stated otherwise, any mechanism we consider must be both individually rational (IR) and dominant-strategy incentive compatible (DSIC). Trade mechanisms are also required not to lose money:
Definition 3.3. A randomized mechanism is weakly budget balanced (WBB) if, for every valuation profile ( v s , v b ) ∈ V s × V b (v_s,v_b) \in V_s \times V_b ( v s , v b ) ∈ V s × V b , the expected payment of the buyer is at least the expected payment of the seller, where the expectation is only over the mechanism’s internal randomness. Equivalently,
p B ( v s , v b ) ≥ p S ( v s , v b ) . (7) p_B(v_s,v_b) \ge p_S(v_s,v_b). \tag*{(7)} p B ( v s , v b ) ≥ p S ( v s , v b ) . (7)
The mechanism is called strongly budget-balanced (SBB) if this inequality holds as equality.
We also consider ex-post versions of these notions. A randomized mechanism satisfies ex-post individual rationality (ex-post IR) if, for every valuation profile ( v s , v b ) ∈ V s × V b (v_s,v_b) \in V_s \times V_b ( v s , v b ) ∈ V s × V b , the individual rationality conditions in Equations (5) and (6) hold for every realization of the mechanism’s internal randomness, rather than merely in expectation over this randomness. Similarly, a randomized mechanism is ex-post weakly budget balanced (ex-post WBB) or ex-post strongly budget-balanced (ex-post SBB) if the corresponding payment condition (inequality (7) ) holds for every valuation profile and every realization of the mechanism’s internal randomness (with equality, for ex-post SBB).
Throughout the paper, individual rationality, strong budget balance, and weak budget balance refer to expectations over the mechanism’s internal randomness, at every valuation profile. We explicitly use the qualifier “ex-post” when requiring these properties for every realization of this randomness.
The following remark is a simple useful fact, also used in the literature before.
Basic Properties
We repeatedly use the following simple consequence of dominant-strategy incentive compatibility, individual rationality, and weak budget balance, which follows from Myerson’s lemma.
Lemma 3.6 (Allocation inequality from dominant-strategy incentive compatibility, individual rationality, and weak budget balance). Let M = ( x , p B , p S ) \mathcal{M}=(x,p_B,p_S) M = ( x , p B , p S ) be a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism. For every v s ∈ V s , v b ∈ V b v_s\in V_s,v_b\in V_b v s ∈ V s , v b ∈ V b such that v s ≤ v b v_s\le v_b v s ≤ v b ,
∫ v s v b x ( z , v b ) d z + ∫ v s v b x ( v s , z ) d z ≤ ( v b − v s ) ⋅ x ( v s , v b ) . (8) \int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z+\int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z\le(v_b-v_s)\cdot x(v_s,v_b). \tag*{(8)} ∫ v s v b x ( z , v b ) d z + ∫ v s v b x ( v s , z ) d z ≤ ( v b − v s ) ⋅ x ( v s , v b ) . (8)
Proof of Lemma 3.6. Note that, for every valuation profile ( v s , v b ) (v_s,v_b) ( v s , v b ) , WBB and IR imply
v s ⋅ x ( v s , v b ) ≤ p S ( v s , v b ) ≤ p B ( v s , v b ) ≤ v b ⋅ x ( v s , v b ) . (9) v_s\cdot x(v_s,v_b)\le p_S(v_s,v_b)\le p_B(v_s,v_b)\le v_b\cdot x(v_s,v_b). \tag*{(9)} v s ⋅ x ( v s , v b ) ≤ p S ( v s , v b ) ≤ p B ( v s , v b ) ≤ v b ⋅ x ( v s , v b ) . (9)
This has two consequences. First, if there is no trade, that is, x ( v s , v b ) = 0 x(v_s,v_b)=0 x ( v s , v b ) = 0 , then both payments are zero: p B ( v s , v b ) = p S ( v s , v b ) = 0 p_B(v_s,v_b)=p_S(v_s,v_b)=0 p B ( v s , v b ) = p S ( v s , v b ) = 0 . Second, if v s > v b v_s>v_b v s > v b , then (9) forces x ( v s , v b ) = 0 x(v_s,v_b)=0 x ( v s , v b ) = 0 , and hence both payments are zero. If v s = v b v_s=v_b v s = v b , all the inequalities in (9) hold with equality, so
p B ( v s , v s ) = p S ( v s , v s ) = v s ⋅ x ( v s , v s ) . (10) p_B(v_s,v_s)=p_S(v_s,v_s)=v_s\cdot x(v_s,v_s). \tag*{(10)} p B ( v s , v s ) = p S ( v s , v s ) = v s ⋅ x ( v s , v s ) . (10)
Applying Myerson’s lemma, for v s ≤ v b v_s\le v_b v s ≤ v b we obtain
p B ( v s , v b ) = v b ⋅ x ( v s , v b ) − ∫ v s v b x ( v s , z ) d z + p B ( v s , v s ) − v s ⋅ x ( v s , v s ) = ( 10 ) v b ⋅ x ( v s , v b ) − ∫ v s v b x ( v s , z ) d z \begin{aligned}
p_B(v_s,v_b)&=v_b\cdot x(v_s,v_b)-\int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z+p_B(v_s,v_s)-v_s\cdot x(v_s,v_s)\\
&\underset{(10)}{=}v_b\cdot x(v_s,v_b)-\int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z
\end{aligned} p B ( v s , v b ) = v b ⋅ x ( v s , v b ) − ∫ v s v b x ( v s , z ) d z + p B ( v s , v s ) − v s ⋅ x ( v s , v s ) ( 10 ) = v b ⋅ x ( v s , v b ) − ∫ v s v b x ( v s , z ) d z
and
p S ( v s , v b ) = v s ⋅ x ( v s , v b ) + ∫ v s v b x ( z , v b ) d z + p S ( v b , v b ) − v b ⋅ x ( v b , v b ) = v s ⋅ x ( v s , v b ) + ∫ v s v b x ( z , v b ) d z . (11) \begin{aligned}
p_S(v_s,v_b)=v_s\cdot x(v_s,v_b)+\int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z+p_S(v_b,v_b)-v_b\cdot x(v_b,v_b) \\
&=v_s\cdot x(v_s,v_b)+\int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z. \tag*{(11)}
\end{aligned} p S ( v s , v b ) = v s ⋅ x ( v s , v b ) + ∫ v s v b x ( z , v b ) d z + p S ( v b , v b ) − v b ⋅ x ( v b , v b ) = v s ⋅ x ( v s , v b ) + ∫ v s v b x ( z , v b ) d z . (11)
WBB gives p B ( v s , v b ) ≥ p S ( v s , v b ) p_B(v_s,v_b)\ge p_S(v_s,v_b) p B ( v s , v b ) ≥ p S ( v s , v b ) . Substituting the two payment identities into this inequality and rearranging gives Equation (8) .
Drexl and Kleiner [37 ] show that, for every pair of independent distributions over the agents’ values, an optimal deterministic, WBB DSIC and IR mechanism for the sum of the agents’ utilities can be chosen to be SBB. Their proof implies the following stronger, pointwise statement about the allocation rule.
Proposition 3.7 (Essentially [37 ] ). For every deterministic, dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced bilateral-trade mechanism with allocation rule x x x , there is a deterministic, dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism with allocation rule x ′ x' x ′ such that
x ( v s , v b ) ≤ x ′ ( v s , v b ) x(v_s,v_b)\le x'(v_s,v_b) x ( v s , v b ) ≤ x ′ ( v s , v b ) for every valuation profile ( v s , v b ) (v_s,v_b) ( v s , v b ) .
The proof of Proposition 3.7 is deferred to Appendix § 7 .§ 1 .
Objectives
Our two main objectives are the traders’ utility , which is the sum of the buyer’s and seller’s utilities, and the traders’ surplus , which is the improvement in this sum relative to no trade (the seller keeps the item). Under WBB, the buyer may pay more than the seller receives. The mechanism’s surplus , denoted by u M ( v s , v b ) u_M(v_s,v_b) u M ( v s , v b ) , is the expectation of the difference between the payment collected from the buyer and the payment made to the seller. Under WBB it is nonnegative, and under SBB it is zero. We take the traders’ perspective and interpret the mechanism’s surplus as money burned: it is paid by the buyer but not received by the seller.
Adding the mechanism’s surplus to the traders’ utility gives the standard notion of social welfare : the total utility of the buyer, the seller, and the mechanism. Since payments cancel in this sum, it equals the expected value of the agent who holds the item at the end of the mechanism’s execution. Similarly, adding the mechanism’s surplus to the traders’ surplus gives the gains-from-trade : the improvement in social welfare relative to no trade. These objectives depend only on the allocation, so we call them allocation-based objectives . Equivalently, the traders’ utility and the traders’ surplus are obtained from social welfare and gains-from-trade by removing the mechanism’s surplus. Thus, under WBB, each traders’ objective is at most its allocation-based counterpart; under SBB, the corresponding objectives coincide.
Formally, for every mechanism M = ( x , p B , p S ) \mathcal{M}=(x,p_B,p_S) M = ( x , p B , p S ) and valuation profile ( v s , v b ) ∈ V s × V b (v_s,v_b)\in V_s\times V_b ( v s , v b ) ∈ V s × V b , the buyer’s surplus is his utility, T S M b ( v s , v b ) = v b ⋅ x ( v s , v b ) − p B ( v s , v b ) \mathrm{TS}^{b}_{\mathcal{M}}(v_s,v_b)=v_b\cdot x(v_s,v_b)-p_B(v_s,v_b) TS M b ( v s , v b ) = v b ⋅ x ( v s , v b ) − p B ( v s , v b ) , and the seller’s surplus is the improvement in her utility relative to keeping the item, T S M s ( v s , v b ) = p S ( v s , v b ) − v s ⋅ x ( v s , v b ) \mathrm{TS}^{s}_{\mathcal{M}}(v_s,v_b)=p_S(v_s,v_b)-v_s\cdot x(v_s,v_b) TS M s ( v s , v b ) = p S ( v s , v b ) − v s ⋅ x ( v s , v b ) . By individual rationality, both are nonnegative. The mechanism’s surplus is
u M ( v s , v b ) = p B ( v s , v b ) − p S ( v s , v b ) . (12) u_{\mathcal{M}}(v_s,v_b)=p_B(v_s,v_b)-p_S(v_s,v_b). \tag*{(12)} u M ( v s , v b ) = p B ( v s , v b ) − p S ( v s , v b ) . (12)
The objectives that include this surplus are
S W M ( v s , v b ) = u b ( v s , v b ) + u s ( v s , v b ) + u M ( v s , v b ) = v b ⋅ x ( v s , v b ) + v s ⋅ ( 1 − x ( v s , v b ) ) , (13) \begin{aligned}
\mathrm{SW}_{\mathcal{M}}(v_s,v_b) &= u_b(v_s,v_b) + u_s(v_s,v_b) + u_{\mathcal{M}}(v_s,v_b) \\
&= v_b \cdot x(v_s,v_b) + v_s \cdot(1-x(v_s,v_b)), \tag*{(13)}
\end{aligned} SW M ( v s , v b ) = u b ( v s , v b ) + u s ( v s , v b ) + u M ( v s , v b ) = v b ⋅ x ( v s , v b ) + v s ⋅ ( 1 − x ( v s , v b )) , (13)
G F T M ( v s , v b ) = S W M ( v s , v b ) − v s = ( v b − v s ) ⋅ x ( v s , v b ) . (14) \mathrm{GFT}_{\mathcal{M}}(v_s,v_b) = \mathrm{SW}_{\mathcal{M}}(v_s,v_b) - v_s = (v_b-v_s)\cdot x(v_s,v_b). \tag*{(14)} GFT M ( v s , v b ) = SW M ( v s , v b ) − v s = ( v b − v s ) ⋅ x ( v s , v b ) . (14)
The objectives that count only the traders’ utilities are
T U M ( v s , v b ) = u b ( v s , v b ) + u s ( v s , v b ) = S W M ( v s , v b ) − u M ( v s , v b ) , (15) \begin{aligned}
\mathrm{TU}_{\mathcal{M}}(v_s,v_b) &= u_b(v_s,v_b) + u_s(v_s,v_b) \\
&= \mathrm{SW}_{\mathcal{M}}(v_s,v_b) - u_{\mathcal{M}}(v_s,v_b), \tag*{(15)}
\end{aligned} TU M ( v s , v b ) = u b ( v s , v b ) + u s ( v s , v b ) = SW M ( v s , v b ) − u M ( v s , v b ) , (15)
T S M ( v s , v b ) = T S M b ( v s , v b ) + T S M s ( v s , v b ) = T U M ( v s , v b ) − v s = G F T M ( v s , v b ) − u M ( v s , v b ) . (16) \begin{aligned}
\mathrm{TS}_{\mathcal{M}}(v_s,v_b) &= \mathrm{TS}^{b}_{\mathcal{M}}(v_s,v_b) + \mathrm{TS}^{s}_{\mathcal{M}}(v_s,v_b) \\
&= \mathrm{TU}_{\mathcal{M}}(v_s,v_b) - v_s \\
&= \mathrm{GFT}_{\mathcal{M}}(v_s,v_b) - u_{\mathcal{M}}(v_s,v_b). \tag*{(16)}
\end{aligned} TS M ( v s , v b ) = TS M b ( v s , v b ) + TS M s ( v s , v b ) = TU M ( v s , v b ) − v s = GFT M ( v s , v b ) − u M ( v s , v b ) . (16)
For a prior F \mathcal{F} F , we evaluate each objective in expectation over the distribution of traders’ values. That is,
S W M ( F ) = E ( v s , v b ) ∼ F [ S W M ( v s , v b ) ] , \mathrm{SW}_{\mathcal{M}}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\mathrm{SW}_{\mathcal{M}}(v_s,v_b)\right], SW M ( F ) = E ( v s , v b ) ∼ F [ SW M ( v s , v b ) ] ,
G F T M ( F ) = E ( v s , v b ) ∼ F [ G F T M ( v s , v b ) ] = S W M ( F ) − E ( v s , v b ) ∼ F [ v s ] , \mathrm{GFT}_{\mathcal{M}}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\mathrm{GFT}_{\mathcal{M}}(v_s,v_b)\right] = \mathrm{SW}_{\mathcal{M}}(\mathcal{F}) - \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s], GFT M ( F ) = E ( v s , v b ) ∼ F [ GFT M ( v s , v b ) ] = SW M ( F ) − E ( v s , v b ) ∼ F [ v s ] ,
T U M ( F ) = E ( v s , v b ) ∼ F [ T U M ( v s , v b ) ] = S W M ( F ) − E ( v s , v b ) ∼ F [ u M ( v s , v b ) ] , \mathrm{TU}_{\mathcal{M}}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\mathrm{TU}_{\mathcal{M}}(v_s,v_b)\right] = \mathrm{SW}_{\mathcal{M}}(\mathcal{F}) - \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[u_{\mathcal{M}}(v_s,v_b)\right], TU M ( F ) = E ( v s , v b ) ∼ F [ TU M ( v s , v b ) ] = SW M ( F ) − E ( v s , v b ) ∼ F [ u M ( v s , v b ) ] ,
T S M ( F ) = E ( v s , v b ) ∼ F [ T S M ( v s , v b ) ] = G F T M ( F ) − E ( v s , v b ) ∼ F [ u M ( v s , v b ) ] . \mathrm{TS}_{\mathcal{M}}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\mathrm{TS}_{\mathcal{M}}(v_s,v_b)\right] = \mathrm{GFT}_{\mathcal{M}}(\mathcal{F}) - \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[u_{\mathcal{M}}(v_s,v_b)\right]. TS M ( F ) = E ( v s , v b ) ∼ F [ TS M ( v s , v b ) ] = GFT M ( F ) − E ( v s , v b ) ∼ F [ u M ( v s , v b ) ] .
Similarly, for a prior F \mathcal{F} F , the buyer’s and the seller’s expected surpluses are
T S M b ( F ) = E ( v s , v b ) ∼ F [ T S M b ( v s , v b ) ] , \mathrm{TS}^{b}_{\mathcal{M}}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\mathrm{TS}^{b}_{\mathcal{M}}(v_s,v_b)\right], TS M b ( F ) = E ( v s , v b ) ∼ F [ TS M b ( v s , v b ) ] ,
T S M s ( F ) = E ( v s , v b ) ∼ F [ T S M s ( v s , v b ) ] . \mathrm{TS}^{s}_{\mathcal{M}}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\mathrm{TS}^{s}_{\mathcal{M}}(v_s,v_b)\right]. TS M s ( F ) = E ( v s , v b ) ∼ F [ TS M s ( v s , v b ) ] .
For a distribution F \mathcal{F} F over the traders’ values, we denote by S W O P T ( F ) \mathrm{SW}_{OPT}(\mathcal{F}) SW O P T ( F ) and G F T O P T ( F ) \mathrm{GFT}_{OPT}(\mathcal{F}) GFT O P T ( F ) the optimal expected social welfare and gains-from-trade, respectively, if the traders’ private values were public. These are the first-best benchmarks:
S W O P T ( F ) = E ( v s , v b ) ∼ F [ max { v s , v b } ] , G F T O P T ( F ) = E ( v s , v b ) ∼ F [ max { v b − v s , 0 } ] . \mathrm{SW}_{OPT}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\max\{v_s,v_b\}\right], \qquad\mathrm{GFT}_{OPT}(\mathcal{F}) = \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}\left[\max\{v_b-v_s,0\}\right]. SW O P T ( F ) = E ( v s , v b ) ∼ F [ max { v s , v b } ] , GFT O P T ( F ) = E ( v s , v b ) ∼ F [ max { v b − v s , 0 } ] .
We denote by T U O P T ( F ) \mathrm{TU}_{OPT}(\mathcal{F}) TU O P T ( F ) and T S O P T ( F ) \mathrm{TS}_{OPT}(\mathcal{F}) TS O P T ( F ) the traders’ utility and traders’ surplus of the first-best. Since the first-best burns no money, T U O P T ( F ) = S W O P T ( F ) \mathrm{TU}_{OPT}(\mathcal{F}) = \mathrm{SW}_{OPT}(\mathcal{F}) TU O P T ( F ) = SW O P T ( F ) and T S O P T ( F ) = G F T O P T ( F ) \mathrm{TS}_{OPT}(\mathcal{F}) = \mathrm{GFT}_{OPT}(\mathcal{F}) TS O P T ( F ) = GFT O P T ( F ) .
Money Burning Mechanisms are Arbitrarily Better
In this section we present our main result, showing that for randomized dominant-strategy incentive-compatible and individually rational mechanisms, the traders can be arbitrarily better off when the mechanism burns money than when it does not. That is, weakly budget-balanced mechanisms can perform arbitrarily better than every strongly budget-balanced mechanism. We show this in two settings: first, for traders’ surplus under independent distributions, and second, for traders’ utility under correlated distributions. We first state the two results. Both rely on a general construction of WBB DSIC and IR mechanisms, which we present in § 4.1 , followed by the proofs of the two results in § 4.2 and § 4.3 , respectively.
For traders’ surplus, SBB DSIC mechanisms cannot provide a constant approximation to first-best gains-from-trade, even under independent distributions [11 ] .12 We show that randomized WBB DSIC mechanisms can do arbitrarily better than SBB ones (Theorem 4.1 ). Yet, in Section 5 we show that they still cannot guarantee a constant approximation to the first-best gains-from-trade (Theorem 5.1 ).
Theorem 4.1. For every ε > 0 \varepsilon> 0 ε > 0 , there are independent seller and buyer distributions F s \mathcal{F}_s F s and F b \mathcal{F}_b F b and a randomized dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB such that, for every randomized dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB ,
ε ⋅ T S M W B B ( F s × F b ) > T S M S B B ( F s × F b ) = G F T M S B B ( F s × F b ) . \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) = \mathrm{GFT}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}_s \times\mathcal{F}_b). ε ⋅ TS M WBB ( F s × F b ) > TS M SBB ( F s × F b ) = GFT M SBB ( F s × F b ) . Moreover, the construction is symmetric, and so each of the traders is arbitrarily better off when moving from SBB mechanisms to using money burning (see Remark 4.7 ).
For traders’ utility, we cannot obtain an unbounded separation under independent distributions, since SBB mechanisms provide a constant approximation to first-best social welfare [11 , 26 , 12 , 57 , 63 , 34 , 49 , 55 , 64 ] . For correlated distributions, however, no SBB mechanism provides such a guarantee [39 ] . We therefore show an unbounded separation between WBB and SBB mechanisms for traders’ utility under correlated distributions (Theorem 4.2 ).
Theorem 4.2. For every ε > 0 \varepsilon> 0 ε > 0 , there is a joint distribution F \mathcal{F} F and a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB such that, for every dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB ,
ε ⋅ T U M W B B ( F ) > T U M S B B ( F ) = S W M S B B ( F ) . \varepsilon\cdot\mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) > \mathrm{TU}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) = \mathrm{SW}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}). ε ⋅ TU M WBB ( F ) > TU M SBB ( F ) = SW M SBB ( F ) .
In both theorems, the money burned by the WBB mechanism is not counted in its objective: the traders’ surplus and the traders’ utility objectives only count the two traders. For a WBB mechanism, counting the burnt money can only increase these two objectives, while for an SBB mechanism, traders’ surplus coincides with gains-from-trade, and traders’ utility coincides with social welfare.
Hence, both theorems also give the corresponding separations for gains-from-trade and social welfare:
ε ⋅ G F T M W B B ( F s × F b ) ≥ ε ⋅ T S M W B B ( F s × F b ) > G F T M S B B ( F s × F b ) (by xref‘Theorem 4.1‘), \varepsilon\cdot\mathrm{GFT}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_s \times\mathcal{F}_b) \ge\varepsilon\cdot\mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_s \times\mathcal{F}_b) > \mathrm{GFT}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}_s \times\mathcal{F}_b) \qquad\text{(by {xref}`Theorem 4.1`),} ε ⋅ GFT M WBB ( F s × F b ) ≥ ε ⋅ TS M WBB ( F s × F b ) > GFT M SBB ( F s × F b ) (by xref ‘Theorem 4.1‘),
ε ⋅ S W M W B B ( F ) ≥ ε ⋅ T U M W B B ( F ) > S W M S B B ( F ) (by xref‘Theorem 4.2‘). \varepsilon\cdot\mathrm{SW}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) \ge\varepsilon\cdot\mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) > \mathrm{SW}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) \qquad\text{(by {xref}`Theorem 4.2`).} ε ⋅ SW M WBB ( F ) ≥ ε ⋅ TU M WBB ( F ) > SW M SBB ( F ) (by xref ‘Theorem 4.2‘).
A Construction of Weakly Budget-Balanced DSIC Mechanisms
In this section, we present a general construction of dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanisms that we use to establish our two separation results (Theorems 4.1 and 4.2 ). We first provide intuition for the construction and explain its main features. The formal construction and its proof follow in Lemma 4.3.
Intuition and high-level description. The purpose of this construction is to obtain WBB DSIC and IR mechanisms that can outperform SBB DSIC and IR mechanisms. We begin by identifying a structural limitation of strongly budget-balanced mechanisms, and then we construct a WBB mechanism that circumvents this limitation.
Recall that since we consider DSIC mechanisms, the incentive constraints do not involve the distribution of the values: truthful reporting must be optimal for each agent regardless of the other agent’s report. Hence, when constructing our mechanism, we only need to consider the agents’ value spaces V s V_s V s and V b V_b V b ; the distribution plays a role only when we measure the performance of the mechanism. For the purpose of this discussion, let V s = V b = [ 0 , 1 ] V_s = V_b = [0,1] V s = V b = [ 0 , 1 ] .13
It was shown that every randomized SBB DSIC and IR mechanism can be represented as a distribution over posted prices [53 ČP16] . Consider such a mechanism, let x x x denote its allocation function, and let p p p be the random posted price drawn from a distribution μ \mu μ . At the agents’ profile ( v s , v b ) (v_s,v_b) ( v s , v b ) , the allocation probability is at most the probability that the posted price lies in [ v s , v b ] [v_s,v_b] [ v s , v b ] , that is, x ( v s , v b ) ≤ Pr p ∼ μ [ p ∈ [ v s , v b ] ] x(v_s,v_b) \le\Pr_{p\sim\mu}[p \in[v_s,v_b]] x ( v s , v b ) ≤ Pr p ∼ μ [ p ∈ [ v s , v b ]] . Consequently, for any profiles ( v s ( 1 ) , v b ( 1 ) ) , … , ( v s ( m ) , v b ( m ) ) (v_s^{(1)},v_b^{(1)}), \ldots, (v_s^{(m)},v_b^{(m)}) ( v s ( 1 ) , v b ( 1 ) ) , … , ( v s ( m ) , v b ( m ) ) whose intervals [ v s ( j ) , v b ( j ) ] [v_s^{(j)},v_b^{(j)}] [ v s ( j ) , v b ( j ) ] are pairwise disjoint,
∑ j = 1 m x ( v s ( j ) , v b ( j ) ) ≤ ∑ j = 1 m Pr p ∼ μ [ p ∈ [ v s ( j ) , v b ( j ) ] ] ≤ 1. \sum_{j=1}^{m} x(v_s^{(j)},v_b^{(j)}) \le\sum_{j=1}^{m} \Pr_{p\sim\mu}\left[p \in[v_s^{(j)},v_b^{(j)}]\right] \le1. j = 1 ∑ m x ( v s ( j ) , v b ( j ) ) ≤ j = 1 ∑ m p ∼ μ Pr [ p ∈ [ v s ( j ) , v b ( j ) ] ] ≤ 1.
Thus, an SBB mechanism cannot assign substantial allocation probability to all these profiles simultaneously: at least one of them has allocation probability at most 1 / m 1/m 1/ m . Our WBB construction overcomes precisely this limitation: it assigns high allocation probability to all such profiles simultaneously (in the specific constructions we use, at least 1 / 2 1/2 1/2 ).
We now describe the construction. Its allocation rule is a step function in each agent’s report: fixing the buyer’s report, the allocation probability is a step function of the seller’s report, and vice versa. The thresholds at which the steps occur are derived from a grid on the value space [ 0 , 1 ] [0,1] [ 0 , 1 ] that is common to the buyer and the seller. This grid is the input of the construction: an increasing sequence Q Q Q of n + 1 n+1 n + 1 values
0 = q 0 < ⋯ < q n = 1. 0 = q_0 < \cdots< q_n = 1. 0 = q 0 < ⋯ < q n = 1.
Each interior grid point q i q_i q i gives rise to two nearby thresholds: a seller threshold s i = q i + τ s_i = q_i + \tau s i = q i + τ slightly above q i q_i q i and a buyer threshold b i = q i − τ b_i = q_i - \tau b i = q i − τ slightly below q i q_i q i , for a small τ > 0 \tau> 0 τ > 0 .14 Thus, the buyer and seller thresholds are derived from the same grid, and the slight separation between them distinguishes the two sides of each grid point. In particular, s i > b i s_i > b_i s i > b i for every interior grid point, while for τ \tau τ that is small enough, s i − 1 < b i s_{i-1} < b_i s i − 1 < b i for every i ∈ [ n ] i \in[n] i ∈ [ n ] . Hence, for any small enough τ > 0 \tau> 0 τ > 0 , the intervals
K i = [ s i − 1 , b i ] , i ∈ [ n ] , K_i = [s_{i-1},b_i], \qquad i \in[n], K i = [ s i − 1 , b i ] , i ∈ [ n ] ,
that is, [ s 0 , b 1 ] , [ s 1 , b 2 ] , … , [ s n − 1 , b n ] [s_0,b_1], [s_1,b_2], \ldots, [s_{n-1},b_n] [ s 0 , b 1 ] , [ s 1 , b 2 ] , … , [ s n − 1 , b n ] , are nonempty and pairwise disjoint. These are the intervals on which we exhibit the gap between the two classes of mechanisms: by the discussion above, the allocation probabilities of an SBB mechanism at the profiles ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) sum to at most 1 1 1 , whereas in the specific constructions we use, this sum is at least n / 2 n/2 n /2 .
The allocation rule of the mechanism starts by rounding the reports of the traders by the rounding procedure below. Then there is trade with some probability (that is later specified), if the rounded buyer value is strictly larger than the rounded seller value. The seller’s report is rounded upward to the nearest seller threshold, and the buyer’s report is rounded downward to the nearest buyer threshold; we denote the resulting indices by ι S ( v s ) \iota_S(v_s) ι S ( v s ) and ι B ( v b ) \iota_B(v_b) ι B ( v b ) , respectively. Hence, each profile is associated with a pair of grid indices. The profiles with seller index r r r and buyer index t t t form a rectangle : the product of the set of seller values rounded up to r r r and the set of buyer values rounded down to t t t . We say that this rectangle is at level t − r t-r t − r , that is, the level of a profile is the number of grid steps by which the buyer’s index exceeds the seller’s. The mechanism trades exactly when the buyer’s index is strictly larger than the seller’s, and the allocation probability depends only on the difference between the two indices: increasing the buyer’s index by one, or decreasing the seller’s index by one, multiplies the allocation probability by the same factor Γ > 1 \Gamma>1 Γ > 1 , which we call the growth factor . Thus, for buyer index that is larger than the seller index by d > 0 d>0 d > 0 , the allocation probability is Γ − n + d \Gamma^{-n+d} Γ − n + d . See Figure 1 for an illustration of the allocation rule.
The resulting allocation rule is nondecreasing in the buyer’s report and nonincreasing in the seller’s report. Thus, by Myerson’s lemma, there are payments that make the mechanism DSIC and IR; we use the normalized payments defined in the proof of Lemma 4.3. For any large enough growth factor Γ \Gamma Γ , the resulting mechanism is also WBB. We choose Γ > 1 \Gamma>1 Γ > 1 as in Equation (18) , and we normalize the allocation probabilities so that they are at most 1.
The growth factor depends on the grid. When we apply the construction in the proofs of Theorems 4.1 and 4.2 , we carefully pick the grid points so that Γ n − 1 < 2 \Gamma^{n-1}<2 Γ n − 1 < 2 , and hence every positive allocation probability is greater than 1 / 2 1/2 1/2 .
We now return to the intervals K 1 , … , K n K_1,\ldots,K_n K 1 , … , K n and compare the two classes of mechanisms on them. Fix i ∈ [ n ] i\in[n] i ∈ [ n ] and consider the profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) , whose values are the endpoints of K i K_i K i . By the definition of the rounding, ι S ( s i − 1 ) = i − 1 \iota_S(s_{i-1})=i-1 ι S ( s i − 1 ) = i − 1 and ι B ( b i ) = i \iota_B(b_i)=i ι B ( b i ) = i , so the two rounded indices are exactly one grid step apart, that is, the profile is at level 1, and
x ( s i − 1 , b i ) = Γ − ( n − 1 ) . x(s_{i-1},b_i)=\Gamma^{-(n-1)}. x ( s i − 1 , b i ) = Γ − ( n − 1 ) .
These are the profiles marked in Figure 1 . When we apply the construction, we choose the grid so that Γ n − 1 < 2 \Gamma^{n-1}<2 Γ n − 1 < 2 . Hence, in our construction, each of these allocation probabilities is greater than 1 / 2 1/2 1/2 , and their sum is greater than n / 2 n/2 n /2 , while for every SBB mechanism this sum is at most 1.
If we only cared about gains from trade or social welfare, which do not depend on the payments, we could stop here: the difference in the allocation probabilities at the profiles ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) is enough to obtain an unbounded separation between the gains from trade (for independent distributions) and the social welfare (for correlated distributions) of WBB and SBB mechanisms. However, at the exact profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) the payments leave the traders with zero surplus. For a step allocation rule, the payments of Myerson’s lemma charge each trader the values at which the trader’s allocation probability jumps. At this profile, the buyer’s allocation probability, as a function of his value, jumps only at b i b_i b i , from 0 to x ( s i − 1 , b i ) x(s_{i-1},b_i) x ( s i − 1 , b i ) : lowering his value below b i b_i b i moves the profile to a rectangle with no trade. Similarly, the seller’s allocation probability jumps only at s i − 1 s_{i-1} s i − 1 . Hence, the buyer pays b i ⋅ x ( s i − 1 , b i ) b_i\mathbin{\cdot}x(s_{i-1},b_i) b i ⋅ x ( s i − 1 , b i ) and the seller receives s i − 1 ⋅ x ( s i − 1 , b i ) s_{i-1}\mathbin{\cdot}x(s_{i-1},b_i) s i − 1 ⋅ x ( s i − 1 , b i ) . These payments equal the traders’ values times the allocation probability, so the entire gain from trade is burned. 15 To obtain the separation for traders’ surplus and traders’ utility, we need a more elaborate construction and more nuanced argument.
Constructing the allocation rule level by level. Once the allocation probabilities at the rectangles of level 1, which contain the profiles ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) , are fixed, WBB and DSIC (through monotonicity) impose restrictions on the allocation probabilities at the rectangles of higher levels. Specifically, the allocation probability at each rectangle is tied to the allocation probabilities at the rectangles with the same seller values and lower buyer values (below it in the same column) and at the rectangles with the same buyer values and higher seller values (to its right in the same row; see Figure 2 ), all of which are at lower levels. We therefore construct the allocation rule from the bottom up, one level at a time. Along the way, we show how the construction leaves the traders a positive surplus at levels 2 and higher.
To see where the dependence comes from, recall that with the payments given by Myerson’s lemma, WBB at a profile ( v s , v b ) (v_s, v_b) ( v s , v b ) with positive allocation probability is equivalent to
( v b − v s ) x ( v s , v b ) ≥ ∫ v s v b x ( v s , z ) d z + ∫ v s v b x ( z , v b ) d z (v_b-v_s)x(v_s,v_b) \ge\int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z+\int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z ( v b − v s ) x ( v s , v b ) ≥ ∫ v s v b x ( v s , z ) d z + ∫ v s v b x ( z , v b ) d z
(see the proof of Lemma 4.3). The first integral is over buyer values between v s v_s v s and v b v_b v b with the seller value fixed, and the second is over seller values between v s v_s v s and v b v_b v b with the buyer value fixed. Apart from the rectangle of ( v s , v b ) (v_s,v_b) ( v s , v b ) itself, both integrals only involve rectangles at lower levels, or profiles with zero allocation probability. Moreover, the right-hand side is exactly the traders’ surplus at ( v s , v b ) (v_s,v_b) ( v s , v b ) : the first integral is the buyer’s utility and the second is the seller’s surplus (the allocation probability is zero for buyer values below v s v_s v s and for seller values above v b v_b v b ). The left-hand side is the gain from trade realized at ( v s , v b ) (v_s,v_b) ( v s , v b ) . Thus, WBB says that the traders’ surplus is at most the realized gain from trade, and the difference is the money burned.
Level 1. Consider the rectangle with seller index i − 1 i-1 i − 1 and buyer index i i i , which contains the profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) . All the other profiles in the two integrals have zero allocation probability, and the inequality reduces to b i ≥ s i − 1 b_i \ge s_{i-1} b i ≥ s i − 1 , which holds since K i K_i K i is nonempty. Hence, the allocation probabilities at level 1 can be chosen freely, and we set all of them to the same value. At the profile ( s i − 1 , b i ) (s_{i-1},b_i) ( s i − 1 , b i ) both integrals are zero, so, as noted above, the traders’ surplus there is zero.
Level 2. Consider the rectangle with seller index i − 1 i-1 i − 1 and buyer index i + 1 i+1 i + 1 , which lies above the level-1 rectangles of K i K_i K i and K i + 1 K_{i+1} K i + 1 (see Figure 2 (a)). Let x i x_i x i and x i + 1 x_{i+1} x i + 1 be the allocation probabilities at these two level-1 rectangles, and let y y y be the allocation probability at the level-2 rectangle. Computing the two integrals, WBB at this rectangle becomes
( b i + 1 − s i − 1 ) y ≥ ( b i + 1 − b i ) x i + ( s i − s i − 1 ) x i + 1 . (b_{i+1}-s_{i-1})y \ge(b_{i+1}-b_i)x_i+(s_i-s_{i-1})x_{i+1}. ( b i + 1 − s i − 1 ) y ≥ ( b i + 1 − b i ) x i + ( s i − s i − 1 ) x i + 1 .
Thus, y y y is bounded from below by a combination of x i x_i x i and x i + 1 x_{i+1} x i + 1 whose weights sum to
( b i + 1 − b i ) + ( s i − s i − 1 ) b i + 1 − s i − 1 = 1 + s i − b i b i + 1 − s i − 1 > 1. \frac{(b_{i+1}-b_i)+(s_i-s_{i-1})}{b_{i+1}-s_{i-1}}=1+\frac{s_i-b_i}{b_{i+1}-s_{i-1}}>1. b i + 1 − s i − 1 ( b i + 1 − b i ) + ( s i − s i − 1 ) = 1 + b i + 1 − s i − 1 s i − b i > 1.
In particular, if x i = x i + 1 x_i=x_{i+1} x i = x i + 1 , the allocation probability must grow by a factor of at least 1 + ( s i − b i ) / ( b i + 1 − s i − 1 ) 1+(s_i-b_i)/(b_{i+1}-s_{i-1}) 1 + ( s i − b i ) / ( b i + 1 − s i − 1 ) from level 1 to level 2. In addition, monotonicity requires y ≥ max { x i , x i + 1 } y \ge\max\{x_i,x_{i+1}\} y ≥ max { x i , x i + 1 } . The right-hand side is the traders’ surplus at the profile ( s i − 1 , b i + 1 ) (s_{i-1},b_{i+1}) ( s i − 1 , b i + 1 ) : the buyer’s utility comes from the level-1 rectangle of K i K_i K i , and the seller’s utility comes from the level-1 rectangle of K i + 1 K_{i+1} K i + 1 . Unlike at level 1, this surplus is positive. If x i = x i + 1 = x x_i=x_{i+1}=x x i = x i + 1 = x and y = Γ x y=\Gamma x y = Γ x , the traders’ surplus is at least ( b i + 1 − s i − 1 ) x (b_{i+1}-s_{i-1})x ( b i + 1 − s i − 1 ) x , so the traders keep at least a 1 / Γ 1/\Gamma 1/Γ fraction of the realized gain ( b i + 1 − s i − 1 ) y (b_{i+1}-s_{i-1})y ( b i + 1 − s i − 1 ) y , and only the rest is burned.
Higher levels. In general, the rectangle with seller index i − 1 i-1 i − 1 and buyer index j j j is constrained by the rectangles below it in its column and to its right in its row, down to level 1 (see Figure 2 ): those with seller index i − 1 i-1 i − 1 and buyer indices i , … , j − 1 i,\ldots,j-1 i , … , j − 1 , and those with buyer index j j j and seller indices i , … , j − 1 i,\ldots,j-1 i , … , j − 1 . All of these are at lower levels. Hence, once the allocation probabilities at levels 1 , … , d − 1 1,\ldots,d-1 1 , … , d − 1 are fixed, weak budget balance and monotonicity give lower bounds on the allocation probabilities at level d d d , and we can continue to the next level.
Our construction makes the simplest choice at every level: all rectangles at the same level have the same allocation probability, and moving one level up multiplies it by the growth factor Γ \Gamma Γ . Under this choice, the weak budget balance constraint at level d d d becomes inequality (31) in the proof of Lemma 4.3, and Equation (18) chooses a Γ \Gamma Γ that satisfies these constraints at all levels simultaneously. Finally, we divide by Γ n − 1 \Gamma^{n-1} Γ n − 1 so that the allocation probability at the top level is 1.
As at level 2, the traders’ surplus is positive at every level d ≥ 2 d \ge2 d ≥ 2 . At the profile ( s i − 1 , b j ) (s_{i-1}, b_j) ( s i − 1 , b j ) with j ≥ i + 1 j \ge i+1 j ≥ i + 1 , the buyer’s integral covers [ b i , b j ] [b_i,b_j] [ b i , b j ] and the seller’s integral covers [ s i − 1 , s j − 1 ] [s_{i-1},s_{j-1}] [ s i − 1 , s j − 1 ] , and the allocation probability on both is at least Γ − ( n − 1 ) \Gamma^{-(n-1)} Γ − ( n − 1 ) . Since the total length of these two intervals is at least b j − s i − 1 b_j-s_{i-1} b j − s i − 1 , the traders’ surplus is at least Γ − ( n − 1 ) ( b j − s i − 1 ) \Gamma^{-(n-1)}(b_j-s_{i-1}) Γ − ( n − 1 ) ( b j − s i − 1 ) , which is more than half of the gain from trade when Γ n − 1 < 2 \Gamma^{n-1}<2 Γ n − 1 < 2 . This is the surplus that our separation results use: in both proofs, the lower bound on the traders’ surplus of our mechanism comes from profiles at level 2.
For correlated values, it is straightforward to construct a distribution under which most of the first-best gains-from-trade comes from these profiles. We draw an index i i i , and then a seller value slightly above q i q_i q i and a buyer value slightly below q i + 2 q_{i+2} q i + 2 . Since Theorem 4.2 is about the traders’ utility, we also make sure that the seller’s expected value is negligible compared to the first-best gains-from-trade. For independent values, this is more challenging, since a seller value near q 2 ℓ − 1 q_{2\ell-1} q 2 ℓ − 1 can appear together with a buyer value near q 2 r + 1 q_{2r+1} q 2 r + 1 for any r r r . To circumvent this challenge, we make the seller’s value more likely to be near high grid points, and the buyer’s value more likely to be near low grid points, with probabilities that grow (for the seller) and shrink (for the buyer) exponentially along the grid. If r < ℓ r < \ell r < ℓ , the buyer’s value is below the seller’s value, so there is no gain from trade. If r > ℓ r > \ell r > ℓ , there is a gain from trade, but either the seller’s value is near an unlikely low point or the buyer’s value is near an unlikely high point. Figure 3 shows the probabilities of the resulting independent distribution, and Figure 4 shows that almost all of its first-best gains-from-trade comes from the level-2 profiles. We give the formal distributions in § 4.2 and § 4.3 .
Lemma 4.3 (weak-budget-balance construction). Let the value spaces be V s = V b = [ 0 , 1 ] V_s = V_b = [0,1] V s = V b = [ 0 , 1 ] . Given an integer n ≥ 2 n \ge2 n ≥ 2 and a sequence
0 = q 0 < q 1 < ⋯ < q n = 1 , 0 = q_0 < q_1 < \cdots< q_n = 1, 0 = q 0 < q 1 < ⋯ < q n = 1 ,
set τ \tau τ such that
0 < τ < 1 2 min i ∈ [ n ] ( q i − q i − 1 ) . (17) 0 < \tau< \frac{1}{2}\min_{i\in[n]}(q_i-q_{i-1}). \tag*{(17)} 0 < τ < 2 1 i ∈ [ n ] min ( q i − q i − 1 ) . (17)
Let the seller and buyer thresholds be
s 0 = 0 , s i = q i + τ ( 1 ≤ i ≤ n − 1 ) , s n = 1 , b 0 = 0 , b i = q i − τ ( 1 ≤ i ≤ n − 1 ) , b n = 1. \begin{aligned}
s_0 &= 0, & s_i &= q_i+\tau&& (1\le i\le n-1),\\
s_n &= 1,\\
b_0 &= 0, & b_i &= q_i-\tau&& (1\le i\le n-1),\\
b_n &= 1.
\end{aligned} s 0 s n b 0 b n = 0 , = 1 , = 0 , = 1. s i b i = q i + τ = q i − τ ( 1 ≤ i ≤ n − 1 ) , ( 1 ≤ i ≤ n − 1 ) ,
set the growth factor Γ \Gamma Γ to
Γ = 1 + max 1 ≤ i < j ≤ n q j − 1 − q i + 2 τ q j − q i − 1 − τ ⋅ 1 { i > 1 } − τ ⋅ 1 { j < n } . (18) \Gamma=1+\max_{1\le i<j\le n}\frac{q_{j-1}-q_i+2\tau}{q_j-q_{i-1}-\tau\cdot\mathbf{1}_{\{i>1\}}-\tau\cdot\mathbf{1}_{\{j<n\}}}. \tag*{(18)} Γ = 1 + 1 ≤ i < j ≤ n max q j − q i − 1 − τ ⋅ 1 { i > 1 } − τ ⋅ 1 { j < n } q j − 1 − q i + 2 τ . (18)
Then there exists a dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism whose allocation rule is
x ( v s , v b ) = { 0 , ι S ( v s ) ≥ ι B ( v b ) , Γ ι B ( v b ) − ι S ( v s ) − 1 Γ n − 1 , ι S ( v s ) < ι B ( v b ) . (19) x(v_s,v_b)=
\begin{cases}
0, & \iota_S(v_s)\ge\iota_B(v_b),\\
\frac{\Gamma^{\iota_B(v_b)-\iota_S(v_s)-1}}{\Gamma^{n-1}}, & \iota_S(v_s)<\iota_B(v_b).
\end{cases} \tag*{(19)} x ( v s , v b ) = { 0 , Γ n − 1 Γ ι B ( v b ) − ι S ( v s ) − 1 , ι S ( v s ) ≥ ι B ( v b ) , ι S ( v s ) < ι B ( v b ) . (19)
where
ι S ( v s ) = min { r ∈ { 0 , … , n } : v s ≤ s r } , \iota_S(v_s)=\min\{r\in\{0,\ldots,n\}:v_s\le s_r\}, ι S ( v s ) = min { r ∈ { 0 , … , n } : v s ≤ s r } ,
ι B ( v b ) = max { r ∈ { 0 , … , n } : v b ≥ b r } . \iota_B(v_b)=\max\{r\in\{0,\ldots,n\}:v_b\ge b_r\}. ι B ( v b ) = max { r ∈ { 0 , … , n } : v b ≥ b r } .
In particular, whenever the buyer’s rounded index ι B ( v b ) \iota_B(v_b) ι B ( v b ) is strictly larger than the seller’s rounded index ι S ( v s ) \iota_S(v_s) ι S ( v s ) , the allocation probability is x ( v s , v b ) ≥ Γ − ( n − 1 ) x(v_s,v_b)\ge\Gamma^{-(n-1)} x ( v s , v b ) ≥ Γ − ( n − 1 ) .
The proof of Lemma 4.3 formalizes the discussion above, and is deferred to Appendix § 7 .§ 2 .
We next present our main lemma, Lemma 4.5 , that is used in the proofs of both Theorems 4.1 and 4.2. Definition 4.4 below states the conditions on the grid and the slack that the lemma assumes, and the first step in the proof of the lemma shows that for such a grid every positive allocation probability of the mechanism of Lemma 4.3 is greater than 1 2 \frac{1}{2} 2 1 . The second step uses it to compare, at a profile whose values are two grid steps apart, our mechanism with an SBB mechanism. Our mechanism leaves the traders at least half of the gain from trade, while an SBB mechanism, which posts a random price, leaves them at most the probability that the price falls between the two grid points times the gain. Since every price falls between only a few such pairs of grid points, an SBB mechanism does well on only a few of these profiles, while our mechanism does well on all of them. Lemma 4.5 uses this to obtain a gap for every distribution of the agents’ values under which most of the first-best gains-from-trade comes from these profiles. Thus, to prove Theorems 4.1 and 4.2, we need to construct a grid and a distribution of the agents’ values that satisfy the conditions of this lemma. For Theorem 4.1 , the seller’s and buyer’s values must be independent, which makes it harder to concentrate the probability on the profiles two grid steps apart. For Theorem 4.2 , the values may be correlated, but since the theorem compares the traders’ utility, the expected seller’s value must also be small.
Lemma 4.5 below assumes the following conditions on the grid and the slack, and we refer to a grid with slack τ \tau τ that satisfies them as a separation grid .
Definition 4.4 (Separation grid). For n ≥ 4 n \ge4 n ≥ 4 , fix a grid 0 = q 0 < ⋯ < q n = 1 0 = q_0 < \cdots< q_n = 1 0 = q 0 < ⋯ < q n = 1 , and let L = min r ∈ [ n ] ( q r − q r − 1 ) L = \min_{r \in[n]}(q_r - q_{r-1}) L = min r ∈ [ n ] ( q r − q r − 1 ) be the smallest gap of the grid. We say that this grid is a separation grid with slack τ \tau τ if there exists 0 < δ ≤ 1 100 ⋅ n 0 < \delta\le\frac{1}{100 \cdot n} 0 < δ ≤ 100 ⋅ n 1 such that 0 < τ ≤ δ L 100 0 < \tau\le\frac{\delta L}{100} 0 < τ ≤ 100 δ L , and it holds that
q j − 1 − q i ≤ 4 δ ( q j − q i − 1 ) for every 1 ≤ i < j ≤ n . (20) q_{j-1} - q_i \le4\delta(q_j - q_{i-1}) \qquad\text{for every } 1 \le i < j \le n. \tag*{(20)} q j − 1 − q i ≤ 4 δ ( q j − q i − 1 ) for every 1 ≤ i < j ≤ n . (20)
The separation in our result grows with n n n , so we next always assume that n ≥ 4 n \ge4 n ≥ 4 . For every 1 ≤ i ≤ n − 3 1 \le i \le n - 3 1 ≤ i ≤ n − 3 , let R i \mathcal{R}_i R i be the set of profiles ( v s , v b ) (v_s,v_b) ( v s , v b ) in which the seller’s value is slightly above q i q_i q i and the buyer’s value is slightly below q i + 2 q_{i+2} q i + 2 , that is, q i ≤ v s < q i + τ q_i \le v_s < q_i + \tau q i ≤ v s < q i + τ and q i + 2 − τ < v b ≤ q i + 2 q_{i+2} - \tau< v_b \le q_{i+2} q i + 2 − τ < v b ≤ q i + 2 .
The following lemma gives the separation. Suppose that the distribution of the agents’ values is concentrated on profiles two grid steps apart, that is, on profiles in the sets R i \mathcal{R}_i R i , so that each such pair of grid points contributes the same amount to the first-best gains-from-trade, and the contribution of all other profiles is arbitrarily small. That is, most of the first-best gains-from-trade comes from these profiles. Then our mechanism obtains much more traders’ surplus than every SBB mechanism.
Lemma 4.5. Let 0 = q 0 < ⋯ < q n = 1 0 = q_0 < \cdots< q_n = 1 0 = q 0 < ⋯ < q n = 1 be a separation grid with slack τ \tau τ , and let M W B B \mathcal{M}^{\mathrm{WBB}} M WBB be the mechanism of Lemma 4.3 for this grid and slack. Let I I I be a nonempty subset of indices I ⊆ { 1 , … , n − 3 } I \subseteq\{1,\ldots,n-3\} I ⊆ { 1 , … , n − 3 } , of size m m m , and let F \mathcal{F} F be a distribution over the agents’ values. Suppose there exist C > 0 C > 0 C > 0 and ε 1 ≥ 0 \varepsilon_1 \ge0 ε 1 ≥ 0 such that the following two conditions hold:
For every i ∈ I i \in I i ∈ I , the contribution to the first-best gains-from-trade of the profiles in R i \mathcal{R}_i R i is between C / 2 C/2 C /2 and C C C . That is,
C 2 ≤ E [ ( v b − v s ) + ⋅ 1 ( v s , v b ) ∈ R i ] ≤ C . \frac{C}{2} \le\mathbb{E}[(v_b-v_s)_+ \cdot\mathbf{1}_{(v_s,v_b)\in\mathcal{R}_i}] \le C. 2 C ≤ E [( v b − v s ) + ⋅ 1 ( v s , v b ) ∈ R i ] ≤ C . The contribution to the first-best gains-from-trade of the profiles outside ⋃ i ∈ I R i \bigcup_{i\in I}\mathcal{R}_i ⋃ i ∈ I R i is at most ε 1 \varepsilon_1 ε 1 . That is,
E [ ( v b − v s ) + ⋅ 1 ( v s , v b ) ∉ ⋃ i ∈ I R i ] ≤ ε 1 . \mathbb{E}[(v_b-v_s)_+ \cdot\mathbf{1}_{(v_s,v_b)\notin\bigcup_{i\in I}\mathcal{R}_i}] \le\varepsilon_1. E [( v b − v s ) + ⋅ 1 ( v s , v b ) ∈ / ⋃ i ∈ I R i ] ≤ ε 1 . Here ( v b − v s ) + = max { v b − v s , 0 } (v_b-v_s)_+ = \max\{v_b-v_s,0\} ( v b − v s ) + = max { v b − v s , 0 } is the first-best gain from trade at ( v s , v b ) (v_s,v_b) ( v s , v b ) . Let h h h be the maximal number of intervals [ q i , q i + 2 ] [q_i,q_{i+2}] [ q i , q i + 2 ] for i ∈ I i \in I i ∈ I that contain a common price. Then M W B B \mathcal{M}^{\mathrm{WBB}} M WBB satisfies
T S M W B B ( F ) > m ⋅ C 4 , \mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) > \frac{m \cdot C}{4}, TS M WBB ( F ) > 4 m ⋅ C , and every dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB satisfies
T S M S B B ( F ) ≤ h ⋅ C + ε 1 . \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) \le h \cdot C + \varepsilon_1. TS M SBB ( F ) ≤ h ⋅ C + ε 1 .
Note that each of the intervals [ q i ; q i + 2 ] [q_i;q_{i+2}] [ q i ; q i + 2 ] for i ∈ I i \in I i ∈ I contains only three grid points, so h ≤ 3 h \le3 h ≤ 3 regardless of n n n , and depending on I I I it can be smaller. Hence, if ε 1 ≤ C \varepsilon_1 \le C ε 1 ≤ C , then the ratio between the traders’ surplus of M W B B \mathcal{M}^{\mathrm{WBB}} M WBB and the traders’ surplus of every SBB mechanism becomes unbounded as m m m grows.
The proof of Lemma 4.5 is deferred to Appendix § 7 .§ 3 . Here we only give a high-level description of the proof. Fix an SBB DSIC and IR mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB . The proof compares the traders’ surplus of M W B B \mathcal{M}^{\mathrm{WBB}} M WBB and of M S B B \mathcal{M}^{\mathrm{SBB}} M SBB at the profiles in the sets R i \mathcal{R}_i R i for i ∈ I i \in I i ∈ I . By Condition 2 of the lemma, the profiles outside these sets contribute little to the first-best gains-from-trade, and hence to the traders’ surplus of every mechanism, so we can focus on the profiles in these sets. We first show that the allocation probability of M W B B \mathcal{M}^{\mathrm{WBB}} M WBB is greater than 1 2 \frac{1}{2} 2 1 at every profile in which the rounded value of the seller is below the rounded value of the buyer. We then use Myerson’s lemma to show that although M W B B \mathcal{M}^{\mathrm{WBB}} M WBB burns money, its traders’ surplus at every profile in R i \mathcal{R}_i R i is more than half of the first-best gain from trade. For M S B B \mathcal{M}^{\mathrm{SBB}} M SBB , we use the characterization of [53 CP16] , by which M S B B \mathcal{M}^{\mathrm{SBB}} M SBB posts a price drawn from some distribution μ \mu μ , to show that it trades at a profile in R i \mathcal{R}_i R i with probability at most μ ( [ q i , q i + 2 ] ) \mu([q_i,q_{i+2}]) μ ([ q i , q i + 2 ]) . Since every price belongs to at most h h h of the intervals [ q i , q i + 2 ] [q_i,q_{i+2}] [ q i , q i + 2 ] for i ∈ I i \in I i ∈ I , these probabilities sum to at most h h h . By Condition 1, each of the sets R i \mathcal{R}_i R i contributes roughly the same amount to the first-best gains-from-trade. We conclude that M W B B \mathcal{M}^{\mathrm{WBB}} M WBB obtains a constant fraction of the contribution of each of the m m m sets, while from all the sets together M S B B \mathcal{M}^{\mathrm{SBB}} M SBB obtains at most the contribution of about h h h of them. Finally, the lemma is about the traders’ surplus, but Theorem 4.2 is about the traders’ utility, which is the traders’ surplus plus the seller’s expected value E [ v s ] \mathbb{E}[v_s] E [ v s ] . In its proof (§ 4.3 ), we construct a distribution that satisfies the conditions of the lemma and under which the seller’s expected value is at most C C C , so the separation in traders’ surplus implies a separation in traders’ utility.
Proof of Theorem 4.1
We prove the theorem by applying Lemma 4.5 to a specific grid and specific independent distributions. Throughout this subsection, fix ε > 0 \varepsilon> 0 ε > 0 , let k ≥ 2 k \ge2 k ≥ 2 be an integer such that ( k − 1 ) / 12 ≥ 1 / ε (k-1)/12 \ge1/\varepsilon ( k − 1 ) /12 ≥ 1/ ε , and let n = 2 k n = 2k n = 2 k .
The grid. Let δ = 1 / ( 100 n ) \delta= 1/(100n) δ = 1/ ( 100 n ) . We build the grid symmetrically around 1 / 2 1/2 1/2 : the middle point is q k = 1 / 2 q_k = 1/2 q k = 1/2 , the points on the left approach 1 / 2 1/2 1/2 with distances δ , δ 2 , … , δ k − 1 \delta, \delta^2, \ldots, \delta^{k-1} δ , δ 2 , … , δ k − 1 , and the points on the right are their reflections around 1 / 2 1/2 1/2 . Formally,
q i = { 0 i = 0 ; 1 2 − δ i 1 ≤ i < k ; 1 2 i = k ; 1 2 + δ 2 k − i k < i ≤ 2 k − 1 ; 1 i = n . (21) q_i =
\begin{cases}
0 & i=0;\\
\frac{1}{2}-\delta^i & 1 \le i < k;\\
\frac{1}{2} & i=k;\\
\frac{1}{2}+\delta^{2k-i} & k < i \le2k-1;\\
1 & i=n.
\end{cases} \tag*{(21)} q i = ⎩ ⎨ ⎧ 0 2 1 − δ i 2 1 2 1 + δ 2 k − i 1 i = 0 ; 1 ≤ i < k ; i = k ; k < i ≤ 2 k − 1 ; i = n . (21)
Thus, the gaps between consecutive points decrease geometrically when moving from either endpoint toward the middle. For every i ∈ [ n ] i \in[n] i ∈ [ n ] , let L i = q i − q i − 1 L_i = q_i-q_{i-1} L i = q i − q i − 1 denote the gap between q i − 1 q_{i-1} q i − 1 and q i q_i q i . Then
L i = { 1 2 − δ i = 1 or i = n ; ( 1 − δ ) δ i − 1 2 ≤ i ≤ k − 1 ; δ k − 1 i = k or i = k + 1 ; ( 1 − δ ) δ n − i k + 2 ≤ i ≤ n − 1. L_i =
\begin{cases}
\frac{1}{2}-\delta& i=1\text{ or }i=n;\\
(1-\delta)\delta^{i-1} & 2 \le i \le k-1;\\
\delta^{k-1} & i=k\text{ or }i=k+1;\\
(1-\delta)\delta^{n-i} & k+2 \le i \le n-1.
\end{cases} L i = ⎩ ⎨ ⎧ 2 1 − δ ( 1 − δ ) δ i − 1 δ k − 1 ( 1 − δ ) δ n − i i = 1 or i = n ; 2 ≤ i ≤ k − 1 ; i = k or i = k + 1 ; k + 2 ≤ i ≤ n − 1.
Let τ > 0 \tau> 0 τ > 0 be small enough for the grid with slack τ \tau τ to be a separation grid (this is possible by Lemma 4.6 below), and let M W B B \mathcal{M}^{\mathrm{WBB}} M WBB be the resulting mechanism of Lemma 4.3.
The distributions. The seller’s value is concentrated slightly above the grid points q 1 , q 3 , … , q n − 3 q_1,q_3,\ldots,q_{n-3} q 1 , q 3 , … , q n − 3 , and the buyer’s value is concentrated slightly below the grid points q 3 , q 5 , … , q n − 1 q_3,q_5,\ldots,q_{n-1} q 3 , q 5 , … , q n − 1 . For every ℓ ∈ [ k − 1 ] \ell\in[k-1] ℓ ∈ [ k − 1 ] , a profile with a seller value near q 2 ℓ − 1 q_{2\ell-1} q 2 ℓ − 1 and a buyer value near q 2 ℓ + 1 q_{2\ell+1} q 2 ℓ + 1 lies in R 2 ℓ − 1 \mathcal{R}_{2\ell-1} R 2 ℓ − 1 . Ideally, the seller’s value would be near q 2 ℓ − 1 q_{2\ell-1} q 2 ℓ − 1 exactly when the buyer’s value is near q 2 ℓ + 1 q_{2\ell+1} q 2 ℓ + 1 , as in a correlated distribution. Since the values are independent, there are also profiles in which the seller’s value is near q 2 ℓ − 1 q_{2\ell-1} q 2 ℓ − 1 and the buyer’s value is near q 2 r + 1 q_{2r+1} q 2 r + 1 for some r ≠ ℓ r \ne\ell r = ℓ . We choose the probabilities so that these cases contribute little. If r < ℓ r < \ell r < ℓ , the buyer’s value is below the seller’s value, so the first-best gains-from-trade are 0. If r > ℓ r > \ell r > ℓ , the gains from trade are positive, but this case is unlikely: the seller’s value is more likely to be near high grid points, and the buyer’s value is more likely to be near low grid points, so either the seller’s value is near an unlikely low point or the buyer’s value is near an unlikely high point. Thus, although the values are independent, positive gains from trade arise, up to a small error, only when the seller’s value is near q 2 ℓ − 1 q_{2\ell-1} q 2 ℓ − 1 and the buyer’s value is near q 2 ℓ + 1 q_{2\ell+1} q 2 ℓ + 1 for the same ℓ \ell ℓ , that is, in R 2 ℓ − 1 R_{2\ell-1} R 2 ℓ − 1 . Finally, we choose the probabilities so that each ℓ \ell ℓ contributes approximately the same amount to the first-best gains-from-trade: the probability of R 2 ℓ − 1 R_{2\ell-1} R 2 ℓ − 1 is inversely proportional to q 2 ℓ + 1 − q 2 ℓ − 1 q_{2\ell+1}-q_{2\ell-1} q 2 ℓ + 1 − q 2 ℓ − 1 , which is approximately the gain from trade in this case. Figure 3 shows the probabilities of the resulting distribution: the seller’s value is likely to be near a high grid point, and the buyer’s value is likely to be near a low grid point. Figure 4 shows the contribution of each pair of seller and buyer values to the first-best gains-from-trade: the pairs in which the buyer’s value is below the seller’s value contribute nothing, each level-2 pair contributes about the same amount, and all other pairs contribute little.
Formally, fix 0 < η < τ 0 < \eta< \tau 0 < η < τ . For every ℓ ∈ [ k − 1 ] \ell\in[k-1] ℓ ∈ [ k − 1 ] , let
S ℓ = [ q 2 ℓ − 1 , q 2 ℓ − 1 + η ] , B ℓ = [ q 2 ℓ + 1 − η , q 2 ℓ + 1 ] , Δ ℓ = q 2 ℓ + 1 − q 2 ℓ − 1 . S_\ell= [q_{2\ell-1},q_{2\ell-1}+\eta], \qquad B_\ell= [q_{2\ell+1}-\eta,q_{2\ell+1}], \qquad\Delta_\ell= q_{2\ell+1}-q_{2\ell-1}. S ℓ = [ q 2 ℓ − 1 , q 2 ℓ − 1 + η ] , B ℓ = [ q 2 ℓ + 1 − η , q 2 ℓ + 1 ] , Δ ℓ = q 2 ℓ + 1 − q 2 ℓ − 1 .
Let R > 1 R > 1 R > 1 be large enough that
∑ 1 ≤ ℓ < r ≤ k − 1 R ℓ − r q 2 r + 1 − q 2 ℓ − 1 Δ ℓ Δ r ≤ 1 ; (22) \sum_{1\le\ell<r\le k-1} R^{\ell-r}\frac{q_{2r+1}-q_{2\ell-1}}{\sqrt{\Delta_\ell\Delta_r}} \le1; \tag*{(22)} 1 ≤ ℓ < r ≤ k − 1 ∑ R ℓ − r Δ ℓ Δ r q 2 r + 1 − q 2 ℓ − 1 ≤ 1 ; (22)
such R R R exists since the sum is finite and each term tends to 0 as R → ∞ R \to\infty R → ∞ . For every ℓ ∈ [ k − 1 ] \ell\in[k-1] ℓ ∈ [ k − 1 ] , let
α ℓ = R ℓ Δ ℓ , β ℓ = R − ℓ Δ ℓ , C = 1 ( ∑ r α r ) ( ∑ r β r ) . \alpha_\ell= \frac{R^\ell}{\sqrt{\Delta_\ell}}, \qquad\beta_\ell= \frac{R^{-\ell}}{\sqrt{\Delta_\ell}}, \qquad C = \frac{1}{(\sum_r \alpha_r)(\sum_r \beta_r)}. α ℓ = Δ ℓ R ℓ , β ℓ = Δ ℓ R − ℓ , C = ( ∑ r α r ) ( ∑ r β r ) 1 .
To draw the seller’s value, we first draw an index ℓ ∈ [ k − 1 ] \ell\in[k-1] ℓ ∈ [ k − 1 ] with probability α ℓ / ∑ r α r \alpha_\ell/\sum_r \alpha_r α ℓ / ∑ r α r , and then draw the value uniformly from S ℓ S_\ell S ℓ . Similarly, to draw the buyer’s value, we first draw an index ℓ ∈ [ k − 1 ] \ell\in[k-1] ℓ ∈ [ k − 1 ] with probability β ℓ / ∑ r β r \beta_\ell/\sum_r \beta_r β ℓ / ∑ r β r , and then draw the value uniformly from B ℓ B_\ell B ℓ . The two values are drawn independently. Let F s F_s F s and F b F_b F b denote the resulting seller and buyer distributions. Note that, for ( v s , v b ) ∼ F s × F b (v_s,v_b) \sim F_s \times F_b ( v s , v b ) ∼ F s × F b and every ℓ , r ∈ [ k − 1 ] \ell,r \in[k-1] ℓ , r ∈ [ k − 1 ] ,
Pr [ ( v s , v b ) ∈ S ℓ × B r ] = C ⋅ α ℓ ⋅ β r . \Pr\left[(v_s,v_b) \in S_\ell\times B_r\right] = C \cdot\alpha_\ell\cdot\beta_r. Pr [ ( v s , v b ) ∈ S ℓ × B r ] = C ⋅ α ℓ ⋅ β r .
In particular, for r = ℓ ∈ [ k − 1 ] r=\ell\in[k-1] r = ℓ ∈ [ k − 1 ] ,
Pr [ ( v s , v b ) ∈ S ℓ × B ℓ ] = C / Δ ℓ . \Pr\left[(v_s,v_b) \in S_\ell\times B_\ell\right] = C/\Delta_\ell. Pr [ ( v s , v b ) ∈ S ℓ × B ℓ ] = C / Δ ℓ .
Analysis. We first show that the grid in Equation (21) satisfies the grid condition of Definition 4.4 .
The proof of Lemma 4.6 is deferred to Appendix § 7 .§ 4 .
Proof of Theorem 4.1 . Let F s F_s F s , F b F_b F b , and M W B B \mathcal{M}_{\mathrm{WBB}} M WBB be as above. We apply Lemma 4.5 with I = { 2 ℓ − 1 : ℓ ∈ [ k − 1 ] } I = \{2\ell-1:\ell\in[k-1]\} I = { 2 ℓ − 1 : ℓ ∈ [ k − 1 ]} , so m = k − 1 m=k-1 m = k − 1 . By Lemma 4.6 , the grid with slack τ \tau τ is a separation grid. Consecutive intervals [ q 2 ℓ − 1 , q 2 ℓ + 1 ] [q_{2\ell-1},q_{2\ell+1}] [ q 2 ℓ − 1 , q 2 ℓ + 1 ] share only an endpoint, so every price belongs to at most two of them, that is, h ≤ 2 h \le2 h ≤ 2 . It remains to verify the two conditions of Lemma 4.5 .
For the first condition, fix ℓ ∈ [ k − 1 ] \ell\in[k-1] ℓ ∈ [ k − 1 ] and let i = 2 ℓ − 1 i = 2\ell- 1 i = 2 ℓ − 1 . Since η < τ \eta< \tau η < τ , the profiles in S ℓ × B ℓ S_\ell\times B_\ell S ℓ × B ℓ lie in R i \mathcal{R}_i R i , and no other profile in the support of F s × F b F_s \times F_b F s × F b does. Hence, Pr [ ( v s , v b ) ∈ R i ] = Pr [ ( v s , v b ) ∈ S ℓ × B ℓ ] = C / Δ ℓ \Pr[(v_s,v_b) \in\mathcal{R}_i] = \Pr[(v_s,v_b) \in S_\ell\times B_\ell] = C/\Delta_\ell Pr [( v s , v b ) ∈ R i ] = Pr [( v s , v b ) ∈ S ℓ × B ℓ ] = C / Δ ℓ . On S ℓ × B ℓ S_\ell\times B_\ell S ℓ × B ℓ , the expected gain from trade is Δ ℓ − η \Delta_\ell- \eta Δ ℓ − η , so the profiles in R i \mathcal{R}_i R i contribute C ( Δ ℓ − η ) / Δ ℓ C(\Delta_\ell-\eta)/\Delta_\ell C ( Δ ℓ − η ) / Δ ℓ to the first-best gains-from-trade. This is between C / 2 C/2 C /2 and C C C , since η < τ < Δ ℓ / 2 \eta< \tau< \Delta_\ell/2 η < τ < Δ ℓ /2 .
For the second condition, every profile in the support outside ⋃ i ∈ I R i \bigcup_{i\in I}\mathcal{R}_i ⋃ i ∈ I R i lies in S ℓ × B r S_\ell\times B_r S ℓ × B r for some ℓ ≠ r \ell\ne r ℓ = r . If ℓ > r \ell> r ℓ > r , then v b ≤ v s v_b \le v_s v b ≤ v s , so the gain from trade is 0. If ℓ < r \ell< r ℓ < r , the gain from trade is at most q 2 r + 1 − q 2 ℓ − 1 q_{2r+1} - q_{2\ell-1} q 2 r + 1 − q 2 ℓ − 1 , and Pr [ ( v s , v b ) ∈ S ℓ × B r ] = C R ℓ − r / Δ ℓ Δ r \Pr[(v_s,v_b) \in S_\ell\times B_r] = C R^{\ell-r}/\sqrt{\Delta_\ell\Delta_r} Pr [( v s , v b ) ∈ S ℓ × B r ] = C R ℓ − r / Δ ℓ Δ r . Summing over all pairs ℓ < r \ell< r ℓ < r , the first-best gains-from-trade outside these sets is at most
C ⋅ ∑ 1 ≤ ℓ < r ≤ k − 1 R ℓ − r q 2 r + 1 − q 2 ℓ − 1 Δ ℓ Δ r ≤ C , C \cdot\sum_{1\le\ell<r\le k-1} R^{\ell-r}\frac{q_{2r+1}-q_{2\ell-1}}{\sqrt{\Delta_\ell\Delta_r}} \le C, C ⋅ 1 ≤ ℓ < r ≤ k − 1 ∑ R ℓ − r Δ ℓ Δ r q 2 r + 1 − q 2 ℓ − 1 ≤ C ,
due to Equation (22) , so the second condition holds with ϵ 1 = C \epsilon_1 = C ϵ 1 = C .
By Lemma 4.5, every SBB DSIC and IR mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB satisfies
ϵ ⋅ T S M W B B ( F s × F b ) > ϵ ⋅ ( k − 1 ) C 4 ≥ 3 C ≥ T S M S B B ( F s × F b ) , \epsilon\cdot\mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(F_s \times F_b) > \epsilon\cdot\frac{(k-1)C}{4} \ge3C \ge\mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(F_s \times F_b), ϵ ⋅ TS M WBB ( F s × F b ) > ϵ ⋅ 4 ( k − 1 ) C ≥ 3 C ≥ TS M SBB ( F s × F b ) ,
where the second inequality holds since ( k − 1 ) / 12 ≥ 1 / ϵ (k-1)/12 \ge1/\epsilon ( k − 1 ) /12 ≥ 1/ ϵ , and the third since h ≤ 2 h \le2 h ≤ 2 and ϵ 1 = C \epsilon_1 = C ϵ 1 = C . Since the payments of an SBB mechanism cancel, T S M S B B ( F s × F b ) = G F T M S B B ( F s × F b ) \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(F_s \times F_b) = \mathrm{GFT}_{\mathcal{M}^{\mathrm{SBB}}}(F_s \times F_b) TS M SBB ( F s × F b ) = GFT M SBB ( F s × F b ) , which proves the theorem.
Recall that T S M b \mathrm{TS}^{b}_{\mathcal{M}} TS M b and T S M s \mathrm{TS}^{s}_{\mathcal{M}} TS M s denote the buyer’s and the seller’s surplus under a mechanism M \mathcal{M} M , which sum to the traders’ surplus T S M \mathrm{TS}_{\mathcal{M}} TS M (§ 3.3 ).
Lemma 4.8. In the construction of Theorem 4.1 , T S M W B B b ( F s × F b ) = T S M W B B s ( F s × F b ) = 1 2 T S M W B B ( F s × F b ) TS^{b}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_{s}\times\mathcal{F}_{b})=TS^{s}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}_{s}\times\mathcal{F}_{b})=\frac{1}{2}TS^{\mathrm{MWBB}}(\mathcal{F}_{s}\times\mathcal{F}_{b}) T S M WBB b ( F s × F b ) = T S M WBB s ( F s × F b ) = 2 1 T S MWBB ( F s × F b ) .
The proof of Lemma 4.8 is deferred to Appendix § 7 .§ 5 .
Proof of Theorem 4.2
We prove the theorem by applying Lemma 4.5 to a specific grid and a specific correlated distribution. Throughout this subsection, fix ε > 0 \varepsilon>0 ε > 0 , and let n ≥ 4 n\ge4 n ≥ 4 be an integer such that ( n − 3 ) / 16 ≥ 1 / ε (n-3)/16\ge1/\varepsilon ( n − 3 ) /16 ≥ 1/ ε .
The grid. Let δ = 1 / ( 100 n ) \delta=1/(100n) δ = 1/ ( 100 n ) , and let the grid points be
q i = δ n − i − δ n 1 − δ n (23) q_i=\frac{\delta^{n-i}-\delta^n}{1-\delta^n} \tag*{(23)} q i = 1 − δ n δ n − i − δ n (23)
for every i ∈ { 0 , 1 , … , n } i\in\{0,1,\ldots,n\} i ∈ { 0 , 1 , … , n } .
In particular, q 0 = 0 q_0=0 q 0 = 0 and q n = 1 q_n=1 q n = 1 , and the gaps are
L i = q i − q i − 1 = ( 1 − δ ) δ n − i 1 − δ n L_i=q_i-q_{i-1}=\frac{(1-\delta)\delta^{n-i}}{1-\delta^n} L i = q i − q i − 1 = 1 − δ n ( 1 − δ ) δ n − i
for every i ∈ [ n ] i\in[n] i ∈ [ n ] , so each gap is 1 / δ 1/\delta 1/ δ times the previous one. Thus, the gaps grow quickly from left to right. In particular, for every i ∈ [ n ] i\in[n] i ∈ [ n ] , the gaps to the left of L i L_i L i sum to a small fraction of L i L_i L i , since
∑ r = 1 i − 1 L r = q i − 1 ≤ δ n − i + 1 1 − δ n = δ 1 − δ L i . \sum_{r=1}^{i-1}L_r=q_{i-1}\le\frac{\delta^{n-i+1}}{1-\delta^n}=\frac{\delta}{1-\delta}L_i. r = 1 ∑ i − 1 L r = q i − 1 ≤ 1 − δ n δ n − i + 1 = 1 − δ δ L i .
Let τ > 0 \tau>0 τ > 0 be small enough for the grid with slack τ \tau τ to be a separation grid (this is possible by Lemma 4.9 below), and let M W B B \mathcal{M}^{\mathrm{WBB}} M WBB be the resulting mechanism of Lemma 4.3.
The distribution. Since the values may be correlated, we put all the probability on profiles in R i − 1 \mathcal{R}_{i-1} R i − 1 , in which the seller’s value is near q i − 1 q_{i-1} q i − 1 and the buyer’s value is near q i + 1 q_{i+1} q i + 1 . We choose the probabilities so that each i i i contributes approximately the same amount to the first-best social welfare. At these profiles, trade is efficient, so the first-best welfare is the buyer’s value v b v_b v b , which equals the seller’s value v s v_s v s plus the gain from trade v b − v s v_b-v_s v b − v s , where v s v_s v s is close to q i − 1 q_{i-1} q i − 1 and v b − v s v_b-v_s v b − v s is close to q i + 1 − q i − 1 q_{i+1}-q_{i-1} q i + 1 − q i − 1 . Since the gaps grow quickly, the seller’s value q i − 1 q_{i-1} q i − 1 is small compared to this gain. Hence, as in § 4.2 , it suffices to make the probability of each i i i inversely proportional to q i + 1 − q i − 1 q_{i+1}-q_{i-1} q i + 1 − q i − 1 .
Formally, for every i ∈ { 2 , … , n − 2 } i\in\{2,\ldots,n-2\} i ∈ { 2 , … , n − 2 } , let Δ i = q i + 1 − q i − 1 \Delta_i=q_{i+1}-q_{i-1} Δ i = q i + 1 − q i − 1 , fix
0 < η < min { τ , δ 2 min 2 ≤ i ≤ n − 2 Δ i } . 0<\eta<\min\left\{\tau,\delta^2\min_{2\le i\le n-2}\Delta_i\right\}. 0 < η < min { τ , δ 2 2 ≤ i ≤ n − 2 min Δ i } .
and let
S i = [ q i − 1 , q i − 1 + η ] , B i = [ q i + 1 − η , q i + 1 ] , C = 1 ∑ r = 2 n − 2 1 / Δ r . S_i=[q_{i-1},q_{i-1}+\eta],\qquad B_i=[q_{i+1}-\eta,q_{i+1}],\qquad C=\frac{1}{\sum_{r=2}^{n-2}1/\Delta_r}. S i = [ q i − 1 , q i − 1 + η ] , B i = [ q i + 1 − η , q i + 1 ] , C = ∑ r = 2 n − 2 1/ Δ r 1 .
To draw the agents’ values, we first draw an index i ∈ { 2 , … , n − 2 } i\in\{2,\ldots,n-2\} i ∈ { 2 , … , n − 2 } with probability C / Δ i C/\Delta_i C / Δ i , and then draw the seller’s value uniformly from S i S_i S i and, independently, the buyer’s value uniformly from B i B_i B i . Let F \mathcal{F} F denote the resulting joint distribution. The two values are correlated, since the same index selects both intervals. Note that, for ( v s , v b ) ∼ F (v_s,v_b)\sim\mathcal{F} ( v s , v b ) ∼ F and every i ∈ { 2 , … , n − 2 } i\in\{2,\ldots,n-2\} i ∈ { 2 , … , n − 2 } ,
Pr [ ( v s , v b ) ∈ S i × B i ] = C Δ i . \Pr\left[(v_s,v_b)\in S_i\times B_i\right]=\frac{C}{\Delta_i}. Pr [ ( v s , v b ) ∈ S i × B i ] = Δ i C .
Analysis. We first show that the grid in Equation (23) satisfies the grid condition of Definition 4.4 .
To bound the traders’ utility of an SBB mechanism, we also need a bound on the expected seller’s value. We next show that it is small.
Lemma 4.10. E ( v s , v b ) ∼ F [ v s ] ≤ C \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s] \le C E ( v s , v b ) ∼ F [ v s ] ≤ C .
The proofs of Lemmas 4.9 and 4.10 are deferred to Appendices § 7 .6 and § 7 .7, respectively.
Proof of Theorem 4.2. Let F \mathcal{F} F and M W B B \mathcal{M}^{\mathrm{WBB}} M WBB be as above. We apply Lemma 4.5 with I = { 1 , … , n − 3 } I = \{1,\ldots,n-3\} I = { 1 , … , n − 3 } , so m = n − 3 m = n-3 m = n − 3 . By Lemma 4.9 , the grid with slack τ \tau τ is a separation grid. Every price belongs to at most three of the intervals [ q i , q i + 2 ] [q_i,q_{i+2}] [ q i , q i + 2 ] , i ∈ I i \in I i ∈ I , that is, h ≤ 3 h \le3 h ≤ 3 . It remains to verify the two conditions of Lemma 4.5 .
For the first condition, fix i ∈ I i \in I i ∈ I . Since η < τ \eta< \tau η < τ , the profiles in S i + 1 × B i + 1 S_{i+1} \times B_{i+1} S i + 1 × B i + 1 lie in R i \mathcal{R}_i R i , and no other profile in the support of F \mathcal{F} F does. Hence, Pr [ ( v s , v b ) ∈ R i ] = Pr [ ( v s , v b ) ∈ S i + 1 × B i + 1 ] = C / Δ i + 1 \Pr[(v_s,v_b) \in\mathcal{R}_i] = \Pr[(v_s,v_b) \in S_{i+1} \times B_{i+1}] = C/\Delta_{i+1} Pr [( v s , v b ) ∈ R i ] = Pr [( v s , v b ) ∈ S i + 1 × B i + 1 ] = C / Δ i + 1 . On S i + 1 × B i + 1 S_{i+1} \times B_{i+1} S i + 1 × B i + 1 , the expected gain from trade is Δ i + 1 − η \Delta_{i+1} - \eta Δ i + 1 − η , so the profiles in R i \mathcal{R}_i R i contribute C ( Δ i + 1 − η ) / Δ i + 1 C(\Delta_{i+1}-\eta)/\Delta_{i+1} C ( Δ i + 1 − η ) / Δ i + 1 to the first-best gains-from-trade. This is between C / 2 C/2 C /2 and C C C , since η < τ < Δ i + 1 / 2 \eta< \tau< \Delta_{i+1}/2 η < τ < Δ i + 1 /2 .
For the second condition, all the probability is on ⋃ i ∈ I R i \bigcup_{i\in I}\mathcal{R}_i ⋃ i ∈ I R i , so it holds with ϵ 1 = 0 \epsilon_1 = 0 ϵ 1 = 0 .
By Lemma 4.5 , every SBB DSIC and IR mechanism M S B B \mathcal{M}^{\mathrm{SBB}} M SBB satisfies
ϵ ⋅ T U M W B B ( F ) ≥ ϵ ⋅ T S M W B B ( F ) > ϵ ⋅ ( n − 3 ) C 4 ≥ 4 C ≥ T U M S B B ( F ) , \epsilon\cdot\mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) \ge\epsilon\cdot\mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) > \epsilon\cdot\frac{(n-3)C}{4} \ge4C \ge\mathrm{TU}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}), ϵ ⋅ TU M WBB ( F ) ≥ ϵ ⋅ TS M WBB ( F ) > ϵ ⋅ 4 ( n − 3 ) C ≥ 4 C ≥ TU M SBB ( F ) ,
where the first inequality holds since T U M W B B ( F ) = E [ v s ] + T S M W B B ( F ) \mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) = \mathbb{E}[v_s] + \mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) TU M WBB ( F ) = E [ v s ] + TS M WBB ( F ) , and the third holds since ( n − 3 ) / 16 ≥ 1 / ϵ (n-3)/16 \ge1/\epsilon ( n − 3 ) /16 ≥ 1/ ϵ . The last inequality holds since T U M S B B ( F ) = E [ v s ] + T S M S B B ( F ) \mathrm{TU}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) = \mathbb{E}[v_s] + \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) TU M SBB ( F ) = E [ v s ] + TS M SBB ( F ) , where E [ v s ] ≤ C \mathbb{E}[v_s] \le C E [ v s ] ≤ C by Lemma 4.10 and T S M S B B ( F ) ≤ 3 C \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) \le3C TS M SBB ( F ) ≤ 3 C by Lemma 4.5 . Since the payments of an SBB mechanism cancel, T U M S B B ( F ) = S W M S B B ( F ) \mathrm{TU}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) = \mathrm{SW}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F}) TU M SBB ( F ) = SW M SBB ( F ) , which proves the theorem. □
Remark 4.11. On the distributions of Theorem 4.1 and Theorem 4.2 , the mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB obtains a constant approximation to the first-best: its traders’ surplus is more than 1/8 of the first-best gains-from-trade for independent values, and its traders’ utility is more than 1/8 of the first-best social welfare for correlated values (see Appendix § 7 .8).
The Limitations of Weakly Budget-Balanced Mechanisms
The separation results of § 4 show that money burning can substantially improve the traders’ surplus and the traders’ utility. Weakly budget-balanced mechanisms can obtain arbitrarily more traders’ surplus and traders’ utility than strongly budget-balanced ones, with independent and correlated values, respectively (Theorems 4.1 and 4.2 ). This raises the natural question of whether this additional power is enough to overcome the known barriers to approximating the first-best with SBB DSIC mechanisms. The following results show a sharp limit: even WBB DSIC mechanisms cannot guarantee a constant approximation to the first-best traders’ surplus (for independent values) or the first-best traders’ utility (for correlated values). 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.
Theorem 5.1. For every ε > 0 \varepsilon> 0 ε > 0 , there are independent seller and buyer distributions F s \mathcal{F}_s F s and F b \mathcal{F}_b F b such that every dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB satisfies
T S M W B B ( F s × F b ) ≤ G F T M W B B ( F s × F b ) < ε ⋅ G F T O P T ( F s × F b ) = ε ⋅ T S O P T ( F s × F b ) . \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}_{\mathcal{OPT}}(\mathcal{F}_s \times\mathcal{F}_b) = \varepsilon\cdot\mathrm{TS}_{\mathcal{OPT}}(\mathcal{F}_s \times\mathcal{F}_b). TS M WBB ( F s × F b ) ≤ GFT M WBB ( F s × F b ) < ε ⋅ GFT O P T ( F s × F b ) = ε ⋅ TS O P T ( F s × F b ) .
Theorem 5.2. For every ε > 0 \varepsilon> 0 ε > 0 , there is a correlated distribution F \mathcal{F} F such that every dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced mechanism M W B B \mathcal{M}^{\mathrm{WBB}} M WBB satisfies
T U M W B B ( F ) ≤ S W M W B B ( F ) < ε ⋅ S W O P T ( F ) = ε ⋅ T U O P T ( F ) . \mathrm{TU}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) \le\mathrm{SW}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F}) < \varepsilon\cdot\mathrm{SW}_{\mathcal{OPT}}(\mathcal{F}) = \varepsilon\cdot\mathrm{TU}_{\mathcal{OPT}}(\mathcal{F}). TU M WBB ( F ) ≤ SW M WBB ( F ) < ε ⋅ SW O P T ( F ) = ε ⋅ TU O P T ( F ) .
For independent values, Blumrosen and Dobzinski [11 ] showed that no SBB DSIC and IR mechanism guarantees a constant fraction of the first-best gains-from-trade. Theorem 5.1 establishes the same impossibility for the larger class of WBB DSIC and IR mechanisms, using the same family of distributions as in [11 ] .
For correlated values, Dobzinski and Shaulker [39 ] showed that no SBB mechanism in which both traders have a dominant strategy guarantees a constant approximation to first-best social welfare. Theorem 5.2 shows that allowing the randomized DSIC mechanism to be WBB is still not enough to overcome this barrier.
Proof of Theorem 5.1
To prove the theorem we consider the same family of independent distributions as in [11 ] .
The distributions. For every t ≥ 4 t \ge4 t ≥ 4 , let F s t \mathcal{F}_s^t F s t and F b t \mathcal{F}_b^t F b t be the seller’s and the buyer’s value distributions, respectively, both supported on the interval [ 0 , t ] [0,t] [ 0 , t ] . We denote by F s t F_s^t F s t and f s t f_s^t f s t the cumulative distribution function and the probability density function of F s t \mathcal{F}_s^t F s t , and by F b t F_b^t F b t and f b t f_b^t f b t those of F b t \mathcal{F}_b^t F b t . For every z ∈ [ 0 , t ] z \in[0,t] z ∈ [ 0 , t ] ,
F b t ( z ) = λ ( 1 − e − z ) , f b t ( z ) = λ e − z , F_b^t(z) = \lambda(1-e^{-z}), \qquad f_b^t(z) = \lambda e^{-z}, F b t ( z ) = λ ( 1 − e − z ) , f b t ( z ) = λ e − z ,
F s t ( z ) = λ ( e z − t − e − t ) , f s t ( z ) = λ e z − t , F_s^t(z) = \lambda(e^{z-t}-e^{-t}), \qquad f_s^t(z) = \lambda e^{z-t}, F s t ( z ) = λ ( e z − t − e − t ) , f s t ( z ) = λ e z − t ,
where λ = 1 1 − e − t \lambda= \frac{1}{1-e^{-t}} λ = 1 − e − t 1 . {#eq:23}
Proof of Theorem 5.1. Let ε > 0 \varepsilon> 0 ε > 0 be as in the statement of the theorem, and let t ≥ 4 t \ge4 t ≥ 4 be such that
2 t ( 1 + 11 e ( 1 2 + log t ) ) < ε ; (24) \frac{2}{t}\left(1+\frac{11}{e}\left(\frac{1}{2}+\log t\right)\right) < \varepsilon; \tag*{(24)} t 2 ( 1 + e 11 ( 2 1 + log t ) ) < ε ; (24)
such t t t exists since the left-hand side tends to 0 0 0 as t → ∞ t \to\infty t → ∞ . Now that t t t is fixed, we drop it from the notation and write F s \mathcal{F}_s F s , F b \mathcal{F}_b F b , F s F_s F s , f s f_s f s , F b F_b F b , and f b f_b f b for simplicity. Let M = ( x , p B , p S ) \mathcal{M}=(x,p_B,p_S) M = ( x , p B , p S ) be a WBB DSIC and IR mechanism for F s × F b \mathcal{F}_s \times\mathcal{F}_b F s × F b . For every r ∈ [ 0 , t ] r \in[0,t] r ∈ [ 0 , t ] , let
A ( r ) = ∫ 0 t − r x ( v s , v s + r ) d v s . (25) A(r) = \int_{0}^{t-r} x(v_s,v_s+r)\,\mathrm{d}v_s. \tag*{(25)} A ( r ) = ∫ 0 t − r x ( v s , v s + r ) d v s . (25)
That is, A ( r ) A(r) A ( r ) is the integral of the trade probability over the profiles with gain from trade r r r .
Lemma 5.3 below expresses the gains-from-trade of M \mathcal{M} M in terms of A A A . It uses the fact that, under F s × F b \mathcal{F}_s \times\mathcal{F}_b F s × F b , all the profiles with the same gain from trade r r r have the same density.
Lemma 5.3 (Gains-from-trade and trade probabilities). The gains-from-trade of M \mathcal{M} M are
G F T M ( F s × F b ) = λ 2 e − t ∫ 0 t r e − r A ( r ) d r . \mathrm{GFT}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) = \lambda^2 e^{-t} \int_{0}^{t} r e^{-r} A(r)\,\mathrm{d}r. GFT M ( F s × F b ) = λ 2 e − t ∫ 0 t r e − r A ( r ) d r .
Lemma 5.4 uses WBB to bound the expression for the gains-from-trade of M \mathcal{M} M given by Lemma 5.3. Applying the inequality of Lemma 3.6 at the profiles with gain from trade r r r shows that trade at the profiles with a smaller gain from trade forces trade at the profiles with gain from trade r r r . Since the trade probability is at most 1, this limits the trade at the profiles with a small gain from trade, which carry most of the weight in this integral.
Lemma 5.4 (Trade at profiles with a small gain from trade). The function A A A satisfies
∫ 0 t r e − r A ( r ) d r ≤ 1 + 11 e ( 1 2 + log t ) . (26) \int_{0}^{t} r e^{-r} A(r)\,dr \le1+\frac{11}{e}\left(\frac{1}{2}+\log t\right). \tag*{(26)} ∫ 0 t r e − r A ( r ) d r ≤ 1 + e 11 ( 2 1 + log t ) . (26)
The following upper bound on the gains-from-trade of M \mathcal{M} M follows directly from Lemmas 5.3 and 5.4, by substituting the bound of Lemma 5.4 into the expression of Lemma 5.3.
Corollary 5.5. The gains-from-trade of M \mathcal{M} M satisfy
GFT M ( F s × F b ) ≤ λ 2 e − t ( 1 + 11 e ( 1 2 + log t ) ) . (27) \operatorname{GFT}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) \le\lambda^2 e^{-t}\left(1+\frac{11}{e}\left(\frac{1}{2}+\log t\right)\right). \tag*{(27)} GFT M ( F s × F b ) ≤ λ 2 e − t ( 1 + e 11 ( 2 1 + log t ) ) . (27)
Finally, Lemma 5.6 gives a lower bound on the first-best gains-from-trade.
Lemma 5.6 (First-best gains-from-trade). The first-best gains-from-trade satisfy
GFT O P T ( F s × F b ) = λ 2 ( ( t − 2 ) e − t + ( t + 2 ) e − 2 t ) ≥ λ 2 e − t 2 . \operatorname{GFT}_{\mathrm{OPT}}(\mathcal{F}_s \times\mathcal{F}_b)=\lambda^2\left((t-2)e^{-t}+(t+2)e^{-2t}\right)\ge\frac{\lambda^2e^{-t}}{2}. GFT OPT ( F s × F b ) = λ 2 ( ( t − 2 ) e − t + ( t + 2 ) e − 2 t ) ≥ 2 λ 2 e − t .
Combining Corollary 5.5 and Lemma 5.6 bounds the approximation ratio of M \mathcal{M} M :
GFT M ( F s × F b ) GFT O P T ( F s × F b ) ≤ 2 t ( 1 + 11 e ( 1 2 + log t ) ) < ε , \frac{\operatorname{GFT}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b)}{\operatorname{GFT}_{\mathrm{OPT}}(\mathcal{F}_s \times\mathcal{F}_b)}
\le\frac{2}{t}\left(1+\frac{11}{e}\left(\frac{1}{2}+\log t\right)\right)<\varepsilon, GFT OPT ( F s × F b ) GFT M ( F s × F b ) ≤ t 2 ( 1 + e 11 ( 2 1 + log t ) ) < ε ,
where the last inequality holds due to Inequality (24). Moreover, since M \mathcal{M} M is WBB, the money it burns is nonnegative, so TSM M ( F s × F b ) ≤ GFT M ( F s × F b ) \operatorname{TSM}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b)\le\operatorname{GFT}_{\mathcal{M}}(\mathcal{F}_s \times\mathcal{F}_b) TSM M ( F s × F b ) ≤ GFT M ( F s × F b ) . Since M \mathcal{M} M is an arbitrary WBB DSIC and IR mechanism, this proves the theorem.
The proofs of Lemmas 5.3, 5.4, and 5.6 are deferred to Appendices A.9, A.10, and A.11, respectively.
Proof of Theorem 5.2
To prove the theorem we consider a family of correlated distributions supported on a geometric grid.
The distributions. For every integer n ≥ 4 n \ge4 n ≥ 4 , let R = n R=\sqrt{n} R = n , and let
q i = R i − n , i = 0 , … , n , q_i=R^{i-n},\qquad i=0,\ldots,n, q i = R i − n , i = 0 , … , n ,
so that q i = R q i − 1 q_i=Rq_{i-1} q i = R q i − 1 for every i ∈ [ n ] i\in[n] i ∈ [ n ] , and q n = 1 q_n=1 q n = 1 . Let F n \mathcal{F}^n F n be the joint distribution supported on the n n n profiles ( q i − 1 , q i ) (q_{i-1},q_i) ( q i − 1 , q i ) , $i\in[n],16 w h e r e t h e p r o f i l e where the profile w h er e t h e p r o f i l e (q_{i-1},q_i)$ has probability
π i = 1 Z q i , where Z = ∑ r = 1 n 1 q r . (28) \pi_i=\frac{1}{Zq_i},\qquad\text{where } Z=\sum_{r=1}^{n}\frac{1}{q_r}. \tag*{(28)} π i = Z q i 1 , where Z = r = 1 ∑ n q r 1 . (28)
Proof of Theorem 5.2 . Let ε > 0 \varepsilon> 0 ε > 0 be as in the statement of the theorem, and let n ≥ 4 n \ge4 n ≥ 4 be an integer such that 6 / n < ε 6/\sqrt{n} < \varepsilon 6/ n < ε . Now that n n n is fixed, we drop it from the notation and write F \mathcal{F} F for F n \mathcal{F}^{n} F n . Let M = ( x , p B , p S ) \mathcal{M} = (x,p_B,p_S) M = ( x , p B , p S ) be a WBB DSIC and IR mechanism for F \mathcal{F} F .
Lemma 5.7 below expresses the social welfare of M \mathcal{M} M in terms of its trade probabilities at the profiles in the support. It uses the fact that the probability of each profile in the support is inversely proportional to its buyer’s value.
Lemma 5.7 (Social welfare and trade probabilities). The social welfare of M \mathcal{M} M is
SW M ( F ) = 1 Z ∑ i = 1 n ( 1 R + ( 1 − 1 R ) x ( q i − 1 , q i ) ) . \operatorname{SW}_{\mathcal{M}}(\mathcal{F}) = \frac{1}{Z}\sum_{i=1}^{n}\left(\frac{1}{R}+\left(1-\frac{1}{R}\right)x(q_{i-1},q_i)\right). SW M ( F ) = Z 1 i = 1 ∑ n ( R 1 + ( 1 − R 1 ) x ( q i − 1 , q i ) ) .
Lemma 5.8 bounds the sum of the trade probabilities in the expression of Lemma 5.7 . The bound follows from WBB, through the inequality of Lemma 3.6 , which combines WBB with Myerson’s lemma.
Lemma 5.8 (Allocation bound on a geometric grid). The trade probabilities of M \mathcal{M} M satisfy
∑ i = 1 n x ( q i − 1 , q i ) ≤ 5 R . (29) \sum_{i=1}^{n}x(q_{i-1},q_i) \le5R. \tag*{(29)} i = 1 ∑ n x ( q i − 1 , q i ) ≤ 5 R . (29)
The following upper bound on the social welfare of M \mathcal{M} M follows directly from Lemmas 5.7 and 5.8 , by substituting the bound of Lemma 5.8 into the expression of Lemma 5.7 .
Corollary 5.9. The social welfare of M \mathcal{M} M satisfies
SW M ( F ) ≤ 1 Z ( n R + 5 R ) . \operatorname{SW}_{\mathcal{M}}(\mathcal{F}) \le\frac{1}{Z}\left(\frac{n}{R}+5R\right). SW M ( F ) ≤ Z 1 ( R n + 5 R ) .
Finally, Lemma 5.10 gives the first-best social welfare.
Lemma 5.10 (First-best social welfare). The first-best social welfare is SW O P T ( F ) = n / Z \operatorname{SW}_{OPT}(\mathcal{F}) = n/Z SW O P T ( F ) = n / Z .
Combining Corollary 5.9 and Lemma 5.10 bounds the approximation ratio of M \mathcal{M} M :
SW M ( F ) SW O P T ( F ) ≤ 1 R + 5 R n = 6 n < ε . \frac{\operatorname{SW}_{\mathcal{M}}(\mathcal{F})}{\operatorname{SW}_{OPT}(\mathcal{F})} \le\frac{1}{R}+\frac{5R}{n}=\frac{6}{\sqrt{n}}<\varepsilon. SW O P T ( F ) SW M ( F ) ≤ R 1 + n 5 R = n 6 < ε .
Moreover, since M \mathcal{M} M is WBB, the money it burns is nonnegative, so TU M ( F ) ≤ SW M ( F ) \operatorname{TU}_{\mathcal{M}}(\mathcal{F}) \le\operatorname{SW}_{\mathcal{M}}(\mathcal{F}) TU M ( F ) ≤ SW M ( F ) . Since M \mathcal{M} M is an arbitrary WBB DSIC and IR mechanism, this proves the theorem.
The proofs of Lemmas 5.7 , 5.8 , and 5.10 are deferred to Appendices § 7 .12, § 7 .13, and § 7 .14, respectively.
AI Disclosure
All ideas, technical content, proofs, and results are the authors’ own. We used Codex and Claude to assist in drafting and editing the text throughout the paper, and in creating the figures. We have also used AI tools to review the paper. The authors verified the correctness and originality of all content, including references, and take full responsibility for it.
Omitted Proofs
Proof of Proposition 3.7
Proof of Proposition 3.7. Let T T T be the set of profiles at which the given mechanism trades, that is, T = { ( v s , v b ) ∣ x ( v s , v b ) = 1 } T = \{(v_s,v_b) \mid x(v_s,v_b) = 1\} T = {( v s , v b ) ∣ x ( v s , v b ) = 1 } . If T T T is empty, the claim is immediate, so assume that it is not. By individual rationality and weak budget balance, v s ≤ v b v_s \le v_b v s ≤ v b for every ( v s , v b ) ∈ T (v_s,v_b) \in T ( v s , v b ) ∈ T .
We claim that v s ′ ≤ v b v_s' \le v_b v s ′ ≤ v b for every two profiles ( v s , v b ) , ( v s ′ , v b ′ ) ∈ T (v_s,v_b),(v_s',v_b') \in T ( v s , v b ) , ( v s ′ , v b ′ ) ∈ T . Suppose instead that v b < v s ′ v_b < v_s' v b < v s ′ . Then v b < v s ′ ≤ v b ′ v_b < v_s' \le v_b' v b < v s ′ ≤ v b ′ , so by monotonicity the mechanism also trades at ( v s , v b ′ ) (v_s,v_b') ( v s , v b ′ ) . By dominant-strategy incentive compatibility, the buyer’s payment is the same at ( v s , v b ′ ) (v_s,v_b') ( v s , v b ′ ) and at ( v s , v b ) (v_s,v_b) ( v s , v b ) , and by individual rationality at ( v s , v b ) (v_s,v_b) ( v s , v b ) it is at most v b v_b v b . Similarly, the amount that the seller receives is the same at ( v s , v b ′ ) (v_s,v_b') ( v s , v b ′ ) and at ( v s ′ , v b ′ ) (v_s',v_b') ( v s ′ , v b ′ ) , and by individual rationality at ( v s ′ , v b ′ ) (v_s',v_b') ( v s ′ , v b ′ ) it is at least v s ′ v_s' v s ′ . Since v b < v s ′ v_b < v_s' v b < v s ′ , the buyer pays less than the seller receives at ( v s , v b ′ ) (v_s,v_b') ( v s , v b ′ ) , which violates weak budget balance.
Let p = sup ( v s , v b ) ∈ T v s p = \sup_{(v_s,v_b)\in T} v_s p = sup ( v s , v b ) ∈ T v s . By the claim, p p p is finite and v s ≤ p ≤ v b v_s \le p \le v_b v s ≤ p ≤ v b for every ( v s , v b ) ∈ T (v_s,v_b) \in T ( v s , v b ) ∈ T . The mechanism that posts the price p p p is deterministic, dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced, and it trades at every profile in T T T . □
Proof of Lemma 4.3
Proof of Lemma 4.3. We first verify that the parameters of the construction are well defined. The restriction on τ \tau τ guarantees that s i − 1 < b i s_{i-1} < b_i s i − 1 < b i for every i ∈ [ n ] i \in[n] i ∈ [ n ] . It also guarantees that every denominator in Equation (18) is positive: for every $1 \le i < j \le n$, the denominator is at least
q j − q i − 1 − 2 τ > 0. q_j - q_{i-1} - 2\tau> 0. q j − q i − 1 − 2 τ > 0.
Thus, Γ \Gamma Γ is finite.
We next verify DSIC and IR. In Equation (19) , the exponent of every positive allocation probability lies between 0 0 0 and n − 1 n-1 n − 1 . Hence, the normalization by Γ n − 1 \Gamma^{n-1} Γ n − 1 keeps all allocation probabilities in [ 0 , 1 ] [0,1] [ 0 , 1 ] , and the smallest positive probability is Γ − ( n − 1 ) \Gamma^{-(n-1)} Γ − ( n − 1 ) . Moreover, increasing the seller’s report can only increase her rounded index and therefore decrease the allocation probability. Similarly, increasing the buyer’s report can only increase his rounded index and therefore increase the allocation probability. Thus, the allocation rule is nonincreasing in v s v_s v s and nondecreasing in v b v_b v b .
Myerson’s lemma therefore provides payments that make the mechanism DSIC and IR. We use normalized payments, which are zero whenever x ( v s , v b ) = 0 x(v_s,v_b)=0 x ( v s , v b ) = 0 . For all agents’ value profiles ( v s , v b ) (v_s,v_b) ( v s , v b ) with positive allocation probability, they are
p B ( v s , v b ) = v b ⋅ x ( v s , v b ) − ∫ v s v b x ( v s , z ) d z , p_B(v_s,v_b)=v_b\cdot x(v_s,v_b)-\int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z, p B ( v s , v b ) = v b ⋅ x ( v s , v b ) − ∫ v s v b x ( v s , z ) d z ,
p S ( v s , v b ) = v s ⋅ x ( v s , v b ) + ∫ v s v b x ( z , v b ) d z . p_S(v_s,v_b)=v_s\cdot x(v_s,v_b)+\int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z. p S ( v s , v b ) = v s ⋅ x ( v s , v b ) + ∫ v s v b x ( z , v b ) d z .
Thus, WBB holds immediately at all agents’ profiles with zero allocation probability. At agents’ profiles with positive allocation probability, substituting these payments into p B ( v s , v b ) ≥ p S ( v s , v b ) p_B(v_s,v_b)\ge p_S(v_s,v_b) p B ( v s , v b ) ≥ p S ( v s , v b ) shows that WBB is equivalent to
∫ v s v b x ( v s , z ) d z + ∫ v s v b x ( z , v b ) d z ≤ ( v b − v s ) x ( v s , v b ) . (30) \int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z+\int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z\le(v_b-v_s)x(v_s,v_b). \tag*{(30)} ∫ v s v b x ( v s , z ) d z + ∫ v s v b x ( z , v b ) d z ≤ ( v b − v s ) x ( v s , v b ) . (30)
It remains to verify this inequality. Fix the agents’ value profile ( v s , v b ) (v_s,v_b) ( v s , v b ) with positive allocation probability and write
i = ι S ( v s ) + 1 , j = ι B ( v b ) . i=\iota_S(v_s)+1,\qquad j=\iota_B(v_b). i = ι S ( v s ) + 1 , j = ι B ( v b ) .
Partitioning the two integrals at the buyer and seller thresholds, and using that x x x is constant between consecutive thresholds, gives
∫ v s v b x ( v s , z ) d z = 1 Γ n − 1 ( ∑ r = i j − 1 ( b r + 1 − b r ) Γ r − i + ( v b − b j ) Γ j − i ) , \int_{v_s}^{v_b}x(v_s,z)\,\mathrm{d}z=\frac{1}{\Gamma^{n-1}}\left(\sum_{r=i}^{j-1}(b_{r+1}-b_r)\Gamma^{r-i}+(v_b-b_j)\Gamma^{j-i}\right), ∫ v s v b x ( v s , z ) d z = Γ n − 1 1 ( r = i ∑ j − 1 ( b r + 1 − b r ) Γ r − i + ( v b − b j ) Γ j − i ) ,
∫ v s v b x ( z , v b ) d z = 1 Γ n − 1 ( ( s i − 1 − v s ) Γ j − i + ∑ r = i + 1 j ( s r − 1 − s r − 2 ) Γ j − r ) . \int_{v_s}^{v_b}x(z,v_b)\,\mathrm{d}z=\frac{1}{\Gamma^{n-1}}\left((s_{i-1}-v_s)\Gamma^{j-i}+\sum_{r=i+1}^{j}(s_{r-1}-s_{r-2})\Gamma^{j-r}\right). ∫ v s v b x ( z , v b ) d z = Γ n − 1 1 ( ( s i − 1 − v s ) Γ j − i + r = i + 1 ∑ j ( s r − 1 − s r − 2 ) Γ j − r ) .
Substituting these expressions into Equation (30) and rearranging the inequality yields
( b j − s i − 1 ) Γ j − i ≥ ∑ r = i j − 1 ( b r + 1 − b r ) Γ r − i + ∑ r = i + 1 j ( s r − 1 − s r − 2 ) Γ j − r . (31) (b_j-s_{i-1})\Gamma^{j-i}\ge\sum_{r=i}^{j-1}(b_{r+1}-b_r)\Gamma^{r-i}+\sum_{r=i+1}^{j}(s_{r-1}-s_{r-2})\Gamma^{j-r}. \tag*{(31)} ( b j − s i − 1 ) Γ j − i ≥ r = i ∑ j − 1 ( b r + 1 − b r ) Γ r − i + r = i + 1 ∑ j ( s r − 1 − s r − 2 ) Γ j − r . (31)
So we are left to show that this indeed holds. We consider two cases. If i = j i=j i = j , both sums vanish, and the inequality follows immediately. Suppose instead that i < j i<j i < j . Every exponent on the right-hand side is at most j − i − 1 j-i-1 j − i − 1 . Moreover, by the definitions of the thresholds,
( b j − b i ) + ( s j − 1 − s i − 1 ) b j − s i − 1 = 1 + q j − 1 − q i + 2 τ q j − q i − 1 − τ ⋅ 1 { i > 1 } − τ ⋅ 1 { j < n } ≤ Γ , \frac{(b_j-b_i)+(s_{j-1}-s_{i-1})}{b_j-s_{i-1}}=1+\frac{q_{j-1}-q_i+2\tau}{q_j-q_{i-1}-\tau\cdot\mathbb{1}_{\{i>1\}}-\tau\cdot\mathbb{1}_{\{j<n\}}}\le\Gamma, b j − s i − 1 ( b j − b i ) + ( s j − 1 − s i − 1 ) = 1 + q j − q i − 1 − τ ⋅ 1 { i > 1 } − τ ⋅ 1 { j < n } q j − 1 − q i + 2 τ ≤ Γ ,
where the inequality follows from Equation (18) . We can therefore bound the right-hand side of Equation (31) as follows:
∑ r = i j − 1 ( b r + 1 − b r ) Γ r − i + ∑ r = i + 1 j ( s r − 1 − s r − 2 ) Γ j − r ≤ Γ j − i − 1 ( ( b j − b i ) + ( s j − 1 − s i − 1 ) ) ≤ Γ j − i ( b j − s i − 1 ) . \begin{aligned}
\sum_{r=i}^{j-1}(b_{r+1}-b_r)\Gamma^{r-i}+\sum_{r=i+1}^{j}(s_{r-1}-s_{r-2})\Gamma^{j-r}
&\le\Gamma^{j-i-1}\left((b_j-b_i)+(s_{j-1}-s_{i-1})\right)\\
&\le\Gamma^{j-i}(b_j-s_{i-1}).
\end{aligned} r = i ∑ j − 1 ( b r + 1 − b r ) Γ r − i + r = i + 1 ∑ j ( s r − 1 − s r − 2 ) Γ j − r ≤ Γ j − i − 1 ( ( b j − b i ) + ( s j − 1 − s i − 1 ) ) ≤ Γ j − i ( b j − s i − 1 ) .
Thus, inequality (31) holds, and the constructed mechanism is indeed WBB.
Proof of Lemma 4.5
Proof of Lemma 4.5. We first show two claims. Claim A.1 shows that every positive allocation probability of M W B B \mathcal{M}^{\mathrm{WBB}} M WBB is greater than 1 2 \frac{1}{2} 2 1 , and Claim A.2 uses it to compare, at the profiles in the sets R i \mathcal{R}_i R i , our mechanism with an SBB mechanism.
Claim A.1. The allocation rule x x x of M W B B \mathcal{M}^{\mathrm{WBB}} M WBB satisfies x ( v s , v b ) > 1 2 x(v_s,v_b)>\frac{1}{2} x ( v s , v b ) > 2 1 for every ( v s , v b ) (v_s,v_b) ( v s , v b ) with ι S ( v s ) < ι B ( v b ) \iota_S(v_s)<\iota_B(v_b) ι S ( v s ) < ι B ( v b ) .
Proof of Claim A.1. Let δ \delta δ and L L L be as in Definition 4.4. By the definition, τ ≤ δ L / 100 < L / 2 \tau\leq\delta L/100<L/2 τ ≤ δ L /100 < L /2 , which is the condition of Lemma 4.3 in (17) . Fix 1 ≤ i < j ≤ n 1\leq i<j\leq n 1 ≤ i < j ≤ n . Since i < j i<j i < j , the difference q j − q i − 1 = ∑ r = i j ( q r − q r − 1 ) q_j-q_{i-1}=\sum_{r=i}^{j}(q_r-q_{r-1}) q j − q i − 1 = ∑ r = i j ( q r − q r − 1 ) is a sum of at least two gaps of the grid, so it is at least 2 L 2L 2 L , and hence 2 τ ≤ ( δ / 100 ) ⋅ 2 L ≤ ( δ / 100 ) ( q j − q i − 1 ) 2\tau\leq(\delta/100)\cdot2L\leq(\delta/100)(q_j-q_{i-1}) 2 τ ≤ ( δ /100 ) ⋅ 2 L ≤ ( δ /100 ) ( q j − q i − 1 ) . Therefore,
q j − 1 − q i + 2 τ q j − q i − 1 − τ ⋅ 1 { i > 1 } − τ ⋅ 1 { j < n } ≤ q j − 1 − q i + 2 τ q j − q i − 1 − 2 τ ≤ ( 4 δ + δ / 100 ) ( q j − q i − 1 ) ( 1 − δ / 100 ) ( q j − q i − 1 ) = 4 δ + δ / 100 1 − δ / 100 ≤ 8 δ . \frac{q_{j-1}-q_i+2\tau}{q_j-q_{i-1}-\tau\cdot\mathbf{1}_{\{i>1\}}-\tau\cdot\mathbf{1}_{\{j<n\}}}
\leq
\frac{q_{j-1}-q_i+2\tau}{q_j-q_{i-1}-2\tau}
\leq
\frac{(4\delta+\delta/100)(q_j-q_{i-1})}{(1-\delta/100)(q_j-q_{i-1})}
=
\frac{4\delta+\delta/100}{1-\delta/100}
\leq8\delta. q j − q i − 1 − τ ⋅ 1 { i > 1 } − τ ⋅ 1 { j < n } q j − 1 − q i + 2 τ ≤ q j − q i − 1 − 2 τ q j − 1 − q i + 2 τ ≤ ( 1 − δ /100 ) ( q j − q i − 1 ) ( 4 δ + δ /100 ) ( q j − q i − 1 ) = 1 − δ /100 4 δ + δ /100 ≤ 8 δ .
where the first inequality holds since each indicator is at most 1, the second follows from (20) for the first term of the numerator and from 2 τ ≤ ( δ / 100 ) ( q j − q i − 1 ) 2\tau\leq(\delta/100)(q_j-q_{i-1}) 2 τ ≤ ( δ /100 ) ( q j − q i − 1 ) for the remaining terms, and the last holds since δ ≤ 1 / 200 \delta\leq1/200 δ ≤ 1/200 . Since this holds for every 1 ≤ i < j ≤ n 1\leq i<j\leq n 1 ≤ i < j ≤ n , the growth factor in (18) satisfies Γ ≤ 1 + 8 δ \Gamma\leq1+8\delta Γ ≤ 1 + 8 δ , and Γ n − 1 ≤ ( 1 + 8 δ ) n − 1 < e 8 δ n ≤ e 0.08 < 2 \Gamma^{n-1}\leq(1+8\delta)^{n-1}<e^{8\delta n}\leq e^{0.08}<2 Γ n − 1 ≤ ( 1 + 8 δ ) n − 1 < e 8 δ n ≤ e 0.08 < 2 . The claim follows since, by Lemma 4.3, x ( v s , v b ) ≥ Γ − ( n − 1 ) > 1 2 x(v_s,v_b)\geq\Gamma^{-(n-1)}>\frac{1}{2} x ( v s , v b ) ≥ Γ − ( n − 1 ) > 2 1 whenever ι S ( v s ) < ι B ( v b ) \iota_S(v_s)<\iota_B(v_b) ι S ( v s ) < ι B ( v b ) .
Claim A.2. Let M S B B \mathcal{M}^{\mathrm{SBB}} M SBB be a dominant-strategy incentive-compatible, individually rational, and strongly budget-balanced mechanism. By [ČP16], the allocation rule of M S B B \mathcal{M}^{\mathrm{SBB}} M SBB satisfies x S B B ( v s , v b ) ≤ μ ( [ v s , v b ] ) x^{\mathrm{SBB}}(v_s,v_b)\leq\mu([v_s,v_b]) x SBB ( v s , v b ) ≤ μ ([ v s , v b ]) for some distribution μ \mu μ over posted prices. Then for every 1 ≤ i ≤ n − 3 1\leq i\leq n-3 1 ≤ i ≤ n − 3 and every ( v s , v b ) ∈ R i (v_s,v_b)\in\mathcal{R}_i ( v s , v b ) ∈ R i ,
T S M W B B ( v s , v b ) > v b − v s 2 and T S M S B B ( v s , v b ) ≤ ( v b − v s ) ⋅ μ ( [ q i , q i + 2 ] ) . \mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(v_s,v_b)>\frac{v_b-v_s}{2}
\qquad\text{and}\qquad
\mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(v_s,v_b)\leq(v_b-v_s)\cdot\mu([q_i,q_{i+2}]). TS M WBB ( v s , v b ) > 2 v b − v s and TS M SBB ( v s , v b ) ≤ ( v b − v s ) ⋅ μ ([ q i , q i + 2 ]) .
Proof of Claim A.2. Since 1 ≤ i 1\leq i 1 ≤ i and i + 2 ≤ n − 1 i+2\leq n-1 i + 2 ≤ n − 1 , we have s i − 1 < v s ≤ s i s_{i-1}<v_s\leq s_i s i − 1 < v s ≤ s i and b i + 2 ≤ v b < b i + 3 b_{i+2}\leq v_b<b_{i+3} b i + 2 ≤ v b < b i + 3 , so ι S ( v s ) = i \iota_S(v_s)=i ι S ( v s ) = i and ι B ( v b ) = i + 2 \iota_B(v_b)=i+2 ι B ( v b ) = i + 2 . For the payments of Lemma 4.3,
T S M W B B ( v s , v b ) = ∫ 0 v b x ( v s , z ) d z + ∫ v s 1 x ( z , v b ) d z ≥ ∫ b i + 1 b i + 2 x ( v s , z ) d z + ∫ s i s i + 1 x ( z , v b ) d z > 1 2 ( b i + 2 − b i + 1 ) + 1 2 ( s i + 1 − s i ) = 1 2 ( q i + 2 − q i + 1 ) + 1 2 ( q i + 1 − q i ) = q i + 2 − q i 2 ≥ v b − v s 2 . \begin{aligned}
\mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(v_s,v_b)
&=\int_0^{v_b}x(v_s,z)\,\mathrm{d}z+\int_{v_s}^{1}x(z,v_b)\,\mathrm{d}z\\
&\geq\int_{b_{i+1}}^{b_{i+2}}x(v_s,z)\,\mathrm{d}z+\int_{s_i}^{s_{i+1}}x(z,v_b)\,\mathrm{d}z\\
&>\frac{1}{2}(b_{i+2}-b_{i+1})+\frac{1}{2}(s_{i+1}-s_i)\\
&=\frac{1}{2}(q_{i+2}-q_{i+1})+\frac{1}{2}(q_{i+1}-q_i)\\
&=\frac{q_{i+2}-q_i}{2}\geq\frac{v_b-v_s}{2}.
\end{aligned} TS M WBB ( v s , v b ) = ∫ 0 v b x ( v s , z ) d z + ∫ v s 1 x ( z , v b ) d z ≥ ∫ b i + 1 b i + 2 x ( v s , z ) d z + ∫ s i s i + 1 x ( z , v b ) d z > 2 1 ( b i + 2 − b i + 1 ) + 2 1 ( s i + 1 − s i ) = 2 1 ( q i + 2 − q i + 1 ) + 2 1 ( q i + 1 − q i ) = 2 q i + 2 − q i ≥ 2 v b − v s .
The first equality holds by Myerson’s lemma, applied to the normalized payments of Lemma 4.3: the buyer’s utility is ∫ 0 v b x ( v s , z ) d z \int_0^{v_b}x(v_s,z)\,\mathrm{d}z ∫ 0 v b x ( v s , z ) d z and the seller’s utility minus v s v_s v s is ∫ v s 1 x ( z , v b ) d z \int_{v_s}^{1}x(z,v_b)\,\mathrm{d}z ∫ v s 1 x ( z , v b ) d z . The first inequality holds since the allocation probabilities are nonnegative, [ b i + 1 , b i + 2 ] ⊆ [ 0 , v b ] [b_{i+1},b_{i+2}]\subseteq[0,v_b] [ b i + 1 , b i + 2 ] ⊆ [ 0 , v b ] , and [ s i , s i + 1 ] ⊆ [ v s , 1 ] [s_i,s_{i+1}]\subseteq[v_s,1] [ s i , s i + 1 ] ⊆ [ v s , 1 ] . The second inequality holds by Claim A.1, since ι B ( z ) = i + 1 > ι S ( v s ) \iota_B(z)=i+1>\iota_S(v_s) ι B ( z ) = i + 1 > ι S ( v s ) for z ∈ [ b i + 1 , b i + 2 ) z\in[b_{i+1},b_{i+2}) z ∈ [ b i + 1 , b i + 2 ) , and ι S ( z ) = i + 1 < ι B ( v b ) \iota_S(z)=i+1<\iota_B(v_b) ι S ( z ) = i + 1 < ι B ( v b ) for z ∈ ( s i , s i + 1 ] z\in(s_i,s_{i+1}] z ∈ ( s i , s i + 1 ] . The second equality holds since b r = q r − τ b_r=q_r-\tau b r = q r − τ and s r = q r + τ s_r=q_r+\tau s r = q r + τ for every $1\leq r\leq n-1, and the indices i i i , i + 1 i+1 i + 1 , and i + 2 i+2 i + 2 are all in this range, so τ \tau τ cancels in each difference. The third inequality holds since q i ≤ v s q_i\leq v_s q i ≤ v s and v b ≤ q i + 2 v_b\leq q_{i+2} v b ≤ q i + 2 .
For the SBB mechanism, the payments cancel, so
T S M S B B ( v s , v b ) ≤ ( v b − v s ) ⋅ μ ( [ v s , v b ] ) ≤ ( v b − v s ) ⋅ μ ( [ q i , q i + 2 ] ) , \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(v_s,v_b) \leq(v_b-v_s)\cdot\mu([v_s,v_b]) \leq(v_b-v_s)\cdot\mu([q_i,q_{i+2}]), TS M SBB ( v s , v b ) ≤ ( v b − v s ) ⋅ μ ([ v s , v b ]) ≤ ( v b − v s ) ⋅ μ ([ q i , q i + 2 ]) ,
since [ v s , v b ] ⊆ [ q i , q i + 2 ] [v_s,v_b]\subseteq[q_i,q_{i+2}] [ v s , v b ] ⊆ [ q i , q i + 2 ] .
The sets R i \mathcal{R}_i R i , i ∈ I i\in I i ∈ I , are pairwise disjoint, since τ \tau τ is smaller than every gap of the grid. By individual rationality, T S M W B B ( v s , v b ) ≥ 0 \mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(v_s,v_b)\geq0 TS M WBB ( v s , v b ) ≥ 0 at every profile. By Claim A.2 , for every ( v s , v b ) ∈ R i (v_s,v_b)\in\mathcal{R}_i ( v s , v b ) ∈ R i , we have T S M W B B ( v s , v b ) > ( v b − v s ) / 2 \mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(v_s,v_b)>(v_b-v_s)/2 TS M WBB ( v s , v b ) > ( v b − v s ) /2 . Hence, by the first condition,
T S M W B B ( F ) > ∑ i ∈ I 1 2 E [ ( v b − v s ) ⋅ 1 ( v s , v b ) ∈ R i ] ≥ ∑ i ∈ I C 4 = m C 4 . \mathrm{TS}_{\mathcal{M}^{\mathrm{WBB}}}(\mathcal{F})>\sum_{i\in I}\frac{1}{2}\mathbb{E}\left[(v_b-v_s)\cdot\mathbf{1}_{(v_s,v_b)\in\mathcal{R}_i}\right]\geq\sum_{i\in I}\frac{C}{4}=\frac{mC}{4}. TS M WBB ( F ) > i ∈ I ∑ 2 1 E [ ( v b − v s ) ⋅ 1 ( v s , v b ) ∈ R i ] ≥ i ∈ I ∑ 4 C = 4 m C .
For the SBB mechanism, let μ \mu μ be the distribution over posted prices from [CP16]. Its payments cancel, so its traders’ surplus at ( v s , v b ) (v_s,v_b) ( v s , v b ) is at most ( v b − v s ) μ ( [ v s , v b ] ) (v_b-v_s)\mu([v_s,v_b]) ( v b − v s ) μ ([ v s , v b ]) , which is at most ( v b − v s ) ⋅ 1 v s < v b (v_b-v_s)\cdot\mathbf{1}_{v_s<v_b} ( v b − v s ) ⋅ 1 v s < v b . By Claim A.2 , it is at most ( v b − v s ) ⋅ μ ( [ q i , q i + 2 ] ) (v_b-v_s)\cdot\mu([q_i,q_{i+2}]) ( v b − v s ) ⋅ μ ([ q i , q i + 2 ]) for every ( v s , v b ) ∈ R i (v_s,v_b)\in\mathcal{R}_i ( v s , v b ) ∈ R i . Hence, by the two conditions,
T S M S B B ( F ) ≤ C ∑ i ∈ I μ ( [ q i , q i + 2 ] ) + ε 1 ≤ h C + ε 1 , \mathrm{TS}_{\mathcal{M}^{\mathrm{SBB}}}(\mathcal{F})\leq C\sum_{i\in I}\mu([q_i,q_{i+2}])+\varepsilon_1\leq hC+\varepsilon_1, TS M SBB ( F ) ≤ C i ∈ I ∑ μ ([ q i , q i + 2 ]) + ε 1 ≤ h C + ε 1 ,
where the last inequality holds since every price belongs to at most h h h of the intervals [ q i , q i + 2 ] [q_i,q_{i+2}] [ q i , q i + 2 ] .
Proof of Lemma 4.6
Proof of Lemma 4.6. Since q j − 1 − q i = ∑ r = i + 1 j − 1 L r q_{j-1}-q_i=\sum_{r=i+1}^{j-1}L_r q j − 1 − q i = ∑ r = i + 1 j − 1 L r and L i + L j ≤ q j − q i − 1 L_i+L_j\leq q_j-q_{i-1} L i + L j ≤ q j − q i − 1 , it is enough to show that
∑ r = i + 1 j − 1 L r ≤ 4 δ ( L i + L j ) for every 1 ≤ i < j ≤ n . \sum_{r=i+1}^{j-1}L_r\leq4\delta(L_i+L_j)\qquad\text{for every }1\leq i<j\leq n. r = i + 1 ∑ j − 1 L r ≤ 4 δ ( L i + L j ) for every 1 ≤ i < j ≤ n .
We first bound, for every 1 ≤ i ≤ k − 1 1\leq i\leq k-1 1 ≤ i ≤ k − 1 , the sum of the gaps between q i q_i q i and the middle point q k = 1 / 2 q_k=1/2 q k = 1/2 , that is, ∑ r = i + 1 k L r = q k − q i \sum_{r=i+1}^{k}L_r=q_k-q_i ∑ r = i + 1 k L r = q k − q i . For i = 1 i=1 i = 1 ,
∑ r = 2 k L r = q k − q 1 = δ ≤ 4 δ L 1 , \sum_{r=2}^{k}L_r=q_k-q_1=\delta\leq4\delta L_1, r = 2 ∑ k L r = q k − q 1 = δ ≤ 4 δ L 1 ,
because L 1 = 1 2 − δ ≥ 1 4 L_1=\frac{1}{2}-\delta\geq\frac{1}{4} L 1 = 2 1 − δ ≥ 4 1 . For 2 ≤ i ≤ k − 1 2\leq i\leq k-1 2 ≤ i ≤ k − 1 ,
∑ r = i + 1 k L r = q k − q i = δ i − δ 1 − δ L i ≤ 2 δ L i ≤ 4 δ L i , \sum_{r=i+1}^{k}L_r=q_k-q_i=\delta^i-\frac{\delta}{1-\delta}L_i\leq2\delta L_i\leq4\delta L_i, r = i + 1 ∑ k L r = q k − q i = δ i − 1 − δ δ L i ≤ 2 δ L i ≤ 4 δ L i ,
where the first inequality holds since 1 − δ ≥ 1 2 1-\delta\geq\frac{1}{2} 1 − δ ≥ 2 1 . Hence,
∑ r = i + 1 k L r ≤ 4 δ L i for every 1 ≤ i ≤ k − 1. (32) \sum_{r=i+1}^{k}L_r\leq4\delta L_i\qquad\text{for every }1\leq i\leq k-1. \tag*{(32)} r = i + 1 ∑ k L r ≤ 4 δ L i for every 1 ≤ i ≤ k − 1. (32)
Symmetrically, we bound, for every k + 2 ≤ j ≤ n k+2\leq j\leq n k + 2 ≤ j ≤ n , the sum of the gaps between the middle point q k q_k q k and q j − 1 q_{j-1} q j − 1 , that is, ∑ r = k + 1 j − 1 L r = q j − 1 − q k \sum_{r=k+1}^{j-1}L_r=q_{j-1}-q_k ∑ r = k + 1 j − 1 L r = q j − 1 − q k . For j = n j=n j = n ,
∑ r = k + 1 n − 1 L r = q n − 1 − q k = δ ≤ 4 δ L n , \sum_{r=k+1}^{n-1}L_r=q_{n-1}-q_k=\delta\leq4\delta L_n, r = k + 1 ∑ n − 1 L r = q n − 1 − q k = δ ≤ 4 δ L n ,
and for k + 2 ≤ j ≤ n − 1 k+2\le j\le n-1 k + 2 ≤ j ≤ n − 1 ,
∑ r = k + 1 j − 1 L r = q j − 1 − q k = δ n − j + 1 = δ 1 − δ L j ≤ 2 δ L j ≤ 4 δ L j , \sum_{r=k+1}^{j-1} L_r=q_{j-1}-q_k=\delta^{n-j+1}=\frac{\delta}{1-\delta}L_j\le2\delta L_j\le4\delta L_j, r = k + 1 ∑ j − 1 L r = q j − 1 − q k = δ n − j + 1 = 1 − δ δ L j ≤ 2 δ L j ≤ 4 δ L j ,
where the first inequality holds since 1 − δ ≥ 1 2 1-\delta\ge\frac{1}{2} 1 − δ ≥ 2 1 . Hence,
∑ r = k + 1 j − 1 L r ≤ 4 δ L j for every k + 2 ≤ j ≤ n . (33) \sum_{r=k+1}^{j-1}L_r\le4\delta L_j\qquad\text{for every }k+2\le j\le n. \tag*{(33)} r = k + 1 ∑ j − 1 L r ≤ 4 δ L j for every k + 2 ≤ j ≤ n . (33)
Now fix 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n . We consider three cases.
∑ r = i + 1 j − 1 L r ≤ ∑ r = i + 1 k L r ≤ 4 δ L i , \sum_{r=i+1}^{j-1}L_r\le\sum_{r=i+1}^{k}L_r\le4\delta L_i, r = i + 1 ∑ j − 1 L r ≤ r = i + 1 ∑ k L r ≤ 4 δ L i ,
where the first inequality holds since j − 1 ≤ k j-1\le k j − 1 ≤ k and the gaps are positive, and the second is Equation (32) .
∑ r = i + 1 j − 1 L r ≤ ∑ r = k + 1 j − 1 L r ≤ 4 δ L j , \sum_{r=i+1}^{j-1}L_r\le\sum_{r=k+1}^{j-1}L_r\le4\delta L_j, r = i + 1 ∑ j − 1 L r ≤ r = k + 1 ∑ j − 1 L r ≤ 4 δ L j ,
where the first inequality holds since i + 1 ≥ k + 1 i+1\ge k+1 i + 1 ≥ k + 1 and the gaps are positive, and the second is Equation (33) .
∑ r = i + 1 j − 1 L r = ∑ r = i + 1 k L r + ∑ r = k + 1 j − 1 L r ≤ 4 δ L i + 4 δ L j . \sum_{r=i+1}^{j-1}L_r=\sum_{r=i+1}^{k}L_r+\sum_{r=k+1}^{j-1}L_r\le4\delta L_i+4\delta L_j. r = i + 1 ∑ j − 1 L r = r = i + 1 ∑ k L r + r = k + 1 ∑ j − 1 L r ≤ 4 δ L i + 4 δ L j .
The first sum is 0 0 0 if i = k i=k i = k , and is bounded by Equation (32) otherwise. The second sum is 0 0 0 if j = k + 1 j=k+1 j = k + 1 , and is bounded by Equation (33) otherwise.
In all cases, ∑ r = i + 1 j − 1 L r ≤ 4 δ ( L i + L j ) \sum_{r=i+1}^{j-1}L_r\le4\delta(L_i+L_j) ∑ r = i + 1 j − 1 L r ≤ 4 δ ( L i + L j ) . □ \square □
Proof of Lemma 4.8
Proof of Lemma 4.8. The mirror of a profile ( v s , v b ) (v_s,v_b) ( v s , v b ) is the profile ( 1 − v b , 1 − v s ) (1-v_b,1-v_s) ( 1 − v b , 1 − v s ) , in which the seller’s value is 1 − v b 1-v_b 1 − v b and the buyer’s value is 1 − v s 1-v_s 1 − v s . The mirror of the mirror is the original profile. We show that a profile and its mirror are equally likely, and that the buyer’s surplus at a profile equals the seller’s surplus at its mirror.
Equally likely. By Equation (21) , 1 − q i = q n − i 1-q_i=q_{n-i} 1 − q i = q n − i for every i i i . Since n = 2 k n=2k n = 2 k , the mirror of S ℓ S_\ell S ℓ is B k − ℓ B_{k-\ell} B k − ℓ , and the mirror of B r B_r B r is S k − r S_{k-r} S k − r . Hence, the mirror of a profile in S ℓ × B r S_\ell\times B_r S ℓ × B r is in S k − r × B k − ℓ S_{k-r}\times B_{k-\ell} S k − r × B k − ℓ . Moreover, Δ k − j = Δ j \Delta_{k-j}=\Delta_j Δ k − j = Δ j for every j j j , so
Pr [ ( v s , v b ) ∈ S ℓ × B r ] = C α ℓ β r = C R ℓ − r Δ ℓ Δ r = C α k − r β k − ℓ = Pr [ ( v s , v b ) ∈ S k − r × B k − ℓ ] . \Pr\left[(v_s,v_b)\in S_\ell\times B_r\right]=C\alpha_\ell\beta_r=C\frac{R^{\ell-r}}{\sqrt{\Delta_\ell\Delta_r}}=C\alpha_{k-r}\beta_{k-\ell}=\Pr\left[(v_s,v_b)\in S_{k-r}\times B_{k-\ell}\right]. Pr [ ( v s , v b ) ∈ S ℓ × B r ] = C α ℓ β r = C Δ ℓ Δ r R ℓ − r = C α k − r β k − ℓ = Pr [ ( v s , v b ) ∈ S k − r × B k − ℓ ] .
Since the values are uniform within these intervals, a profile and its mirror are equally likely.
Switched surpluses. The mirror maps every seller threshold s i s_i s i to the buyer threshold b n − i b_{n-i} b n − i , so a seller’s value with rounded index i i i becomes a buyer’s value with rounded index n − i n-i n − i , and vice versa. Hence, a profile and its mirror are at the same level, and since the allocation rule depends only on the level, x ( 1 − v b , 1 − v s ) = x ( v s , v b ) x(1-v_b,1-v_s)=x(v_s,v_b) x ( 1 − v b , 1 − v s ) = x ( v s , v b ) . With the payments of Lemma 4.3, the buyer’s surplus at ( v s , v b ) (v_s,v_b) ( v s , v b ) is ∫ 0 v b x ( v s , z ) d z \int_0^{v_b}x(v_s,z)\,\mathrm{d}z ∫ 0 v b x ( v s , z ) d z , and the seller’s surplus is ∫ v s 1 x ( z , v b ) d z \int_{v_s}^1x(z,v_b)\,\mathrm{d}z ∫ v s 1 x ( z , v b ) d z . Since x ( 1 − z , 1 − v s ) = x ( v s , z ) x(1-z,1-v_s)=x(v_s,z) x ( 1 − z , 1 − v s ) = x ( v s , z ) for every z z z ,
∫ 0 v b x ( v s , z ) d z = ∫ 0 v b x ( 1 − z , 1 − v s ) d z = ∫ 1 − v b 1 x ( w , 1 − v s ) d w . \int_0^{v_b}x(v_s,z)\,\mathrm{d}z=\int_0^{v_b}x(1-z,1-v_s)\,\mathrm{d}z=\int_{1-v_b}^1x(w,1-v_s)\,\mathrm{d}w. ∫ 0 v b x ( v s , z ) d z = ∫ 0 v b x ( 1 − z , 1 − v s ) d z = ∫ 1 − v b 1 x ( w , 1 − v s ) d w .
which is the seller’s surplus at the mirror profile. Since a profile and its mirror are equally likely, it follows that T S M W B B b ( F s × F b ) = T S M W B B s ( F s × F b ) \mathrm{TS}_{\mathcal{M}\mathrm{WBB}}^b(\mathcal{F}_s\times\mathcal{F}_b)=\mathrm{TS}_{\mathcal{M}\mathrm{WBB}}^s(\mathcal{F}_s\times\mathcal{F}_b) TS M WBB b ( F s × F b ) = TS M WBB s ( F s × F b ) . The two sum to T S M W B B ( F s × F b ) \mathrm{TS}_{\mathcal{M}\mathrm{WBB}}(\mathcal{F}_s\times\mathcal{F}_b) TS M WBB ( F s × F b ) , so each of them is half of it.
Proof of Lemma 4.9
Proof of Lemma 4.9 . Fix 1 ≤ i < j ≤ n 1\le i<j\le n 1 ≤ i < j ≤ n . Since every gap is δ \delta δ times the next one, L r = δ j − r L j L_r=\delta^{j-r}L_j L r = δ j − r L j for every r < j r<j r < j . Hence,
q j − 1 − q i = ∑ r = i + 1 j − 1 L r = L j ∑ r = i + 1 j − 1 δ j − r ≤ L j ∑ t = 1 ∞ δ t = δ 1 − δ L j ≤ 2 δ L j ≤ 4 δ ( q j − q i − 1 ) . q_{j-1}-q_i=\sum_{r=i+1}^{j-1}L_r=L_j\sum_{r=i+1}^{j-1}\delta^{j-r}\le L_j\sum_{t=1}^{\infty}\delta^t=\frac{\delta}{1-\delta}L_j\le2\delta L_j\le4\delta(q_j-q_{i-1}). q j − 1 − q i = r = i + 1 ∑ j − 1 L r = L j r = i + 1 ∑ j − 1 δ j − r ≤ L j t = 1 ∑ ∞ δ t = 1 − δ δ L j ≤ 2 δ L j ≤ 4 δ ( q j − q i − 1 ) .
The third equality is the sum of the geometric series, ∑ t = 1 ∞ δ t = δ 1 − δ \sum_{t=1}^{\infty}\delta^t=\frac{\delta}{1-\delta} ∑ t = 1 ∞ δ t = 1 − δ δ for 0 < δ < 1 0<\delta<1 0 < δ < 1 . The second inequality holds since δ = 1 / ( 100 n ) ≤ 1 / 2 \delta=1/(100n)\le1/2 δ = 1/ ( 100 n ) ≤ 1/2 , so 1 1 − δ ≤ 2 \frac{1}{1-\delta}\le2 1 − δ 1 ≤ 2 , and the last holds since q j − q i − 1 = ∑ r = i j L r ≥ L j q_j-q_{i-1}=\sum_{r=i}^{j}L_r\ge L_j q j − q i − 1 = ∑ r = i j L r ≥ L j .
Proof of Lemma 4.10
Proof of Lemma 4.10 . Every v s ∈ S i v_s\in S_i v s ∈ S i satisfies v s ≤ q i − 1 + η v_s\le q_{i-1}+\eta v s ≤ q i − 1 + η . Since every gap is δ \delta δ times the next one, q i − 1 = ∑ r = 1 i − 1 L r ≤ δ 2 1 − δ Δ i + 1 ≤ δ 2 1 − δ Δ i q_{i-1}=\sum_{r=1}^{i-1}L_r\le\frac{\delta^2}{1-\delta}\Delta_{i+1}\le\frac{\delta^2}{1-\delta}\Delta_i q i − 1 = ∑ r = 1 i − 1 L r ≤ 1 − δ δ 2 Δ i + 1 ≤ 1 − δ δ 2 Δ i , and by the choice of η \eta η , η ≤ δ 2 Δ i \eta\le\delta^2\Delta_i η ≤ δ 2 Δ i . Hence,
E [ v s ] ≤ ∑ i = 2 n − 2 C Δ i ( q i − 1 + η ) ≤ ( n − 3 ) C ( δ 2 1 − δ + δ 2 ) ≤ 3 ( n − 3 ) δ 2 C ≤ C . \mathbb{E}[v_s]\le\sum_{i=2}^{n-2}\frac{C}{\Delta_i}(q_{i-1}+\eta)\le(n-3)C\left(\frac{\delta^2}{1-\delta}+\delta^2\right)\le3(n-3)\delta^2C\le C. E [ v s ] ≤ i = 2 ∑ n − 2 Δ i C ( q i − 1 + η ) ≤ ( n − 3 ) C ( 1 − δ δ 2 + δ 2 ) ≤ 3 ( n − 3 ) δ 2 C ≤ C .
The first inequality holds since Pr [ ( v s , v b ) ∈ S i × B i ] = C / Δ i \Pr\left[(v_s,v_b)\in S_i\times B_i\right]=C/\Delta_i Pr [ ( v s , v b ) ∈ S i × B i ] = C / Δ i and v s ≤ q i − 1 + η v_s\le q_{i-1}+\eta v s ≤ q i − 1 + η on S i S_i S i . The second holds since, by the two bounds above, each of the n − 3 n-3 n − 3 terms satisfies q i − 1 Δ i ≤ δ 2 1 − δ \frac{q_{i-1}}{\Delta_i}\le\frac{\delta^2}{1-\delta} Δ i q i − 1 ≤ 1 − δ δ 2 and η Δ i ≤ δ 2 \frac{\eta}{\Delta_i}\le\delta^2 Δ i η ≤ δ 2 . The third holds since 1 1 − δ ≤ 2 \frac{1}{1-\delta}\le2 1 − δ 1 ≤ 2 , and the last holds since 3 ( n − 3 ) δ 2 ≤ 3 n ( 100 n ) 2 < 1 3(n-3)\delta^2\le\frac{3n}{(100n)^2}<1 3 ( n − 3 ) δ 2 ≤ ( 100 n ) 2 3 n < 1 .
Proof of Remark 4.11
Proof of Remark 4.11. For independent values, consider the proof of Theorem 4.1 . Each of the k − 1 k-1 k − 1 sets R i R_i R i , i ∈ I i\in I i ∈ I , contributes at most C C C to the first-best gains-from-trade, and the profiles outside these sets contribute at most C C C , so G F T O P T ( F s × F b ) ≤ k C \mathrm{GFT}_{\mathrm{OPT}}(\mathcal{F}_s\times\mathcal{F}_b)\le kC GFT OPT ( F s × F b ) ≤ k C . By Lemma 4.5 , T S M W B B ( F s × F b ) > ( k − 1 ) C / 4 \mathrm{TS}_{\mathcal{M}\mathrm{WBB}}(\mathcal{F}_s\times\mathcal{F}_b)>(k-1)C/4 TS M WBB ( F s × F b ) > ( k − 1 ) C /4 . Hence, the fraction is more than ( k − 1 ) / ( 4 k ) ≥ 1 / 8 (k-1)/(4k)\ge1/8 ( k − 1 ) / ( 4 k ) ≥ 1/8 , since k ≥ 2 k\ge2 k ≥ 2 .
For correlated values, consider the proof of Theorem 4.2 . Each of the n − 3 n-3 n − 3 sets R i R_i R i , i ∈ I i\in I i ∈ I , contributes at most C C C to the first-best gains-from-trade, and no other profile is in the support, so the first-best gains-from-trade is at most ( n − 3 ) C (n-3)C ( n − 3 ) C . The first-best social welfare is this quantity plus E [ v s ] \mathbb{E}[v_s] E [ v s ] , and E [ v s ] ≤ C \mathbb{E}[v_s]\le C E [ v s ] ≤ C by Lemma 4.10 , so S W O P T ( F ) ≤ ( n − 2 ) C \mathrm{SW}_{\mathrm{OPT}}(\mathcal{F})\le(n-2)C SW OPT ( F ) ≤ ( n − 2 ) C . By Lemma 4.5 , T U M W B B ( F ) ≥ T S M W B B ( F ) > ( n − 3 ) C / 4 \mathrm{TU}_{\mathcal{M}\mathrm{WBB}}(\mathcal{F})\ge\mathrm{TS}_{\mathcal{M}\mathrm{WBB}}(\mathcal{F})>(n-3)C/4 TU M WBB ( F ) ≥ TS M WBB ( F ) > ( n − 3 ) C /4 . Hence, the fraction is more than ( n − 3 ) / ( 4 ( n − 2 ) ) ≥ 1 / 8 (n-3)/(4(n-2))\ge1/8 ( n − 3 ) / ( 4 ( n − 2 )) ≥ 1/8 , since n ≥ 4 n\ge4 n ≥ 4 .
Proof of Lemma 5.3
Proof of Lemma 5.3. Let t t t , F s \mathcal{F}_s F s , F b \mathcal{F}_b F b , M \mathcal{M} M , and A A A be as in the proof of Theorem 5.1 . By Inequality (9), IR and WBB imply that x ( v s , v b ) = 0 x(v_s,v_b)=0 x ( v s , v b ) = 0 whenever v b < v s v_b<v_s v b < v s . Hence, by Equation (14) , only the profiles with v b ≥ v s v_b\ge v_s v b ≥ v s contribute to the gains-from-trade. By Equation (23), for every r ∈ [ 0 , t ] r\in[0,t] r ∈ [ 0 , t ] and v s ∈ [ 0 , t − r ] v_s\in[0,t-r] v s ∈ [ 0 , t − r ] , the density of the profile ( v s , v s + r ) (v_s,v_s+r) ( v s , v s + r ) is
f s ( v s ) ⋅ f b ( v s + r ) = λ 2 e − t e − r , (34) f_s(v_s)\cdot f_b(v_s+r)=\lambda^2 e^{-t}e^{-r}, \tag*{(34)} f s ( v s ) ⋅ f b ( v s + r ) = λ 2 e − t e − r , (34)
which depends only on its gain from trade r r r . Writing v b = v s + r v_b=v_s+r v b = v s + r and using Equation (34) ,
GFT M ( F s × F b ) = ∫ 0 t ∫ v s t ( v b − v s ) x ( v s , v b ) f s ( v s ) f b ( v b ) d v b d v s = λ 2 e − t ∫ 0 t ∫ 0 t − v s r e − r x ( v s , v s + r ) d r d v s = λ 2 e − t ∫ 0 t r e − r ∫ 0 t − r x ( v s , v s + r ) d v s d r = λ 2 e − t ∫ 0 t r e − r A ( r ) d r , \begin{aligned}
\operatorname{GFT}_{\mathcal{M}}(\mathcal{F}_s\times\mathcal{F}_b)=\int_0^t\int_{v_s}^t(v_b-v_s)x(v_s,v_b)f_s(v_s)f_b(v_b)\,\mathrm{d}v_b\,\mathrm{d}v_s \\
&=\lambda^2e^{-t}\int_0^t\int_0^{t-v_s}re^{-r}x(v_s,v_s+r)\,\mathrm{d}r\,\mathrm{d}v_s \\
&=\lambda^2e^{-t}\int_0^t re^{-r}\int_0^{t-r}x(v_s,v_s+r)\,\mathrm{d}v_s\,\mathrm{d}r
=\lambda^2e^{-t}\int_0^t re^{-r}A(r)\,\mathrm{d}r,
\end{aligned} GFT M ( F s × F b ) = ∫ 0 t ∫ v s t ( v b − v s ) x ( v s , v b ) f s ( v s ) f b ( v b ) d v b d v s = λ 2 e − t ∫ 0 t ∫ 0 t − v s r e − r x ( v s , v s + r ) d r d v s = λ 2 e − t ∫ 0 t r e − r ∫ 0 t − r x ( v s , v s + r ) d v s d r = λ 2 e − t ∫ 0 t r e − r A ( r ) d r ,
where the third equality changes the order of integration over the pairs ( v s , r ) (v_s,r) ( v s , r ) with v s , r ≥ 0 v_s,r\ge0 v s , r ≥ 0 and v s + r ≤ t v_s+r\le t v s + r ≤ t .
Proof of Lemma 5.4
Proof of Lemma 5.4. Let t t t , M \mathcal{M} M , and A A A be as in the proof of Theorem 5.1 . For every r ∈ [ 0 , t ] r\in[0,t] r ∈ [ 0 , t ] , let B ( r ) = ∫ 0 r A ( s ) d s B(r)=\int_0^r A(s)\,\mathrm{d}s B ( r ) = ∫ 0 r A ( s ) d s . We first show that, for every r ∈ [ 0 , t ] r\in[0,t] r ∈ [ 0 , t ] ,
r A ( r ) ≥ 2 B ( r ) − r 2 . (35) rA(r)\ge2B(r)-r^2. \tag*{(35)} r A ( r ) ≥ 2 B ( r ) − r 2 . (35)
Fix r ∈ [ 0 , t ] r\in[0,t] r ∈ [ 0 , t ] and v s ∈ [ 0 , t − r ] v_s\in[0,t-r] v s ∈ [ 0 , t − r ] . Applying Lemma 3.6 to the profile ( v s , v s + r ) (v_s,v_s+r) ( v s , v s + r ) and substituting z = v s + s z=v_s+s z = v s + s in both integrals gives
∫ 0 r x ( v s , v s + s ) d s + ∫ 0 r x ( v s + s , v s + r ) d s ≤ r x ( v s , v s + r ) . \int_0^r x(v_s,v_s+s)\,\mathrm{d}s+\int_0^r x(v_s+s,v_s+r)\,\mathrm{d}s\le rx(v_s,v_s+r). ∫ 0 r x ( v s , v s + s ) d s + ∫ 0 r x ( v s + s , v s + r ) d s ≤ r x ( v s , v s + r ) .
The profile ( v s , v s + s ) (v_s,v_s+s) ( v s , v s + s ) in the first integral has gain from trade s s s , and the profile ( v s + s , v s + r ) (v_s+s,v_s+r) ( v s + s , v s + r ) in the second integral has gain from trade r − s r-s r − s . Integrating over v s ∈ [ 0 , t − r ] v_s\in[0,t-r] v s ∈ [ 0 , t − r ] and changing the order of integration,
r A ( r ) ≥ ∫ 0 r ∫ 0 t − r x ( v s , v s + s ) d v s d s + ∫ 0 r ∫ 0 t − r x ( v s + s , v s + r ) d v s d s . (36) rA(r)\ge\int_0^r\int_0^{t-r}x(v_s,v_s+s)\,\mathrm{d}v_s\,\mathrm{d}s+\int_0^r\int_0^{t-r}x(v_s+s,v_s+r)\,\mathrm{d}v_s\,\mathrm{d}s. \tag*{(36)} r A ( r ) ≥ ∫ 0 r ∫ 0 t − r x ( v s , v s + s ) d v s d s + ∫ 0 r ∫ 0 t − r x ( v s + s , v s + r ) d v s d s . (36)
We compare each inner integral to A A A . Fix s ∈ [ 0 , r ] s\in[0,r] s ∈ [ 0 , r ] . The first inner integral covers the profiles with gain from trade s s s , except for the seller’s values in [ t − r , t − s ] [t-r,t-s] [ t − r , t − s ] , an interval of length r − s r-s r − s . Since x ≤ 1 x\le1 x ≤ 1 ,
∫ 0 t − r x ( v s , v s + s ) d v s ≥ A ( s ) − ( r − s ) . \int_0^{t-r}x(v_s,v_s+s)\,\mathrm{d}v_s\ge A(s)-(r-s). ∫ 0 t − r x ( v s , v s + s ) d v s ≥ A ( s ) − ( r − s ) .
For the second inner integral, substituting ℓ = v s + s \ell=v_s+s ℓ = v s + s gives
∫ 0 t − r x ( v s + s , v s + r ) d v s = ∫ s t − ( r − s ) x ( ℓ , ℓ + ( r − s ) ) d ℓ , \int_0^{t-r}x(v_s+s,v_s+r)\,\mathrm{d}v_s=\int_s^{t-(r-s)}x(\ell,\ell+(r-s))\,\mathrm{d}\ell, ∫ 0 t − r x ( v s + s , v s + r ) d v s = ∫ s t − ( r − s ) x ( ℓ , ℓ + ( r − s )) d ℓ ,
which covers the profiles with gain from trade r − s r-s r − s , except for the seller’s values in [ 0 , s ] [0,s] [ 0 , s ] , an interval of length s s s . Since x ≤ 1 x \le1 x ≤ 1 ,
∫ 0 t − r x ( v s + s , v s + r ) d v s ≥ A ( r − s ) − s . \int_{0}^{t-r} x(v_s+s,v_s+r)\,dv_s \ge A(r-s)-s. ∫ 0 t − r x ( v s + s , v s + r ) d v s ≥ A ( r − s ) − s .
Substituting both bounds into Inequality (36) gives
r A ( r ) ≥ ∫ 0 r ( A ( s ) − ( r − s ) ) d s + ∫ 0 r ( A ( r − s ) − s ) d s = 2 B ( r ) − r 2 , rA(r) \ge\int_{0}^{r}\left(A(s)-(r-s)\right)\,ds+\int_{0}^{r}\left(A(r-s)-s\right)\,ds=2B(r)-r^2, r A ( r ) ≥ ∫ 0 r ( A ( s ) − ( r − s ) ) d s + ∫ 0 r ( A ( r − s ) − s ) d s = 2 B ( r ) − r 2 ,
which proves Inequality (35) .
We now use Inequality (35) to bound B B B . Since 0 ≤ x ≤ 1 0 \le x \le1 0 ≤ x ≤ 1 , we have 0 ≤ A ( u ) ≤ t − u 0 \le A(u) \le t-u 0 ≤ A ( u ) ≤ t − u for every u ∈ [ 0 , t ] u \in[0,t] u ∈ [ 0 , t ] . Hence, the function B B B is Lipschitz, B ′ ( u ) = A ( u ) B'(u)=A(u) B ′ ( u ) = A ( u ) for almost every u u u , and
B ( t ) ≤ ∫ 0 t ( t − u ) d u = t 2 / 2. B(t)\le\int_{0}^{t}(t-u)\,du=t^2/2. B ( t ) ≤ ∫ 0 t ( t − u ) d u = t 2 /2.
Fix r ∈ ( 0 , t ] r\in(0,t] r ∈ ( 0 , t ] , and let G ( u ) = B ( u ) / u 2 G(u)=B(u)/u^2 G ( u ) = B ( u ) / u 2 for u ∈ [ r , t ] u\in[r,t] u ∈ [ r , t ] . The function G G G is Lipschitz on [ r , t ] [r,t] [ r , t ] , and for almost every u ∈ [ r , t ] u\in[r,t] u ∈ [ r , t ] , by Inequality (35) ,
G ′ ( u ) = u A ( u ) − 2 B ( u ) u 3 ≥ − u 2 u 3 = − 1 u . G'(u)=\frac{uA(u)-2B(u)}{u^3}\ge-\frac{u^2}{u^3}=-\frac{1}{u}. G ′ ( u ) = u 3 u A ( u ) − 2 B ( u ) ≥ − u 3 u 2 = − u 1 .
Integrating over [ r , t ] [r,t] [ r , t ] gives
G ( t ) − G ( r ) ≥ − ∫ r t 1 u d u = − log t r . G(t)-G(r)\ge-\int_{r}^{t}\frac{1}{u}\,du=-\log\frac{t}{r}. G ( t ) − G ( r ) ≥ − ∫ r t u 1 d u = − log r t .
Since B ( t ) ≤ t 2 / 2 B(t)\le t^2/2 B ( t ) ≤ t 2 /2 , we have G ( t ) ≤ 1 / 2 G(t)\le1/2 G ( t ) ≤ 1/2 , and therefore G ( r ) ≤ 1 2 + log t r G(r)\le\frac{1}{2}+\log\frac{t}{r} G ( r ) ≤ 2 1 + log r t . Multiplying by r 2 r^2 r 2 gives, for every r ∈ ( 0 , t ] r\in(0,t] r ∈ ( 0 , t ] ,
B ( r ) ≤ r 2 ( 1 2 + log t r ) . (37) B(r)\le r^2\left(\frac{1}{2}+\log\frac{t}{r}\right). \tag*{(37)} B ( r ) ≤ r 2 ( 2 1 + log r t ) . (37)
Finally, we use Inequality (37) to bound the integral in the lemma. Since B ( 0 ) = 0 B(0)=0 B ( 0 ) = 0 and B ′ = A B'=A B ′ = A almost everywhere, integration by parts gives
∫ 0 t r e − r A ( r ) d r = t e − t B ( t ) + ∫ 0 t ( r − 1 ) e − r B ( r ) d r . \int_{0}^{t}re^{-r}A(r)\,dr=te^{-t}B(t)+\int_{0}^{t}(r-1)e^{-r}B(r)\,dr. ∫ 0 t r e − r A ( r ) d r = t e − t B ( t ) + ∫ 0 t ( r − 1 ) e − r B ( r ) d r .
For the first term, B ( t ) ≤ t 2 / 2 B(t)\le t^2/2 B ( t ) ≤ t 2 /2 and t 3 e − t ≤ 27 e − 3 < 2 t^3e^{-t}\le27e^{-3}<2 t 3 e − t ≤ 27 e − 3 < 2 , so t e − t B ( t ) < 1 te^{-t}B(t)<1 t e − t B ( t ) < 1 . For the second term, ( r − 1 ) e − r B ( r ) ≤ 0 (r-1)e^{-r}B(r)\le0 ( r − 1 ) e − r B ( r ) ≤ 0 for r ∈ [ 0 , 1 ] r\in[0,1] r ∈ [ 0 , 1 ] , and for r ∈ [ 1 , t ] r\in[1,t] r ∈ [ 1 , t ] , Inequality (37) gives B ( r ) ≤ r 2 ( 1 2 + log t ) B(r)\le r^2\left(\frac{1}{2}+\log t\right) B ( r ) ≤ r 2 ( 2 1 + log t ) . Therefore,
∫ 0 t ( r − 1 ) e − r B ( r ) d r ≤ ( 1 2 + log t ) ∫ 1 ∞ ( r − 1 ) r 2 e − r d r = 11 e ( 1 2 + log t ) . \int_{0}^{t}(r-1)e^{-r}B(r)\,dr\le\left(\frac{1}{2}+\log t\right)\int_{1}^{\infty}(r-1)r^2e^{-r}\,dr=\frac{11}{e}\left(\frac{1}{2}+\log t\right). ∫ 0 t ( r − 1 ) e − r B ( r ) d r ≤ ( 2 1 + log t ) ∫ 1 ∞ ( r − 1 ) r 2 e − r d r = e 11 ( 2 1 + log t ) .
Combining the two bounds proves the lemma.
Proof of Lemma 5.6
Proof of Lemma 5.6. Let t t t , F s \mathcal{F}_s F s , and F b \mathcal{F}_b F b be as in the proof of Theorem 5.1 . The first-best gains-from-trade are E [ max { v b − v s , 0 } ] \mathbb{E}[\max\{v_b-v_s,0\}] E [ max { v b − v s , 0 }] , which are the gains-from-trade of the allocation that trades exactly at the profiles with v b ≥ v s v_b\ge v_s v b ≥ v s . The computation in the proof of Lemma 5.3 applies to this allocation, for which A ( r ) = t − r A(r)=t-r A ( r ) = t − r . This gives
G F T O P T ( F s × F b ) = λ 2 e − t ∫ 0 t ( t − r ) r e − r d r = λ 2 ( ( t − 2 ) e − t + ( t + 2 ) e − 2 t ) . \mathrm{GFT}_{OPT}(\mathcal{F}_s\times\mathcal{F}_b)=\lambda^2e^{-t}\int_{0}^{t}(t-r)re^{-r}\,dr=\lambda^2\left((t-2)e^{-t}+(t+2)e^{-2t}\right). GFT O P T ( F s × F b ) = λ 2 e − t ∫ 0 t ( t − r ) r e − r d r = λ 2 ( ( t − 2 ) e − t + ( t + 2 ) e − 2 t ) .
Since t ≥ 4 t\ge4 t ≥ 4 , we have t − 2 ≥ t / 2 t-2\ge t/2 t − 2 ≥ t /2 , and the inequality follows.
Proof of Lemma 5.7
Proof of Lemma 5.7. Let R R R , the grid q 0 , … , q n q_0,\ldots,q_n q 0 , … , q n , F \mathcal{F} F , and M \mathcal{M} M be as in the proof of Theorem 5.2 . Fix i ∈ [ n ] i \in[n] i ∈ [ n ] . By Equation (13) , and since q i − 1 = q i / R q_{i-1}=q_i/R q i − 1 = q i / R , the social welfare of M \mathcal{M} M at the profile ( q i − 1 , q i ) (q_{i-1},q_i) ( q i − 1 , q i ) is
q i ⋅ x ( q i − 1 , q i ) + q i − 1 ⋅ ( 1 − x ( q i − 1 , q i ) ) = q i ( 1 R + ( 1 − 1 R ) x ( q i − 1 , q i ) ) . q_i \cdot x(q_{i-1},q_i)+q_{i-1}\cdot\left(1-x(q_{i-1},q_i)\right)=q_i\left(\frac{1}{R}+\left(1-\frac{1}{R}\right)x(q_{i-1},q_i)\right). q i ⋅ x ( q i − 1 , q i ) + q i − 1 ⋅ ( 1 − x ( q i − 1 , q i ) ) = q i ( R 1 + ( 1 − R 1 ) x ( q i − 1 , q i ) ) .
Multiplying by π i = 1 / ( Z q i ) \pi_i=1/(Zq_i) π i = 1/ ( Z q i ) and summing over i ∈ [ n ] i \in[n] i ∈ [ n ] proves the lemma.
Proof of Lemma 5.8
Proof of Lemma 5.8. Let R R R , the grid q 0 , … , q n q_0,\ldots,q_n q 0 , … , q n , and M \mathcal{M} M be as in the proof of Theorem 5.2 . Recall that R = n ≥ 2 R=\sqrt{n}\ge2 R = n ≥ 2 and q i = R q i − 1 q_i=Rq_{i-1} q i = R q i − 1 for every i ∈ [ n ] i \in[n] i ∈ [ n ] . Fix j ≥ 2 j\ge2 j ≥ 2 and apply Lemma 3.6 at ( q 0 , q j ) (q_0,q_j) ( q 0 , q j ) . We use the following two lower bounds on the integrals in that lemma:
B j = ∑ r = 1 j − 1 ( q r + 1 − q r ) ⋅ x ( q 0 , q r ) , S j = ∑ i = 2 j ( q i − 1 − q i − 2 ) ⋅ x ( q i − 1 , q i ) . B_j=\sum_{r=1}^{j-1}(q_{r+1}-q_r)\cdot x(q_0,q_r),\qquad S_j=\sum_{i=2}^{j}(q_{i-1}-q_{i-2})\cdot x(q_{i-1},q_i). B j = r = 1 ∑ j − 1 ( q r + 1 − q r ) ⋅ x ( q 0 , q r ) , S j = i = 2 ∑ j ( q i − 1 − q i − 2 ) ⋅ x ( q i − 1 , q i ) .
Indeed, on [ q r , q r + 1 ] [q_r,q_{r+1}] [ q r , q r + 1 ] , monotonicity in the buyer’s value gives
x ( q 0 , z ) ≥ x ( q 0 , q r ) . x(q_0,z)\ge x(q_0,q_r). x ( q 0 , z ) ≥ x ( q 0 , q r ) .
Similarly, for i ≤ j i\le j i ≤ j and z ∈ [ q i − 2 , q i − 1 ] z\in[q_{i-2},q_{i-1}] z ∈ [ q i − 2 , q i − 1 ] , monotonicity in both reports gives
x ( z , q j ) ≥ x ( q i − 1 , q j ) ≥ x ( q i − 1 , q i ) . x(z,q_j)\ge x(q_{i-1},q_j)\ge x(q_{i-1},q_i). x ( z , q j ) ≥ x ( q i − 1 , q j ) ≥ x ( q i − 1 , q i ) .
The first inequality follows from monotonicity in the seller’s report, and the second from monotonicity in the buyer’s report. The two integrals in the weak-budget-balance allocation inequality are therefore at least B j B_j B j and S j S_j S j , respectively. Hence
B j + S j ≤ ( q j − q 0 ) ⋅ x ( q 0 , q j ) . (38) B_j+S_j\le(q_j-q_0)\cdot x(q_0,q_j). \tag*{(38)} B j + S j ≤ ( q j − q 0 ) ⋅ x ( q 0 , q j ) . (38)
For the analysis, we extend the sequence to q n + 1 = R q n q_{n+1}=Rq_n q n + 1 = R q n . By the definition of B j B_j B j ,
B j + 1 = B j + ( q j + 1 − q j ) ⋅ x ( q 0 , q j ) = B j + ( R − 1 ) q j ⋅ x ( q 0 , q j ) . \begin{aligned}
B_{j+1}&=B_j+(q_{j+1}-q_j)\cdot x(q_0,q_j)\\
&=B_j+(R-1)q_j\cdot x(q_0,q_j).
\end{aligned} B j + 1 = B j + ( q j + 1 − q j ) ⋅ x ( q 0 , q j ) = B j + ( R − 1 ) q j ⋅ x ( q 0 , q j ) .
Combining this identity with Equation (38) gives
B j + 1 q j + 1 ≥ B j R q j + R − 1 R B j + S j q j − q 0 ≥ B j q j + R − 1 R S j q j − q 0 . (39) \begin{aligned}
\frac{B_{j+1}}{q_{j+1}}&\ge\frac{B_j}{Rq_j}+\frac{R-1}{R}\frac{B_j+S_j}{q_j-q_0}\\
&\ge\frac{B_j}{q_j}+\frac{R-1}{R}\frac{S_j}{q_j-q_0}. \tag*{(39)}
\end{aligned} q j + 1 B j + 1 ≥ R q j B j + R R − 1 q j − q 0 B j + S j ≥ q j B j + R R − 1 q j − q 0 S j . (39)
For the second inequality, we used B j / ( q j − q 0 ) ≥ B j / q j B_j/(q_j-q_0)\ge B_j/q_j B j / ( q j − q 0 ) ≥ B j / q j . We now verify the claimed upper bound on the final ratio. Since every allocation probability is at most one,
B n + 1 ≤ ∑ r = 1 n ( q r + 1 − q r ) = q n + 1 − q 1 < q n + 1 . (40) B_{n+1}\le\sum_{r=1}^{n}(q_{r+1}-q_r)=q_{n+1}-q_1<q_{n+1}. \tag*{(40)} B n + 1 ≤ r = 1 ∑ n ( q r + 1 − q r ) = q n + 1 − q 1 < q n + 1 . (40)
Summing Equation (39) over j = 2 , … , n j=2,\ldots,n j = 2 , … , n gives
∑ j = 2 n B j + 1 q j + 1 ≥ ∑ j = 2 n B j q j + R − 1 R ∑ j = 2 n S j q j − q 0 . \sum_{j=2}^{n}\frac{B_{j+1}}{q_{j+1}} \ge\sum_{j=2}^{n}\frac{B_j}{q_j}+\frac{R-1}{R}\sum_{j=2}^{n}\frac{S_j}{q_j-q_0}. j = 2 ∑ n q j + 1 B j + 1 ≥ j = 2 ∑ n q j B j + R R − 1 j = 2 ∑ n q j − q 0 S j .
Canceling the common terms gives
B n + 1 q n + 1 ≥ B 2 q 2 + R − 1 R ∑ j = 2 n S j q j − q 0 ≥ R − 1 R ∑ j = 2 n S j q j − q 0 . \begin{aligned}
\frac{B_{n+1}}{q_{n+1}} \ge\frac{B_2}{q_2}+\frac{R-1}{R}\sum_{j=2}^{n}\frac{S_j}{q_j-q_0} \\
&\ge\frac{R-1}{R}\sum_{j=2}^{n}\frac{S_j}{q_j-q_0}.
\end{aligned} q n + 1 B n + 1 ≥ q 2 B 2 + R R − 1 j = 2 ∑ n q j − q 0 S j ≥ R R − 1 j = 2 ∑ n q j − q 0 S j .
where the last inequality uses B 2 ≥ 0 B_2\ge0 B 2 ≥ 0 . Together with Equation (40) , this yields
1 ≥ B n + 1 q n + 1 ≥ R − 1 R ∑ j = 2 n S j q j − q 0 . (41) 1\ge\frac{B_{n+1}}{q_{n+1}}\ge\frac{R-1}{R}\sum_{j=2}^{n}\frac{S_j}{q_j-q_0}. \tag*{(41)} 1 ≥ q n + 1 B n + 1 ≥ R R − 1 j = 2 ∑ n q j − q 0 S j . (41)
The last term in S j S_j S j is ( q j − 1 − q j − 2 ) ⋅ x ( q j − 1 , q j ) (q_{j-1}-q_{j-2})\cdot x(q_{j-1},q_j) ( q j − 1 − q j − 2 ) ⋅ x ( q j − 1 , q j ) . Since q j = q 0 R j q_j=q_0R^j q j = q 0 R j , we have
S j q j − q 0 ≥ ( q j − 1 − q j − 2 ) ⋅ x ( q j − 1 , q j ) q j = R − 1 R 2 ⋅ x ( q j − 1 , q j ) . \begin{aligned}
\frac{S_j}{q_j-q_0}\ge\frac{(q_{j-1}-q_{j-2})\cdot x(q_{j-1},q_j)}{q_j} \\
&=\frac{R-1}{R^2}\cdot x(q_{j-1},q_j).
\end{aligned} q j − q 0 S j ≥ q j ( q j − 1 − q j − 2 ) ⋅ x ( q j − 1 , q j ) = R 2 R − 1 ⋅ x ( q j − 1 , q j ) .
Substituting this bound into Equation (41) gives
∑ j = 2 n x ( q j − 1 , q j ) < R 3 ( R − 1 ) 2 ≤ 4 R , \sum_{j=2}^{n}x(q_{j-1},q_j)<\frac{R^3}{(R-1)^2}\le4R, j = 2 ∑ n x ( q j − 1 , q j ) < ( R − 1 ) 2 R 3 ≤ 4 R ,
where the last inequality uses R ≥ 2 R\ge2 R ≥ 2 . Finally, x ( q 0 , q 1 ) ≤ 1 ≤ R x(q_0,q_1)\le1\le R x ( q 0 , q 1 ) ≤ 1 ≤ R , and therefore
∑ i = 1 n x ( q i − 1 , q i ) ≤ 5 R . \sum_{i=1}^{n}x(q_{i-1},q_i)\le5R. i = 1 ∑ n x ( q i − 1 , q i ) ≤ 5 R .
Proof of Lemma 5.10
Proof of Lemma 5.10. Let R R R , the grid q 0 , … , q n q_0,\ldots,q_n q 0 , … , q n , and F \mathcal{F} F be as in the proof of Theorem 5.2 . At every profile ( q i − 1 , q i ) (q_{i-1},q_i) ( q i − 1 , q i ) in the support, the buyer’s value is larger than the seller’s value, so the first-best trades and its social welfare is q i q_i q i . Hence,
S W O P T ( F ) = ∑ i = 1 n π i q i = ∑ i = 1 n 1 Z = n Z . \mathrm{SW}_{OPT}(\mathcal{F})=\sum_{i=1}^{n}\pi_iq_i=\sum_{i=1}^{n}\frac{1}{Z}=\frac{n}{Z}. SW O P T ( F ) = i = 1 ∑ n π i q i = i = 1 ∑ n Z 1 = Z n .
From Traders' Surplus to Traders' Utility
Observation A.3. Let F \mathcal{F} F be a distribution over the buyer’s and the seller’s values such that the seller’s expected value is bounded, and let M \mathcal{M} M and M ′ \mathcal{M}' M ′ be two mechanisms with finite objectives. Then
TS M ( F ) > TS M ′ ( F ) ⟺ TU M ( F ) > TU M ′ ( F ) , \operatorname{TS}_{\mathcal{M}}(\mathcal{F}) > \operatorname{TS}_{\mathcal{M}'}(\mathcal{F}) \Longleftrightarrow\operatorname{TU}_{\mathcal{M}}(\mathcal{F}) > \operatorname{TU}_{\mathcal{M}'}(\mathcal{F}), TS M ( F ) > TS M ′ ( F ) ⟺ TU M ( F ) > TU M ′ ( F ) , GFT M ( F ) > GFT M ′ ( F ) ⟺ SW M ( F ) > SW M ′ ( F ) . \operatorname{GFT}_{\mathcal{M}}(\mathcal{F}) > \operatorname{GFT}_{\mathcal{M}'}(\mathcal{F}) \Longleftrightarrow\operatorname{SW}_{\mathcal{M}}(\mathcal{F}) > \operatorname{SW}_{\mathcal{M}'}(\mathcal{F}). GFT M ( F ) > GFT M ′ ( F ) ⟺ SW M ( F ) > SW M ′ ( F ) . Moreover, for every α ≥ 1 \alpha\ge1 α ≥ 1 ,
TU M ( F ) ≥ α ⋅ TU M ′ ( F ) ⟹ TS M ( F ) ≥ α ⋅ TS M ′ ( F ) , \operatorname{TU}_{\mathcal{M}}(\mathcal{F}) \ge\alpha\cdot\operatorname{TU}_{\mathcal{M}'}(\mathcal{F}) \Longrightarrow\operatorname{TS}_{\mathcal{M}}(\mathcal{F}) \ge\alpha\cdot\operatorname{TS}_{\mathcal{M}'}(\mathcal{F}), TU M ( F ) ≥ α ⋅ TU M ′ ( F ) ⟹ TS M ( F ) ≥ α ⋅ TS M ′ ( F ) , SW M ( F ) ≥ α ⋅ SW M ′ ( F ) ⟹ GFT M ( F ) ≥ α ⋅ GFT M ′ ( F ) . \operatorname{SW}_{\mathcal{M}}(\mathcal{F}) \ge\alpha\cdot\operatorname{SW}_{\mathcal{M}'}(\mathcal{F}) \Longrightarrow\operatorname{GFT}_{\mathcal{M}}(\mathcal{F}) \ge\alpha\cdot\operatorname{GFT}_{\mathcal{M}'}(\mathcal{F}). SW M ( F ) ≥ α ⋅ SW M ′ ( F ) ⟹ GFT M ( F ) ≥ α ⋅ GFT M ′ ( F ) .
Proof. By Equations (14) and (16) , for every mechanism M \mathcal{M} M ,
TU M ( F ) = TS M ( F ) + E ( v s , v b ) ∼ F [ v s ] , SW M ( F ) = GFT M ( F ) + E ( v s , v b ) ∼ F [ v s ] . \operatorname{TU}_{\mathcal{M}}(\mathcal{F}) = \operatorname{TS}_{\mathcal{M}}(\mathcal{F}) + \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s], \qquad\operatorname{SW}_{\mathcal{M}}(\mathcal{F}) = \operatorname{GFT}_{\mathcal{M}}(\mathcal{F}) + \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s]. TU M ( F ) = TS M ( F ) + E ( v s , v b ) ∼ F [ v s ] , SW M ( F ) = GFT M ( F ) + E ( v s , v b ) ∼ F [ v s ] .
The term E ( v s , v b ) ∼ F [ v s ] \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s] E ( v s , v b ) ∼ F [ v s ] is non-negative and does not depend on the mechanism, so the first part follows. For the second part, if TU M ( F ) ≥ α ⋅ TU M ′ ( F ) \operatorname{TU}_{\mathcal{M}}(\mathcal{F}) \ge\alpha\cdot\operatorname{TU}_{\mathcal{M}'}(\mathcal{F}) TU M ( F ) ≥ α ⋅ TU M ′ ( F ) , then TS M ( F ) ≥ α ⋅ TU M ′ ( F ) − E [ v s ] = α ⋅ TS M ′ ( F ) + ( α − 1 ) E [ v s ] ≥ α ⋅ TS M ′ ( F ) \operatorname{TS}_{\mathcal{M}}(\mathcal{F}) \ge\alpha\cdot\operatorname{TU}_{\mathcal{M}'}(\mathcal{F}) - \mathbb{E}[v_s] = \alpha\cdot\operatorname{TS}_{\mathcal{M}'}(\mathcal{F}) + (\alpha-1)\mathbb{E}[v_s] \ge\alpha\cdot\operatorname{TS}_{\mathcal{M}'}(\mathcal{F}) TS M ( F ) ≥ α ⋅ TU M ′ ( F ) − E [ v s ] = α ⋅ TS M ′ ( F ) + ( α − 1 ) E [ v s ] ≥ α ⋅ TS M ′ ( F ) , and the same holds for social welfare and gains-from-trade. Since this holds for every mechanism, for every class C \mathcal{C} C of mechanisms,
sup M ∈ C TU M ( F ) = sup M ∈ C TS M ( F ) + E ( v s , v b ) ∼ F [ v s ] , \sup_{\mathcal{M}\in\mathcal{C}} \operatorname{TU}_{\mathcal{M}}(\mathcal{F}) = \sup_{\mathcal{M}\in\mathcal{C}} \operatorname{TS}_{\mathcal{M}}(\mathcal{F}) + \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s], M ∈ C sup TU M ( F ) = M ∈ C sup TS M ( F ) + E ( v s , v b ) ∼ F [ v s ] ,
sup M ∈ C SW M ( F ) = sup M ∈ C GFT M ( F ) + E ( v s , v b ) ∼ F [ v s ] , \sup_{\mathcal{M}\in\mathcal{C}} \operatorname{SW}_{\mathcal{M}}(\mathcal{F}) = \sup_{\mathcal{M}\in\mathcal{C}} \operatorname{GFT}_{\mathcal{M}}(\mathcal{F}) + \mathbb{E}_{(v_s,v_b)\sim\mathcal{F}}[v_s], M ∈ C sup SW M ( F ) = M ∈ C sup GFT M ( F ) + E ( v s , v b ) ∼ F [ v s ] ,
so the same statements hold between the best mechanisms in two classes, such as the best WBB and SBB mechanisms.