- Docente: Giovanni Rossi
- Credits: 6
- SSD: SECS-P/01
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
Second cycle degree programme (LM) in
Mathematics (cod. 8208)
Also valid for Second cycle degree programme (LM) in Computer Science (cod. 8028)
Learning outcomes
The course aims to provide discrete mathematics knowledge for understanding and interpreting problems arising in computer science. Especially in the second part, which is the main one, players are likely to become variables of objective functions (in combinatorial optimization problems), as well as coalitions may become clusters or feasible subsets in given set systems.
Course contents
1 Strategic games
1.0 Rational preference (binary) relations: alternative representations and aggregation (Pareto efficiency)
1.1 Simultaneous move and multistage games
1.2 Extensive form, game tree and information sets
1.3 Strategies: dominated, rationalizable and best responses
1.4 Random strategies and expected utility
1.5 Equilibrium: existence, multiplicity and efficiency
1.6 Coalitional strategies and strong equilibrium
1.7 Potential and congestion games
2 Cooperative games
2.1 Introduction to ordered structures: posets and lattices
2.2 Coalitional games and the Boolean lattice
2.3 Solutions: valuations and Moebius inversion; Pseudo-Boolean functions and polynomial multilinear extension
2.4 Probabilistic and random-order solutions
2.5 Shapley and Banzhaf solutions
2.6 Core and convexity
2.7 Cooperation restrictions: partitions, graphs and set systems
2.8 Coalition formation games
2.9 Coalition structures, games in partition function form
Readings/Bibliography
Lecture notes are made periodically available to students. Many further readings, mostly in the form of journal articles, are specified during classes.
Teaching methods
Frontal lectures
Assessment methods
Grades obtain through two written tests: one after the first half of the course (at end of october / beginning of november), and the other one as soon as classes end (around dec 20th). Occasionally, an additional oral discussion is necessary, in case the written tests display substantial ambiguities. The student may always ask to discuss his/her written tests.
Links to further information
http://www.researchgate.net/profile/Giovanni_Rossi4
Office hours
See the website of Giovanni Rossi