1 citations · 3 across the 12 of their papers we have counts for
12 papers
On algorithmically boosting fixed-point computations
Ioannis Avramopoulos, Nikolaos Vasiloglou
The main topic of this paper are algorithms for computing Nash equilibria. We cast our particular methods as instances of a general algorithmic abstraction, namely, a method we cal…
A dynamic that evolves toward a Nash equilibrium
Ioannis Avramopoulos
In this paper, we study an exponentiated multiplicative weights dynamic based on Hedge, a well-known algorithm in theoretical machine learning and algorithmic game theory. The empi…
Poising on Ariadne's thread: An algorithm for computing a maximum clique in polynomial time
Ioannis Avramopoulos
In this paper, we present a polynomial-time algorithm for the maximum clique problem, which implies P = NP. Our algorithm is based on a continuous game-theoretic representation of…
Evolution toward a Nash equilibrium
Ioannis Avramopoulos
In this paper, we study the dynamic behavior of Hedge, a well-known algorithm in theoretical machine learning and algorithmic game theory. The empirical average (arithmetic mean) o…
On incremental deployability
Ioannis Avramopoulos
Motivated by the difficulty of effecting fundamental change in the architecture of the Internet, in this paper, we study from a theoretical perspective the question of how individu…
Multiplicative weights, equalizers, and P=PPAD
Ioannis Avramopoulos
We show that, by using multiplicative weights in a game-theoretic thought experiment (and an important convexity result on the composition of multiplicative weights with the relati…
Evolutionary stability implies asymptotic stability under multiplicative weights
Ioannis Avramopoulos
We show that evolutionarily stable states in general (nonlinear) population games (which can be viewed as continuous vector fields constrained on a polytope) are asymptotically sta…
Jump-starting coordination in a stag hunt: Motivation, mechanisms, and their analysis
Ioannis Avramopoulos
The stag hunt (or assurance game) is a simple game that has been used as a prototype of a variety of social coordination problems (ranging from the social contract to the adoption…
On the computational complexity of evolution
Ioannis Avramopoulos
It is well-known that the problem of recognizing an ESS in a symmetric bimatrix game is coNP-complete. In this paper, we show that recognizing an ESS even in doubly symmetric bimat…
Multiplicative weights in monotropic games
Ioannis Avramopoulos
We introduce a new class of population games that we call monotropic; these are games characterized by the presence of a unique globally neutrally stable Nash equilibrium. Monotrop…
A general theory of equilibrium behavior
Ioannis Avramopoulos
Economists were content with the concept of the Nash equilibrium as game theory's solution concept until Daskalakis, Goldberg, and Papadimitriou showed that finding a Nash equilibr…
Architectural innovation: A game-theoretic approach
Ioannis Avramopoulos
In this paper, we view the Internet under a game-theoretic lens in an effort to explain and overcome the Internet's innovation slump. Game Theory is used to model Internet environm…