Double Auctions in Markets for Multiple Kinds of Goods

1 Introduction

The recent auction for radio spectrum reallocation [LeytonBrown et al., 2017] has incited a surge of interest in double auction mechanisms - mechanisms for arranging trade in two-sided markets. Such markets differ from one-sided markets in that the valuations of both buyers and sellers are their private information, and both sides might act strategically.

An important requirement from a double-auction is efficiency, which is measured by its gain-from-trade (GFT) - the total value gained by the buyers minus the total value contributed by the sellers. As an example, consider a stock market with two sellers: Alice holds a unit of stock x which she values as 41 and Bob holds a unit of stock y which he values as 46. There is a single buyer, George, who wants a unit of a single stock which can be either x or y; he values x as 47 and y as 48. Then, if George buys x from Alice the GFT is 47 - 41 = 6 while if he buys y from Bob the GFT is 48 - 46 = 2. Therefore, an optimal double-auction mechanism would make the former trade. If the mechanism makes the wrong trade, it attains only 1/3 of the optimal GFT. 1

A common double-auction mechanism is the Walrasian mechanism [Rustichini et al., 1994; Babaioff et al., 2014].

1 Note that the social welfare - the sum of agents' valuations - is much easier to approximate than the GFT. E.g, in the above example, the wrong deal attains 48+41 47+46 > 95% of the optimum.

It computes an equilibrium price-vector - a price for each good, at which the supply of each good equals its demand: the total number of units that sellers want to sell at this price equals the total number of units that buyers want to buy at this price. This mechanism attains the maximum GFT [Nisan et al., 2007, Th. 11.13]. Unfortunately, it is not truthful - traders may gain by reporting false valuations.

In fact, in a two-sided market, any truthful mechanism that attains the maximum GFT cannot be budget-balanced (BB) - the market-maker has to subsidize the trade [Myerson and Satterthwaite, 1983]. Therefore, it is interesting to develop double-auction mechanisms that are truthful, BB and attain an approximately maximal GFT. We define the competitive ratio of a mechanism as the minimum ratio (over all utility profiles) of its GFT divided by the optimal GFT. The first truthful and BB approximation mechanism was presented in the seminal work of McAfee [1992]: Its competitive-ratio is 1 - 1/k, where k is the number of units traded in the optimal situation. (i.e, its GFT is always at least 1 - 1/k of the maximum GFT). Thus, McAfee's mechanism is asymptotically optimal - when the market-size k grows to infinity, the GFT approaches the maximum. Another advantage of McAfee's mechanism is that it is prior-free (PF) - it does not require any probabilistic knowledge on traders' valuations; it works even for adversarial valuations. Its main drawback is that it works only in a single-good market when each trader can trade a single unit.

Currently, as far as we know, no truthful mechanism attains asymptotic optimality in a two-sided market with multiple kinds of goods (see related work in §1.3). Recently, Segal-Halevi et al. [2018a] presented an truthful, BB, PF and asymptotically-optimal mechanism for a single-good market that allows many units per trader. It is called MUDA and is based on a random-halving scheme:

Split the market into two sub-markets, left and right, by sending each trader to each side with probability 1/2, independently of the others. Then, in each sub-market:

1. Calculate a Walrasian equilibrium price (pR at the right, pL at the left).
2. Let the traders trade at the price from the other market (pL at the right, pR at the left).

The competitive ratio of MUDA is 1-O(M √ ln k k ), where k is again the total number of units traded in the optimal situation and M is the maximum number of units per trader.

The goal of this paper is to break the single-good barrier and attain truthful, BB, PF and asymptotic optimality in a multi-good market. We show that is is possible to extend the random-halving scheme of MUDA to multi-good markets. We call the extended version MIDA - Multiple Item-kind Double Auction. However, the extension is not trivial and requires several additional assumptions, presented below.

1.1 Truthfulness in aMulti-GoodMarket

First, since step 1 of MUDA calculates Walrasian equilibria, extending it requires that a Walrasian equilibrium exists. Gul and Stacchetti [1999] prove that a sufficient condition for the existence of a Walrasian equilibrium is that all traders' valuations satisfy a condition called gross-substitute (GS).

The GS condition means that, if an agent wants to buy a good x and the price of another good y increases, the agent still wants to buy x (so the demand for good x weakly increases). A typical example of a GS market is a market for used cars: usually, people consider cars of different models to be substitutes, so when the price of one model increases, the demand for other models weakly increases.

