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
An O(log n)-Competitive Posted-Price Algorithm for Online Matching on the Line
Motivated by demand-responsive parking pricing systems,
we consider posted-price algorithms for the online metric matching prob-
lem. We give an O(log n)-competitive posted-price randomized algorithm
in the case that the metric space is a line. In particular, in this setting
we show how to implement the ubiquitous guess-and-double technique
using prices.
more »
« less
- Award ID(s):
- 1907673
- PAR ID:
- 10549895
- Publisher / Repository:
- Springer
- Date Published:
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)more » « less
Efficient and truthful mechanisms to price time on remote servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers online revenue maximization for a unit capacity server, when jobs are non preemptive, in the Bayesian setting: at each time step, one job arrives, with parameters drawn from an underlying distribution.We design an efficiently computable truthful posted price mechanism, which maximizes revenue in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent's type, and the computed pricing scheme is deterministic.We also show the pricing mechanism is robust to learning the job distribution from samples, where polynomially many samples suffice to obtain near optimal prices.
-
Abstract Efficient and truthful mechanisms to price resources on servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers revenue maximization in the online stochastic setting with non-preemptive jobs and a unit capacity server. One agent/job arrives at every time step, with parameters drawn from the underlying distribution. We design a posted-price mechanism which can be efficiently computed and is revenue-optimal in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent’s type, and the computed pricing scheme is deterministic, depending only on the length of the allotted time interval and on the earliest time the server is available. We also prove that the proposed pricing strategy is robust to imprecise knowledge of the job distribution and that a distribution learned from polynomially many samples is sufficient to obtain a near-optimal truthful pricing strategy.more » « less
-
null (Ed.)We characterize revenue maximizing mechanisms in a common value environment where the value of the object is equal to the highest of the bidders' independent signals. If the revenue maximizing solution is to sell the object with probability 1, then an optimal mechanism is simply a posted price, namely, the highest price such that every type of every bidder is willing to buy the object. If the object is optimally sold with probability less than 1, then optimal mechanisms skew the allocation toward bidders with lower signals. The resulting allocation induces a “winner's blessing,” whereby the expected value conditional on winning is higher than the unconditional expectation. By contrast, standard auctions that allocate to the bidder with the highest signal (e.g., the first‐price, second‐price, or English auctions) deliver lower revenue because of the winner's curse generated by the allocation. Our qualitative results extend to more general common value environments with a strong winner's curse.more » « less
-
A single seller faces a sequence of buyers with unit demand. The buyers are forward‐looking and long‐lived. Each buyer has private information about his arrival time and valuation where the latter evolves according to a geometric Brownian motion. Any incentive‐compatible mechanism has to induce truth‐telling about the arrival time and the evolution of the valuation. We establish that the optimal stationary allocation policy can be implemented by a simple posted price. The truth‐telling constraint regarding the arrival time can be represented as an optimal stopping problem that determines the first time at which the buyer participates in the mechanism. The optimal mechanism thus induces progressive participation by each buyer: he either participates immediately or at a future random time.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
