Mathematical Game Theory and Applications E-Book

Vladimir Mazalov

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 603

Veröffentlichungsjahr: 2014

Beschreibung

Mathematical Game Theory and Applications

Mathematical Game Theory and Applications

An authoritative and quantitative approach to modern game theory with applications from economics, political science, military science and finance.

Mathematical Game Theory and Applications combines both the theoretical and mathematical foundations of game theory with a series of complex applications along with topics presented in a logical progression to achieve a unified presentation of research results. This book covers topics such as two-person games in strategic form, zero-sum games, N-person non-cooperative games in strategic form, two-person games in extensive form, parlor and sport games, bargaining theory, best-choice games, co-operative games and dynamic games. Several classical models used in economics are presented which include Cournot, Bertrand, Hotelling and Stackelberg as well as coverage of modern branches of game theory such as negotiation models, potential games, parlor games and best choice games.

Mathematical Game Theory and Applications:

• Presents a good balance of both theoretical foundations and complex applications of game theory.
• Features an in-depth analysis of parlor and sport games, networking games, and bargaining models.
• Provides fundamental results in new branches of game theory, best choice games, network games and dynamic games.
• Presents numerous examples and exercises along with detailed solutions at the end of each chapter.
• Is supported by an accompanying website featuring course slides and lecture content.

Covering a host of important topics, this book provides a research springboard for graduate students and a reference for researchers who might be working in the areas of applied mathematics, operations research, computer science or economical cybernetics.

Leseprobe

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 officeJohn 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.3–dc23

2014019649

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

ISBN: 978-1-118-89962-5

Contents

Preface

Introduction

1 Strategic-form two-player games

Introduction

1.1 The Cournot duopoly

1.2 Continuous improvement procedure

1.3 The Bertrand duopoly

1.4 The Hotelling duopoly

1.5 The Hotelling duopoly in 2D space

1.6 The Stackelberg duopoly

1.7 Convex games

1.8 Some examples of bimatrix games

1.9 Randomization

1.10 Games 2 × 2

1.11 Games 2 ×

n

and

m

× 2

1.12 The Hotelling duopoly in 2D space with non-uniform distribution of buyers

1.13 Location problem in 2D space

Exercises

2 Zero-sum games

Introduction

2.1 Minimax and maximin

2.2 Randomization

2.3 Games with discontinuous payoff functions

2.4 Convex-concave and linear-convex games

2.5 Convex games

2.6 Arbitration procedures

2.7 Two-point discrete arbitration procedures

2.8 Three-point discrete arbitration procedures with interval constraint

2.9 General discrete arbitration procedures

Exercises

3 Non-cooperative strategic-form

n

-player games

Introduction

3.1 Convex games. The Cournot oligopoly

3.2 Polymatrix games

3.3 Potential games

3.4 Congestion games

3.5 Player-specific congestion games

3.6 Auctions

3.7 Wars of attrition

3.8 Duels, truels, and other shooting accuracy contests

3.9 Prediction games

Exercises

4 Extensive-form

n

-player games

Introduction

4.1 Equilibrium in games with complete information

4.2 Indifferent equilibrium

4.3 Games with incomplete information

4.4 Total memory games

Exercises

5 Parlor games and sport games

Introduction

5.1 Poker. A game-theoretic model

5.2 The poker model with variable bets

5.3 Preference. A game-theoretic model

5.4 The preference model with cards play

5.5 Twenty-one. A game-theoretic model

5.6 Soccer. A game-theoretic model of resource allocation

Exercises

6 Negotiation models

Introduction

6.1 Models of resource allocation

6.2 Negotiations of time and place of a meeting

6.3 Stochastic design in the cake cutting problem

6.4 Models of tournaments

6.5 Bargaining models with incomplete information

6.6 Reputation in negotiations

Exercises

7 Optimal stopping games

Introduction

7.1 Optimal stopping game: The case of two observations

7.2 Optimal stopping game: The case of independent observations

7.3 The game Γ

N

(

G

) under

N

⩾ 3

7.4 Optimal stopping game with random walks

7.5 Best choice games

7.6 Best choice game with stopping before opponent

7.7 Best choice game with rank criterion. Lottery

7.8 Best choice game with rank criterion. Voting

7.9 Best mutual choice game

Exercises

8 Cooperative games

Introduction

8.1 Equivalence of cooperative games

8.2 Imputations and core

8.3 Balanced games

8.4 The τ-value of a cooperative game

8.5 Nucleolus

8.6 The bankruptcy game

8.7 The Shapley vector

8.8 Voting games. The Shapley–Shubik power index and the Banzhaf power index

8.9 The mutual influence of players. The Hoede–Bakker index

Exercises

9 Network games

Introduction

9.1 The KP-model of optimal routing with indivisible traffic. The price of anarchy

9.2 Pure strategy equilibrium. Braess’s paradox

9.3 Completely mixed equilibrium in the optimal routing problem with inhomogeneous users and homogeneous channels

9.4 Completely mixed equilibrium in the optimal routing problem with homogeneous users and inhomogeneous channels

9.5 Completely mixed equilibrium: The general case

9.6 The price of anarchy in the model with parallel channels and indivisible traffic