Second, step 2 of MUDA lets traders trade in a price that is not an equilibrium price at their own market, so it must handle excess demand and supply. In a single-good market this is easy since there is excess only in one side of the market, so it can be solved using randomization. In a multi-good market this is harder since in each side we can have excess demand in some goods and excess supply in other goods.

Currently we know to solve this problem for markets in which only one of the two sides can trade multiple goods. For concreteness, we assume that the buyers can trade multiple goods while each seller sells multiple units of a single good.

Under these two assumptions, MIDA works as follows.

Halve the market randomly (like MUDA). In each half:

1. Calculate a Walrasian equilibrium price-vector - a price for each good-kind (pR at the right, pL at the left).
2. Let the traders trade at the price-vector from the other market (pL at the right, pR at the left) as follows:
3. For each good-kind x, put all the sellers of x in a queue, ordered randomly. For each x-seller, calculate the number of x-units that maximize his gain at the market price-vector; sum all these numbers to get the aggregate supply of x.
4. Put all buyers in a single queue, ordered randomly. For each buyer i in the buyers' queue, calculate the bundle that maximizes his net gain at the market price-vector, among all bundles that are contained in the aggregate supply. Let the buyer buy this bundle from the first sellers in the sellers' queues. Whenever a first seller exhausts his optimal supply, he leaves the market and the next seller in this queue becomes first.

Theorem1. Suppose each seller sells multiple units of a single good, and all traders have gross-substitute valuations. Then, MIDA is strongly budget-balanced (= has no deficit and no surplus) and truthful. Moreover, these properties hold ex-post - for every outcome of the randomization.

Proof. Strong budget-balance is obvious since all monetary transfers are between buyers and sellers. We now prove that this mechanism is truthful for every randomization outcome.

The buyers effectively play random-serial-dictatorship, which is known to be truthful. Whenever it's a buyer's turn to buy a bundle, the mechanism picks for him the best possible bundle given the available supply.

The sellers have GS valuations. Gul and Stacchetti [1999] prove that GS valuations are submodular. This means that a seller gains the highest utility from selling the first unit, a lower utility from selling the second unit, etc. Hence, for each seller there is an optimal number of units to sell in the given market-prices, and it is always optimal for a seller to sell as many units as possible up to the optimal number, then leave. This is exactly what the mechanism does for them.

Remark. (a) MIDA is truthful only for single-good sellers. Consider a seller who can sell multiple goods. For example, an additive seller who, in the market prices, gains 5 from selling x and 3 from selling y (and 8 from selling both). MIDA has to let such a seller participate simultaneously in both seller-queues. Suppose there is a single unit-demand buyer who gains 6 from buying x and 8 from buying y. If the seller reports truthfully then the buyer buys y. But the seller can strategize by claiming that he loses from selling y (i.e, standing only in the queue of x-sellers); then the buyer will be forced to buy x and the seller will gain more.

(b) MIDA is truthful only for submodular sellers. Consider a non-submodular seller. For example, a seller who values a single unit as 10 and two units as 40. If the market price is 25 per unit, then the seller gains -5 from selling a single unit ans +10 from selling two units. Suppose the first buyer in the buyers' queue wants a single unit. The best response of the seller depends on the preferences of the following buyers: if another buyer wants a unit then it is best to truthfully report a supply of 2, but if no other buyer wants a unit then it is best to untruthfully report a supply of 0.

1.2 Asymptotic Optimality in aMulti-Good Market

Asymptotic optimality means that, when the market is sufficiently large, the GFT approaches its maximum value. We have to define what is meant by "large market". The definition implied by McAfee [1992] is that k - the number of units traded in the optimal situation - approaches infinity. This definition cannot be used as-is in a multi-good market. As an extreme example, suppose the market has two independent goods x and y, where most GFT comes from trading a single unit of x, but the market-size of y approaches infinity. It is clear that the competitive ratio will not approach 1 in this case. Therefore, we extend the "large market" definition as follows. Let G be the number of different good-kinds. For any good-kind x ∈ {1, . . . ,G}, let kx be the total number of units of x traded in the optimal situation. A large market is a market where for all x, kx → ∞. To ensure that not all these units come from few large traders, we also assume that the number of units traded by a single person is bounded by a constant M (a similar assumption is used in MUDA).

Surprisingly we found out that, even in a large market, the random halving technique might attain sub-optimal GFT. This can happen when the market-size in one good is much larger than the market-size in another good. Appendix A shows a concrete example where G = 2 and M = 1 but the GFT is at most 63/64 of the maximum even if ∀x : kx → ∞.

