Buchumschlag

Constant Inapproximability for PPA

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Deligkas, Argyrios, Fearnley, John, Hollender, Alexandros, Melissourgos, Themistoklis
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Computational Complexity Computer Science and Game Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Constant Inapproximability for Fisher Markets
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Pure-Circuit: Tight Inapproximability for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2022)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Pizza Sharing is PPA-hard
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2020)

Tight Inapproximability of Nash Equilibria in Public Goods Games
von: Dinh, Jérémi Do, et al.
Veröffentlicht: (2024)

On the Smoothed Complexity of Combinatorial Local Search
von: Giannakopoulos, Yiannis, et al.
Veröffentlicht: (2022)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
von: Ghosh, Abheek, et al.
Veröffentlicht: (2024)

Envy-Free Cake-Cutting for Four Agents
von: Hollender, Alexandros, et al.
Veröffentlicht: (2023)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

On the Computation of Equilibria in Discrete First-Price Auctions
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2024)

Equilibrium Computation in First-Price Auctions with Correlated Priors
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2025)

EF1 and EFX Orientations
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2024)

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

Distributed Agent-Constrained Truthful Facility Location
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Agent-Constrained Truthful Facility Location Games
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2024)

Computing Equilibrium Points of Electrostatic Potentials
von: Ghosh, Abheek, et al.
Veröffentlicht: (2025)

Efficient Equilibrium Computation in Symmetric First-Price Auctions
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2026)

The Complexity of Sparse Win-Lose Bimatrix Games
von: Batziou, Eleni, et al.
Veröffentlicht: (2026)

Truthful Interval Covering
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2023)

Online EFX Allocations with Predictions
von: Melissourgos, Themistoklis, et al.
Veröffentlicht: (2025)

Min-Max Optimization Requires Exponentially Many Queries
von: Bernasconi, Martino, et al.
Veröffentlicht: (2026)

The Complexity of Fair Division of Indivisible Items with Externalities
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2023)

Mechanism Design with Outliers and Predictions
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2025)

The Complexity of Two-Team Polymatrix Games with Independent Adversaries
von: Hollender, Alexandros, et al.
Veröffentlicht: (2024)

Stability in Distance Preservation Games on Graphs
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Balanced and Fair Partitioning of Friends
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2025)

How to Resolve Envy by Adding Goods
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

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

Smoothed analysis of deterministic discounted and mean-payoff games
von: Loff, Bruno, et al.
Veröffentlicht: (2024)

On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
von: Hansen, Kristoffer Arnsfelt, et al.
Veröffentlicht: (2025)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
von: D'Amico-Wong, Luca, et al.
Veröffentlicht: (2024)

Controlling Borda Elections by Adding or Deleting either Votes or Candidates: Complete and Top-Truncated Votes
von: Zhou, Aizhong, et al.
Veröffentlicht: (2024)

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
von: Gao, Ruiquan, et al.
Veröffentlicht: (2024)

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

Committee Elections with Candidate Attribute Constraints
von: Zhou, Aizhong, et al.
Veröffentlicht: (2024)

Skating System Unveiled: Exploring Preference Aggregation in Ballroom Tournaments
von: Horn, Laryssa, et al.
Veröffentlicht: (2025)

Modelling Network Resilience: The Complexity of Some Graph Division Games
von: Gutowski, Grzegorz, et al.
Veröffentlicht: (2026)

Bribery's Influence on Ranked Aggregation
von: Jain, Pallavi, et al.
Veröffentlicht: (2026)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

Spatial Voting with Incomplete Voter Information
von: Imber, Aviram, et al.
Veröffentlicht: (2023)