Bachelor 2020/2021

Operations Research and Game Theory

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: 3 year, 3, 4 module

Mode of studies: offline

Instructors: Nikolay Klemashev, Marina Sandomirskaia

Language: English

ECTS credits: 6

Contact hours: 80

Course Syllabus

Abstract

This course has two parts. The first part introduces main concepts and models of classic and modern operations research. The operations research combines methods from different fields of mathematics in order to aid decision makers in making optimal decisions. In order to apply operations research methods, one needs to transform an actual problem into an appropriate mathematical model. In order to develop intuition for developing mathematical models all the operations research techniques are widely illustrated by examples from different industries, including agriculture, oil and gas, manufacturing, urban development, and retail. The second part of the course is devoted to game theory is a mathematical language of modern economic and social science. Any time a model involves conflict of interest game theory is needed since it is the study of strategic decision making. Game theory has numerous applications including economic theory, political science, evolutionary biology, computer science, etc. This course covers the non-cooperative and cooperative game theory, bargaining theory, foundations of mechanism design, as well as giving insights into some of its present-day applications. The course presents main ideas and techniques of game-theoretic analysis. The aim is to teach students to use game theoretic approach in modeling of real-life problem and to think strategically. Success with this course gives edge both in deeper understanding of human behavior and in tackling business problems.

Learning Objectives

• To familiarize students with the basic concepts, models and statements of the operations research theory.
• To familiarize students with the basic concepts, models and statements of the modern game theory.

Expected Learning Outcomes

• A student should learn the foundations and logic of utility theory
• A student should learn the concept of the game, its elements, Nash equilibrium and dominance. She should solve the games in pure strategies.
• A student should find Nash equilibrium in mixed strategies in games 2x2 and 2xN.
• A student should solve dynamic games with complete information and find Nash equilibria and SPNE.
• A student should aplly the Folk theorem to solving repeated game.
• A student should know the notion of types and find the complete strategy equilibrium profile in Bayesian games.
• A student should solve sealed-bid first-price and second-price auctions.
• A student should analyze dynamic games, know the notion of information set, beliefs, can find WSE and check if it is SSE.
• A student should model the dynamic game as signaling and find and interpret its equilibria.
• A student should solve different types of two-person bargaining problems.
• Knows how to formulate linear programs and solve them.
• Knows Lagrange multipliers methods for solving extremum problems.
• Knows properties of transportation models.
• Knows network optimization algorithms.
• Knows how to formulate integer linear programs and solve them.
• Knows dynamic programming method and its classical applications.
• Knows queuieng theory models and applications.
• Knows how to estimate performance measures of queueing models with simulation modeling.

Course Contents

• Utility theory. Prospect theory.
  Preference relations and their representation. Preference relations over uncertain outcomes: the model. The axioms of utility theory. The characterization theorem for utility functions. Attitude towards risk. Subjective probability. Decision process and prospect theory. Applications: disposition effect, reversing of risk aversion/risk seeking, framing, etc.
• Repeated games.
  Finite and infinite repeated games. A Markovian strategy. Folk Theorem.
• Bayesian games: Games with incomplete information.
  Information set. Bayesian-Nash equilibrium. Perfect Bayesian equilibrium
• Introduction to auction theory.
  Types of auctions. Sealed bid auctions with private values. Revenue equivalence theorem.
• Dynamic games with incomplete information.
  Sequential equilibrium, weak and strong. Connection with perfect Bayesian equilibrium.
• Signaling games
  Separating and pooling equilibrium. Applications: beer-quiche game, spence job-market signaling game
• Static games with complete information: pure strategy.
  Definition of game. Examples of playing and non-playing problems. Examples of simple games: the prisoner’s dilemma, coordination game, the inspectorate. Concept of the strategy. Domination. Elimination of dominated strategy. The equilibrium dominance. Nash Equilibrium. The connection between equilibrium dominance and Nash equilibrium.
• Static games with complete information: mixed strategy.
  Concept of mixed strategy. Games of 2x2 and 2xN.
• Bargaining Problem.
  A two-person bargain problem. Nash bargaining solution. Kalai–Smorodinsky bargaining solution. Egalitarian bargaining solution. Rubinstein procedure. Connection between Nash and Rubinstein bargaining.
• Dynamic Games of Complete Information.
  Examples of dynamic games. The game in extensive form. Backward induction. Behavioral strategy. The equivalence of mixed and behavioral strategies. Threats and promises. Subgame perfect equilibrium. Alternative logic: equilibrium in secure strategies and Nash-2 equilibrium.