Intuitively, The random halving process creates an imbalance in the number of traders in the two market-halves. Standard tail bounds tell us that, with high probability, the imbalance is in the order of square-root of the number of traders sampled. With one good, this imbalance is negligible as √k/k → 0 when k → ∞. However, if we have two goods x and y and √kx > ky, then the sample deviation in x might destroy all the trade in y.

The example in Appendix A is interesting, since the random-halving technique has been used successfully in various domains [Goldberg et al., 2001; 2006; Devanur et al., 2015; Balcan et al., 2008; 2007; Devanur and Hayes, 2009], and one could think it is an omnipotent technique. Our example shows the limitations of random-halving and illustrates the inherent difficulties in multi-good markets.

In contrast to this negative example, we prove that MIDA is asymptotically-optimal when the market sizes in all goods go to infinity in a similar rate. We define kmin := minx kx and kmax := maxx kx and c := kmax/kmin = the largest ratio between the market-sizes of different goods. Then:

Theorem 2. Suppose all traders have GS valuations. Then the expected competitive ratio of MIDA is at least:

where G is the number of good-kinds, M the maximum number of units of a single good traded by a single person, kmax the largest market-size of a single good, and c = kmax/kmin = the largest ratio between market-sizes.

Note that previously it was not known if asymptotic optimality is possible even with two goods (G = 2). Therefore, it is encouraging that we can get asymptotic optimality for a constant number of goods.

The assumption that c is bounded means that, as the population grows, the market-sizes in the different good-kinds grow at a similar rate. It is reasonable if we believe that the ratio between market-sizes depends on some characteristics of the population that remain approximately constant when the population grows. This is analogous to the thickness assumption introduced e.g. by Kojima and Pathak [2009] in the context of two-sided matching.

It is possible to replace c with a different parameter - h - the ratio of the largest to the smallest marginal gain from a deal in a single item. We assume that the traders' valuations are normalized such that, whenever a seller sells an item to a buyer, the marginal GFT contributed by this deal is between 1 and h. This assumption comes from the random-halving literature (e.g. Goldberg et al. [2001]). There, it is common to assume that the valuation of each buyer with positive valuation is bounded in [1, h], so that each buyer contributes at most h to the total welfare. Our definition is the natural generalization of this assumption to a two-sided market.

Theorem 3. Suppose all traders have GS valuations. Then the expected competitive ratio of MIDA is at least:

where G is the number of good-kinds, M is the maximum number of units of a single good traded by a single person, and the marginal gain from each unit traded is in [1, h].

So when M and G are bounded, and either c or h (or both) are bounded, and kmax → ∞, The GFT of MIDA approaches its maximum value.

Note that MIDA does not have to know the parameters used in Theorems 2 and 3 (M,G, c, h, kmax, etc.); they are used only in the analysis. The mechanism itself is prior-free.

Note also that Theorems 2 and 3 do not need the assumption that each seller sells a single good-kind. This assumption is needed only for the truthfulness (see Theorem 1 and the following remark).

Paper layout. Related work is surveyed below. Formal model is presented in Section 2. Theorems 2 and 3 are proved in Section 3. Section 4 discusses the limitations of our results and presents directions for future work.

1.3 RelatedWork

Mechanisms for multi-unit double auction are surveyed in Segal-Halevi et al. [2018a]. Below we survey more advanced mechanisms that handle multi-good markets.

1. Feng et al. [2012] present TAHES - Truthful doubleAuction for HEterogeneous Spectrum. The mechanism is inspired by the problem of re-allocating radio frequencyspectrum from primary owners to secondary users. In their setting, each seller (primary owner) has a single unit of a unique good-kind, each buyer (secondary user) has a different valuation for each kind, and each buyer wants a single unit. This is similar to a special case of our setting, in which all buyers have unit-demand valuations. The authors do not analyze the competitive ratio of their mechanism.
2. Blumrosen and Dobzinski [2014] present two Combinatorial Reallocation mechanisms for multi-good markets. The first one attains a competitive ratio of 1/[8 · Θ(log M)] where M is the maximum number of items per single seller, but it is not prior-free since it needs to know the median value of the initial endowment of each seller. The second one is priorfree and attains a competitive ratio of 1/48. Both competitive ratios do not approach 1.
3. Gonen et al. [2007] present a general scheme for converting a truthful mechanism with deficit to a truthful mechanism without deficit. Their scheme can handle combinatorial double auctions, but only when traders are single-valued, e.g, when each trader has a set of desired bundles and values all these bundles the same.
4. Chu and Shen [2006] present a double-auction mechanism that can handle multiple goods. However, its truthfulness depends on substitutability conditions between buyers to

