9 papers
Improved Last-iterate Convergence Properties for the FLBR-MWU Dynamics
Michail Fasoulakis, Evangelos Markakis, Giorgos Roussakis +1
We revisit a variant of Multiplicative Weights Update (MWU), defined recently by Fasoulakis et al. [AISTATS; 2022], and denoted as Forward Looking Best Response MWU (FLBR-MWU). The…
Delegated Fair Division
Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis +2
Motivated by recently introduced problems on delegated resource allocation, we study a model of fair division, where a set of indivisible goods is to be allocated to some agents, e…
On Altruism and Spite in Bimatrix Games
Michail Fasoulakis, Leonidas Bakopoulos, Charilaos Akasiadis +1
One common assumption in game theory is that any player optimizes a utility function that takes into account only its own payoff. However, it has long been observed that in real li…
A Descent-based method on the Duality Gap for solving zero-sum games
Michail Fasoulakis, Evangelos Markakis, Giorgos Roussakis +1
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…
Revisit the Arimoto-Blahut algorithm: New Analysis with Approximation
Michail Fasoulakis, Konstantinos Varsos, Apostolos Traganitis
By the seminal paper of Claude Shannon \cite{Shannon48}, the computation of the capacity of a discrete memoryless channel has been considered as one of the most important and funda…
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
Argyrios Deligkas, Michail Fasoulakis, Evangelos Markakis
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 -ap…