Yang Cai 0001

ICLR Conference 2025 Conference Paper

Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games

• Yang Cai 0001
• Gabriele Farina
• Julien Grand-Clément
• Christian Kroer
• Chung-Wei Lee
• Haipeng Luo
• Weiqiang Zheng

We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching$^+$ (RM$^+$). Despite their widespread use for solving real games, virtually nothing is known about their last-iterate convergence. A major obstacle to analyzing RM-type dynamics is that their regret operators lack Lipschitzness and (pseudo)monotonicity. We start by showing numerically that several variants used in practice, such as RM$^+$, predictive RM$^+$ and alternating RM$^+$, all lack last-iterate convergence guarantees even on a simple $3\times 3$ matrix game. We then prove that recent variants of these algorithms based on a smoothing technique, extragradient RM$^{+}$ and smooth Predictive RM$^+$, enjoy asymptotic last-iterate convergence (without a rate), $1/\sqrt{t}$ best-iterate convergence, and when combined with restarting, linear-rate last-iterate convergence. Our analysis builds on a new characterization of the geometric structure of the limit points of our algorithms, marking a significant departure from most of the literature on last-iterate convergence. We believe that our analysis may be of independent interest and offers a fresh perspective for studying last-iterate convergence in algorithms based on non-monotone operators.

ICML Conference 2024 Conference Paper

Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion

• Yang Cai 0001
• Argyris Oikonomou
• Weiqiang Zheng

We study constrained comonotone min-max optimization, a structured class of nonconvex-nonconcave min-max optimization problems, and their generalization to comonotone inclusion. In our first contribution, we extend the Extra Anchored Gradient (EAG) algorithm, originally proposed by Yoon and Ryu (2021) for unconstrained min-max optimization, to constrained comonotone min-max optimization and comonotone inclusion, achieving an optimal convergence rate of $O\left(\frac{1}{T}\right)$ among all first-order methods. Additionally, we prove that the algorithm’s iterations converge to a point in the solution set. In our second contribution, we extend the Fast Extra Gradient (FEG) algorithm, as developed by Lee and Kim (2021), to constrained comonotone min-max optimization and comonotone inclusion, achieving the same $O\left(\frac{1}{T}\right)$ convergence rate. This rate is applicable to the broadest set of comonotone inclusion problems yet studied in the literature. Our analyses are based on simple potential function arguments, which might be useful for analyzing other accelerated algorithms.

STOC Conference 2024 Conference Paper

The Power of Two-Sided Recruitment in Two-Sided Markets

• Yang Cai 0001
• Christopher Liaw
• Aranyak Mehta
• Mingfei Zhao

ICLR Conference 2023 Conference Paper

Accelerated Single-Call Methods for Constrained Min-Max Optimization

• Yang Cai 0001
• Weiqiang Zheng

We study first-order methods for constrained min-max optimization. Existing methods either require two gradient calls or two projections in each iteration, which may be costly in some applications. In this paper, we first show that a variant of the \emph{Optimistic Gradient (OG)} method, a \emph{single-call single-projection} algorithm, has $O(\frac{1}{\sqrt{T}})$ best-iterate convergence rate for inclusion problems with operators that satisfy the weak Minty variation inequality (MVI). Our second result is the first single-call single-projection algorithm -- the \emph{Accelerated Reflected Gradient (ARG)} method that achieves the \emph{optimal $O(\frac{1}{T})$} last-iterate convergence rate for inclusion problems that satisfy negative comonotonicity. Both the weak MVI and negative comonotonicity are well-studied assumptions and capture a rich set of non-convex non-concave min-max optimization problems. Finally, we show that the \emph{Reflected Gradient (RG)} method, another \emph{single-call single-projection} algorithm, has $O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate for constrained convex-concave min-max optimization, answering an open problem of [Hsieh et al., 2019]. Our convergence rates hold for standard measures such as the tangent residual and the natural residual.

ICML Conference 2023 Conference Paper

Doubly Optimal No-Regret Learning in Monotone Games