9.7 The price of anarchy in the optimal routing model with linear social costs and indivisible traffic for an arbitrary network

9.8 The mixed price of anarchy in the optimal routing model with linear social costs and indivisible traffic for an arbitrary network

9.9 The price of anarchy in the optimal routing model with maximal social costs and indivisible traffic for an arbitrary network

9.10 The Wardrop optimal routing model with divisible traffic

9.11 The optimal routing model with parallel channels. The Pigou model. Braess’s paradox

9.12 Potential in the optimal routing model with indivisible traffic for an arbitrary network

9.13 Social costs in the optimal routing model with divisible traffic for convex latency functions

9.14 The price of anarchy in the optimal routing model with divisible traffic for linear latency functions

9.15 Potential in the Wardrop model with parallel channels for player-specific linear latency functions

9.16 The price of anarchy in an arbitrary network for player-specific linear latency functions

Exercises

10 Dynamic games

Introduction

10.1 Discrete-time dynamic games

10.2 Some solution methods for optimal control problems with one player

10.3 The maximum principle and the Bellman equation in discrete- and continuous-time games of

N

players

10.4 The linear-quadratic problem on finite and infinite horizons

10.5 Dynamic games in bioresource management problems. The case of finite horizon

10.6 Dynamic games in bioresource management problems. The case of infinite horizon

10.7 Time-consistent imputation distribution procedure

Exercises

References

Index

End User License Agreement

List of Tables

Chapter 5

Table 5.1

Table 5.2

Table 5.3

Chapter 7

Table 7.1

Table 7.2

Table 7.3

Table 7.4

Chapter 8

Table 8.1

Table 8.2

Table 8.3

Table 8.4

Table 8.5

Table 8.6

Table 8.7

Guide

Cover

Table of Contents

Preface

Pages

xi

xiii

xiv

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

Preface

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 reader’s 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.

Introduction

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

From Hermann Hesse’s 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.

Game theory admits numerous applications. One would hardly find a field of sciences focused on life and society without usage of game-theoretic methods. In the first place, it is necessary to mention economic models, models of market relations and competition, pricing models, models of seller-buyer relations, negotiation, and stable agreements, etc. The pioneering book by J. von Neumann and O. Morgenstern, the founders of game theory, was entitled Theory of Games and Economic Behavior. The behavior of market participants, modeling of their psychological features forms the subject of a new science known as experimental economics.

Game-theoretic methods generated fundamental results in evolutionary biology. The notion of evolutionary stable strategies introduced by British biologist J.M. Smith enabled explaining the evolution of several behavioral peculiarities of animals such as aggressiveness, migration, and struggle for survival. Game-theoretic methods are intensively used in rational nature management problems. For instance, fishing quotas distribution in the ocean, timber extraction by several participants, agricultural pricing are problems of game theory. Today, it seems even impossible to implement intergovernmental agreements on natural resources utilization and environmental pollution reduction (e.g., The Kyoto Protocol) without game-theoretic analysis. In political sciences, game theory concerns voting models in parliaments, influence assessment models for certain political factions, as well as models of defense resources distribution for stable peace achievement. In jurisprudence, game theory is applied in arbitration for assessing the behavioral impact of conflicting sides on judicial decisions.

We have recently observed a technological breakthrough in the analysis of the virtual information world. In terms of game theory, all participants of the global computer network (Internet) and mobile communication networks represent interacting players that receive and transmit information by appropriate data channels. Each player pursues individual interests (acquire some information or complicate this process). Players strive for channels with high-level capacities, and the problem of channel distribution among numerous players arises naturally. And game-theoretic methods are of assistance here. Another problem concerns the impact of user service centralization on system efficiency. The estimate of the centralization effect in a system, where each participant follows individual interests (maximal channel capacity, minimal delay, the maximal amount of received information, etc.) is known as the price of anarchy. Finally, an important problem lies in defining the influence of information network topology on the efficiency of player service. These are non-trivial problems causing certain paradoxes. We describe the corresponding phenomena in the book.

Which fields of knowledge manage without game-theoretic methods? Perhaps, medical science and finance do so, although game-theoretic methods have also recently found some applications in these fields.

The approach to material presentation in this book differs from conventional ones. We intentionally avoid a detailed treatment of matrix games, as far as they are described in many publications. Our study begins with nonzero-sum games and the fundamental theorem on equilibrium existence in convex games. Later on, this result is extended to the class of zero-sum games. The discussion covers several classical models used in economics (the models of market competition suggested by Cournot, Bertrand, Hotelling, and Stackelberg, as well as auctions). Next, we pass from normal-form games to extensive-form games and parlor games. The early chapters of the book consider two-player games, and further analysis embraces n-player games (first, non-cooperative games, and then cooperative ones).

Subsequently, we provide fundamental results in new branches of game theory, best choice games, network games, and dynamic games. The book proposes new schemes of negotiations, much attention is paid to arbitration procedures. Some results belong to the author and his colleagues. The fundamentals of mathematical analysis, algebra, and probability theory are the necessary prerequisites for reading.

This book contains an accompanying website. Please visit www.wiley.com/go/game_theory.