buyers, sellers to sellers, and buyers to sellers. It is not clear whether these conditions hold in our setting. Moreover, they do not analyze the competitive ratio in a multi-good market.

1. Colini-Baldeschi et al. [2017b] present a combinatorial double-auction mechanism in a Bayesian setting (not priorfree). In contrast to our work, they approximate the social welfare rather than the gain-from-trade. Note that any mechanism that attains a fraction α of the optimal GFT also attains a fraction of at least α of the optimal social welfare [Brustle et al., 2017; Colini-Baldeschi et al., 2017a], but the opposite is not true. Moreover, their competitive ratios (1/4, 1/6 or 1/16) do not approach 1.
2. Gonen and Egri [2017] present a combinatorial dynamic double-auction mechanism that relies on partial prior information - the maximum and minimum values of the traders. They, too, approximate the social welfare rather than the GFT: they show by simulations that their mechanism attains about 0.5 of the maximum social welfare.
3. Hirai and Sato [2017] present a double-auction mechanism for budgeted buyers, that is Pareto-optimal and truthful for the buyers, but not truthful for the sellers.

2 Model

Traders and Valuations. We consider a market in which some traders, the "sellers", are endowed with discrete goods, and other traders, the "buyers", are endowed with unlimited money. There are G different kinds of goods and each trader can hold at most M units of each good, for some constants G and M. A bundle is a vector X ∈ {0, . . . ,M}G. The empty bundle is denoted by ∅ = (0, . . . , 0). A price-vector is a vector p = (p1, . . . , pG). The price of a bundle X is p · X.

Each trader i has a value function vi on bundles, normalized such that vi(∅) = 0. All traders' utilities are quasi-linear in money, so the net gain of a buyer i from buying a bundle X at price p is ui(X, p) = vi(X) - p · X.

For each seller j with initial endowment Ej, we define a sale-value function v′j on negative bundles: v′j (-X) := vj(Ej) - vj(Ej -X). Hence the net gain of seller j from selling a bundle X at price-vector p is uj (-X, p) = p · X - v′j (-X). Note that the gain from no trade is 0 both for a buyer and a seller: ∀i, p : ui(∅, p) = 0.

We present the gain of a trader as a sum of marginal gains, in which there is a term for each unit traded, ordered from good 1 to good G. For example, for a buyer who buys two units of good 1 and one unit of good 2, the net gain is:

We present each trader as a set of at most MG virtual traders, each of whom trades a single unit and enjoys the marginal utility of that unit (a similar idea was used by Chawla et al. [2010]). So the above buyer represents three virtual buyers: the first buys good 1 and gains ui([1, 0], p), the second buys good 1 and gains ui([2, 0], p) - ui([1, 0], p), and the third buys good 2 and gains ui([2, 1], p) - ui([2, 0], p).

Demand and Supply. We assume that traders' valuations are generic, i.e, values of different bundles and of different traders are different and linearly-independent over the integers (no linear combination with integer coefficients equals zero). This assumption guarantees that, given a price-vector pR determined in the right market, every trader i in the left market has a unique bundle that maximizes ui(·, p), and vice versa. 2 We call this maximizing bundle the demand of i at p. If i is a seller then his demand is a weakly-negative vector; we call the absolute value of this vector the supply of i at p.

Gross Substitutes. We assume that all traders' valuations are gross-substitute (GS); see Kelso and Crawford [1982] and [Gul and Stacchetti, 1999] for formal definitions. Intuitively, GS means that there are no complementarities between different items, so that when the price of a single unit of a single good increases, the demands for the other units and the other goods do not decrease. For example, suppose at price-vector p the demand of some buyer is [2, 1], e.g, two units of good x and one unit of good y. Suppose that the price of the first unit of x increases while the prices of the other units remain fixed. GS means that the buyer will still want to buy at least one unit of x and one unit of y.

When all traders have GS valuations, a Walrasian equilibrium exists and can be found efficiently using an ascending auction [Gul and Stacchetti, 2000; Ben-Zwi et al., 2013]. Intuitively, the GS property guarantees that the auctioneer can increase the prices of over-demanded items, without creating a demand-shortage in other items, until the market converges to an equilibrium.