• Yang Cai 0001
• Weiqiang Zheng

We consider online learning in multi-player smooth monotone games. Existing algorithms have limitations such as (1) being only applicable to strongly monotone games; (2) lacking the no-regret guarantee; (3) having only asymptotic or slow $\mathcal{O}(\frac{1}{\sqrt{T}})$ last-iterate convergence rate to a Nash equilibrium. While the $\mathcal{O}(\frac{1}{\sqrt{T}})$ rate is tight for a large class of algorithms including the well-studied extragradient algorithm and optimistic gradient algorithm, it is not optimal for all gradient-based algorithms. We propose the accelerated optimistic gradient (AOG) algorithm, the first doubly optimal no-regret learning algorithm for smooth monotone games. Namely, our algorithm achieves both (i) the optimal $\mathcal{O}(\sqrt{T})$ regret in the adversarial setting under smooth and convex loss functions and (ii) the optimal $\mathcal{O}(\frac{1}{T})$ last-iterate convergence rate to a Nash equilibrium in multi-player smooth monotone games. As a byproduct of the accelerated last-iterate convergence rate, we further show that each player suffers only an $\mathcal{O}(\log T)$ individual worst-case dynamic regret, providing an exponential improvement over the previous state-of-the-art $\mathcal{O}(\sqrt{T})$ bound.

STOC Conference 2023 Conference Paper

On the Optimal Fixed-Price Mechanism in Bilateral Trade

• Yang Cai 0001
• Jinzhao Wu

We study the problem of social welfare maximization in bilateral trade, where two agents, a buyer and a seller, trade an indivisible item. The seminal result of Myerson and Satterthwaite shows that no incentive compatible and budget balanced (i.e., the mechanism does not run a deficit) mechanism can achieve the optimal social welfare in bilateral trade. Motivated by this impossibility result, we focus on approximating the optimal social welfare. We consider arguably the simplest form of mechanisms – the fixed-price mechanisms, where the designer offers trade at a fixed price to the seller and buyer. Besides the simple form, fixed-price mechanisms are also the only dominant strategy incentive compatible and budget balanced mechanisms in bilateral trade.

FOCS Conference 2023 Conference Paper

Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders

• Yang Cai 0001
• Ziyun Chen
• Jinzhao Wu

We study revenue maximization in multi-item auctions, where bidders have subadditive valuations over independent items [48]. Providing a simple mechanism that is approximately revenue-optimal in this setting is a major open problem in mechanism design [20]. In this paper, we present the first simple mechanism whose revenue is at least a constant fraction of the optimal revenue in multi-item auctions with subadditive bidders. Our mechanism is a simultaneous auction that incorporates either a personalized entry fee or a personalized reserve price per item. We prove that for any simultaneous auction that satisfies c-efficiency– a new property we propose, its revenue is at least an $O(c)$-approximation to the optimal revenue. We further show that both the simultaneous first-price and the simultaneous all-pay auction are $\frac{1}{2}$-efficient. Providing revenue guarantees for non-truthful simple mechanisms, e. g. , simultaneous auctions, in multi-dimensional environments has been recognized by Roughgarden et al. [47] as an important open question. Prior to our result, the only such revenue guarantees are due to Daskalakis et al. [30] for bidders who have additive valuations over independent items. Our result significantly extends the revenue guarantees of these non-truthful simple auctions to settings where bidders have combinatorial valuations.

STOC Conference 2022 Conference Paper

Computing simple mechanisms: Lift-and-round over marginal reduced forms

• Yang Cai 0001
• Argyris Oikonomou
• Mingfei Zhao

