82114 - GIOCHI E MODELLI BOOLEANI

Learning outcomes

The first part of the course is devoted to non-cooperative (or strategic) games, while also marginally dealing with decision making under uncertainty. Preferences over a finite set of alternatives are represented via: (a) binary relations, (b) sub-groups of permutations, (c) ordered partitions, and (d) utility functions. The von Neumann-Morgenstern expected utility theory is covered in terms of discrete random variables, while detailing the well-known Allais and Ellsberg paradoxes. Strategies are formalized through the game tree associated with multistage games, with partitions of nodes formalizing incomplete information. Random/mixed strategies are looked at as points in a unit simplex, with extreme points corresponding to non-random/pure strategies. Equilibria are fixed points of the set-valued best-response mapping. Non-cooperative games are eventually considered in terms of pure strategies only, in order to focus on: (i) strong equilibria, (ii) potential games, (iii) congestion games.

Before addressing cooperative games in the second part of the course, probabilities are also briefly framed as set functions, and in particular as valuations of the Boolean lattice whose elements are events. This enables to introduce discrete fuzzy measures as generalized probabilities, thereby leading to show how the Choquet expected utility theory enables to overcome the above-mentioned paradoxes.

The second part of the course is devoted to cooperative games and Boolean functions. Coalitional games being real-valued set functions, attention is immediately placed on pseudo-Boolean functions, looking at coalitions or subsets of a finite player set as the extreme points of a unit hypercube. Möbius inversion is detailed for generic poset functions, while its specialization for the case of pseudo-Boolean functions enables to focus on the polynomial multilinear extension MLE of these latter, which is fundamental for dealing with several discrete optimization problems in a continuous setting. Fuzzy coalitions simply are non-extreme points of the unit hypercube, and two main solutions of coalitional games, namely the Shapley and Banzhaf values, are also approached by means of the values taken by the gradient of the MLE inside the hypercube. Cooperation restrictions are mostly considered through graph-restricted games, while the final classess are devoted to more complex cooperative games involving the (geometric indecomposable) lattice of partitions of players, as well as to coalition formation games, which combine both non-cooperative and cooperative games.

Course contents

1 Introduction

2 Preliminaries
2.1 Sets
2.2 Mappings
2.3 Posets: subsets and partitions
2.4 Formalizing preferences

3 Preferences
3.1 Binary relations
3.2 Rational preferences
3.3 Preference aggregation
3.4 Utility representation

4 Discrete probability
4.1 Discrete random variables: lotteries
4.2 Probabilities as set functions
4.3 Expected utility
4.4 Ellsberg paradox

5 Strategies
5.1 Information in multistage games
5.2 Dominated and dominant strategies
5.3 Deletion of dominated strategies
5.4 Equilibrium

6 Random strategies
6.1 Dominance
6.2 Best responses
6.3 Equilibrium
6.4 Exercises

7 Strong equilibrium

8 Potential games
9 Congestion games 26
10 Choquet expected utility theory
11 Types of cooperative games
12 Order: posets and lattices
12.1 Maximal chains of subsets and permutations
12.2 Subset or Boolean lattices
12.2.1 Atomic lattices
12.2.2 Complementation

13 Möbius inversion
13.1 Incidence algebra
13.2 Möbius inversion
13.3 Vector spaces and bases
13.4 Lattice functions
13.4.1 Set functions and Boolean/Pseudo-Boolean functions
13.4.2 Polynomial multilinear extension of set functions

14 Solutions of coalitional games
14.1 Axiomatic characterization of solutions
14.2 The Shapley value: existence and uniqueness
14.2.1 Integrating MLE first derivatives
14.3 Random-order and probabilistic solutions
14.4 Weights and Shapley values
14.5 Core of coalitional games
14.6 Cooperation restrictions
14.6.1 Partition constraints type I
14.6.2 Partition constraints type II
14.6.3 Graph-restricted games

15 Geometric lattices
15.1 Two examples by means of partitions
15.2 Cooperation restrictions in general
16 Coalition formation
16.1 Network formation
16.2 Fuzzy coalitions
17 Set packing and partitioning in combinatorial optimization

Readings/Bibliography

- M. Aigner. Combinatorial Theory. Springer, 1997
- R. Aumann and J. Dréze. Cooperative games with coalition structures. International Journal of Game Theory, 3:217–237, 1974.
- J. F. Banzhaf. Weighted voting doesn’t work: A mathematical analysis. Rutgers Law Review, 19(2):317–343, 1965.
- K. Border. Fixed point theorems with applications to economics and game theory. Cambridge University Press, 1985.
- P. Borm, G. Owen, and S. Tijs. On the position value for communication situations. SIAM Journal on Discrete Mathematics, 5(3):305–320, 1992.
- E. Boros and P. L. Hammer. Pseudo-Boolean optimization. Discrete Appl. Math., 123:155–225, 2002.
- Y. Crama and P. L. Hammer. Boolean Models and Methods in Mathematics, Computer Science, and Engineering. Cambridge University Press, 2010.
- Y. Crama and P. L. Hammer. Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, 2011.
- B. A. Davey and H. A. Priestley. Introduction to lattices and order. Cambridge university press, 2002.
- I. Gilboa and E. Lehrer. Global games. International Journal of Game Theory, (20):120–147, 1990.
- L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1994.
- I. N. Herstein. Algebra. Editori Riuniti, 1995. III edizione.
- R. Holzman and N. Law-Yone. Strong equilibrium in congestion games. Games and Economic Behavior, (21):85–101, 1997.
- A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic theory. Oxford University Press, 1995.
- D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, (14):124–143, 1996.
- R. G. Myerson. Graphs and cooperation in games. Mathematics of Operations Research, 2(3):225–229, 1977.
- G. Owen. Values of games with a priori unions. In R. Henn and
O. Moeschlin, editors, Essays in Mathematical Economics and Game Theory, pages 76–88. Springer, 1977.
- G. Owen. Values of graph-restricted games. SIAM Journal on Algebraic Discrete Methods, 7(2):210–220, 1986.
- G.-C. Rota. On the foundations of combinatorial theory I: theory of Möbius functions. Z. Wahrscheinlichkeitsrechnung u. verw. Geb., 2:340–368, 1964.
- A. E. Roth, editor. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge University Press - second edition, 1988.
- L. S. Shapley. A value for n-person games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory of Games, vol. II (Ann. Math. Studies 28), pages 307–317. Princeton University Press, 1953.
- L. S. Shapley. On balanced sets and cores. Naval Research Logistics Quarterly, 14:453–460, 1967.
- L. S. Shapley. Cores of convex games. International Journal of Game Theory, 1(1):11–26, 1971.
- M. Slikker. Coalition formation and potential games. Games and Economic Behavior, 37:436–448, 2001.

Assessment methods

two written exams: exercises

Office hours

See the website of Giovanni Rossi