• Operations research. Mathematical models of operations research. Solution of the operations research models. Unrestricted extremum problems. Constrained extremum problems.
• Linear Programming. Introduction to linear programing (LP). Standard form of the linear programming problem. Linear programming applications. Graphical method of solution of the linear programming problem. Transition from graphical to algebraic solution. Simplex method. Special cases in applying the simplex method. Graphical Sensitivity Analysis. Dual program identification. The relations between direct and dual problem. Economic interpretation of duality.
• Transportation models. Solution of the transportation problem. Problem of allocation. Transportation model with transshipment points.
• Classic and modern network models. Shortest path problem. Maximum flow problem. Minimum-cost flow problem. Critical path method.
• Integer linear programming. Integer linear programming applications. Methods for solving linear integer programming problems. Travelling salesperson problem.
• Deterministic model of the dynamic programming. Recurrent algorithm of the forward and backward solution. Loading problem. Equipment replacement problem.
• Deterministic models of inventory. Classical problem of the economic order quantity. Problem of the economic order quantity with price breaks. Multicommodity static model with the limited capacity of the stock. Dynamic problems of the economic order quantity.
• Queueing theory. Principal elements of the queueing theory models. Exponential distribution in the queueing systems. Birth-death models (connection between exponential and Poisson distribution). General Poisson queuing model. Specialized Poisson queues.
• Simulation modeling Monte-Carlo method. Types of simulation models. Elements of discrete event simulation. Mechanics of discrete simulation. Methods for gathering statistical observations. Software for simulation modeling.

Assessment Elements

• Домашняя работа ТИ-1
  Homework consists of tasks that are equivalent or similar to those which have been studied at lectures and seminars.
• Домашняя работа ТИ-2
  Homework consists of tasks that are equivalent or similar to those which have been studied at lectures and seminars.
• Экзамен Final
  Экзамен и первая пересдача включают вторую часть курса (теорию игр). Пересдача с комиссией включает все материалы курса. Экзамен проводится в письменной форме. Экзамен проводится на платформе Zoom. К экзамену необходимо подключиться с начала времени проведения экзамена по РУЗ. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Zoom Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, во время всего экзамена держать включенным микрофон и камеру. Во время экзамена студентам запрещено: выключать камеру без согласования с преподавателем, выключать микрофон, отходить от рабочего места. Пользоваться конспектами с материалами курса разрешено. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 10 минут. Долговременным нарушением связи во время экзамена считается нарушение 10 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи проводится в соответствии с правилами курса. После окончания экзамена студент в течении 10 минут должен сфотографировать свое решение и выслать его на почту преподавателя, по аналогии с форматом домашних работ.
• Домашняя работа ИО-1
  Homework consists of tasks that are equivalent or similar to those which have been studied at lectures and seminars.
• Домашняя работа ИО-2
• Midterm тест
  Operation Research part is only included.

Interim Assessment

• Interim assessment (4 module)
  0.3 * Midterm тест + 0.1 * Домашняя работа ИО-1 + 0.1 * Домашняя работа ИО-2 + 0.1 * Домашняя работа ТИ-1 + 0.1 * Домашняя работа ТИ-2 + 0.3 * Экзамен Final

Bibliography

Recommended Core Bibliography

• A first course in optimization theory, Sundaram, R. K., 2011
• An introduction to game theory, Osborne, M. J., 2004
• An introduction to game theory, Osborne, M. J., 2009
• Maschler,Michael, Solan,Eilon, & Zamir,Shmuel. (2013). Game Theory. Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.b.cup.cbooks.9781107005488
• Zamir, S., Solan, E., & Maschler, M. (2013). Game Theory. Cambridge: Cambridge eText. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=527892

Recommended Additional Bibliography

• Binmore, K. (2007). Playing for Real: A Text on Game Theory. Oxford University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.b.oxp.obooks.9780195300574
• Game theory : analysis of conflict, Myerson, R. B., 1997
• Game theory : analysis of conflict, Myerson, R. B., 2004
• Game Theory: A Multi-Leveled Approach. (2008). Springer Verlag. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsnar&AN=edsnar.oai.cris.maastrichtuniversity.nl.publications.f0459d98.4840.4780.9538.9cb97d614697
• Iskakov, M., Iskakov, A., & d’Aspremont-Lynden, C. (2018). Games for cautious players: The Equilibrium in Secure Strategies. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.D42CDAA3
• Michael Spence. (1973). Job Market Signaling. The Quarterly Journal of Economics, (3), 355. https://doi.org/10.2307/1882010
• Sandomirskaia, M. (2017). Nash-2 equilibrium: selective farsightedness under uncertain response. MPRA Paper. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.p.pra.mprapa.83152