EC@EC

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 special cases, including markets with PLC utilities, markets with satiation, and matching markets. For the special case of PLC utilities, although the problem is PPAD-hard, Devanur and Kannan (FOCS 2008) gave a polynomial-time algorithm when the number of items is constant. Our main result is a fixed parameter approximation scheme for computing an approximate equilibrium, where the parameters are the number of agents and the approximation accuracy. This provides an answer to an open question by Devanur and Kannan for PLC utilities, and gives a simpler and faster algorithm for matching markets as the one by Alaei, Jalaly and Tardos (EC 2017).

The main technical idea is to work with the stronger concept of thrifty equilibria, and approximating the input utility functions by 'robust' utilities that have favorable marginal properties. With some restrictions, the results also extend to the Arrow-Debreu exchange market model.

Based on joint work with Jugal Garg and Yixin Tao.
arXiv

We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problems with polynomial-time verifiable solutions. In particular, we construct a "pseudogate", coined the linear-OPT-gate, which can be used as a "plug-and-play" component in a linear arithmetic circuit, as an integral component of the "Linear-FIXP" equivalent definition of the class. The linear-OPT-gate can solve several convex optimization programs, including quadratic programs, which often appear organically in the simplest existence proofs for these problems. This effectively transforms existence proofs to PPAD-membership proofs, and consequently establishes the existence of solutions described by rational numbers.

Using the linear-OPT-gate, we are able to significantly simplify and generalize almost all known PPAD-membership proofs for finding exact solutions in the application domains of game theory, competitive markets, auto-bidding auctions, and fair division, as well as to obtain new PPAD-membership results for problems in these domains.

Based on joint work with Aris Filos-Ratsikas, Kasper Høgh, and Alexandros Hollender.

We present a fully polynomial-time approximation scheme (FPTAS) for computing equilibria in congestion games, under smoothed running-time analysis. More precisely, we prove that if the resource costs of a congestion game are randomly perturbed by independent noises, whose density is at most ϕ, then any sequence of (1+ε)-improving dynamics will reach an (1+ε)-approximate pure Nash equilibrium (PNE) after an expected number of steps which is strongly polynomial in 1/ε, ϕ, and the size of the game's description. Our results establish a sharp contrast to the traditional worst-case analysis setting, where it is known that better-response dynamics take exponentially long to converge to α-approximate PNE, for any constant factor α≥1. As a matter of fact, computing α-approximate PNE in congestion games is PLS-hard.

We demonstrate how our analysis can be applied to various different models of congestion games including general, step-function, and polynomial cost, as well as fair cost-sharing games (where the resource costs are decreasing). It is important to note that our bounds do not depend explicitly on the cardinality of the players' strategy sets, and thus the smoothed FPTAS is readily applicable to network congestion games as well.

arXiv

Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before.

Based on joint work with Zhile Jiang.
arXiv

We introduce the use of generative adversarial learning to compute equilibria in general game-theoretic settings, specifically the generalized Nash equilibrium (GNE) in pseudo-games, and its specific instantiation as the competitive equilibrium (CE) in Arrow-Debreu competitive economies. Pseudo-games are a generalization of games in which players' actions affect not only the payoffs of other players but also their feasible action spaces. Although the computation of GNE and CE is intractable in the worst-case, i.e., PPAD-hard, in practice, many applications only require solutions with high accuracy in expectation over a distribution of problem instances. We introduce Generative Adversarial Equilibrium Solvers (GAES): a family of generative adversarial neural networks that can learn GNE and CE from only a sample of problem instances. We provide computational and sample complexity bounds, and apply the framework to finding Nash equilibria in normal-form games, CE in Arrow-Debreu competitive economies, and GNE in an environmental economic model of the Kyoto mechanism.

Based on joint work with David C. Parkes, Ian Gemp, Luke Marris, Georgios Piliouras, Romuald Elie, Guy Lever, and Andrea Tacchetti.
arXiv

In a Fisher market, agents (users) spend a budget of (artificial) currency to buy goods that maximize their utilities while a central planner sets prices on capacity-constrained goods such that the market clears. However, the efficacy of pricing schemes in achieving an equilibrium outcome in Fisher markets typically relies on complete knowledge of users' budgets and utilities and requires that transactions happen in a static market wherein all users are present simultaneously.

