Approximately Maximizing the Broker's Profit in a Two-sided Market

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.