Cover Image

Solving Matrix Games with Near-Optimal Matvec Complexity

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Karmarkar, Ishani, O'Carroll, Liam, Sidford, Aaron
Format:	Preprint
Published:	2026
Subjects:	Optimization and Control Data Structures and Algorithms Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Solving Zero-Sum Games with Fewer Matrix-Vector Products
by: Karmarkar, Ishani, et al.
Published: (2025)

Extracting Dual Solutions via Primal Optimizers
by: Carmon, Yair, et al.
Published: (2024)

Isotropic Noise in Stochastic and Quantum Convex Optimization
by: Marsden, Annie, et al.
Published: (2025)

Reusing Samples in Variance Reduction
by: Jin, Yujia, et al.
Published: (2025)

Truncated Variance Reduced Value Iteration
by: Jin, Yujia, et al.
Published: (2024)

Robust Optimality of Bundling Goods Beyond Finite Variance
by: van Eck, Tim S. G., et al.
Published: (2025)

Revenue Maximization in Choice-Based Matching Markets
by: Nissim, Dan, et al.
Published: (2024)

Barely Random Algorithms and Collective Metrical Task Systems
by: Cosson, Romain, et al.
Published: (2024)

Online Fair Allocation with Best-of-Many-Worlds Guarantees
by: Yang, Zongjun, et al.
Published: (2024)

Sequential Selection with Expirations
by: Xu, Yihua, et al.
Published: (2024)

Fare Zone Assignment on Trees
by: Hoefer, Martin, et al.
Published: (2025)

Online Proportional Apportionment
by: Cembrano, Javier, et al.
Published: (2025)

Algorithmically Fair Maximization of Multiple Submodular Objective Functions
by: Amanatidis, Georgios, et al.
Published: (2024)

On the Correlation Gap of Matroids
by: Husić, Edin, et al.
Published: (2022)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
by: Molina, Mathieu, et al.
Published: (2024)

Optimal Contest Beyond Convexity
by: Golrezaei, Negin, et al.
Published: (2026)

Generalized Nash Equilibrium Problems with Mixed-Integer Variables
by: Harks, Tobias, et al.
Published: (2021)

Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement
by: Bansak, Kirk, et al.
Published: (2024)

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

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

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

Near-Feasible Stable Matchings: Incentives and Optimality
by: Glitzner, Frederik
Published: (2026)

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

Sparse Submodular Function Minimization
by: Graur, Andrei, et al.
Published: (2023)

On computing approximate Lewis weights
by: Apers, Simon, et al.
Published: (2024)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
by: Chen, Li, et al.
Published: (2025)

Entropy Regularization and Faster Decremental Matching in General Graphs
by: Chen, Jiale, et al.
Published: (2023)

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)

Balancing Gradient and Hessian Queries in Non-Convex Optimization
by: Adil, Deeksha, et al.
Published: (2025)

Convex optimization with $p$-norm oracles
by: Adil, Deeksha, et al.
Published: (2024)

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

Quantum speedups for stochastic optimization
by: Sidford, Aaron, et al.
Published: (2023)

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

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

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

Optimal Pricing with Unreliable Signals
by: Tang, Zhihao Gavin, et al.
Published: (2026)

Optimal Stopping with Interdependent Values
by: Mauras, Simon, et al.
Published: (2024)