Vladimir Mazalov - Mathematical Game Theory and Applications

Vladimir Mazalov

Research Director of the Institute of Applied Mathematical Research,
Karelia Research Center of Russian Academy of Sciences, Russia

This edition first published 2014
2014 John Wiley & Sons, Ltd

Registered office
John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data

Mazalov, V. V. (Vladimir Viktorovich), author.
Mathematical game theory and applications / Vladimir Mazalov.
pages cm
Includes bibliographical references and index.
ISBN 978-1-118-89962-5 (hardback)
1. Game theory. I. Title.
QA269.M415 2014
519.3dc23

2014019649

A catalogue record for this book is available from the British Library.

ISBN: 978-1-118-89962-5

This book offers a combined course of lectures on game theory which the author has delivered for several years in Russian and foreign universities.

In addition to classical branches of game theory, our analysis covers modern branches left without consideration in most textbooks on the subject (negotiation models, potential games, parlor games, best choice games, and network games). The fundamentals of mathematical analysis, algebra, and probability theory are the necessary prerequisites for reading.

The book can be useful for students specializing in applied mathematics and informatics, as well as economical cybernetics. Moreover, it attracts the mutual interest of mathematicians operating in the field of game theory and experts in the fields of economics, management science, and operations research.

Each chapter concludes with a series of exercises intended for better understanding. Some exercises represent open problems for conducting independent investigations. As a matter of fact, stimulation of readers research is the main priority of the book. A comprehensive bibliography will guide the audience in an appropriate scientific direction.

For many years, the author has enjoyed the opportunity to discuss derived results with Russian colleagues L.A. Petrosjan, V.V. Zakharov, N.V. Zenkevich, I.A. Seregin, and A.Yu. Garnaev (St. Petersburg State University), A.A. Vasin (Lomonosov Moscow State University), D.A. Novikov (Trapeznikov Institute of Control Sciences, Russian Academy of Sciences), A.V. Kryazhimskii and A.B. Zhizhchenko (Steklov Mathematical Institute, Russian Academy of Sciences), as well as with foreign colleagues M. Sakaguchi (Osaka University), M. Tamaki (Aichi University), K. Szajowski (Wroclaw University of Technology), B. Monien (University of Paderborn), K. Avratchenkov (INRIA, Sophia-Antipolis), and N. Perrin (University of Lausanne). They all have my deep and sincere appreciation. The author expresses profound gratitude to young colleagues A.N. Rettieva, J.S. Tokareva, Yu.V. Chirkova, A.A. Ivashko, A.V. Shiptsova and A.Y. Kondratjev from Institute of Applied Mathematical Research (Karelian Research Center, Russian Academy of Sciences) for their assistance in typing and formatting of the book. Next, my frank acknowledgement belongs to A.Yu. Mazurov for his careful translation, permanent feedback, and contribution to the English version of the book.

A series of scientific results included in the book were established within the framework of research supported by the Russian Foundation for Basic Research (projects no. 13-01-00033-a, 13-01-91158), Russian Academy of Sciences (Branch of Mathematics) and the Strategic Development Program of Petrozavodsk State University.

Equilibrium arises from righteousness, and righteousness arises from the meaning of the cosmos.

From Hermann Hesses The Glass Bead Game

Game theory represents a branch of mathematics, which analyzes models of optimal decision-making in the conditions of a conflict. Game theory belongs to operations research, a science originally intended for planning and conducting military operations. However, the range of its applications appears much wider. Game theory always concentrates on models with several participants. This forms a fundamental distinction of game theory from optimization theory. Here the notion of an optimal solution is a matter of principle. There exist many definitions of the solution of a game. Generally, the solution of a game is called an equilibrium, but one can choose different concepts of an equilibrium (a Nash equilibrium, a Stackelberg equilibrium, a Wardrop equilibrium, to name a few).

In the last few years, a series of outstanding researchers in the field of game theory were awarded Nobel Prize in Economic Sciences. They are J.C. Harsanyi, J.F. Nash Jr., and R. Selten (1994) for their pioneering analysis of equilibria in the theory of non-cooperative games, F.E. Kydland and E.C. Prescott (2004) for their contributions to dynamic macroeconomics: the time consistency of economic policy and the driving forces behind business cycles, R.J. Aumann and T.C. Schelling (2005) for having enhanced our understanding of conflict and cooperation through game-theory analysis, L. Hurwicz, E.S. Maskin, and R.B. Myerson (2007) for having laid the foundations of mechanism design theory. Throughout the book, we will repeatedly cite these names and corresponding problems.

Depending on the number of players, one can distinguish between zero-sum games (antagonistic games) and nonzero-sum games. Strategy sets are finite or infinite (matrix games and games on compact sets, respectively). Next, players may act independently or form coalitions; the corresponding models represent non-cooperative games and cooperative games. There are games with complete or partial incoming information.