Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets
187
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of welfare maximization in two-sided markets using simple mechanisms that are prior-independent. The Myerson-Satterthwaite impossibility theorem shows that even for bilateral trade, there is no feasible (IR, truthful, budget balanced) mechanism that has welfare as high as the optimal-yet-infeasible VCG mechanism, which attains maximal welfare but runs a deficit. On the other hand, the optimal feasible mechanism needs to be carefully tailored to the Bayesian prior, and is extremely complex, eluding a precise description. We present Bulow-Klemperer-style results to circumvent these hurdles in double-auction markets. We suggest using the Buyer Trade Reduction (BTR) mechanism, a variant of McAfees mechanism, which is feasible and simple (in particular, deterministic, truthful, prior-independent, anonymous). First, in the setting where buyers and sellers values are sampled i.i.d. from the same distribution, we show that for any such market of any size, BTR with one additional buyer whose value is sampled from the same distribution has expected welfare at least as high as the optimal in the original market. We then move to a more general setting where buyers values are sampled from one distribution and sellers from another, focusing on the case where the buyers distribution first-order stochastically dominates the sellers. We present bounds on the number of buyers that, when added, guarantees that BTR in the augmented market have welfare at least as high as the optimal in the original market. Our lower bounds extend to a large class of mechanisms, and all of our results extend to adding sellers instead of buyers. In addition, we present positive results about the usefulness of pricing at a sample for welfare maximization in two-sided markets under the above two settings, which to the best of our knowledge are the first sampling results in this context.
rate research
Read More
The Arrow-Debreu extension of the classic Hylland-Zeckhauser scheme for a one-sided matching market -- called ADHZ in this paper -- has natural applications but has instances which do not admit equilibria. By introducing approximation, we define the $epsilon$-approximate ADHZ model, and we give the following results. * Existence of equilibrium under linear utility functions. We prove that the equilibrium satisfies Pareto optimality, approximate envy-freeness, and approximate weak core stability. * A combinatorial polynomial-time algorithm for an $epsilon$-approximate ADHZ equilibrium for the case of dichotomous, and more generally bi-valued, utilities. * An instance of ADHZ, with dichotomous utilities and a strongly connected demand graph, which does not admit an equilibrium. Since computing an equilibrium for HZ is likely to be highly intractable and because of the difficulty of extending HZ to more general utility functions, Hosseini and Vazirani proposed (a rich collection of) Nash-bargaining-based matching market models. For the dichotomous-utilities case of their model linear Arrow-Debreu Nash bargaining one-sided matching market (1LAD), we give a combinatorial, strongly polynomial-time algorithm and show that it admits a rational convex program.
Motivated by the emergence of popular service-based two-sided markets where sellers can serve multiple buyers at the same time, we formulate and study the {em two-sided cost sharing} problem. In two-sided cost sharing, sellers incur different costs for serving different subsets of buyers and buyers have different values for being served by different sellers. Both buyers and sellers are self-interested agents whose values and costs are private information. We study the problem from the perspective of an intermediary platform that matches buyers to sellers and assigns prices and wages in an effort to maximize welfare (i.e., buyer values minus seller costs) subject to budget-balance in an incentive compatible manner. In our markets of interest, agents trade the (often same) services multiple times. Moreover, the value and cost for the same service differs based on the context (e.g., location, urgency, weather conditions, etc). In this framework, we design mechanisms that are efficient, ex-ante budget-balanced, ex-ante individually rational, dominant strategy incentive compatible, and ex-ante in the core (a natural generalization of the core that we define here).
A seminal result of Bulow and Klemperer [1989] demonstrates the power of competition for extracting revenue: when selling a single item to $n$ bidders whose values are drawn i.i.d. from a regular distribution, the simple welfare-maximizing VCG mechanism (in this case, a second price-auction) with one additional bidder extracts at least as much revenue in expectation as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a {em prior-independent} mechanism, where the seller possesses no information about the distribution, and yet, by recruiting one additional bidder it performs better than any prior-dependent mechanism tailored exactly to the distribution at hand (without the additional bidder). In this work, we establish the first {em full Bulow-Klemperer} results in {em multi-dimensional} environments, proving that by recruiting additional bidders, the revenue of the VCG mechanism surpasses that of the optimal (possibly randomized, Bayesian incentive compatible) mechanism. For a given environment with i.i.d. bidders, we term the number of additional bidders needed to achieve this guarantee the environments {em competition complexity}. Using the recent duality-based framework of Cai et al. [2016] for reasoning about optimal revenue, we show that the competition complexity of $n$ bidders with additive valuations over $m$ independent, regular items is at most $n+2m-2$ and at least $log(m)$. We extend our results to bidders with additive valuations subject to downward-closed constraints, showing that these significantly more general valuations increase the competition complexity by at most an additive $m-1$ factor. We further improve this bound for the special case of matroid constraints, and provide additional extensions as well.
Two-sided matching platforms provide users with menus of match recommendations. To maximize the number of realized matches between the two sides (referred here as customers and suppliers), the platform must balance the inherent tension between recommending customers more potential suppliers to match with and avoiding potential collisions. We introduce a stylized model to study the above trade-off. The platform offers each customer a menu of suppliers, and customers choose, simultaneously and independently, either a supplier from their menu or to remain unmatched. Suppliers then see the set of customers that have selected them, and choose to either match with one of these customers or to remain unmatched. A match occurs if a customer and a supplier choose each other (in sequence). Agents choices are probabilistic, and proportional to public scores of agents in their menu and a score that is associated with remaining unmatched. The platforms problem is to construct menus for costumers to maximize the number of matches. This problem is shown to be strongly NP-hard via a reduction from 3-partition. We provide an efficient algorithm that achieves a constant-factor approximation to the expected number of matches.
We design novel mechanisms for welfare-maximization in two-sided markets. That is, there are buyers willing to purchase items and sellers holding items initially, both acting rationally and strategically in order to maximize utility. Our mechanisms are designed based on a powerful correspondence between two-sided markets and prophet inequalities. They satisfy individual rationality, dominant-strategy incentive compatibility, budget-balance constraints and give constant-factor approximations to the optimal social welfare. We improve previous results in several settings: Our main focus is on matroid double auctions, where the set of buyers who obtain an item needs to be independent in a matroid. We construct two mechanisms, the first being a $1/3$-approximation of the optimal social welfare satisfying strong budget-balance and requiring the agents to trade in a customized order, the second being a $1/2$-approximation, weakly budget-balanced and able to deal with online arrival determined by an adversary. In addition, we construct constant-factor approximations in two-sided markets when buyers need to fulfill a knapsack constraint. Also, in combinatorial double auctions, where buyers have valuation functions over item bundles instead of being interested in only one item, using similar techniques, we design a mechanism which is a $1/2$-approximation of the optimal social welfare, strongly budget-balanced and can deal with online arrival of agents in an adversarial order.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
