Bilbao Cooperative Games on Combinatorial Structures

2000
ISBN: 978-1-4615-4393-0
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 26, 326 Seiten, eBook

Reihe: Theory and Decision Library C

The aim of Cooperative Games on Combinatorial Structures is to analyze conflict situations in which two or more players can make coalitions and obtain prizes and penalties. This approach to situations of competition and cooperation was given in the seminal treatise by John von Neumann and Oskar Morgenstern, Theory of Gamesand Economic Behavior . Cooperative game theory has succeeded in providing many applications of game theory. In this volume, games defined on combinatorial structures will be analyzed, i.e. a set system over a set of players. In many situations the author will work in a closure space . Examples of closure operators are the spanning operator of linear algebra and all convex hull operators. Chapters 1-4 constitute a review of mathematical concepts from Cooperative Game Theory, Graph Theory, Linear and IntegerProgramming, Combinatorial Optimization, Discrete Convex Analysis and Computational Complexity . The table of contents is a short guide to the topics and methods covered in this book. In Chapters 11 and 12, several notebooks are presented with the system Mathematica by Wolfram in the contexts of the packages DiscreteMath (Skiena) and Cooperative (Carter). There will also be found in the book several research projects. These are intended to offer new ideas that the reader should consider with caution. This book will be of interest to graduate students with some experience in game theory or mathematical programming and professional researchers in game theory, operational research and its applications in economic theory, and the political and social sciences. In addition, it will be especially useful for professionals who are interested in models for understanding and managing conflicts: management and operational research scientists, political and military scientists, and professional negotiators.

Zielgruppe

Research

Autoren/Hrsg.

Bilbao, Jesús Mario

Inhaltsverzeichnis

1 Structures.- 1.1 Cooperative games.- 1.2 Graph theory.- 1.3 Examples of cooperative games.- 1.4 Closure spaces and convex geometries.- 1.5 Matroids, greedoids and antimatroids.- 1.6 Project: Bicooperative games.- 2 Linear optimization methods.- 2.1 Polyhedra.- 2.2 Linear programming.- 2.3 Integer and combinatorial optimization.- 2.4 Balanced games.- 2.5 The greedy algorithm.- 2.6 Polymatroids.- 3 Discrete convex analysis.- 3.1 Fenchel conjugation.- 3.2 Subgradients and subdifferentials.- 3.3 Indirect functions of cooperative games.- 3.4 The least increment function.- 3.5 The Lovasz extension of games.- 4 Computational complexity.- 4.1 Models of computation.- 4.2 The complexity classes P and NP.- 4.3 NP-completeness and #P-completeness.- 4.4 Complexity in cooperative game theory.- 4.5 Project: Locally concave (convex) games.- 5 Restricted games by partition systems.- 5.1 Partition systems.- 5.2 F-restricted games.- 5.3 The core of restricted games.- 5.4 Hart and Mas-Colell potential.- 5.5 The Shapley and Banzhaf values.- 6 Restricted games by union stable systems.- 6.1 Union stable systems.- 6.2 Components of sets.- 6.3 The Myerson value.- 6.4 The position value.- 6.5 Convexity of the conference game.- 6.6 Project: Solution continuation games.- 7 Values for games on convex geometries.- 7.1 Games on convex geometries.- 7.2 Probabilistic values for games.- 7.3 Efficiency and compatible-order values.- 7.4 Axioms for the Shapley value.- 7.5 Axioms for the Banzhaf index.- 7.6 Project: Maxginalist and efficient values.- 8 Values for games on matroids.- 8.1 The rank game.- 8.2 The Shapley value for games on matroids.- 8.3 Quasi-probabilistic values.- 8.4 The probabilistic Shapley value.- 9 The core, the selectope and the Weber set.- 9.1 The core.- 9.2 The selectope.- 9.3 TheWeber set.- 9.4 Convex and quasi-convex games.- 9.5 Marginal operators.- 10 Simple games on closure spaces.- 10.1 Minimal winning coalitions.- 10.2 The core.- 10.3 The Weber set.- 10.4 Stable sets.- 10.5 Bargaining sets.- 11 Voting power.- 11.1 Weighted voting games.- 11.2 Generating functions.- 11.3 Computational complexity.- 11.4 Algorithms with Mathematica.- 11.5 Power in 2-weighted voting games.- 12 Computing values with Mathematica.- 12.1 Computing values of restricted games.- 12.2 Computing convex Shapley values.- 12.3 Computing convex Banzhaf indices.- 12.4 The Banzhaf power in the European Union.- 12.5 Computing the number of subtrees.- 12.6 The Myerson value in the European Union.