82114 - GIOCHI E MODELLI BOOLEANI

Conoscenze e abilità da conseguire

L'insegnamento si divide in due parti. Nella prima parte, l'obiettivo dell'insegnamento è quello di fornire allo studente gli strumenti per l'analisi dell'equilibrio con strategie deterministiche (o pure) e random (o miste), e poi proseguire studiando l'equilibrio strong, i potential games e i congestion games. Nella seconda parte, i giochi cooperativi vengono studiati come funzioni a valori reali su insiemi parzialmente ordinati e accanto ai coalitional games vengono anche considerati problemi di ottimizzazione combinatoria basati sulle partizioni di un insieme finito.

Contenuti

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

Testi/Bibliografia

- 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.

Metodi didattici

lezioni frontali

Modalità di verifica e valutazione dell'apprendimento

due prove scritte: esercizi

Orario di ricevimento

Consulta il sito web di Giovanni Rossi