Yang Cai

Yang Cai

Auto-generated profile, based on publicly available information

Yang Cai

Yale University, New Haven, USA

Research Focus & Metrics

Academic Career Length

16Years (2011-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 January 2013
Verified
Conference Paper
Open access
YCYang Cai
Yang Cai
CDConstantinos Daskalakis
Constantinos Daskalakis
SWS. Matthew Weinberg
S. Matthew Weinberg

10 June 2024
Verified
Conference Paper
Open access
YCYang Cai
Yang Cai
CLChristopher Liaw
Christopher Liaw
AMAranyak Mehta
Aranyak Mehta
MZMingfei Zhao
Mingfei Zhao
We consider the problem of maximizing the gains from trade (GFT) in two-sided markets. The seminal impossibility result by Myerson and Satterthwaite (1983) shows that even for bilateral trade, there is no individually rational (IR), Bayesian incentive compatible (BIC) and budget balanced (BB) mechanism that can achieve the full GFT. Moreover, the optimal BIC, IR and BB mechanism that maximizes the GFT is known to be complex and heavily depends on the prior. In this paper, we pursue a Bulow-Klemperer-style question, i.e., does augmentation allow for prior-independent mechanisms to compete against the optimal mechanism? Our first main result shows that in the double auction setting with m i.i.d. buyers and n i.i.d. sellers, by augmenting O(1) buyers and sellers to the market, the GFT of a simple, dominant strategy incentive compatible (DSIC), and prior-independent mechanism in the augmented market is at least the optimal in the original market, when the buyers’ distribution first-order stochastically dominates the sellers’ distribution. The mechanism we consider is a slight variant of the standard Trade Reduction mechanism due to McAfee (1992). For comparison, Babaioff, Goldner, and Gonczarowski (2020) showed that if one is restricted to augmenting only one side of the market, then n(m + 4√m) additional agents are sufficient for their mechanism to beat the original optimal and ⌊ log2 m ⌋ additional agents are necessary for any prior-independent mechanism. Next, we go beyond the i.i.d. setting and study the power of two-sided recruitment in more general markets. Our second main result is that for any ε > 0 and any set of O(1/ε) buyers and sellers where the buyers’ value exceeds the sellers’ value with constant probability, if we add these additional agents into any market with arbitrary correlations, the Trade Reduction mechanism obtains a (1−ε)-approximation of the GFT of the augmented market. Importantly, the newly recruited agents are agnostic to the original market.

13 May 2024
Verified
Conference Paper
Open access
YCYang Cai
Yang Cai
ZFZhe Feng
Zhe Feng
CLChristopher Liaw
Christopher Liaw
AMAranyak Mehta
Aranyak Mehta
GVGrigoris Velegkas
Grigoris Velegkas
We propose a new Markov Decision Process (MDP) model for ad auctions to capture the user response to the quality of ads, with the objective of maximizing the long-term discounted revenue. By incorporating user response, our model takes into consideration all three parties involved in the auction (advertiser, auctioneer, and user). The state of the user is modeled as a user-specific click-through rate (CTR) with the CTR changing in the next round according to the set of ads shown to the user in the current round. We characterize the optimal mechanism for this MDP as a Myerson's auction with a notion of modified virtual value, which relies on the value distribution of the advertiser, the current user state, and the future impact of showing the ad to the user. Leveraging this characterization, we design a sample-efficient and computationally-efficient algorithm which outputs an approximately optimal policy that requires only sample access to the true MDP and the value distributions of the bidders. Finally, we propose a simple mechanism built upon second price auctions with personalized reserve prices and show it can achieve a constant-factor approximation to the optimal long term discounted revenue.

1 June 2015
Verified
Book Chapter
Open access
PDF file
YCYang Cai
Yang Cai
CDConstantinos Daskalakis
Constantinos Daskalakis
MWMatthew Weinberg
Matthew Weinberg
STOC2012; Cai, Daskalakis, Weinberg FOCS2012; Cai, Daskalakis, Weinberg SODA2013; Cai, Daskalakis, Weinberg FOCS2013; Cai, Daskalakis, Weinberg SODA2015; Daskalakis, Weinberg The goal is to design algorithms that succeed in models where input is reported by strategic agents (henceforth referred to as strategic input), as opposed to standard models where the input is directly given (henceforth referred to as honest input). For example, consider a resource allocation problem where a single user has m jobs to process on n self-interested machines. Each machine i can process job j in time ti j, and this is privately known only to the machine. Each machine reports some processing times ...

8 July 2024
Verified
Conference Paper
Open access
YCYang Cai
Yang Cai
YLYingkai Li
Yingkai Li
JWJinzhao Wu
Jinzhao Wu

4 December 2018 in arXiv
Verified
Preprint
Open access
PDF file
YCYang Cai
Yang Cai
NDNikhil R. Devanur
Nikhil R. Devanur
SWS. Matthew Weinberg
S. Matthew Weinberg
We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai et al. [CDW13b], simple auctions for additive buyers [HN12], and posted-price mechanisms for unit-demand bidders [CHK07]. Additionally, we show that viewing these three previously disjoint lines of work through the same lens leads to new developments as well. First, we provide a duality framework for Bayesian mechanism design, which naturally accommodates multiple agents and arbitrary objectives/feasibility constraints. Using this, we prove that either a posted-price mechanism or the Vickrey-Clarke-Groves auction with per-bidder entry fees achieves a constant-factor of the optimal revenue achievable by a Bayesian Incentive Compatible mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. [CHMS10] and Yao [Yao15], and improving both approximation ratios (from 30 to 24 and 69 to 8, respectively). Finally, we show that this view also leads to improved structural characterizations in the Cai et al. framework.