On randomized fictitious play for approximating saddle points over convex sets
From MaRDI portal
DOI10.1007/s00453-014-9902-8zbMath1330.91012arXiv1301.5290OpenAlexW2128220784MaRDI QIDQ747628
Kurt Mehlhorn, Kazuhisa Makino, Fahimeh Ramezani, Khaled M. Elbassioni
Publication date: 19 October 2015
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1301.5290
Linear programming (90C05) 2-person games (91A05) Combinatorial optimization (90C27) Randomized algorithms (68W20)
Related Items
A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs, A Multiplicative Weights Update Algorithm for Packing and Covering Semi-infinite Linear Programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two-person zero-sum games
- Faster and simpler approximation algorithms for mixed packing and covering problems
- A general saddle point theorem and its applications
- Geometric algorithms and combinatorial optimization.
- The weighted majority algorithm
- A 2-person game on a polyhedral set of connected strategies
- Saddle point theorems on generalized convex spaces
- Adaptive game playing using multiplicative weights
- A sublinear-time randomized approximation algorithm for matrix games
- Best response dynamics for continuous zero-sum games
- An iterative method of solving a game
- Generalization of a theorem by v. Neumann concerning zero sum two person games
- Approximate Max-Min Resource Sharing for Structured Concave Optimization
- Note on a computation method in the theory of games
- The geometry of logconcave functions and sampling algorithms
- Popular Mixed Matchings
- A Minimax Theorem
- Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control
- Coordination Complexity of Parallel Price-Directive Decomposition
- A parallel approximation algorithm for positive linear programming
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- Simulated Annealing for Convex Optimization
- Algorithms – ESA 2004
- Hit-and-Run from a Corner
- On the min-max theorem for finite two-person zero-sum games
- Convex Analysis
- Some Minimax Theorems.
- Solving convex programs by random walks
