53 citations · 141 across the 28 of their papers we have counts for
37 papers
Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents
Paul W. Goldberg, Alexandros Hollender, Giannis Tyrovolas
The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate str…
The Complexity of Min-Max Optimization for Quadratic Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are mu…
On Cutting Cakes and Crossing Curves
Alexandros Hollender, Gilbert Maystre, Kilian Risse
We consider the classic envy-free cake-cutting problem where the goal is to cut and allocate a divisible resource among a set of agents in a way that avoids any envy between them.…
Min-Max Optimization Requires Exponentially Many Queries
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We study the query complexity of min-max optimization of a nonconvex-nonconcave function over . We show that, given oracle access to and to its grad…
Constant Inapproximability for Fisher Markets
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We study the problem of computing approximate market equilibria in Fisher markets with separable piecewise-linear concave (SPLC) utility functions. In this setting, the problem was…
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We study the problem of computing a competitive equilibrium with approximately optimal bundles in Fisher markets with separable piecewise-linear concave (SPLC) utility functions, m…
Efficient Equilibrium Computation in Symmetric First-Price Auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +1
We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values…
Computing Equilibrium Points of Electrostatic Potentials
Abheek Ghosh, Paul W. Goldberg, Alexandros Hollender
We study the computation of equilibrium points of electrostatic potentials: locations in space where the electrostatic force arising from a collection of charged particles vanishes…
Discrepancy Beyond Additive Functions with Applications to Fair Division
Alexandros Hollender, Pasin Manurangsi, Raghu Meka +1
We consider a setting where we have a ground set together with real-valued set functions , and the goal is to partition into two sets such that $…
Equilibrium Computation in First-Price Auctions with Correlated Priors
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +1
We consider the computational complexity of computing Bayes-Nash equilibria in first-price auctions, where the bidders' values for the item are drawn from a general (possibly corre…
The Complexity of Symmetric Bimatrix Games with Common Payoffs
Abheek Ghosh, Alexandros Hollender
We study symmetric bimatrix games that also have the common-payoff property, i.e., the two players receive the same payoff at any outcome of the game. Due to the symmetry property,…
The Complexity of Two-Team Polymatrix Games with Independent Adversaries
Alexandros Hollender, Gilbert Maystre, Sai Ganesh Nagarajan
Adversarial multiplayer games are an important object of study in multiagent learning. In particular, polymatrix zero-sum games are a multiplayer setting where Nash equilibria are…
Tight Inapproximability of Nash Equilibria in Public Goods Games
Jérémi Do Dinh, Alexandros Hollender
We study public goods games, a type of game where every player has to decide whether or not to produce a good which is public, i.e., neighboring players can also benefit from it. S…
On the Computation of Equilibria in Discrete First-Price Auctions
Aris Filos-Ratsikas, Yiannis Giannakopoulos, Alexandros Hollender +1
We study the computational complexity of computing Bayes-Nash equilibria in first-price auctions with discrete value distributions and discrete bidding space, under general subject…
PPAD-membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization
Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh +1
We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problem…
The Complexity of Computing KKT Solutions of Quadratic Programs
John Fearnley, Paul W. Goldberg, Alexandros Hollender +1
It is well known that solving a (non-convex) quadratic program is NP-hard. We show that the problem remains hard even if we are only looking for a Karush-Kuhn-Tucker (KKT) point, i…
Envy-Free Cake-Cutting for Four Agents
Alexandros Hollender, Aviad Rubinstein
In the envy-free cake-cutting problem we are given a resource, usually called a cake and represented as the interval, and a set of agents with heterogeneous preferences…
The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
Alexandros Hollender, Manolis Zampetakis
Finding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions over unrestricted -dimensional dom…
The Frontier of Intractability for EFX with Two Agents
Paul W. Goldberg, Kasper Høgh, Alexandros Hollender
We consider the problem of sharing a set of indivisible goods among agents in a fair manner, namely such that the allocation is envy-free up to any good (EFX). We focus on the prob…
Tight Inapproximability for Graphical Games
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied appro…
Pure-Circuit: Tight Inapproximability for PPAD
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
The current state-of-the-art methods for showing inapproximability in PPAD arise from the -Generalized-Circuit (-GCircuit) problem. Rubinstein (2018) show…
Separations in Proof Complexity and TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
It is well-known that Resolution proofs can be efficiently simulated by Sherali-Adams (SA) proofs. We show, however, that any such simulation needs to exploit huge coefficients: Re…
Further Collapses in TFNP
Mika Göös, Alexandros Hollender, Siddhartha Jain +4
We show . Here the class consists of all total search problems that reduce to the End-of-Potential-Line problem, which…
Constant Inapproximability for PPA
Argyrios Deligkas, John Fearnley, Alexandros Hollender +1
In the -Consensus-Halving problem, we are given probability measures on the interval , and the goal is to partition into two parts…