--- title: "Approximately Maximizing the Broker's Profit in a Two-sided Market" authors: - "Jing Chen" - "Bo Li" - "Yingkai Li" doi: "10.24963/ijcai.2019/22" url: "https://ijcai.org/proceedings/2019/22" pdf: "https://ijcai.org/proceedings/2019/0022.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "151-157" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" - "Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems" --- # Approximately Maximizing the Broker's Profit in a Two-sided Market Jing Chen, Bo Li, Yingkai Li *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 151-157. DOI: [10.24963/ijcai.2019/22](https://doi.org/10.24963/ijcai.2019/22) ## Abstract We study how to maximize the broker's (expected) profit in a two-sided market, where she buys items from a set of sellers and resells them to a set of buyers. Each seller has a single item to sell and holds a private value on her item, and each buyer has a valuation function over the bundles of the sellers' items. We consider the Bayesian setting where the agents' values/valuations are independently drawn from prior distributions, and aim at designing dominant-strategy incentive-compatible (DSIC) mechanisms that are approximately optimal. Production-cost markets, where each item has a publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we show how to covert a mechanism for production-cost markets into a mechanism for the broker, whenever the former satisfies cost-monotonicity. This reduction holds even when buyers have general combinatorial valuation functions. When the buyers' valuations are additive, we generalize an existing mechanism to production-cost markets in an approximation-preserving way. We then show that the resulting mechanism is cost-monotone and thus can be converted into an 8-approximation mechanism for two-sided markets. ## Full text ## 1 Introduction Two-sided markets are widely studied in economics [Myerson and Satterthwaite, 1983; McAfee, 1992; McAfee, 2008], where a number of buyers and a number of sellers are connected by an intermediary, such as antique markets, used-car markets, and pre-owned house markets. Here each seller has a single item to trade for money and holds a private value for her item, while each buyer's private information is a combinatorial valuation over the bundles of the sellers' items. A common feature in these situations is that the intermediary keeps the difference between the payments made by the buyers and the payments made to the sellers -that is, the intermediary's profit. We call such an intermediary a broker. The objective of the broker is to acquire the items from the sellers and resell them to the buyers to maximize her profit. The problem studied in our paper is to design the mechanism in the two-sided market that maximize the broker's profit. For convenience, we refer to the sub-market between the sellers and the broker the seller-side market and to the sub-market between the broker and the buyers the buyer-side market. If the broker had all the items, then we would only have the buyer-side market, which is an auction where the broker tries to maximize her revenue. Auctions have been well studied in the literature following the seminal work of Myerson [Myerson, 1981]. In Section 1.2, we will briefly recall the most relevant literature on auctions. If the broker would keep the items, then we only have the seller-side market, which is a procurement game. Budget feasible procurement has been studied by many in the Algorithmic Game Theory literature [Singer, 2010; Dobzinski et al., 2011; Chen et al., 2011; Chan and Chen, 2014]. The broker wants to maximize her value for the items she buys, subject to a budget constraint. Although auctions and procurements are closely related to the broker's problem, they cannot be dealt with separately in two-sided markets. Indeed, the difficulty of the broker's problem is to simultaneously and truthfully elicit both the sellers' and the buyers' valuations, so as to generate a good profit. ## 1.1 Main Results and Techniques In this paper we assume the values of the sellers and buyers are independently distributed, and we study simple dominantstrategy incentive compatible (DSIC) mechanisms. To approximately maximize the (expected) profit of the broker, we first develop a reduction, through which we can directly convert mechanisms for production-cost markets into mechanisms for two-sided markets. In a production-cost market, the broker is able to produce all the items, each item has a cost to be produced and the costs are publicly known. Roughly speaking, we say a mechanism for production-cost markets is cost-monotone if, when the cost of an item increases, the likelihood that it is sold does not increase. We show that any cost-monotone mechanism for production-cost markets can be converted into a mechanism for two-sided markets via a black-box approach. This reduction holds for general combinatorial valuation functions of buyers. Theorem 1 (Informal). Any cost-monotone DSIC mechanism that is an α-approximation for production-cost markets, can be converted into a DSIC mechanism that is an αapproximation for two-sided markets. Next, we use cost-monotonicity as a guideline in constructing concrete mechanisms for two-sided markets. When the buyers have additive valuations, we generalize the duality framework of [Cai et al., 2016] and the mechanism there to design a cost-monotone mechanism for production-cost markets. Following our reduction, we immediately obtain a mechanism for two-sided markets. Theorem 3 (Informal). When the buyers have additive valuations, there exists a DSIC mechanism for two-sided markets which is an 8-approximation to the optimal profit. ## 1.2 RelatedWork Bayesian auctions have been extensively studied since the seminal work of [Myerson, 1981]. For single-parameter settings, Myerson's mechanism is optimal. The problem becomes more complicated in multi-parameter settings [Hart and Nisan, 2017]. Although optimal Bayesian incentivecompatible (BIC) mechanisms have been characterized [Cai et al., 2012b; Cai et al., 2012a], they are too complex to be practical. Also, optimal DSIC mechanisms remain unknown. Thus simple DSIC mechanisms that are approximately optimal have been studied, such as [Kleinberg and Weinberg, 2012; Yao, 2015; Cai et al., 2016] Two-sided markets are also called double auctions [McAfee, 1992], bilateral trading [Myerson and Satterthwaite, 1983] or market intermediation [Jain and Wilkens, 2012] in the literature. Maximizing the broker's profit is an important objective for two-sided market. The seminal paper [Myerson and Satterthwaite, 1983] characterized the optimal mechanism for one seller and one buyer, which is further generalized by [Deng et al., 2014] to multiple single-parameter sellers and buyers. Unlike our work, [Deng et al., 2014] studies the Bayesian Incentive Compatible (BIC) mechanisms. DSIC mechanisms are also studied in the literature, but only for some special cases: [Jain and Wilkens, 2012] studies the case of a single buyer and multiple sellers, [Balseiro et al., 2019] studies the case of a single seller and multiple buyers, and [Gerstgrasser et al., 2016] studies the optimal mechanism when the numbers of sellers and buyers are both constants. Although [Chan and Chen, 2016] studies two-sided markets with multiple buyers and multiple sellers, the dealer there has a fixed budget and their mechanism guarantees that the payment to sellers is within the budget. Before our work, it remained unknown how to design a (simple) DSIC mechanism that approximates the optimal profit in multi-parameter settings with a general number of sellers and buyers. Finally, we briefly discuss the efficiency of two-sided markets, which is measured by gain-from-trade (GFT), i.e., the total value gained by the buyers minus the value contributed by the sellers. [McAfee, 1992] gave the first approximation mechanism for the one seller and one buyer case, and [Brustle et al., 2017] gives approximation mechanisms for multiple buyers with unit demand valuations. Recently, [SegalHalevi et al., 2018a] and [Segal-Halevi et al., 2018b] study the asymptotically efficient mechanisms instead of constant approximations. For maximizing social welfare, [ColiniBaldeschi et al., 2016; Colini-Baldeschi et al., 2017] provide constant-approximation mechanisms. ## 2 Preliminaries A two-sided market includes a set M of m sellers, and a set N of n buyers. We consider the setting where each seller j has one item j to sell, so we may refer to items and sellers interchangeably. The total payment made by the buyers is the broker's revenue, and her profit is the revenue minus the total payment to the sellers. Each buyer i has valuation vB i : 2M → R+ ∪ {0} with vB i (∅) = 0. The function vB i is monotone: for any T ⊆ S ⊆ M, vB i (T) ≤ vB i (S). In our reduction between productioncost and two-sided markets, we consider combinatorial valuations and do not impose any restriction on vB i . Each function vB i is independently drawn from a distribution DB i over the set of all possible valuation functions, with density function f B i and cumulative probability F B i . Let DB = ×i∈NDB i , f B = ×i∈Nf B i and F B = ×i∈NF B i . Each seller j's value on her item, vS j ∈ R+ ∪{0}, is independently drawn from a distribution DS j , with density function f S j and cumulative probability F S j . Let DS = ×j∈MDS j , f S = ×j∈Mf S j and F S = ×j∈MF S j . Let the supports of distributions DB i and DS j be T B i and T S j , respectively. T B i and T S j are called the valuation spaces of buyer i and seller j. Let T B = ×i∈NT B i and T S = ×j∈MT S j . Finally, denote by I = (N,M,DB ,DS ) a two-sided market instance. A mechanismM for two-sided markets is represented by (xB , xS , pB , pS ). Given a valuation profile (vB , vS ), - xB (vB , vS ) = (xBi (vB , vS ))i∈N is the allocation of the buyers, where xBi (vB , vS ) = (xBiA(vB , vS ))A⊆M with xBiA(vB , vS ) ∈ [0, 1], representing the probability that buyer i gets the item set A, under valuation profile vB and vS . Moreover, ∑A xBiA(vB , vS ) = 1. - xS (vB , vS ) = (xSj (vB , vS ))j∈M is the allocation of the sellers with xSj (vB , vS ) ∈ [0, 1], representing the probability that seller j's item is sold under (vB , vS ). - pB (vB , vS ) = (pBi (vB , vS ))i∈N is the payment made by the buyers, where pBi (vB , vS ) ∈ R+ ∪ {0}. - pS (vB , vS ) = (pSj (vB , vS ))j∈M is the payment made to the sellers, where pSj (vB , vS ) ∈ R+ ∪ {0}. A feasible mechanismM is such that for any item j ∈ M and any valuation profile (vB , vS ). In principle, the above condition may allow a mechanism to sell an item that it didn't buy or to buy an item without selling it. However, these cases never happen in the mechanisms in this paper. 1 The expected profit PFT(M; I) of mechanismM for instance I is 1 Note that our feasibility constraint only requires "feasible in expectation" which is weaker than ex post feasibility. All of our results still hold if we change the requirement to be ex post feasible. The utilities of the agents are quasi-linear. That is, for each buyer i, for any valuation subprofile vB -i of the buyers and any valuation profile vS of the sellers, when i reports her true valuation function vB i , her utility under mechanismMis For each seller j, for any valuation subprofile vS-j and vB , when j reports her true value vS j , her utility is MechanismM is dominant-strategy incentive-compatible (DSIC) if: (1) for any buyer i, vB -i , vS , and vB i , v′B i , and (2) for any seller j, vS-j , vB and vS j , v′S j , MechanismM is individually rational (IR) if: (1) for any buyer i, vB i , vB -i and vS , uBi (vB i ;M, vB -i , vS ) ≥ 0; and (2) for any seller j, vS j , vS-j and vB , uSj (vS j ;M, vS-j , vB ) ≥ 0. Mechanism M is Bayesian incentive-compatible (BIC) if (1) for any buyer i and valuation functions vB i , v′B i , and (2) for any seller j and values vS j , v′S j , MechanismM is Bayesian individually rational (BIR) if (1) for any buyer i and valuation function vB i , uBi (vB i ;M) ≥ 0; and (2) for any seller j and value vS j , uSj (vS j ;M) ≥ 0. Finally, we denote by OPT(I) the (expected) profit generated by the optimal DSIC mechanism for instance I. A special case of two-sided markets is production-cost markets, where the broker can produce the items by himself and each item j ∈ M has a publicly known production cost cj ∈ R+ ∪ {0}. Therefore we do not need to consider the sellers' incentives. Letting c = (cj)j∈M, we use I c = (N,M,DB , c) to denote a production-cost market instance and Mc = (xB , pB ) a production-cost market mechanism, where the input of xB and pB is the buyers' valuation profile. Then the broker's profit is the revenue minus the total production cost PFT(Mc ; I c ), which is Auctions are production-cost markets with cost 0. We use I a = (N,M,DB ) to denote an auction instance and Ma = (xB , pB ) an mechanism. The expected revenue is PFT(Ma ; I a ) = EvB ∼DB ∑i∈N pBi (vB ). When there is no ambiguity, the superscript B is omitted in auctions and production-cost markets. In Section 4, we will consider additive valuations for the buyers. In this case, for any buyer i, there exists a valuation vector (vB ij )j∈M such that vB ij = vB ({j}) is i's value on each item j. Then, vB i is additive if vB i (A) = ∑j∈A vB ij for any A ⊆ M. To simplify the notation, in this case we use vB i to denote the vector (vB ij )j∈M instead of the corresponding function. Each vB ij is independently drawn from a distribution DB ij , and DB i = ×j∈MDB ij . Finally, when buyers have additive valuations, their allocation is simplified as xB (vB , vS ) = (xBi (vB , vS ))i∈N, where xBi (vB , vS ) = (xBij (vB , vS ))j∈M with xBij (vB , vS ) ∈ [0, 1], representing the probability that buyer i gets the item j, when the valuations are vB and vS . ## 3 AReduction fromTwo-sidedMarkets to Production-cost Markets Note that the sellers are single-parameter in the two-sided markets under consideration. Thus, each seller is truthful in a mechanism if and only if the selling probability of her item is non-increasing with respect to her value and the payment to her is the threshold payment, i.e., the highest value such that her item can still be sold. More precisely, for any single-value distribution D with density function f and cumulative probability F, if D is a seller's value distribution, then the virtual value function is φS (v) = v + F(v) f(v) . In addition, if D is not regular then φS is the ironed virtual value. Following [Myerson and Satterthwaite, 1983], for single-parameter sellers and any DSIC mechanismM = (xS , xB , pS , pB ), the total payment to the sellers is the virtual social welfare of them, i.e., for any valuation profile vB of the buyers. We now show how to convert a mechanism for productioncost markets into a two-sided market's mechanism. The main idea is to use the sellers' virtual values in two-sided markets as costs, and run the mechanism for production-cost markets. Definition 1. A mechanism Mc = (x, p) for productioncost markets is cost-monotone if for any two instances I c = (N,M,Dc , c) and I ′c = (N,M,Dc , c′ ), where c and c′ differ only at an item j and cj ≤ c′j , for any buyers' valuation profile vc ∼ Dc , the probabilities of item j being sold under the two instances, xj = ∑i∈N ∑A∋j xiA(vc ; I c ) and x′j = ∑i∈N ∑A∋j xiA(vc ; I ′c ), satisfy xj ≥ x′j . Reduction. Let I = (N,M,DS ,DB ) be a two-sided market instance. For any valuation profile vS of the sellers, denote by φS (vS ) = (φSj (vS j ))j∈M the sellers' virtualvalue vector, and let I cφS (vS ) = (N,M,DB , φS (vS )) be a production-cost market instance. We first show that the optimal profit of the two-sided market is no more than the optimal profit generated by the corresponding production-cost markets in expectation. Proof. It suffices to show that for any DSIC mechanism M = (xS , xB , pS , pB ) for two-sided markets, there exists a DSIC mechanism Mc for production-cost markets such that PFT(M; I) ≤ EvS ∼DSPFT(Mc ; I cφS (vS ) ). Indeed, this would imply PFT(M; I) ≤ EvS ∼DSOPT(I cφS (vS ) ) for anyM, and thus OPT(I) ≤ EvS ∼DSOPT(I cφS (vS ) ). Given M and I, we define mechanism Mc = (xc , pc ) as follows. For any instance I cφS (vS ) , Mc first computes vS , the (randomized) pre-image of φS (vS ) with respect to DS . In particular, if for some seller j, the (ironed) virtual value φSj (vS j ) corresponds to a value interval in the support of DS j , then vS j is randomly sampled from DS j conditional on it belongs to this interval. For any reported valuation profile vB and buyer i ∈ N, for any A ⊆ M, and It is easy to see that, given any vS and vB -i , for any true valuation vB i , buyer i has the same utility in Mc and M by reporting the same v′B i . Thus Mc is DSIC whenever M is DSIC. Next, we lower-bound the profit of Mc for each instance I cφS (vS ) . The inequality above is because any feasible mechanism should satisfy ∑i∈N ∑A∋j xBiA(vB , vS ) ≤ xSj (vB , vS ) for any j ∈ M and any valuation profiles vB , vS . Thus, as desired. Here φS (DS ) is the distribution of virtual values induced by DS , and the second equality is by Equation 1. In the following, we show that if a mechanism for production-cost markets is cost-monotone, then it can be converted into a mechanism for two-sided markets. Lemma 2. Given any DSIC cost-monotone mechanismMc for production-cost markets, there exists a DSIC mechanism M for two-sided markets such that Proof. Given mechanism Mc = (xc , pc ), the mechanism M = (xS , xB , pS , pB ) is defined as follows: M first collects vB and vS reported by the buyers and the sellers, and then run Mc on the production-cost instance I cφS (vS ) = (N,M,DB , φS (vS )) to obtain xc (vB ) and pc (vB ). Then for each buyer i, let for any A ⊆ M and For each seller j, let and let pSj (vB , vS ) be the threshold payment for j: namely, the highest reported value of seller j such that the probability that item j is bought by the broker is xSj (vB , vS ). We claim that M is DSIC. First, the buyers will truthfully report their valuations because Mc is DSIC and each buyer has the same allocation and payment inMandMc . For the sellers, sinceMc is cost-monotone and each (ironed) virtual value function φSj is non-decreasing in vS j , the allocation xSj is non-increasing in vS j . As the payments to the sellers are the threshold payments, the sellers are truthful as well. Next we show that P F T (M, I) Combining Lemmas 1 and 2, we get our first main result. Theorem 1. Given any DSIC mechanismMc for productioncost markets, if Mc is cost-monotone and is an αapproximation to the optimal profit, then there exists a DSIC mechanism M for two-sided markets that is an αapproximation to the optimal profit. Proof. Mechanism M is defined as in Lemma 2. For any two-sided market instance I, where the equality is by Lemma 2 and the last inequality is by Lemma 1. ## 4 AMechanism for Two-sidedMarkets with Additive Valuations ## 4.1 Broker's Profit in Production-cost Markets We first design a mechanismMA for production-cost markets which is an 8-approximation of the optimal profit. Our mechanism is inspired by the mechanism in [Yao, 2015] and the duality framework in [Cai et al., 2016] for auctions. In particular, with probability 34 , MA runs the mechanism of [Myerson and Satterthwaite, 1983] for two-sided markets for each item separately, denoted by MIT . The mechanism of [Myerson and Satterthwaite, 1983] is for a single buyer and a ## Mechanism 1MBV CG for Production-Cost Markets - 1: Collect the valuation profile v from the buyers. - 2: For any buyer i and item j, let Pij(v-i) = maxi′ ̸=i vi′ j and βij (v-i) = max{Pij (v-i), cj }. - 3: For any buyer i, set the reserve price for item j to be βij(v-i). Set the entry fee ei(v-i) to be the median of the random variable ∑j∈M (tij -βij (v-i))+, where ti = (tij)j∈M ∼ Di and x+ = max{x, 0} for any x ∈ R. - 4: Each buyer i is considered to accept her entry fee if and only if ∑j∈M (vij - βij(v-i))+ ≥ ei(v-i). - 5: If a buyer i accepts her entry fee, then she gets the set of items j with vij ≥ βij(v-i), and her price is ei(v-i) + ∑j:vij≥βij(v-i) βij(v-i). If i does not accept her entry fee, then she gets no item and pays 0. single seller, but can be generalized to multiple buyers and a single seller as shown in [Deng et al., 2014]. Furthermore, MA generalizes the bundling VCG mechanism of [Yao, 2015] to production-cost markets (denoted by MBV CG) and runs it with probability 14 . Essentially, MechanismMIT runs a second-price auction on the buyers' virtual values, with a reserve price which is the production cost of the item. As shown in [Myerson and Satterthwaite, 1983; Deng et al., 2014], this mechanism is optimal for the broker's profit when the buyers have singleparameter valuations. Mechanism MBVCG is well studied in auctions [Yao, 2015; Cai et al., 2016], and we describe it in Mechanism 1 for production-cost markets I c = (N,M,D, c). Essentially, it is a VCG mechanism with peritem reserve prices and per-agent entry fees. It is not hard to see that bothMIT andMBV CG are DSIC and IR. Indeed, the mechanism of [Myerson and Satterthwaite, 1983] is DSIC and IR, MIT directly applies it to each item, and the buyers have additive valuations across the items. Moreover, MBVCG is DSIC and IR with respect to any reserve prices βij that do not depend on vij, and Mechanism 1 simply incorporates the production costs into reserve prices. In Theorem 2 we use MA to upper-bound the optimal profit for any production-cost instance I c = (N,M,D, c), with proof provided in the online appendix [Chen et al., 2019]. In fact, the proof is similar to the one in [Cai et al., 2016] with modifications to incorporate the production costs into consideration. Note that [Brustle et al., 2017] also adapts the framework of [Cai et al., 2016] to the 2-sided market, but their goal is to maximize the gain from trade and the buyers have unit-demand valuations. Theorem 2. When the buyers have additive valuations, Mechanism MA is DSIC and is an 8-approximation to the optimal profit for production-cost markets. ## 4.2 ConvertingMA to Two-sidedMarkets Next we prove the cost-monotonicity for Mechanism MA. But first, we start with MechanismMIT . Lemma 3. MIT is cost-monotone. Proof. For any two production-cost instances I c = (N,M,D, c) and I ′c = (N,M,D, c′ ), where there exists an item j ∈ M such that c′j > cj and c′j ′ = cj ′ for any j ′ ̸= j, we show that in Mechanism MIT , when buyers' valuation profile is v ∼ D, if item j is not sold in I c , then item j is not sold in I ′c . Since all buyers' valuation functions are additive and MIT sells each item individually, the result of selling one item does not effect any other item. In the mechanism of [Myerson and Satterthwaite, 1983], given the reported valuation profile v, the potential winner of item j is the buyer who has highest virtual value on it, denoted by ij = argmaxi∈N vij. If her virtual value φijj(vijj) is at least the cost of item j, buyer ij takes item j. Otherwise, item j is kept unsold. Therefore, if item j is not sold in I c , then φijj(vijj) - cj < 0 which implies φijj(vijj) - c′j < 0 and item j cannot be sold in I ′c . Thus MIT satisfies costmonotonicity. Next we show MBVCG is cost-monotone. Since we need to apply MBVCG to different instances with different cost vectors c and c′ , we explicitly write βij(v-i, cj) and ei(v-i, c) in Steps 2 and 3 of Mechanism 1. Lemma 4. MBV CG is cost-monotone. Proof. Similarly, for any two production-cost instances I c = (N,M,D, c) and I ′c = (N,M,D, c′ ), where there exists an item j ∈ M such that c′j > cj and c′j ′ = cj ′ for any j ′ ̸= j, we show that in MechanismMBVCG, when buyers' valuation profile is v ∼ D, if item j is sold in I ′c , then item j is also sold in I c . In MechanismMBVCG, given the valuation profile v, the potential winner of item j is the buyer who has highest value on item j, denoted by ij = argmaxi∈N vij. When the cost vector is c, item j is sold to ij if and only if ij accepts the entry fee eij (v-i, c) and vij - βijj(v-ij , cj) > 0. Otherwise item j is unsold. Note that given different production cost c′ , the potential winner of item j remains unchanged. Note that the entry fee ei(v-i, c) is selected such that the probability that buyer i accepts it is exactly 1 2 . Let dj = βijj(v-ij , c′j ) - βijj(v-ij , cj) be the increase of the item reserve inMBVCG for buyer ij. Then Indeed the equality holds in Inequality 2 if vijj - βij j (v-ij , c′j ) ≥ 0. Let e′ij = eij (v-ij , c) - dj. When the cost vector is c, buyer ij's utility is When the cost is c′ , if the entry fee is e′ij , buyer ij's utility is The inequality above is by Inequality 2. Moreover, if vijj - βijj(v-ij , c′j ) ≥ 0, thenu′ij (e′ij ) = uij . (3) That is for any valuation profile vij , buyer ij 's utility under the entry fee e′ij and the cost vector c′ is at least her utility under the entry fee eij (v-ij , c) and the cost vector c. Therefore, Since the real entry fee eij (v-ij , c′ ) is selected to be the median of the random variable ∑j∈M (tijj - βijj(v-ij ))+, we have eij (v-ij , c′ ) ≥ e′ij . Now if under cost vector c′ , item j is sold, then vijj - βijj(v-ij , c′j ) ≥ 0, and Thus under cost vector c, we have vijj - βijj(v-ij , cj) ≥ 0, and by Equation 3, Therefore, under cost vector c, item j is also sold. That is, MBVCG is cost-monotone. By randomly selecting fromMIT and MBVCG, MechanismMA is still cost-monotone. Therefore, by Theorem 1, MA can be converted into a mechanism for two-sided markets, which is again an 8-approximation to the optimal profit. Theorem 3. When the buyers have additive valuations, there exists a DSIC mechanism that is an 8-approximation to the optimal profit for two-sided markets. ## 5 Conclusion and Open Problems In this paper, we proved a general reduction from productioncost markets to two-sided markets, and provided a simple constant-approximation DSIC mechanism for the broker's optimal profit when the buyers have additive valuations. How to design DSIC mechanisms under other valuations of the buyers (e.g. unit-demand or sub-additive) is still open, and it would be interesting to understand the role of productioncost markets in those scenarios. Another interesting direction is to study the situation when the sellers have multiple items. ## Acknowledgments This work is partially supported by NSF CAREER Award No. 1553385. ## References 1. [Balseiro et al., 2019] Santiago R Balseiro, Vahab Mirrokni, Renato Paes Leme, and Song Zuo. Dynamic double auc- tions: Towards first best. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 157-172. SIAM, 2019. 2. [Brustle et al., 2017] Johannes Brustle, Yang Cai, Fa Wu, and Mingfei Zhao. Approximating gains from trade in two-sided markets via simple mechanisms. In 18th ACM Conference on Electronic Commerce (EC'17), pages 589- 590, 2017. 3. [Cai et al., 2012a] Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. An algorithmic characterization of multi-dimensional mechanisms. In 44th Annual ACM Symposium on Theory of Computing (STOC'12), pages 459-478, 2012. 4. [Cai et al., 2012b] Yang Cai, Constantinos Daskalakis, and S Matthew Weinberg. Optimal multi-dimensional mecha- nism design: Reducing revenue to welfare maximization. In 53rd Annual Symposium on Foundations of Computer Science (FOCS'12), pages 130-139, 2012. 5. [Cai et al., 2016] Yang Cai, Nikhil R Devanur, and S Matthew Weinberg. A duality based unified ap- proach to Bayesian mechanism design. In 48th Annual ACM Symposium on Theory of Computing (STOC'16), pages 926-939, 2016. 6. [Chan and Chen, 2014] Hau Chan and Jing Chen. Truthful multi-unit procurements with budgets. In International Conference on Web and Internet Economics (WINE'14), pages 89-105, 2014. 7. [Chan and Chen, 2016] Hau Chan and Jing Chen. Budget feasible mechanisms for dealers. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems (AAMAS'16), pages 113-122, 2016. 8. [Chen et al., 2011] Ning Chen, Nick Gravin, and Pinyan Lu. On the approximability of budget feasible mechanisms. In 22nd annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA'11), pages 685-699, 2011. 9. [Chen et al., 2019] Jing Chen, Bo Li, and Yingkai Li. Ap- proximately maximizing the broker's profit in a two-sided market. arXiv preprint arXiv:1905.09347, 2019. 10. [Colini-Baldeschi et al., 2016] Riccardo Colini-Baldeschi, Bart de Keijzer, Stefano Leonardi, and Stefano Turchetta. Approximately efficient double auctions with strong budget balance. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16), pages 1424-1443. Society for Industrial and Applied Mathematics, 2016. 11. [Colini-Baldeschi et al., 2017] Riccardo Colini-Baldeschi, Paul W Goldberg, Bart de Keijzer, Stefano Leonardi, Tim Roughgarden, and Stefano Turchetta. Approximately efficient two-sided combinatorial auctions. In 18th ACM Conference on Electronic Commerce (EC'17), pages 591-608, 2017. 12. [Deng et al., 2014] Xiaotie Deng, Paul Goldberg, Bo Tang, and Jinshan Zhang. Revenue maximization in a bayesian double auction market. Theoretical Computer Science, 539:1-12, 2014. 13. [Dobzinski et al., 2011] Shahar Dobzinski, Christos H Pa- padimitriou, and Yaron Singer. Mechanisms for complement-free procurement. In 12th ACM Conference on Electronic Commerce (EC'11), pages 273-282, 2011. 14. [Gerstgrasser et al., 2016] Matthias Gerstgrasser, Paul W Goldberg, and Elias Koutsoupias. Revenue maximization for market intermediation with correlated priors. In Inter- national Symposium on Algorithmic Game Theory, pages 273-285. Springer, 2016. 15. [Hart and Nisan, 2017] Sergiu Hart and Noam Nisan. Ap- proximate revenue maximization with multiple items. Journal of Economic Theory, 172:313-347, 2017. 16. [Jain and Wilkens, 2012] Kamal Jain and Christopher A Wilkens. ebay's market intermediation problem. arXiv preprint arXiv:1209.5348, 2012. 17. [Kleinberg and Weinberg, 2012] Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In 44th Annual ACM Symposium on Theory of Computing (STOC'12), pages 123-136, 2012. 18. [McAfee, 1992] R Preston McAfee. A dominant strategy double auction. Journal of Economic Theory, 56(2):434- 450, 1992. 19. [McAfee, 2008] R Preston McAfee. The gains from trade under fixed price mechanisms. Applied Economics Re- search Bulletin, 1(1):1-10, 2008. 20. [Myerson and Satterthwaite, 1983] Roger B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilat- eral trading. Journal of Economic Theory, 29(2):265-281, 1983. 21. [Myerson, 1981] Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981. 22. [Segal-Halevi et al., 2018a] Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. Double auctions in markets for multiple kinds of goods. In IJCAI, pages 489-497, 2018. 23. [Segal-Halevi et al., 2018b] Erel Segal-Halevi, Avinatan Hassidim, and Yonatan Aumann. Muda: a truthful multi- unit double-auction mechanism. In Thirty-Second AAAI Conference on Artificial Intelligence, pages 1193-1201, 2018. 24. [Singer, 2010] Yaron Singer. Budget feasible mechanisms. In 51st Symposium on Foundations of Computer Science (FOCS'10), pages 765-774, 2010. 25. [Yao, 2015] Andrew Chi-Chih Yao. An n-to-1 bidder reduc- tion for multi-item auctions and its applications. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15), pages 92-109, 2015.