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 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.
Two-sided markets are also called double auctions @cite_0 , bilateral trading @cite_5 or market intermediation @cite_6 in the literature. Maximizing the broker's profit is an important objective for two-sided market. The seminal paper @cite_5 characterized the optimal mechanism for one seller and one buyer, which is further generalized by @cite_22 to multiple single-parameter sellers and buyers. Unlike our work, @cite_22 studies the Bayesian Incentive Compatible (BIC) mechanisms. DSIC mechanisms are also studied in the literature, but only for some special cases: @cite_6 studies the case of a single buyer and multiple sellers, @cite_3 studies the case of a single seller and multiple buyers, and @cite_11 studies the optimal mechanism when the numbers of sellers and buyers are both constants. Although @cite_20 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.
@cite_22 @cite_3 @cite_6 @cite_0 @cite_5 @cite_20 @cite_11
2262059501 2028289369 2627057954 1495768673
Mechanism design for one-sided markets is an area of extensive research in economics and, since more than a decade, in computer science as well. Two-sided markets, on the other hand, have not received the same attention despite the numerous applications to web advertisement, stock exchange, and frequency spectrum allocation. This work studies double auctions, in which unit-demand buyers and unit-supply sellers act strategically. An ideal goal in double auction design is to maximize the social welfare of buyers and sellers with individually rational (IR), incentive compatible (IC) and strongly budget-balanced (SBB) mechanisms. The first two properties are standard. SBB requires that the payments charged to the buyers are entirely handed to the sellers. This property is crucial in all the contexts that do not allow the auctioneer retaining a share of buyers' payments or subsidizing the market. Unfortunately, this goal is known to be unachievable even for the special case of bilateral trade, where there is only one buyer and one seller. Therefore, in subsequent papers, meaningful trade-offs between these requirements have been investigated. Our main contribution is the first IR, IC and SBB mechanism that provides an O(1)-approximation to the optimal social welfare. This result holds for any number of buyers and sellers with arbitrary, independent distributions. Moreover, our result continues to hold when there is an additional matroid constraint on the sets of buyers who may get allocated an item. To prove our main result, we devise an extension of sequential posted price mechanisms to two-sided markets. In addition to this, we improve the best-known approximation bounds for the bilateral trade problem. We study double auction market design where the market maker wants to maximize its total revenue by buying low from the sell- ers and selling high to the buyers. We consider a Bayesian setting where buyers and sellers have independent probability distributions on the val- ues of products on the market. For the simplest setting where each seller has one kind of item that can be sold in whole to a buyer, and each buyer's value can be represented by a single parameter, i.e., single-parameter setting, we develop a maximum mechanism for the market maker to maximize its own revenue. For the more general case where the product may be different, we consider various models in terms of supplies and demands constraints. For each of them, we develop a polynomial time computable truthful mechanism for the market maker to achieve a revenue at least a constant α times the revenue of any other truthful mechanism. We consider a double auction market maker who collects valuations from buy- ers and sellers about a certain product to decide on the prices each seller gets and each buyer pays. The buyers may want to buy many units and the sellers may have many units to part with. The buyers and sellers may have different valuations of the product, and there is public knowledge of the probability dis- tributions of the valuations (but each valuation, sampled from its distribution, is known only to its own buyer or seller). For simplicity, we assume that the probability distributions are independent. For the sellers and buyers, they know their own private values exactly. The market maker purchases the products from the sellers and sell them to the buyers. Our goal is to design a market mechanism that maximizes the revenue of the market maker. In other words, the market maker is to buy the same amount of products from the sellers as the amount sold to the buyers with the objective of maximizing the difference of its collected payment from the buyers and the total amount paid to the sellers. When in addi- tion we assume public knowledge of distributions of buyers' private values from the previous sales, we call it a revenue maximization Bayesian double auction market maker. � Supported by EPSRC grant EP G069239 1 "Efficient Decentralised Approaches in We design simple mechanisms to approximate the Gains from Trade (GFT) in two-sided markets with multiple unit-supply sellers and multiple unit-demand buyers. A classical impossibility result by Myerson and Satterthwaite showed that even with only one seller and one buyer, no Bayesian Incentive Compatible (BIC), Individually Rational (IR), and Budget-Balanced (BB) mechanism can achieve full GFT (trade whenever buyer's value is higher than the seller's cost). The same paper also proposed the second-best'' mechanism that maximizes the GFT subject to BIC, IR, and BB constraints, which is unfortunately rather complex for even the single-seller single-buyer case. Our mechanism is simple, BIC, IR, and BB and achieves 1 2 of the optimal GFT among all BIC, IR, and BB mechanisms. The result holds for arbitrary distributions of the buyers' and sellers' values and can accommodate any downward-closed feasibility constraints over the allocations. The analysis of our mechanism is facilitated by extending the Cai-Weinberg-Devanur duality framework to two-sided markets. In this paper, we introduce a novel approach for reducing the k-item n-bidder auction with additive valuation to k-item 1-bidder auctions. This approach, called the Best-Guess reduction, can be applied to address several central questions in optimal revenue auction theory such as the relative strength of simple versus complex mechanisms, the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called Deterministic Best-Guess that yields at least a constant fraction of the optimal revenue by any randomized mechanism. This also gives the first simple mechanism that achieves constant fraction optimal revenue for such multi-buyer multi-item auctions. Second, if all the nk valuation random variables are independent, the optimal revenue achievable in dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in Bayesian incentive compatibility (BIC). Third, when all the nk values are identically distributed according to a common one-dimensional distribution F, the optimal revenue is shown to be expressible in the closed form Θ(k(r + ∫0mr(1 − F(x)n)dx)) where r = supx≥0 x(1 − F(x)n) and m = lk nr; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.