As a result, we study an online variant of Fisher markets, wherein budget-constrained users with privately known utility and budget parameters, drawn i.i.d. from a distribution D, enter the market sequentially. In this setting, we develop an algorithm that adjusts prices solely based on observations of user consumption, i.e., revealed preference feedback, and achieves a regret and capacity violation of O(√n), where n is the number of users and the good capacities scale as O(n). Here, our regret measure is the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an offline oracle with complete information on users' budgets and utilities. To establish the efficacy of our approach, we show that any uniform (static) pricing algorithm, including one that sets expected equilibrium prices with complete knowledge of the distribution D, cannot achieve both a regret and constraint violation of less than Ω(√n). While our revealed preference algorithm requires no knowledge of the distribution D, we show that if D is known, then an adaptive variant of expected equilibrium pricing achieves O(log(n)) regret and constant capacity violation for discrete distributions. Finally, we present numerical experiments to demonstrate the performance of our revealed preference algorithm relative to several benchmarks.

Based on joint work with Yinyu Ye.
arXiv

Darshan Chakrabarti:  Block-Coordinate Methods and Restarting for Solving Extensive-Form Games
Denizalp Goktas:  Fisher Markets with Social Influence
Alexander Grosz:  On the Smoothed Complexity of Combinatorial Local Search
Keegan Harris: Meta-Learning in Games
Devansh Jalota:  Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements
Luke Marris:  Equilibrium-Invariant Embedding, Metric Space, and Fundamental Set of 2×2 Normal-Form Games
Luke Marris:  Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers
Emanuel Tewolde: The Computational Complexity of Single-Player Imperfect-Recall Games
Brian Hu Zhang: Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games
Brian Hu Zhang: Steering No-Regret Learners to Optimal Equilibria

The current state-of-the-art methods for showing inapproximability in PPAD arise from the ε-Generalized-Circuit (ε-GCircuit) problem. Rubinstein (2018) showed that there exists a small unknown constant ε for which ε-GCircuit is PPAD-hard, and subsequent work has shown hardness results for other problems in PPAD by using ε-GCircuit as an intermediate problem.

We introduce Pure-Circuit, a new intermediate problem for PPAD, which can be thought of as ε-GCircuit pushed to the limit as ε→1, and we show that the problem is PPAD-complete. We then prove that ε-GCircuit is PPAD-hard for all ε<0.1 by a reduction from Pure-Circuit, and thus strengthen all prior work that has used GCircuit as an intermediate problem from the existential-constant regime to the large-constant regime.

We show that stronger inapproximability results can be derived by reducing directly from Pure-Circuit. In particular, we prove tight inapproximability results for computing ε-well-supported Nash equilibria in two-action polymatrix games, as well as for finding approximate equilibria in threshold games.

Based on joint work with Argyrios Deligkas, Alexandros Hollender, and Themistoklis Melissourgos.
arXiv

Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main computational challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery rates form the set of fixed points of a simple function, and that these fixed points can be irrational. Furthermore, Schuldenzucker et al. (2016) have shown that finding a weakly (or "almost") approximate (rational) fixed point is PPAD-complete. We further study the clearing problem from the point of view of approximation strength. On this basis, we examine the complexity of finding an exact solution and a strongly (or "near") approximate solution. We establish FIXP-completeness and FIXP_a-completeness for these solution types respectively. Moreover, leveraging a novel toolkit called "Pure-Circuit", introduced by Deligkas et al. (FOCS'22) to show large constant inapproximability in PPAD, we prove that finding weakly (or "almost") approximate solutions is PPAD-hard, within a factor close to 5% which is roughly seven times better than the current state-of-the-art.

Based on joint work with Bart de Keijzer and Carmine Ventre.

Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in this game is known as a pacing equilibrium. In this work, we show that the problem of finding an approximate pacing equilibrium is PPAD-complete for second-price auctions. This resolves an open question of Conitzer et al. [2021]. As a consequence of our hardness result, we show that the tatonnement-style budget-management dynamics introduced by Borgs et al. [2007] are unlikely to converge efficiently for repeated second-price auctions. This disproves a conjecture by Borgs et al. [2007], under the assumption that the complexity class PPAD is not equal to P. Our hardness result also implies the existence of a refinement of supply-aware market equilibria which is hard to compute with simple linear utilities.

Based on joint work with Xi Chen and Christian Kroer.
arXiv

We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.

Based on joint work with Xi Chen.
arXiv