Bachelor
2020/2021
Conflict and Cooperation
Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'
Category 'Best Course for New Knowledge and Skills'
Type:
Elective course (Applied Mathematics and Information Science)
Area of studies:
Applied Mathematics and Information Science
Delivered by:
Department of Mathematics
Where:
Faculty of Computer Science
When:
4 year, 3 module
Mode of studies:
offline
Instructors:
Marina Sandomirskaia
Language:
English
ECTS credits:
4
Contact hours:
46
Course Syllabus
Abstract
This course presents an introduction to cooperative games, solutions and applications to conflict situations. A large number of classic models of cooperative games will be analyzed. It also covers the problems of restricted cooperation and social choice.
Learning Objectives
- To familiarize students with the concepts, models and statements of the cooperative games in application to the theory of conflict.
- To introduce the basic notions of social choice theory.
Expected Learning Outcomes
- A student should know the definition of cooperative game, charachteristic function, and construct the clasic examples.
- A student shoud learn and apply the main solution concepts to cooperative games.
- A student should know the definition of convex games and should apply it to specific games.
- A student should learn the notion of limited cooperation and main approaches.
- A student should learn the foundations and main concepts in social choice theory and should apply them to conflict resolution.
Course Contents
- Cooperative games with transferable utility (TU games) and their interpretation.The characteristic function, relation between TU games and noncooperative normal form games, saving games and cost games. Types of TU games (essential and inessential games, superadditive games, convex games, monotonic games, simple games, constant sum games. Strategic equivalence, normalization. Basis of unanimity games, Harsanyi dividends. Examples of TU games: glove games, a game “landlord and peasants”, bankruptcy games, airport games, weighted majority games, market games, veto rich games, assignments games, big boss games.
- Main solution concepts for cooperative games, their properties and axiomatic characterization.The imputation set. Domination. Stable sets (von Neumann and Morgenstern solutions). The core, balanced games, necessary and sufficient conditions for the nonemptyness of the core. The nucleolus, existence and uniqueness, relation to the core, characterization via balancedness (the Kohlberg’s theorem). The Shapley value, different formula representations and their interpretation. Axiomatic characterization. The potential of the Shapley value. Simple games, the Shapley-Shubik power index. Properties, in particular the null-player out property. Asymmetric extensions of the Shapley value—probabilistic values, random-order values, the weighted Shapley value. Peculiarities of different solution concepts in particular classes of applied TU games.
- Classes of cooperative games with a nonempty coreNecessary and sufficient conditions for the convexity of a game, the Shapley’s lemma and the Ichiishi’s theorem. 1-convex and 1-concave games and their properties, 1- concave basis in the space of all TU games. Applied models of 1-convex/1-concave games: library games, data games, co-insurance games.
- TU games with limited cooperation and their solutions.Games with coalition structures. The Aumann-Drèze value and Owen value. Games with undirected graph communication structures. The Myerson value and its efficient modification, the average tree solution. Games with directed communication structures and their solutions for particular case of forest games. TU games endowed with both coalition and communication structures. Applications: the social capital index; the water distribution problem of a river with multiple sources, a delta and possible islands along the river bed, and a river with multiple users.
- Solution Concepts in Social choice modelsSocial choice models. Classic and non classic concepts of solutions: Condorcet winner, core, different versions of uncovered set, minimal weakly stable set, untrapped set, minimal dominant and undominating sets, k-stable alternatives and k-stable sets. Their matrix-vector representation.
Assessment Elements
- домашняя работа 1Homework is a written work that consists of 4-7 mathematical problems, each can contain several points. Together with the other homework, topics cover the whole course topics. The problems set is send to corporate students' e-mails, and they should send back the solutions (pdf files) during 10-14 days.
- домашняя работа 2Homework is a written work that consists of 4-7 mathematical problems, each can contain several points. Together with the other homework, topics cover the whole course topics. The problems set is send to corporate students' e-mails, and they should send back the solutions (pdf files) during 10-14 days.
- экзаменExam is a written work that consists of 5-6 mathematical problems, each can contain several points. Topics and format are similar to homeworks. The exam is conducted in a written form, i.e. studens should write their solutions on the paper and send scan to the teacher after the end of exam time. The exam is conducted on the Zoom platform. You must connect to the exam according to the response schedule sent by the teacher to the students ' corporate emails on the eve of the exam. The student's computer must meet the following requirements: a working camera and microphone, and Zoom support. To participate in the exam, the student must: put his / her photo on the avatar, appear for the exam according to the exact schedule, and turn on the camera and microphone when answering. During the exam, students are not allowed to turn off the camera. A short-term communication failure during the exam is considered to be a communication failure of less than 5 minutes. A long-term communication violation during the exam is considered to be a violation of 5 minutes or more. If there is a long-term communication failure, the student cannot continue to participate in the exam. The retake procedure involves the use of complicated tasks.
Interim Assessment
- Interim assessment (3 module)0.25 * домашняя работа 1 + 0.25 * домашняя работа 2 + 0.5 * экзамен
Bibliography
Recommended Core Bibliography
- Bezalel Peleg, & Peter Sudhölter. (2007). Introduction to the Theory of Cooperative Games. Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.b.spr.thdlic.978.3.540.72945.7
- Fuad Aleskerov, & Andrey Subochev. (2013). Modeling optimal social choice: matrix-vector representation of various solution concepts based on majority rule. Journal of Global Optimization, (2), 737. https://doi.org/10.1007/s10898-012-9907-2
- Schelling, T. C. (2006). Some Fun, Thirty-Five Years Ago. Handbook of Computational Economics, 1639. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.h.eee.hecchp.2.37
Recommended Additional Bibliography
- Ambec, S., & Sprumont, Y. (2002). Sharing a River. Journal of Economic Theory, (2), 453. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.a.eee.jetheo.v107y2002i2p453.462
- Anna Khmelnitskaya, & Elena Yanovskaya. (2007). Owen coalitional value without additivity axiom. Mathematical Methods of Operations Research, (2), 255. https://doi.org/10.1007/s00186-006-0119-8
- Anna Khmelnitskaya. (2010). Values for rooted-tree and sink-tree digraph games and sharing a river. Theory and Decision, (4), 657. https://doi.org/10.1007/s11238-009-9141-7
- Aumann, R. J., & Maschler, M. (1985). Game theoretic analysis of a bankruptcy problem from the Talmud. Journal of Economic Theory, (2), 195. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.a.eee.jetheo.v36y1985i2p195.213
- Driessen, T. S. H., Fragnelli, V., Katsev, I. V., & Khmelnitskaya, A. B. (2011). On 1-convexity and nucleolus of co-insurance games. Insurance: Mathematics and Economics, (2), 217. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.a.eee.insuma.v48y2011i2p217.225
- Herings, P. J. J., van der Laan, G., & Talman, A. J. J. (2008). The average tree solution for cycle-free graph games. Other Publications TiSEM. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.p.tiu.tiutis.f243609c.2847.415f.ae52.1b97dc517788
- Herings, P. J. J., van der Laan, G., Talman, A. J. J., & Yang, Z. F. (2010). The average tree solution for cooperative games with communication structure. Other Publications TiSEM. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.p.tiu.tiutis.24359ac5.6399.42ee.8f0b.7024fe1ba613
- Khmelnitskaya, A. (2014). Values for games with two-level communication structures. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.95C5FC6E
- René Brink, Gerard Laan, & Valeri Vasil’ev. (2007). Component efficient solutions in line-graph games with applications. Economic Theory, (2), 349. https://doi.org/10.1007/s00199-006-0139-x
- Rene van den Brink, Anna Khmelnitskaya, & Gerard van der Laan. (2011). An Efficient and Fair Solution for Communication Graph Games. Tinbergen Institute Discussion Papers. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.p.tin.wpaper.20110052
- Roger B. Myerson. (1977). Graphs and Cooperation in Games. Mathematics of Operations Research, (3), 225. https://doi.org/10.1287/moor.2.3.225
- Theo Driessen, Anna Khmelnitskaya, & Jordi Sales. (2012). 1-concave basis for TU games and the library game. TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, (3), 578. https://doi.org/10.1007/s11750-010-0157-5