Imagen de Portada

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gao, Ruiquan, Roghani, Mohammad, Rubinstein, Aviad, Saberi, Amin
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity Computer Science and Game Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

Envy-Free House Allocation with Minimum Subsidy
por: Choo, Davin, et al.
Publicado: (2024)

Approximate Envy-Freeness in Graphical Cake Cutting
por: Yuen, Sheung Man, et al.
Publicado: (2023)

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

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

On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness
por: Mehra, Arnav, et al.
Publicado: (2025)

Connected Equitable Cake Division via Sperner's Lemma
por: Bhaskar, Umang, et al.
Publicado: (2024)

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
por: Bernasconi, Martino, et al.
Publicado: (2024)

Stable Matching with Interviews
por: Ashlagi, Itai, et al.
Publicado: (2025)

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

Approximating Gains-from-Trade in Matching Markets
por: Babaioff, Moshe, et al.
Publicado: (2026)

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

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
por: Rubinstein, Aviad
Publicado: (2016)

Approximate Envy-Free Allocations up to any $k$ Goods
por: Filos-Ratsikas, Aris, et al.
Publicado: (2026)

Fair Division via the Cake-Cutting Share
por: Bai, Yannan, et al.
Publicado: (2024)

Quantum Communication Complexity of Classical Auctions
por: Rubinstein, Aviad, et al.
Publicado: (2023)

Smoothed analysis of deterministic discounted and mean-payoff games
por: Loff, Bruno, et al.
Publicado: (2024)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
por: D'Amico-Wong, Luca, et al.
Publicado: (2024)

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

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

Committee Elections with Candidate Attribute Constraints
por: Zhou, Aizhong, et al.
Publicado: (2024)

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

Complexity of Manipulation and Bribery in Premise-Based Judgment Aggregation with Simple Formulas
por: Bredereck, Robert, et al.
Publicado: (2024)

Reforming an Unfair Allocation by Exchanging Goods
por: Yuen, Sheung Man, et al.
Publicado: (2024)

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

Control by Adding Players to Change or Maintain the Shapley-Shubik or the Penrose-Banzhaf Power Index in Weighted Voting Games Is Complete for NP^PP
por: Kaczmarek, Joanna, et al.
Publicado: (2024)

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

Ex-post Stability under Two-Sided Matching: Complexity and Characterization
por: Aziz, Haris, et al.
Publicado: (2024)

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

Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
por: Ron, Shiri, et al.
Publicado: (2024)

Persuading a Credible Agent
por: Gan, Jiarui, et al.
Publicado: (2024)

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

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

Constant Inapproximability for Fisher Markets
por: Deligkas, Argyrios, et al.
Publicado: (2026)

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

Skating System Unveiled: Exploring Preference Aggregation in Ballroom Tournaments
por: Horn, Laryssa, et al.
Publicado: (2025)

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

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

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