Buchumschlag

Solving Zero-Sum Games with Fewer Matrix-Vector Products

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Karmarkar, Ishani, O'Carroll, Liam, Sidford, Aaron
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Optimization and Control Data Structures and Algorithms 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

Solving Matrix Games with Near-Optimal Matvec Complexity
von: Karmarkar, Ishani, et al.
Veröffentlicht: (2026)

Extracting Dual Solutions via Primal Optimizers
von: Carmon, Yair, et al.
Veröffentlicht: (2024)

Isotropic Noise in Stochastic and Quantum Convex Optimization
von: Marsden, Annie, et al.
Veröffentlicht: (2025)

Reusing Samples in Variance Reduction
von: Jin, Yujia, et al.
Veröffentlicht: (2025)

Truncated Variance Reduced Value Iteration
von: Jin, Yujia, et al.
Veröffentlicht: (2024)

Robust Optimality of Bundling Goods Beyond Finite Variance
von: van Eck, Tim S. G., et al.
Veröffentlicht: (2025)

Revenue Maximization in Choice-Based Matching Markets
von: Nissim, Dan, et al.
Veröffentlicht: (2024)

Barely Random Algorithms and Collective Metrical Task Systems
von: Cosson, Romain, et al.
Veröffentlicht: (2024)

Online Fair Allocation with Best-of-Many-Worlds Guarantees
von: Yang, Zongjun, et al.
Veröffentlicht: (2024)

Sequential Selection with Expirations
von: Xu, Yihua, et al.
Veröffentlicht: (2024)

Fare Zone Assignment on Trees
von: Hoefer, Martin, et al.
Veröffentlicht: (2025)

Online Proportional Apportionment
von: Cembrano, Javier, et al.
Veröffentlicht: (2025)

Algorithmically Fair Maximization of Multiple Submodular Objective Functions
von: Amanatidis, Georgios, et al.
Veröffentlicht: (2024)

On the Correlation Gap of Matroids
von: Husić, Edin, et al.
Veröffentlicht: (2022)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
von: Molina, Mathieu, et al.
Veröffentlicht: (2024)

Generalized Nash Equilibrium Problems with Mixed-Integer Variables
von: Harks, Tobias, et al.
Veröffentlicht: (2021)

Optimal Contest Beyond Convexity
von: Golrezaei, Negin, et al.
Veröffentlicht: (2026)

Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement
von: Bansak, Kirk, et al.
Veröffentlicht: (2024)

Markovian Search with Ex-Ante Constraints: Theory and Applications to Socially Aware Algorithmic Hiring
von: Aminian, Mohammad Reza, et al.
Veröffentlicht: (2025)

Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
von: Constantinescu, Andrei, et al.
Veröffentlicht: (2023)

A Generalization of von Neumann's Reduction from the Assignment Problem to Zero-Sum Games
von: Adler, Ilan, et al.
Veröffentlicht: (2024)

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

Sparse Submodular Function Minimization
von: Graur, Andrei, et al.
Veröffentlicht: (2023)

On computing approximate Lewis weights
von: Apers, Simon, et al.
Veröffentlicht: (2024)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
von: Chen, Li, et al.
Veröffentlicht: (2025)

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
von: Dereziński, Michał, et al.
Veröffentlicht: (2025)

Entropy Regularization and Faster Decremental Matching in General Graphs
von: Chen, Jiale, et al.
Veröffentlicht: (2023)

Selfish, Local and Online Scheduling via Vector Fitting
von: Kashaev, Danish
Veröffentlicht: (2025)

Lipschitz Continuous Allocations for Optimization Games
von: Kumabe, Soh, et al.
Veröffentlicht: (2024)

Deviation Dynamics in Cardinal Hedonic Games
von: Zech, Valentin, et al.
Veröffentlicht: (2025)

Welfare Approximation in Additively Separable Hedonic Games
von: Bullinger, Martin, et al.
Veröffentlicht: (2025)

Envy-freeness in 3D Hedonic Games
von: McKay, Michael, et al.
Veröffentlicht: (2022)

Balancing Gradient and Hessian Queries in Non-Convex Optimization
von: Adil, Deeksha, et al.
Veröffentlicht: (2025)

Convex optimization with $p$-norm oracles
von: Adil, Deeksha, et al.
Veröffentlicht: (2024)

Quantum speedups for stochastic optimization
von: Sidford, Aaron, et al.
Veröffentlicht: (2023)

Individual Rationality in Topological Distance Games is Surprisingly Hard
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2024)

The NTU Partitioned Matching Game for International Kidney Exchange Programs
von: Csáji, Gergely, et al.
Veröffentlicht: (2024)

Computing Power Indices in Weighted Majority Games with Formal Power Series
von: Kakimura, Naonori, et al.
Veröffentlicht: (2025)

Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
von: Bullinger, Martin, et al.
Veröffentlicht: (2025)

A Direct Second-Order Method for Solving Two-Player Zero-Sum Games
von: Yang, David, et al.
Veröffentlicht: (2025)