GS valuations are always submodular; see Gul and Stacchetti [1999] for a formal definition and a proof. Intuitively, submodularity means that, if a trader loses some deals, its marginal gain from the other deals weakly increases. For example, if the buyer from above arrives at the head of the buyers' queue when only one unit of good 1 is available for sale, then its gain from this unit will be ui([1, 0], p) which is at least as large as ui([2, 0], p) -ui([1, 0], p), and its additional gain from the unit of good 2 will be ui([1, 1], p)-ui([1, 0], p) which is at least as large as ui([2, 1], p) - ui([2, 0], p).

Mechanisms. Amechanism is a (randomized) function that takes the traders' valuations and returns (1) a price-vector p, (2) for each buyer(seller) i, the bundle Xi to buy(sell) at p. A mechanism is materially-balanced if for each good, the number of units bought equals the number of units sold: ∑i∈Buyers Xi = ∑j∈Sellers Xj .

A mechanism is ex-post truthful, if a trader can never increase his gain by pretending to have different valuations, even when the trader knows in advance the outcomes of all randomizations done by the mechanism.

Given a trading scenario in which each trader i buys/sells a bundle Xi, the gain-from-trade (GFT) is the sum of gains of

2 The genericity assumption can be dropped by using centralized tie-breaking, i.e, whenever a trader has two or more demands, the market-manager may select one of them in a way that maximizes GFT. See Hsu et al. [2016] for other ways to handle ties in markets.

In a materially-balanced setting, the GFT does not depend on the price-vector, since the prices are canceled in the summation; money is only transferred between buyers and sellers.

3 Competitive-Ratio Analysis

For truthfulness we had to assume that, in one side of the market, each trader specializes in a single good. In the present section we do not need this assumption - both buyers and sellers can trade multiple goods and are entirely symmetric. We first analyze the optimal trade, then the right sub-market and finally the left sub-market.

3.1 Optimal Trade

By the gross-substitute assumption, there exists a Walrasian equilibrium in the global population, and it attains the maximum GFT (see Section 2). By the genericity assumption, the equilibrium allocation is unique. We call it the "optimal trade" and denote any equilibrium price-vector by pO.

For any good x ∈ {1, . . . , G}, denote by Bx∗ the set of virtual buyers and by Sx∗ the set of virtual sellers participating in the optimal trade. By definition of equilibrium, the numbers of virtual-traders in both groups are the same; this is the number we denoted by kx:

We call these virtual traders the efficient traders. We make the pessimistic assumption that all GFT in the sub-markets comes only from these efficient traders. Therefore, the GFT of our mechanism depends on the numbers of efficient traders that trade in each sub-market.

The reduction in GFT has two reasons: one is the sampling error - efficient buyers and sellers land in different sub-markets, so they do not meet and cannot trade. This error is easy to bound using standard tail inequalities. The second reason is the pricing error - the prices at the sub-market might be too high or too low, which might create imbalance in the demand and supply. Analyzing this error requires careful analysis of the equilibrium in the optimal situation vs. the equilibrium in each sub-market.

3.2 Right Sub-Market

In the right, we calculate an equilibrium price-vector pR. For each good x ∈ {1, . . . , G}, define the sets of virtual-traders:

• Bx- is the set of efficient virtual buyers of x (members of Bx∗ ) who do not demand x at pR.
• Sx- is the set of efficient virtual-sellers (members of Sx∗ ) who do not supply x at pR.
• B+x is the set of inefficient virtual-buyers (not members of Bx∗ ) who demand x at pR.
• S+x is the set of inefficient virtual-sellers (not members of Sx∗ ) who supply x at pR.

3 In some papers, the gain-for-trade is termed trader surplus or price improvement [Chakraborty et al., 2015].

We denote D+x := B+x ∪ Sx- and Dx- := Bx- ∪ S+x . These sets D+x ,Dx- represent the pricing error - they are responsible for the loss of welfare due to efficient traders quitting or inefficient traders competing with the efficient ones. The goal of our analysis below is to bound the sizes of the sets Dx- and D+x .

For any set T of traders, denote by T R the subset of T that is sampled to the right market and by T L the subset of T sampled to the left market. By definition of the equilibrium price-vector pR, for every good x:

In order to relate (1) and (2), we have to relate BR x∗ , SR x∗ to Bx∗ , Sx∗ . This is be done using the following lemma.

Lemma. For every set T of virtual-traders and integer q > 0

("w.p. x" is a shorthand to "with probability at least x").

The lemma is proved using Hoeffding's inequality. The proof is standard and we omit it.

We apply this lemma 2G times, to Bx∗ and Sx∗ for each x ∈ {1, . . . ,G}, and combine the outcomes using the union bound. This gives, ∀q > 0:

