On randomized fictitious play for approximating saddle points over convex sets

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

zbMATH Keywords

convex optimizationsaddle pointmultiplicative weights update method

Mathematics Subject Classification ID

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