In a game of Network Restoration Games With Quotas, there is an underlying graph where a subset of its edges have to be restored by a set of agents. Each agent has a creation cost for each such edge, a traversal cost for every edge of the graph, and in addition they have a quota on the number of edges they have to restore. Then, given a set of edges that fulfill the quota, the cost of an agent is the cost of creating these edges, plus the cost of reaching them, i.e., the traversal cost. We prove that any cost-minimizing allocation is swap-stable, i.e., there is no profitable exchange of edges between any pair of agents, but computing one is hard even on trees. We complement this by designing an algorithm that finds a swap-stable allocation on trees in polynomial time and we quantify its cost against the optimal one.

We focus on the design of algorithms for finding equilibria in 2-player zero-sum games. Although it is well known that such problems can be solved by a single linear program, there has been a surge of interest in recent years for simpler algorithms, motivated in part by applications in machine learning. Our work proposes such a method, inspired by the observation that the duality gap (a standard metric for evaluating convergence in min-max optimization problems) is a convex function for bilinear zero-sum games. To this end, we analyze a descent-based approach, variants of which have also been used as a subroutine in a series of algorithms for approximating Nash equilibria in general non-zero-sum games. In particular, we study a steepest descent approach, by finding the direction that minimises the directional derivative of the duality gap function. Our main theoretical result is that the derived algorithms achieve a geometric decrease in the duality gap until we reach an approximate equilibrium. Finally, we complement this with an experimental evaluation, which provides promising findings. Our algorithm is comparable with (and in some cases outperforms) some of the standard approaches for solving 0-sum games, such as OGDA (Optimistic Gradient Descent/Ascent), even with thousands of available strategies per player.

Since the seminal PPAD-completeness result for computing a Nash equilibrium even in two-player games, an important line of research has focused on relaxations achievable in polynomial time. In this paper, we consider the notion of ε-well-supported Nash equilibrium, where ε ∈ [0,1] corresponds to the approximation guarantee. Put simply, in an ε-well-supported equilibrium, every player chooses with positive probability actions that are within ε of the maximum achievable payoff, against the other player's strategy. Ever since the initial approximation guarantee of 2/3 for well-supported equilibria, which was established more than a decade ago, the progress on this problem has been extremely slow and incremental. Notably, the small improvements to 0.6608, and finally to 0.6528, were achieved by algorithms of growing complexity. Our main result is a simple and intuitive algorithm, that improves the approximation guarantee to 1/2. Our algorithm is based on linear programming and in particular on exploiting suitably defined zero-sum games that arise from the payoff matrices of the two players. As a byproduct, we show how to achieve the same approximation guarantee in a query-efficient way. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.07007

Abstract. Since the seminal PPAD -completeness result for computing a Nash equilibrium even in two-player games, an important line of research has focused on relaxations achievable in polynomial time. In this paper, we consider the notion of an [Formula: see text]-well-supported Nash equilibrium, where [Formula: see text] corresponds to the approximation guarantee. Put simply, in an [Formula: see text]-well-supported equilibrium, every player chooses with positive probability actions that are within [Formula: see text] of the maximum achievable payoff against the other player’s strategy. Ever since the initial approximation guarantee of 2/3 for well-supported equilibria, which was established more than a decade ago, the progress on this problem has been extremely slow and incremental. Notably, the small improvements to 0.6608, and finally to 0.6528, were achieved by algorithms of growing complexity. Our main result is a simple and intuitive algorithm that improves the approximation guarantee to 1/2. Our algorithm is based on linear programming and in particular on exploiting suitably defined zero-sum games that arise from the payoff matrices of the two players. As a byproduct, we show how to achieve the same approximation guarantee in a query-efficient way.

Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute ε-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis [ 38 ], with an approximation guarantee of (0.3393+δ), remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a \((\frac{1}{3}+\delta)\) -Nash equilibrium, for any constant δ > 0. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of [ 38 ], and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.

In this article, we propose a novel loss function for training generative adversarial networks (GANs) aiming toward deeper theoretical understanding as well as improved stability and performance for the underlying optimization problem. The new loss function is based on cumulant generating functions (CGFs) giving rise to Cumulant GAN. Relying on a recently derived variational formula, we show that the corresponding optimization problem is equivalent to Rényi divergence minimization, thus offering a (partially) unified perspective of GAN losses: the Rényi family encompasses Kullback–Leibler divergence (KLD), reverse KLD, Hellinger distance, and$\chi ^{2}$-divergence. Wasserstein GAN is also a member of cumulant GAN. In terms of stability, we rigorously prove the linear convergence of cumulant GAN to the Nash equilibrium for a linear discriminator, Gaussian distributions, and the standard gradient descent ascent algorithm. Finally, we experimentally demonstrate that image generation is more robust relative to Wasserstein GAN and it is substantially improved in terms of both inception score (IS) and Fréchet inception distance (FID) when both weaker and stronger discriminators are considered.

Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games. The proposed method, which can be formally considered as a variant of Optimistic Mirror Descent (Mertikopoulos et al., 2019), uses a large learning rate for the intermediate gradient step which essentially leads to computing (approximate) best response strategies against the profile of the previous iteration. Although counter-intuitive at first sight due to the irrationally large, for an iterative algorithm, intermediate learning step, we prove that the method guarantees last-iterate convergence to an equilibrium. Particularly, we show that the algorithm reaches first an $\eta^{1/\rho}$-approximate Nash equilibrium, with $\rho > 1$, by decreasing the Kullback-Leibler divergence of each iterate by at least $\Omega(\eta^{1+\frac{1}{\rho}})$, for sufficiently small learning rate $\eta$, until the method becomes a contracting map, and converges to the exact equilibrium. Furthermore, we perform experimental comparisons with the optimistic variant of the multiplicative weights update method, by Daskalakis and Panageas (2019) and show that our algorithm has significant practical potential since it offers substantial gains in terms of accelerated convergence.

Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute $\varepsilon$-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis, with an approximation guarantee of $(0.3393+δ)$, remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a $(\frac{1}{3}+δ)$-Nash equilibrium, for any constant $δ>0$. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of Tsaknakis and Spirakis, and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.

We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players’ payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then computes an approximate Nash equilibrium using only limited communication between the players. Our method gives improved bounds on the complexity of computing approximate Nash equilibria in a number of different settings. Firstly, it gives a polynomial-time algorithm for computing approximate well supported Nash equilibria (WSNE) that always finds a 0.6528-WSNE, beating the previous best guarantee of 0.6608. Secondly, since our algorithm solves the two LPs separately, it can be applied to give an improved bound in the limited communication setting, giving a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE, which beats the previous best known guarantee of 0.732. It can also be applied to the case of approximate Nash equilibria, where we obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and always finds a 0.382-approximate Nash equilibrium, which improves the previous best guarantee of 0.438. Finally, the method can also be applied in the query complexity setting to give an algorithm that makes $$O(n \log n)$$ payoff queries and always finds a 0.6528-WSNE, which improves the previous best known guarantee of 2/3.

We consider the Gaussian interference channel as a non-cooperative game taking into account the cost of the transmission. We study the conditions of the existence of a pure Nash equilibrium. Particularly, for the many-user case we give sufficient conditions that lead to a Nash equilibrium, and for the two-user case we exhaustively describe the conditions of the existence and the uniqueness of a pure Nash equilibrium and we show the existence of best-response dynamics that converge to one of them.