13 papers
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…
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…
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…