We study revenue maximization in multi-item multi-bidder auctions under the natural item-independence assumption – a classical problem in Multi-Dimensional Bayesian Mechanism Design. One of the biggest challenges in this area is developing algorithms to compute (approximately) optimal mechanisms that are not brute-force in the size of the bidder type space, which is usually exponential in the number of items in multi-item auctions. Unfortunately, such algorithms were only known for basic settings of our problem when bidders have unit-demand or additive valuations. In this paper, we significantly improve the previous results and design the first algorithm that runs in time polynomial in the number of items and the number of bidders to compute mechanisms that are O (1)-approximations to the optimal revenue when bidders have XOS valuations, resolving an open problem raised by Chawla, Miller and Cai, Zhao. Moreover, the computed mechanism has a simple structure: It is either a posted price mechanism or a two-part tariff mechanism. As a corollary of our result, we show how to compute an approximately optimal and simple mechanism efficiently using only sample access to the bidders’ value distributions. Our algorithm builds on two innovations that allow us to search over the space of mechanisms efficiently: (i) a new type of succinct representation of mechanisms – the marginal reduced forms, and (ii) a novel Lift-and-Round procedure that concavifies the problem.

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.

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.

FOCS Conference 2017 Conference Paper

Learning Multi-Item Auctions with (or without) Samples

• Yang Cai 0001
• Constantinos Daskalakis

We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of bidder valuations including unit-demand, additive, constrained additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly studied setting where sample access to the bidders' distributions over valuations is given, for both regular distributions and arbitrary distributions with bounded support. Here, our algorithms require polynomially many samples in the number of items and bidders. The second is a more general max-min learning setting that we introduce, where we are given “approximate distributions, ” and we seek to compute a mechanism whose revenue is approximately optimal simultaneously for all “true distributions” that are close to the ones we were given. These results are more general in that they imply the sample-based results, and are also applicable in settings where we have no sample access to the underlying distributions but have estimated them indirectly via market research or by observation of bidder behavior in previously run, potentially non-truthful auctions. All our results hold for valuation distributions satisfying the standard (and necessary) independence-across-items property. They also generalize and improve upon recent works of Goldner and Karlin [25] and Morgenstern and Roughgarden [32], which have provided algorithms that learn approximately optimal multi-item mechanisms in more restricted settings with additive, subadditive and unit-demand valuations using sample access to distributions. We generalize these results to the complete unit-demand, additive, and XOS setting, to i. i. d. subadditive bidders, and to the max-min setting. Our results are enabled by new uniform convergence bounds for hypotheses classes under product measures. Our bounds result in exponential savings in sample complexity compared to bounds derived by bounding the VC dimension and are of independent interest.

STOC Conference 2017 Conference Paper

Simple mechanisms for subadditive buyers via duality

• Yang Cai 0001
• Mingfei Zhao

We provide simple and approximately revenue-optimal mechanisms in the multi-item multi-bidder settings. We unify and improve all previous results, as well as generalize the results to broader cases. In particular, we prove that the better of the following two simple, deterministic and Dominant Strategy Incentive Compatible mechanisms, a sequential posted price mechanism or an anonymous sequential posted price mechanism with entry fee, achieves a constant fraction of the optimal revenue among all randomized, Bayesian Incentive Compatible mechanisms, when buyers' valuations are XOS over independent items. If the buyers' valuations are subadditive over independent items, the approximation factor degrades to O (log m ), where m is the number of items. We obtain our results by first extending the Cai-Devanur-Weinberg duality framework to derive an effective benchmark of the optimal revenue for subadditive bidders, and then analyzing this upper bound with new techniques.

STOC Conference 2016 Conference Paper

A duality based unified approach to Bayesian mechanism design

• Yang Cai 0001
• Nikhil R. Devanur
• 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., simple auctions for additive buyers, and posted-price mechanisms for unit-demand buyers. 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 VCG auction with per-bidder entry fees achieves a constant-factor of the optimal Bayesian IC revenue whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et. al. and Yao, and improving both approximation ratios (from 33.75 to 24 and 69 to 8). Finally, we show that this view also leads to improved structural characterizations in the Cai et. al. framework.

SODA Conference 2016 Conference Paper

On the Economic Efficiency of the Combinatorial Clock Auction

• Nicolas Bousquet 0001
• Yang Cai 0001
• Christoph Hunkenschröder
• Adrian Vetta

SODA Conference 2013 Conference Paper

Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations

