3 citations · 13 across the 15 of their papers we have counts for
15 papers
Optimal Pricing with Unreliable Signals
Zhihao Gavin Tang, Yixin Tao, Shixin Wang
We study a single-buyer pricing problem with unreliable side information, motivated by the increasing use of AI-assisted decision-making and LLM-based predictions. The seller obser…
Proportional Response Dynamics in Gross Substitutes Markets
Yun Kuen Cheung, Richard Cole, Yixin Tao
Proportional response is a well-established distributed algorithm which has been shown to converge to competitive equilibria in both Fisher and Arrow-Debreu markets, for various su…
A First Order Method for Linear Programming Parameterized by Circuit Imbalance
Richard Cole, Christoph Hertrich, Yixin Tao +1
Various first order approaches have been proposed in the literature to solve Linear Programming (LP) problems, recently leading to practically efficient solvers for large-scale LPs…
Mode Connectivity in Auction Design
Christoph Hertrich, Yixin Tao, László A. Végh
Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable eco…
Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
Jugal Garg, Yixin Tao, László A. Végh
We study the equilibrium computation problem in the Fisher market model with constrained piecewise linear concave (PLC) utilities. This general class captures many well-studied spe…
Selecting a Match: Exploration vs Decision
Ishan Agarwal, Richard Cole, Yixin Tao
In a dynamic matching market, such as a marriage or job market, how should agents balance accepting a proposed match with the cost of continuing their search? We consider this prob…
Chaos of Learning Beyond Zero-sum and Coordination via Game Decompositions
Yun Kuen Cheung, Yixin Tao
Machine learning processes, e.g. ''learning in games'', can be viewed as non-linear dynamical systems. In general, such systems exhibit a wide spectrum of behaviors, ranging from s…
Balancing the Robustness and Convergence of Tatonnement
Richard Cole, Yixin Tao
A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify robust natural dist…
On the Existence of Pareto Efficient and Envy Free Allocations
Richard Cole, Yixin Tao
Envy-freeness and Pareto Efficiency are two major goals in welfare economics. The existence of an allocation that satisfies both conditions has been studied for a long time. Whethe…
Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism
Yun Kuen Cheung, Richard Cole, Yixin Tao
Several works have shown linear speedup is achieved by an asynchronous parallel implementation of stochastic coordinate descent so long as there is not too much parallelism. More s…
Fully Asynchronous Stochastic Coordinate Descent: A Tight Lower Bound on the Parallelism Achieving Linear Speedup
Yun Kuen Cheung, Richard Cole, Yixin Tao
We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD)…
An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent
Richard Cole, Yixin Tao
Gradient descent, and coordinate descent in particular, are core tools in machine learning and elsewhere. Large problem instances are common. To help solve them, two orthogonal app…
Dynamics of Distributed Updating in Fisher Markets
Yun Kuen Cheung, Richard Cole, Yixin Tao
A major goal in Algorithmic Game Theory is to justify equilibrium concepts from an algorithmic and complexity perspective. One appealing approach is to identify natural distributed…
Large Market Games with Near Optimal Efficiency
Richard Cole, Yixin Tao
As is well known, many classes of markets have efficient equilibria, but this depends on agents being non-strategic, i.e. that they declare their true demands when offered goods at…
Generalized Second Price Auction with Probabilistic Broad Match
Wei Chen, Di He, Tie-Yan Liu +3
Generalized Second Price (GSP) auctions are widely used by search engines today to sell their ad slots. Most search engines have supported broad match between queries and bid keywo…