Cover Image

Improved Hardness Results for Min-Max Optimization with Coupled Constraints

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bernasconi, Martino, Castiglioni, Matteo, Celli, Andrea, Farina, Gabriele
Format:	Preprint
Published:	2024
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

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

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

The Complexity of Correlated Equilibria in Generalized Games
by: Bernasconi, Martino, et al.
Published: (2025)

Agent-Designed Contracts: How to Sell Hidden Actions
by: Bernasconi, Martino, et al.
Published: (2024)

Single-dimensional Contract Design: Efficient Algorithms and Learning
by: Bernasconi, Martino, et al.
Published: (2025)

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

No-Regret Learning in Bilateral Trade via Global Budget Balance
by: Bernasconi, Martino, et al.
Published: (2023)

Feature-Based Online Bilateral Trade
by: Gaucher, Solenne, et al.
Published: (2024)

Regret-Minimizing Contracts: Agency Under Uncertainty
by: Bernasconi, Martino, et al.
Published: (2024)

Online Learning under Budget and ROI Constraints via Weak Adaptivity
by: Castiglioni, Matteo, et al.
Published: (2023)

Multi-Agent Contract Design beyond Binary Actions
by: Cacciamani, Federico, et al.
Published: (2024)

Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information
by: Balcan, Maria-Florina, et al.
Published: (2025)

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

Nonparametric Contextual Online Bilateral Trade
by: Coccia, Emanuele, et al.
Published: (2026)

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

Constrained Phi-Equilibria
by: Bernasconi, Martino, et al.
Published: (2023)

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

Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
by: Zhang, Brian Hu, et al.
Published: (2022)

Optimal Rates for Feasible Payoff Set Estimation in Games
by: Barbara, Annalisa, et al.
Published: (2026)

Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation
by: Zhang, Brian, et al.
Published: (2022)

Computing Equilibrium beyond Unilateral Deviation
by: Liu, Mingyang, et al.
Published: (2026)

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

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

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

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

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

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

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

On the Computation of Equilibria in Discrete First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (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
by: Kaczmarek, Joanna, et al.
Published: (2024)

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

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

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

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

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

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

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

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)

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