• Yang Cai 0001
• Constantinos Daskalakis
• S. Matthew Weinberg

SODA Conference 2013 Conference Paper

Simple and Nearly Optimal Multi-Item Auctions

• Yang Cai 0001
• Zhiyi Huang 0002

FOCS Conference 2013 Conference Paper

Understanding Incentives: Mechanism Design Becomes Algorithm Design

• Yang Cai 0001
• Constantinos Daskalakis
• S. Matthew Weinberg

We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. Specifically, we give an approximation-preserving reduction from truthfully maximizing any objective under arbitrary feasibility constraints with arbitrary bidder types to (not necessarily truthfully) maximizing the same objective plus virtual welfare (under the same feasibility constraints). Our reduction is based on a fundamentally new approach: we describe a mechanism's behavior indirectly only in terms of the expected value it awards bidders for certain behavior, and never directly access the allocation rule at all. Applying our new approach to revenue, we exhibit settings where our reduction holds both ways. That is, we also provide an approximation-sensitive reduction from (non-truthfully) maximizing virtual welfare to (truthfully) maximizing revenue, and therefore the two problems are computationally equivalent. With this equivalence in hand, we show that both problems are NP-hard to approximate within any polynomial factor, even for a single monotone sub modular bidder. We further demonstrate the applicability of our reduction by providing a truthful mechanism maximizing fractional max-min fairness.

STOC Conference 2012 Conference Paper

An algorithmic characterization of multi-dimensional mechanisms

• Yang Cai 0001
• Constantinos Daskalakis
• S. Matthew Weinberg

We show that every feasible, Bayesian, multi-item multi-bidder mechanism for independent, additive bidders can be implemented as a mechanism that: (a) allocates every item independently of the other items; (b) for the allocation of each item it uses a strict ordering of all bidders' types; and allocates the item using a distribution over hierarchical mechanisms that iron this ordering into a non-strict ordering, and give the item uniformly at random to the bidders whose reported types dominate all other reported types according to the non-strict ordering. Combined with cyclic-monotonicity our results provide a characterization of feasible, Bayesian Incentive Compatible mechanisms in this setting. Our characterization is enabled by a new, constructive proof of Border's theorem [Border 1991], and a new generalization of this theorem to independent (but not necessarily identically distributed) bidders, improving upon the results of [Border 2007, Che-Kim-Mierendorf 2011]. For a single item and independent bidders, we show that every feasible reduced form auction can be implemented as a distribution over hierarchical mechanisms that are consistent with the same strict ordering of all bidders' types, which every mechanism in the support of the distribution irons to a non-strict ordering. We also give a polynomial-time algorithm for determining feasibility of a reduced form auction, or providing a separation hyperplane from the set of feasible reduced forms. To complete the picture, we provide polynomial-time algorithms to find and exactly sample from a distribution over hierarchical mechanisms consistent with a given feasible reduced form. All these results generalize to multi-item reduced form auctions for independent, additive bidders. Finally, for multiple items, additive bidders with hard demand constraints, and arbitrary value correlation across items or bidders, we give a proper generalization of Border's Theorem, and characterize feasible reduced form auctions as multi-commodity flows in related multi-commodity flow instances. We also show that our generalization holds for a broader class of feasibility constraints, including the intersection of any two matroids. As a corollary of our results we compute revenue-optimal, Bayesian Incentive Compatible (BIC) mechanisms in multi-item multi-bidder settings, when each bidder has arbitrarily correlated values over the items and additive valuations over bundles of items, and the bidders are independent. Our mechanisms run in time polynomial in the total number of bidder types (and {not} type profiles). This running time is polynomial in the number of bidders, but potentially exponential in the number of items. We improve the running time to polynomial in both the number of items and the number of bidders by using recent structural results on optimal BIC auctions in item-symmetric settings [Daskalakis-Weinberg 2011].

FOCS Conference 2012 Conference Paper

Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

• Yang Cai 0001
• Constantinos Daskalakis
• S. Matthew Weinberg

