3 citations · 10 across the 24 of their papers we have counts for
18 papers · 1 filter
CLS Hardness of 2D Min-Max Optimization with Product Constraints
Alkis Kalavasis, Panagiotis Patsilinakos, Stratis Skoulakis +1
We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For…
Revenue Guarantee of Anonymous Pricing for Mixed Bidders:Bridging Value and Utility Maximizers
Zhile Jiang, Stratis Skoulakis
Mechanism design increasingly faces heterogeneous environments containing both traditional utility maximizers and value maximizers, the latter of whom seek to maximize acquired val…
A Unified Framework for Uniform-Price Resource Allocation Mechanisms
Ioannis Caragiannis, Dimitris Fotakis, Stratis Skoulakis
Mechanisms for allocating a divisible resource among strategic agents have been widely studied. The prominent paradigm is the proportional (Kelly) mechanism, which elicits a scalar…
Revenue Guarantees of No-Swap-Regret Dynamics in First Price Auctions
Anders Bo Ipsen, Stratis Skoulakis
We study the revenue of approximate correlated equilibrium in discrete first price auctions - the set of allowable bids is for some $k…
Revenue Guarantees in Autobidding Platforms
Ioannis Caragiannis, Anders Bo Ipsen, Stratis Skoulakis
Motivated by autobidding systems in online advertising, we study revenue maximization in markets with divisible goods and budget-constrained buyers with linear valuations. Our aim…
The Welfare Gap of Strategic Storage: Universal Bounds and Price Non-Linearity
Zhile Jiang, Xinhao Nie, Stratis Skoulakis
This paper studies the efficiency of battery storage operations in electricity markets by comparing the social welfare gain achieved by a central planner to that of a decentralized…
Rethinking Pricing in Energy Markets: Pay-as-Bid vs Pay-as-Clear
Ioannis Caragiannis, Zhile Jiang, Stratis Skoulakis
The design of energy markets is a subject of ongoing debate, particularly concerning the choice between the widely adopted Pay-as-Clear (PC) pricing mechanism and the alternative P…
Continuous-Time Analysis of Heavy Ball Momentum in Min-Max Games
Yi Feng, Kaito Fujii, Stratis Skoulakis +2
Since Polyak's pioneering work, heavy ball (HB) momentum has been widely studied in minimization. However, its role in min-max games remains largely unexplored. As a key component…
Polynomial Convergence of Bandit No-Regret Dynamics in Congestion Games
Leello Dadi, Ioannis Panageas, Stratis Skoulakis +2
We introduce an online learning algorithm in the bandit feedback model that, once adopted by all agents of a congestion game, results in game-dynamics that converge to an -appro…
Exponential Lower Bounds for Fictitious Play in Potential Games
Ioannis Panageas, Nikolas Patris, Stratis Skoulakis +1
Fictitious Play (FP) is a simple and natural dynamic for repeated play with many applications in game theory and multi-agent reinforcement learning. It was introduced by Brown (194…
Semi Bandit Dynamics in Congestion Games: Convergence to Nash Equilibrium and No-Regret Guarantees
Ioannis Panageas, Stratis Skoulakis, Luca Viano +2
In this work, we introduce a new variant of online gradient descent, which provably converges to Nash Equilibria and simultaneously attains sublinear regret for the class of conges…
Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps
Volkan Cevher, Georgios Piliouras, Ryann Sim +1
In this paper we present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems while requiring a simple and intuitive analysis. Simila…
Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games
Georgios Piliouras, Lillian Ratliff, Ryann Sim +1
The study of learning in games has thus far focused primarily on normal form games. In contrast, our understanding of learning in extensive form games (EFGs) and particularly in EF…
Online Learning in Periodic Zero-Sum Games
Tanner Fiez, Ryann Sim, Stratis Skoulakis +2
A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build…
Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update
Georgios Piliouras, Ryann Sim, Stratis Skoulakis
In this paper, we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU) for regret minimization in general games. CMWU effectively corresponds to…
Transaction Fees on a Honeymoon: Ethereum's EIP-1559 One Month Later
Daniël Reijsbergen, Shyam Sridhar, Barnabé Monnot +3
Ethereum Improvement Proposal (EIP) 1559 was recently implemented to transform Ethereum's transaction fee market. EIP-1559 utilizes an algorithmic update rule with a constant learn…
Dynamical Analysis of the EIP-1559 Ethereum Fee Market
Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen +2
Participation in permissionless blockchains results in competition over system resources, which needs to be controlled with fees. Ethereum's current fee mechanism is implemented vi…
Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games
Stratis Skoulakis, Tanner Fiez, Ryann Sim +2
The predominant paradigm in evolutionary game theory and more generally online learning in games is based on a clear distinction between a population of dynamic agents that interac…