Combining equations 1, 2 and 4 gives, ∀q > 0:

Our goal now is to get a bound on |D+x |, |Dx-|. We proceed in several steps.

Step A: From Bound on Difference to Bound on Sets. Below we fix some q > 0 and assume that the suffix of inequality (5) holds. This gives us an upper bound on ∣∣|DR x-| - |DR +x |∣∣. We need upper bounds on |DR x-| and |DR +x |. To get it, we use a property of GS valuations called Downward Demand Flow (DDF) [Segal-Halevi et al., 2016]. Consider two price-vectors pO and pR, and let ∆ := pR - pO = the vector of price-increases. Intuitively, DDF means that a trader's demand goes down the price-change ladder - a trader switches from demanding good x at price pO to demanding good y at price pR, only if ∆x > ∆y.

Lemma (DDF Lemma, Segal-Halevi et al. [2016]). Every trader with gross-substitute valuations has the following property. Whenever the price-vector changes from pO to pR, the trader's demand changes in the following way.

(1) If the trader stopped demanding some good x with ∆x ≤ 0, then he started demanding a good y with ∆y < ∆x. (2) If the trader started demanding some good x with ∆x ≥ 0, then he stopped demanding a good y with ∆y > ∆x.

By combining the DDF lemma and (5), we can prove:

The proof is in the full version [Segal-Halevi et al., 2018b].

Step B: From a Bound on Sampled Sets to a Bound on Their Parent Sets. Our goal is now to derive from (6) an upper bound on |Dx-| and |D+x | - the number of virtual traders that change their demand or supply due to the pricing error. These two sets are entirely analogous; we focus on Dx-. First, we derive from (3) the following, by substituting q → |T |/4:

We would like to apply (7) to Dx- and conclude that |Dx-| < 2G4q. But we cannot do so directly since Dx- is a random-set - it depends on the random-sampling through pR - while T in (7) must be a deterministic set - independent of the random-sampling. Our solution is to use the union bound. Let Eq be the set of all possible values of Dxwith cardinality 2G4q (so Eq is a set of sets of virtual traders). We apply (7) simultaneously to all sets in Eq using the union bound. We get, for every integer q:

The same arguments are true for D+x and for every good x ∈ {1, . . . , G}. Combining this with (6) gives, for every q:

Step C: Bounding the Number of Possible Sets. Our goal now is to find an upper bound on |Eq|. In fact, we will bound |E| - the number of possible values of Dx-, regardless of their cardinality. Initially, we bound |E| as a function of n - the total number of real traders that come to the auction. Then, we replace n by a function of kmax.

We present the set Dx- as a function of simpler sets. For every two bundles Y and Z, denote by RY≻Z the set of traders who, at price-vector pR, prefer bundle Y to bundle Z. RY≻Z is a one dimensional random set: it contains all the traders i for whom:

Therefore, for every integer t ∈ {1, . . . , n}, there is exactly one possible value of RY≻Z with cardinality t - it is the set of t traders for whom the difference vi(Y ) - vi(Z) is the highest among all n traders. Therefore the random set RY ≻Z has n possible values. The total number of sets RY≻Z is at most the number of bundle-pairs, which is at most (M G)2 = M 2G. Hence there are at most nM2G ways to choose these sets. Once all the sets RY≻Z are determined, the set Dx- is completely determined too. Therefore:

We now want to replace n by an expression that depends only on kmax. The reason is that n - the total number of traders in the market -might be very large: in theory, every person on Earth might come to the auction as a "trader" without buying or selling anything. Therefore, we cannot hope to get any meaningful approximation factor based on n. Indeed, the approximation factors in the prior-free double-auction literature since McAfee [1992] are given as a function of the number of optimal deals (k), which is a better indicator of the actual market size.

Define a relevant trader as a trader who trades at least one unit of at least one good in at least one price-vector - pO or pR. Our arguments for bounding |E| clearly hold when we use the number of relevant traders instead of n. We will now prove that, with high probability, the number of relevant traders is at most n′ , where n′ := 10Gkmax. Then we will use this bound in (9) and get that |E| < (n′ )M2G .

Lemma. w.p. 1-2 exp ( -2G2 kmax ln (8Gkmax) M2 ), the number of relevant traders is at most 10Gkmax.

Proof. [Proof sketch] By definition, the number of traders who want to trade at pO is at most 2Gkmax. It remains to count the traders who trade nothing at pO, but want to trade something at pR. Let D0 be the set of these traders.

