60 citations · 159 across the 35 of their papers we have counts for
5 papers · 1 filter
A Constructive Approach to Reduced-Form Auctions with Applications to Multi-Item Mechanism Design
Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg
We provide a constructive proof of Border's theorem [Bor91, HR15a] and its generalization to reduced-form auctions with asymmetric bidders [Bor07, MV10, CKM13]. Given a reduced for…
Can Nondeterminism Help Complementation?
Yang Cai, Ting Zhang
Complementation and determinization are two fundamental notions in automata theory. The close relationship between the two has been well observed in the literature. In the case of…
Extreme-Value Theorems for Optimal Multidimensional Pricing
Yang Cai, Constantinos Daskalakis
We provide a near-optimal, computationally efficient algorithm for the unit-demand pricing problem, where a seller wants to price n items to optimize revenue against a unit-demand…
A Tight Lower Bound for Streett Complementation
Yang Cai, Ting Zhang
Finite automata on infinite words (-automata) proved to be a powerful weapon for modeling and reasoning infinite behaviors of reactive systems. Complementation of -automata i…
Tight Upper Bounds for Streett and Parity Complementation
Yang Cai, Ting Zhang
Complementation of finite automata on infinite words is not only a fundamental problem in automata theory, but also serves as a cornerstone for solving numerous decision problems i…