More Like this

1. On Multi-Dimensional Gains from Trade Maximization

   https://doi.org/10.1137/1.9781611976465.67  

   Cai, Y.; Goldner, K.; Ma, S.; Zhao, M. (January 2021, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA))

   We study gains from trade in multi-dimensional two-sided markets. Specifically, we focus on a setting with n heterogeneous items, where each item is owned by a different seller i, and there is a constrained-additive buyer with feasibility constraint ℱ. Multi-dimensional settings in one-sided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are well-understood. In addition, single-dimensional settings in two-sided markets, e.g. where a buyer and seller each seek or own a single item, are also well-understood. Multi-dimensional two-sided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentive-compatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worst-case approximation guarantee for gains from trade in a multi-dimensional two-sided market. Our first result provides an O(log(1/r))-approximation to the first-best gains from trade for a broad class of downward-closed feasibility constraints (such as matroid, matching, knapsack, or the intersection of these). Here r is the minimum probability over all items that a buyer's value for the item exceeds the seller's cost. Our second result removes the dependence on r and provides an unconditional O(log n)-approximation to the second-best gains from trade. We extend both results for a general constrained-additive buyer, losing another O(log n)-factor en-route. The first result is achieved using a fixed posted price mechanism, and the analysis involves a novel application of the prophet inequality or a new concentration inequality. Our second result follows from a stitching lemma that allows us to upper bound the second-best gains from trade by the first-best gains from trade from the “likely to trade” items (items with trade probability at least 1/n) and the optimal profit from selling the “unlikely to trade” items. We can obtain an O(log n)-approximation to the first term by invoking our O(log(1/r))-approximation on the “likely to trade” items. We introduce a generalization of the fixed posted price mechanism—seller adjusted posted price—to obtain an O(log n)-approximation to the optimal profit for the “unlikely to trade” items. Unlike fixed posted price mechanisms, not all seller adjusted posted price mechanisms are incentive compatible and budget balanced. We develop a new argument based on “allocation coupling” to show the seller adjusted posted price mechanism used in our approximation is indeed budget balanced and incentive-compatible. 

   more » « less
2. Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities

   https://doi.org/10.1287/opre.2021.2186  

   Blanchet, Jose H.; Reiman, Martin I.; Shah, Virag; Wein, Lawrence M.; Wu, Linjia (November 2022, Operations Research)

   The utility of a match in a two-sided matching market often depends on a variety of characteristics of the two agents (e.g., a buyer and a seller) to be matched. In contrast to the matching market literature, this utility may best be modeled by a general matching utility distribution. In “Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities,” Blanchet, Reiman, Shah, Wein, and Wu consider general matching utilities in the context of a centralized dynamic matching market. To analyze this difficult problem, they combine two asymptotic techniques: extreme value theory (and regularly varying functions) and fluid asymptotics of queueing systems. A key trade-off in this problem is market thickness: Do we myopically make the best match that is currently available, or do we allow the market to thicken in the hope of making a better match in the future while avoiding agent abandonment? Their asymptotic analysis derives quite explicit results for this problem and reveals how the optimal amount of market thickness increases with the right tail of the matching utility distribution and the amount of market imbalance. Their use of regularly varying functions also allows them to consider correlated matching utilities (e.g., buyers have positively correlated utilities with a given seller), which is ubiquitous in matching markets. 

   more » « less
3. The Segmentation-Thickness Tradeoff in Online Marketplaces

   https://doi.org/10.1145/3311089  

   Alijani, Reza; Banerjee, Siddhartha; Gollapudi, Sreenivas; Kollias, Kostas; Munagala, Kamesh (March 2019, ACM SIGMETRICS performance evaluation review)

   A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller sub-markets) and thickness (wherein the size of the sub-market affects the utility experienced by an agent). An important example of this is in dynamic online marketplaces, where buyers and sellers, in addition to preferences for different matches, also have finite patience (or deadlines) for being matched. We formalize this trade-off via a novel optimization problem that we term as 'Two-sided Facility Location': we consider a market wherein agents arrive at nodes embedded in an underlying metric space, where the distance between a buyer and seller captures the quality of the corresponding match. The platform posts prices and wages at the nodes, and opens a set of virtual clearinghouses where agents are routed for matching. To ensure high match-quality, the platform imposes a distance constraint between an agent and its clearinghouse; to ensure thickness, the platform requires the flow to any clearinghouse be at least a pre-specified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus subject to weak budget balance, i.e., profit being non-negative. Our work characterizes the complexity of this problem by providing both hardness results as well as algorithms for this setting; in particular, we present an algorithm that for any constant ε > 0 yields a (1 + ε ) approximation for the gains from trade, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor. 

   more » « less
4. Bilateral Trade with Correlated Values

   Dobzinski, Shahar; Shaulker, Ariel (June 2024, ACM)

   Mohar, Bojan; Shinkar, Igor; O'Donnell, Ryan (Ed.)

   We study the bilateral trade problem where a seller owns a single indivisible item, and a potential buyer seeks to purchase it. Previous mechanisms for this problem only considered the case where the values of the buyer and the seller are drawn from independent distributions. In contrast, this paper studies bilateral trade mechanisms when the values are drawn from a joint distribution. We prove that the buyer-offering mechanism guarantees an approximation ratio of e/e−1 ≈ 1.582 to the social welfare even if the values are drawn from a joint distribution. The buyer-offering mechanism is Bayesian incentive compatible, but the seller has a dominant strategy. We prove the buyer-offering mechanism is optimal in the sense that no Bayesian mechanism where one of the players has a dominant strategy can obtain an approximation ratio better than e/e−1. We also show that no mechanism in which both sides have a dominant strategy can provide any constant approximation to the social welfare when the values are drawn from a joint distribution. Finally, we prove some impossibility results on the power of general Bayesian incentive compatible mechanisms. In particular, we show that no deterministic Bayesian incentive-compatible mechanism can provide an approximation ratio better than 1+ln2/2≈ 1.346. 

   more » « less
5. The Efficiency of Real-World Bargaining: Evidence from Wholesale Used-Auto Auctions

   https://doi.org/10.1093/restud/rdaa007  

   Larsen, Bradley J (February 2020, The Review of Economic Studies)

   Abstract This study empirically quantifies the efficiency of a real-world bargaining game with two-sided incomplete information. Myerson and Satterthwaite (1983) and Williams (1987) derived the theoretical ex-ante efficient frontier for bilateral trade under two-sided uncertainty and demonstrated that it falls short of ex-post efficiency, but little is known about how well bargaining performs in practice. Using about 265,000 sequences of a game of alternating-offer bargaining following an ascending auction in the wholesale used-car industry, this study estimates (or bounds) distributions of buyer and seller values and evaluates where realized bargaining outcomes lie relative to efficient outcomes. Results demonstrate that the ex-ante and ex-post efficient outcomes are close to one another, but that the real bargaining falls short of both, suggesting that the bargaining is indeed inefficient but that this inefficiency is not solely due to the information constraints highlighted in Myerson and Satterthwaite (1983). Quantitatively, findings indicate that over one-half of failed negotiations are cases where gains from trade exist, leading an efficiency loss of 12–23% of the available gains from trade. 

   more » « less