Cover Image

A Smoothed FPTAS for Equilibria in Congestion Games

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Giannakopoulos, Yiannis
Format:	Preprint
Published:	2023
Subjects:	Computer Science and Game Theory Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

Nemesis, an Escape Game in Graphs
by: Bergé, Pierre, et al.
Published: (2026)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
by: Koenemann, Jochen, et al.
Published: (2021)

Core Stability in Additively Separable Hedonic Games of Low Treewidth
by: Hanaka, Tesshu, et al.
Published: (2024)

An FPTAS for 7/9-Approximation to Maximin Share Allocations
by: Huang, Xin, et al.
Published: (2025)

Partitioned Matching Games for International Kidney Exchange
by: Benedek, Márton, et al.
Published: (2023)

A Quadratic Lower Bound for Stable Roommates Solvability
by: Rosenbaum, Will
Published: (2025)

Unravelling Expressive Delegations: Complexity and Normative Analysis
by: Tyrovolas, Giannis, et al.
Published: (2023)

Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded
by: Benedek, Márton, et al.
Published: (2023)

Hedonic Seat Arrangement Problems
by: Bodlaender, Hans L., et al.
Published: (2020)

The Price of Justified Representation
by: Elkind, Edith, et al.
Published: (2021)

Satisfactory Budget Division
by: Gourvès, Laurent, et al.
Published: (2025)

Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
by: Kawase, Sota, et al.
Published: (2024)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
by: Chen, Xi, et al.
Published: (2024)

Complexity of Auctions with Interdependence
by: Loiseau, Patrick, et al.
Published: (2026)

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

Smooth Nash Equilibria: Algorithms and Complexity
by: Daskalakis, Constantinos, et al.
Published: (2023)

On Binary Networked Public Goods Game with Altruism
by: Maiti, Arnab, et al.
Published: (2022)

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

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

Dynamic Debt Swapping in Financial Networks
by: Froese, Henri, et al.
Published: (2023)

A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
by: Takazawa, Kenjiro
Published: (2024)

Attractors Is All You Need: Parity Games In Polynomial Time
by: van der Heijden, Rick
Published: (2025)

Equilibria, Efficiency, and Inequality in Network Formation for Hiring and Opportunity
by: Dwork, Cynthia, et al.
Published: (2024)

Lipschitz Continuous Allocations for Optimization Games
by: Kumabe, Soh, et al.
Published: (2024)

Deviation Dynamics in Cardinal Hedonic Games
by: Zech, Valentin, et al.
Published: (2025)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

Envy-freeness in 3D Hedonic Games
by: McKay, Michael, et al.
Published: (2022)

Individual Rationality in Topological Distance Games is Surprisingly Hard
by: Deligkas, Argyrios, et al.
Published: (2024)

Equilibria in multiagent online problems with predictions
by: Istrate, Gabriel, et al.
Published: (2024)

The NTU Partitioned Matching Game for International Kidney Exchange Programs
by: Csáji, Gergely, et al.
Published: (2024)

Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
by: Constantinescu, Andrei, et al.
Published: (2023)

Computing Power Indices in Weighted Majority Games with Formal Power Series
by: Kakimura, Naonori, et al.
Published: (2025)

Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
by: Bullinger, Martin, et al.
Published: (2025)

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

Repeated Bilateral Trade Against a Smoothed Adversary
by: Cesa-Bianchi, Nicolò, et al.
Published: (2023)

Fixed Point Computation: Beating Brute Force with Smoothed Analysis
by: Attias, Idan, et al.
Published: (2025)

A Minimax Perspective on Almost-Stable Matchings
by: Glitzner, Frederik, et al.
Published: (2026)

A Strongly Polynomial Algorithm for Arctic Auctions
by: Garg, Jugal, et al.
Published: (2026)

A Reduction from Chores Allocation to Job Scheduling
by: Huang, Xin, et al.
Published: (2023)