We provide a reduction from revenue maximization to welfare maximization in multidimensional Bayesian auctions with arbitrary - possibly combinatorial - feasibility constraints and independent bidders with arbitrary - possibly combinatorial-demand constraints, appropriately extending Myerson's single-dimensional result [21] to this setting. We also show that every feasible Bayesian auction - including in particular the revenue-optimal one - can be implemented as a distribution over virtual VCG allocation rules. A virtual VCG allocation rule has the following simple form: Every bidder's type ti is transformed into a virtual type fi(ti), via a bidder-specific function. Then, the allocation maximizing virtual welfare is chosen. Using this characterization, we show how to find and run the revenue-optimal auction given only black-box access to an implementation of the VCG allocation rule. We generalize this result to arbitrarily correlated bidders, introducing the notion of a second-order VCG allocation rule. Our results are computationally efficient for all multidimensional settings where the bidders are additive, or can be efficiently mapped to be additive, albeit the feasibility and demand constraints may still remain arbitrary combinatorial. In this case, our mechanisms run in time polynomial in the number of items and the total number of bidder types, but not type profiles. This is polynomial in the number of items, the number of bidders, and the cardinality of the support of each bidder's value distribution. For generic correlated distributions, this is the natural description complexity of the problem. The runtime can be further improved to polynomial in only the number of items and the number of bidders in itemsymmetric settings by making use of techniques from [15].

FOCS Conference 2011 Conference Paper

Extreme-Value Theorems for Optimal Multidimensional Pricing

• Yang Cai 0001
• Constantinos Daskalakis

We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed.) For all ϵ >; 0, we obtain a (1 + ϵ)-factor approximation to the optimal revenue in time polynomial, when the values are sampled from Monotone Hazard Rate (MHR) distributions, quasi-polynomial, when sampled from regular distributions, and polynomial in n poly(log r) when sampled from general distributions supported on a set [u min, ru min ]. We also provide an additive PTAS for all bounded distributions. Our algorithms are based on novel extreme value theorems for MHR and regular distributions, and apply probabilistic techniques to understand the statistical properties of revenue distributions, as well as to reduce the size of the search space of the algorithm. As a byproduct of our techniques, we establish structural properties of optimal solutions. We show that, for all ϵ >; 0, g(1/ϵ) distinct prices suffice to obtain a (1 + ϵ)-factor approximation to the optimal revenue for MHR distributions, where g(1/ϵ) is a quasi-linear function of 1/ϵ that does not depend on the number of items. Similarly, for all ϵ >; 0 and n >; 0, g(1/ϵ · log n) distinct prices suffice for regular distributions, where n is the number of items and g(·) is a polynomial function. Finally, in the i. i. d. MHR case, we show that, as long as the number of items is a sufficiently large function of 1/ϵ, a single price suffices to achieve a (1 + ϵ)-factor approximation. Our results represent significant progress to the single-bidder case of the multidimensional optimal mechanism design problem, following Myerson's celebrated work on optimal mechanism design [Myerson 1981].

SODA Conference 2011 Conference Paper

On Minmax Theorems for Multiplayer Games

• Yang Cai 0001
• Constantinos Daskalakis

CSL Conference 2011 Conference Paper

Tight Upper Bounds for Streett and Parity Complementation

• Yang Cai 0001
• 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 in mathematical logic, model-checking, program analysis and verification. For Streett complementation, a significant gap exists between the current lower bound 2^{Omega(n*log(n*k))} and upper bound 2^{O(n*k*log(n*k))}, where n is the state size, k is the number of Streett pairs, and k can be as large as 2^{n}. Determining the complexity of Streett complementation has been an open question since the late 80's. In this paper we show a complementation construction with upper bound 2^{O(n*log(n)+n*k*log(k))} for k=O(n) and 2^{O(n^{2}*log(n))} for k=Omega(n), which matches well the lower bound obtained in the paper arXiv: 1102. 2963. We also obtain a tight upper bound 2^{O(n*log(n))} for parity complementation.