Using the DDF lemma, we can prove that their number in the right market is at most the number of traders who want to trade at pO, so |DR 0 | ≤ 2Gkmax. From this we can infer that:

so the total number of relevant traders is at most 10Gkmax = n′ . The proof details are deferred to the full version [SegalHalevi et al., 2018b].

Substituting n → n′ in (9) and (9) in (8) gives the failure probability:

Denote this probability by PF(q). So by (8), w.p. 1-PF(q):

3.3 Left Sub-Market

For every good x, the set of efficient virtual-buyers in the left market is BL x∗ = Bx∗ \ BR x∗ . All these virtual-buyers want to trade at price pO; all the virtual-buyers who are not in Bxwant to trade at price pR too. Therefore, the set of efficient buyers who are sampled to the left market and want to trade at the price-vector posted for the left market is: Bx∗ \ BR x∗ \ Bx-. Some of these buyers might be "wasted" by trading with inefficient virtual-sellers; the set of inefficient virtualsellers who want to trade x at price pR is S+x . All in all, the number of efficient virtual-buyers in the left submarket who want to trade at price pR and are not wasted on inefficient sellers is at least:

Similarly, the number of efficient virtual-sellers who want to trade at pR and are not wasted on inefficient buyers is at least:

By inequalities (4) and (8) from the previous subsection, we have for every integer q, with probability 1 - PF(q):

Thus, in the left market, at least kx/2 - q - 2G4q efficient deals in good x are done. The same analysis is true in the right market. Therefore, the total number of efficient deals in x done in all submarkets is at least kx-2q-2G8q ≥ kx-2G9q. From here we proceed to prove Theorems 2, 3.

ApproximationBased on c. By the randomordering of the traders in each market, the kx - 2G9q efficient deals executed in the sub-markets are chosen at random from the set of kx efficient deals. The same is true for every good-kind x. We recall that, by submodularity, if a virtual-trader loses a deal, then the marginal-gain of other virtual-traders of the same real-trader do not decrease. Hence, with probability 1-PF(q), the expected competitive ratio is at least 1- 2G9q kmin .

• Hence, with probability 1, the expected competitive ratio is at

All our analysis so far holds simultaneously for every integer q. Now we substitute q = M2G+2 2G-1 · lnn · √kmax. The competitive ratio becomes:

We now substitute n′ → 10Gkmax and kmin → kmax/c. The latter three expressions are clearly in o(1/kmax). Therefore MIDA's competitive ratio is at least as claimed in Theorem 2:

Approximation Based on h. Recall that in each good-kind x, w.p. 1 -PF(q), at most 2G9q deals are lost. By assumption, each deal contributes to the GFT at most h. Therefore, the total loss of GFT in all goods together is at most 2G9qGh. On the other hand, by assumption, each deal contributes to the GFT at least 1. Therefore, the optimal GFT in all goods together is at least kmax. Hence, w.p. 1 -PF(q), the relative loss of GFT is at most 2G9qGh kmax . Hence, w.p. 1, the expected competitive ratio is at least 1- 2G9qGh kmax -PF(q). This is exactly the same expression as in the previous paragraph, except that the 1 kmin in the denominator is replaced by Gh kmax . Therefore, by the same analysis as above we get that the expected competitive ratio is at least as claimed in Theorem 3:

4 Limitations and FutureWork

Our goal in this work was to prove that truthful asymptotic optimality is theoretically possible even with multiple kinds of goods. While we proved this possibility, our work has several limitations that should be handled in future work.

1. MIDA requires that agents have gross-substitute valuations. We do not know how to handle agents with more general valuations, e.g, submodular. The main problem is that a Walrasian equilibrium might not exist, so we cannot use prices from one market to control trade in the other market.
2. MIDA's truthfulness (Theorem 1) requires that in one side of the market (e.g. the seller side), each trader specializes in a single good-kind. We do not know how to handle markets where both sides trade multiple good-kinds. The impossibility result in Segal-Halevi and Hassidim [2017] implies that this might be a hard problem even when the prices are fixed exogenously.
3. MIDA's asymptotic optimality (Theorems 2,3) requires that either the parameter c or the parameter h (or both) are bounded. Even with these assumptions, the competitive ratio guarantee becomes positive only for a very large market. E.g, with M = 2,G = 2, c = 1, where the market-size in both goods is k, Theorem 2 guarantees 1 - 1152 · ln (20k) √k , which becomes positive only for k ≈ 750, 000, 000.

