The Theory of Max-Min and its Application to Weapons Allocation Problems

Max-Min problems are two-step allocation problems in which one side must make his move knowing that the other side will then learn what the move is and optimally counter. They are fundamental in parti­ cular to military weapons-selection problems involvin

  • PDF / 9,531,277 Bytes
  • 135 Pages / 439.37 x 666.142 pts Page_size
  • 93 Downloads / 300 Views

DOWNLOAD

REPORT


v

Herausgegeben von / Edited by M. Beckmann, Bonn· R. Henn, Gottingen . A. Jaeger, Cincinnati W. Krelle, Bonn· H. P. Kiinzi, Ziirich K. Wenke, Ludwigshafen . Ph. Wolfe, Santa Monica (Cal.)

Geschiiftsfohrende Herausgeber / Managing Editors W. Krelle . H. P. Kiinzi

The Theory of Max-Min and its Application to Weapons Allocation Problems

John M. Danskin

With 6 Figures

Springer-Verlag Berlin Heidelberg New York 1967

Dr. JOHN

M.

DANSKIN

Center for Naval Analyses of the Franklin-Institute Arlington, Virginia 22209

ISBN-13: 978-3-642-46094-4 e-ISBN-13: 978-3-642-46092-0 DOl: 10.1007/978-3-642-46092-0 All rights reserved, especially that of translation into foreign languages. It is also forbidden to reproduce this book, either whole or in part, by photomt:chanical means (photostat, microfilm and/or microcard) without written permission from the Publishers.

©

by

Springer~Verlag

Berlin' Heidelberg· 1967.

Softcover reprint of the hardcover 1st edition 1967

Library of Congress Catalog Card Number 66-22462 Titel-Nr. 6480

This book is dedicated to my father JOHN

M.

DANSKIN, SR.

who made it possible for me to become a mathematician

Preface Max-Min problems are two-step allocation problems in which one side must make his move knowing that the other side will then learn what the move is and optimally counter. They are fundamental in particular to military weapons-selection problems involving large systems such as Minuteman or Polaris, where the systems in the mix are so large that they cannot be concealed from an opponent. One must then expect the opponent to determine on an optlmal mixture of, in the case mentioned above, anti-Minuteman and anti-submarine effort. The author's first introduction to a problem of Max-Min type occurred at The RAND Corporation about 1951. One side allocates anti-missile defenses to various cities. The other side observes this allocation and then allocates missiles to those cities. If F(x, y) denotes the total residual value of the cities after the attack, with x denoting the defender's strategy and y the attacker's, the problem is then to find Max MinF(x, y) = Max [MinF(x, x

y

y

x

y)] .

If it happens that

Max MinF(x, y) = Min MaxF(x, y), x

y

y

x

the problem is a standard game-theory problem with a pure-strategy solution. If however Max MinF(x, y) < Min MaxF(x, y), x

y

y

x

i. e., the order of the choices of x and y is essential, then standard game theory fails. The concept of mixed strategy has no meaning: the xplayer knows that his strategy will be observed by his opponent, and the y-player knows x when he acts and needs simply to minimize. Thus the problem needs a separate treatment. That is the object of this book. It is natural to begin by studying the nature of the function cp(x)

= MinF(x, y) y

which is to be maximized. The principal difficulty, illustrated on an example (the "seesaw") in Chapter I, is that cp(x) is not in general differentiable in the usual sense, even when F(x, y) is quite smooth. This is closely connected with non-uniqueness in the set Y