Arrow Research search

Author name cluster

Mingfei Zhao

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
1 author row

Possible papers

5

SODA Conference 2021 Conference Paper

An Efficient ∊ -BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization

  • Yang Cai 0001
  • Argyris Oikonomou
  • Grigoris Velegkas
  • Mingfei Zhao

We consider the black-box reduction from multidimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving reduction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible ( ∊ -BIC). We provide two new polynomial time transformations that convert any ∊ -BIC mechanism to an exactly BIC mechanism with only a negligible revenue loss. • Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample access to the agents' type distributions. • Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents' type distributions. Both transformations only require query access to the original ∊ -BIC mechanism. Other ∊ -BIC to BIC transformations for revenue exist in the literature [23, 36, 18] but all require exponential time to run in both of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. [12, 13, 14, 15] to generate an exactly BIC mechanism.

Details

SODA Conference 2021 Conference Paper

On Multi-Dimensional Gains from Trade Maximization

  • Yang Cai 0001
  • Kira Goldner
  • Steven Ma
  • Mingfei Zhao

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.

Details