Often, the real-life performance of a mechanism is much better than its theoretical worst-case guarantee. This was shown empirically for MUDA [Segal-Halevi et al., 2018a] and we believe this should be the case for MIDA as well. However, currently it is very difficult to find data on multigood two-sided markets, since even the user-interface of such markets (e.g. in stock exchanges) usually accepts only singlegood inputs. We hope that, once multi-good double-auction mechanisms become available, two-sided markets will allow multi-good inputs, which will then enable empirical research.

A Failure of RandomHalving

This Appendix shows that the common random-markethalving technique might fail to attain an asymptoticallyoptimal gain-from-trade. In the example, there is a twogood market where the numbers of traders are parametrized by k. With constant probability (independent of k), randomhalving loses almost all the gain-from-trade even when k → ∞. Hence, the competitive ratio does not approach 1 even when the market-sizes in both goods approach ∞.

We consider a market for medications. There are two goods (medications) denoted y and x:

• Good y is a medication for headache. It is produced by a group Syy of 2k4 sellers who value it as ≈ 1. More precisely, the valuation of seller i in this subset is 1 + i/k5 , for i ∈ {1, . . . , |Syy|}.
• Good x is a strong medication that can cure both headache and a much more lethal disease. It is produced by a group Sx∅ of 2k sellers, each of whom produces a single unit and values it as ≈ 6: the valuation of seller i in this subset is 6 + i/k5 , for i ∈ {1, . . . , |Sx∅|}.

The groups of sellers are disjoint so all sellers are single-good and single-unit. There are three groups of buyers (patients).

• Byy is a large group of headache patients, each of whom wants a unit of y and values it as 9.
• Bxx contains a single patient who has the lethal disease and must get x; he values it very highly - k100 .
• Bxy is a group of patients with a mild disease that can be cured by both x and y; each of them wants a single unit of either x or y and values it as 9.

The valuations and numbers are summarized in Table 1. The first three columns show the trader sets and their valuations. The next two columns show the total number of traders in each group, and what they do in an optimal equilibrium. All sellers sell and all buyers buy; to balance the number of deals in x, all the Bxy buyers buy x. The number of efficient deals in both good-kinds is an increasing function of k.

The next two columns show the number of traders from each group sampled to each sub-market. Here, the dj are random variables and the only thing we require about them is that dj ≥ 0. The probability of getting such a sample approaches a constant independent of k:

• The probability that in Byy at least half the members fall in the left market (d1 ≥ 0) is 1/2; similarly for Bxy, Sx∅.
• The probability that the member of Bxx falls in the left market is 1/2.
• The probability that in Syy at least k4 + k members fall in the right market is less than 1/2; however, because k ≪ √2k4 , this probability converges to 1/2 as k → ∞.

Additionally, we require that lowest-valued seller in Sx∅ - the seller with value 6 + 1/k5 - falls in the right market. The probability for this is 1/2. All in all, the probability of having such a sample converges to 1/64 as k →∞.

We now calculate the equilibrium price-vector pR.

• The number of y-sellers is higher than the total number of potential x-buyers. Therefore, pRy must be near 1, so that the higher-valued sellers from Syy do not sell.
• If pRx is below 6 then no sellers from Sx∅ want to sell x; if pRx is at least 6 then no buyers fromBxy want to buy x (they prefer y). In both cases, no units of x are traded in the right market. Therefore pRx is at most the value of the lowest-valued seller in the right, which is 6 + 1/k5 (in fact, pRx can be any number between pRy and 6+1/k5 ).

When pR is applied in the left market, the price of x is too low for the Sx∅ sellers so they do not sell at all. The supply of x is 0 and the Bxx patient cannot buy the strong medication. Almost all welfare is lost. Since this happens with probability ≈ 1/64, the competitive ratio is at most ≈ 63/64 - it does not approach 1.

This disaster cannot happen in any of the following cases.

• It cannot happen when the ratio between the marketsizes of the two goods is bounded by some constant c. In this case, the probability that the sampling-error in Syy is of the same order-of-magnitude as Bxy approaches 0 as k →∞. This is consistent with our Theorem 2.
• It cannot happen when the welfare contributed by a single agent is bounded by some constant h. In this case, the relative loss of welfare in the sampling scenario above is h/Ω(k), which approaches 0 as k → ∞. This is consistent with our Theorem 3.
• It cannot happen with single good-kind, even when most welfare comes from a single buyer. In this case, as long as k (the number of efficient deals) is sufficiently large, there will be sufficiently many sellers willing to sell the item in a price that the important buyer is willing to pay. This is consistent with Segal-Halevi et al. [2018a].