Cover Image

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Deligkas, Argyrios, Fearnley, John, Hollender, Alexandros, Melissourgos, Themistoklis
Format:	Preprint
Published:	2026
Subjects:	Computer Science and Game Theory Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pure-Circuit: Tight Inapproximability for PPAD
by: Deligkas, Argyrios, et al.
Published: (2022)

Constant Inapproximability for Fisher Markets
by: Deligkas, Argyrios, et al.
Published: (2026)

Constant Inapproximability for PPA
by: Deligkas, Argyrios, et al.
Published: (2022)

Pizza Sharing is PPA-hard
by: Deligkas, Argyrios, et al.
Published: (2020)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
by: Babichenko, Yakov, et al.
Published: (2015)

On the Smoothed Complexity of Combinatorial Local Search
by: Giannakopoulos, Yiannis, et al.
Published: (2022)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
by: Ghosh, Abheek, et al.
Published: (2024)

Envy-Free Cake-Cutting for Four Agents
by: Hollender, Alexandros, et al.
Published: (2023)

Tight Inapproximability of Nash Equilibria in Public Goods Games
by: Dinh, Jérémi Do, et al.
Published: (2024)

On the Computation of Equilibria in Discrete First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2024)

Equilibrium Computation in First-Price Auctions with Correlated Priors
by: Filos-Ratsikas, Aris, et al.
Published: (2025)

Multiplicative weights, equalizers, and P=PPAD
by: Avramopoulos, Ioannis
Published: (2016)

EF1 and EFX Orientations
by: Deligkas, Argyrios, et al.
Published: (2024)

Distributed Agent-Constrained Truthful Facility Location
by: Deligkas, Argyrios, et al.
Published: (2026)

Agent-Constrained Truthful Facility Location Games
by: Deligkas, Argyrios, et al.
Published: (2024)

Computing Equilibrium Points of Electrostatic Potentials
by: Ghosh, Abheek, et al.
Published: (2025)

Efficient Equilibrium Computation in Symmetric First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2026)

The Complexity of Sparse Win-Lose Bimatrix Games
by: Batziou, Eleni, et al.
Published: (2026)

Truthful Interval Covering
by: Deligkas, Argyrios, et al.
Published: (2023)

Online EFX Allocations with Predictions
by: Melissourgos, Themistoklis, et al.
Published: (2025)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

The Computational Complexity of the Housing Market
by: Lock, Edwin, et al.
Published: (2024)

Hardness of Approximate Hylland-Zeckhauser Equilibria
by: Braverman, Mark, et al.
Published: (2026)

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
by: Gao, Ruiquan, et al.
Published: (2024)

The Complexity of Fair Division of Indivisible Items with Externalities
by: Deligkas, Argyrios, et al.
Published: (2023)

Mechanism Design with Outliers and Predictions
by: Deligkas, Argyrios, et al.
Published: (2025)

The Complexity of Two-Team Polymatrix Games with Independent Adversaries
by: Hollender, Alexandros, et al.
Published: (2024)

Stability in Distance Preservation Games on Graphs
by: Deligkas, Argyrios, et al.
Published: (2026)

Balanced and Fair Partitioning of Friends
by: Deligkas, Argyrios, et al.
Published: (2025)

Persuading a Credible Agent
by: Gan, Jiarui, et al.
Published: (2024)

Reducing the complexity of computing the values of a Nash equilibrium
by: Chatterjee, Debtoru, et al.
Published: (2025)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
by: Brânzei, Simina, et al.
Published: (2024)

Modelling Network Resilience: The Complexity of Some Graph Division Games
by: Gutowski, Grzegorz, et al.
Published: (2026)

Bribery's Influence on Ranked Aggregation
by: Jain, Pallavi, et al.
Published: (2026)

On the Complexity of Learning Nash Equilibria
by: Biggar, Oliver, et al.
Published: (2026)

The Complexity of Min-Max Optimization with Product Constraints
by: Bernasconi, Martino, et al.
Published: (2026)

Minimizing the Cost of EFx Allocations
by: Deltl, Eva
Published: (2026)

Necessary President in Elections with Parties
by: Cechlárová, Katarína, et al.
Published: (2026)

How to Resolve Envy by Adding Goods
by: Bentert, Matthias, et al.
Published: (2025)

A Computational Analysis of Strategic Nominations: Modeling Equilibrium and Complexity in Organizational Elections
by: Lin, Chuang-Chieh, et al.
Published: (2023)