6 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…
Online Budget-Feasible Mechanism Design with Predictions
Georgios Amanatidis, Evangelos Markakis, Christodoulos Santorinaios +3
Augmenting the input of algorithms with predictions is an algorithm design paradigm that suggests leveraging a (possibly erroneous) prediction to improve worst-case performance gua…
Do Not Discretize, Optimize: Almost Greedy Fictitious Play
Evangelos Markakis, Christodoulos Santorinaios
Our work revolves around Fictitious Play, one of the first iterative methods that is known to converge to a Nash equilibrium in zero-sum games. In recent years, there has been a re…
Improved Approximation Guarantees for Groupwise Maximin Share Fairness
Georgios Amanatidis, Anna Korfiati, Evangelos Markakis +1
We study the problem of fairly allocating a set of indivisible goods to a set of agents with additive valuation functions. We focus on the very demanding notion of \textit{grou…
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…
On The Pursuit of EFX for Chores: Non-Existence and Approximations
Vasilis Christoforidis, Christodoulos Santorinaios
We study the problem of fairly allocating a set of chores to a group of agents. The existence of envy-free up to any item (EFX) allocations is a long-standing open question for bot…