Ebook: Minimax and Applications

Techniques and principles of minimax theory play a key role in many areas of research, including game theory, optimization, and computational complexity. In general, a minimax problem can be formulated as min max f(x, y) (1) ",EX !lEY where f(x, y) is a function defined on the product of X and Y spaces. There are two basic issues regarding minimax problems: The first issue concerns the establishment of sufficient and necessary conditions for equality minmaxf(x,y) = maxminf(x,y). (2) "'EX !lEY !lEY "'EX The classical minimax theorem of von Neumann is a result of this type. Duality theory in linear and convex quadratic programming interprets minimax theory in a different way. The second issue concerns the establishment of sufficient and necessary conditions for values of the variables x and y that achieve the global minimax function value f(x*, y*) = minmaxf(x, y). (3) "'EX !lEY There are two developments in minimax theory that we would like to mention.

---

Classical minimax theory (von Neumann), duality and saddle point analysis have together played a critical role in optimization and game theory. It is currently recognised that minimax problems and techniques appear throughout a broad spectrum of disciplines, including game theory, optimization, and computational complexity. Many interesting and sophisticated problems are formulated as minimax applications, as in the fields of combinatorial optimization, scheduling, location, packing, searching, and triangulation. The contributions to Minimax and Applications cover a wide range of topics and provide an excellent picture of recent research and developments in minimax theory.
Audience: Accessible to graduate students as well as researchers in optimization, computer science, and related areas.