Hello, my name is Ovanes Petrosian. This online course is devoted to the field of Game Theory. During this course, we will study static games, dynamic and differential games. The static games are the models for processes where agents or players make their moves simultaneously and independently of each other. For dynamic and differential games, for the simplest case, we suppose that the players make their moves one after another. In each step, they observe the actions of other agents. So, they know the information about the game. Also, for both of this class of games, we will study zero-sum games, non-cooperative games and cooperative games. Zero-sum games are the games where we have an agent or a player who tries to maximize his utility and there is the other player or the agent who is acting against him. The question is, how to define the optimal strategies for both of the players, especially for the player one. Non-cooperative games are the models of processes where we have N participants or N agents. Each of these agent has his own goal or his own utility function, which of course depends on the strategies or the actions of all players. In here, the question is of how these players would behave? How can we forecast the behavior of these players? The next class is cooperative games. Cooperative games could be used in order to model the cooperative agreements, where the question is of how to allocate the joint utility or the joint payoff of all players. The next thing we can do is we can define of how the players would cooperate? Which actions or strategies should they choose in order to achieve cooperation or in order to sustain cooperative agreement? But today, we will start with zero-sum games in normal form. Consider a classical game theoretical example called Colonel Blotto game. Suppose that we have a Colonel who has m regiments, and we have his enemy who has n regiments. The question is of how to allocate regiments of Colonel Blotto on two battlefields? And the same question we have for his enemy. In this game model, we suppose that the side that allocates the biggest number of regiments on one battlefields wins there. Of course, both sides try to maximize the number of battlefields they win and, most importantly, we assume that the Colonel Blotto and his opponent make their move simultaneously and independently of each other. So, we suppose that both of these players do not have spies and cannot get the information about the other's actions. In order to construct a mathematical model for this process, we need to introduce a notion zero-sum game in normal form. The system Gamma=(X,Y,K) is called a zero-sum game in normal form if X and Y are the non-empty set of strategies of player one and player two correspondingly, and function K, which is a function defined on the set of possible realizations of this strategy is a payoff function of player one. We will denote x from X as a strategy of player one, and we will denote y from Y as a strategy of player two, a pair (x,y) is a strategy profile in the game, and K(x,y) is a payoff function of player one as a function of a strategy profile. Since we consider a zero-sum game, then the payoff of the second player is equal to the minus payoff of the first player because we suppose that the first player tries to maximize his utility or his payoff, and the second one tries to minimize it or acts against him. For Colonel Blotto game, set of strategies of the first and the second player consists of vectors: vector X=(x1,x2), and vector Y=(y1,y2), where x1 and x2, y1 and y2 are the number of regiments which are to be allocated on the battlefield one and battlefield two. Of course, the total number of regiments for both players are fixed and for Colonel Blotto x1 plus x2 is equal to m. It means that he needs to allocate exactly m regiments on two battlefields. Payoff of the first player or Colonel Blotto is calculated as a sum of payoffs that he obtained on each battlefield. For each battlefield, there are three options. The first option is when Colonel Blotto wins. It happens when x_i is strictly larger than y_i. So, when the number of regiments that the Colonel Blotto allocates on the battlefield i is strictly more than the number of regiments that his opponent allocates there. In this case, the payoff of Colonel Blotto is equal to y_i plus one. So, the number of regiments of his opponent plus one. In case when x_i is equal to y_i, Colonel Blotto receives a payoff equal to zero. So, when the number of regiments of Colonel Blotto and his opponent on the battlefield i is equal, then nobody wins. The third option is when Colonel Blotto loses on particular battlefield. It happens when x_i is strictly less than y_i, when the number of regiments of Colonel Blotto on battlefield i is strictly less than number of regiments of his opponent on the battlefield i. In this case, the payoff of Colonel Blotto is calculated as -(x_i+1). So, the minus number of his regiments plus one. The payoff of the second player is calculated according to the formula presented on the slide. For Colonel Blotto game, we can also construct a matrix game. So the two-person zero-sum games in which both players have finite set of strategies are called matrix games. For matrix games, strategies of the first and second players have the following form, x0, x1 etc... xm, and for the second player, y0, y1 etc... yn. So, there is a finite set of strategies. Set of strategy profiles is also finite and the payoff function of the first player is defined for each of the strategy profile and can be written in the form of a matrix. The payoff of the second player is calculated as minus payoff of the first player. For Colonel Blotto game, we can also construct such a matrix as a matrix of payoffs. But before we do that, we suppose that the strategies of the first and the second player has the following form. So the x_i is equal to (m-i,i) and yj is equal to (n-j,j). So, the number i and j corresponds to the number of regiments which will be allocated on the second battlefield, and m-i and n-j are the number of regiments that will be allocated on the first battlefield. Then, on the right-hand side of the slide, you can see how the payoffs of Colonel Blotto can be computed for an arbitrary values of m, n, i and j. On the left-hand side, you can see a case of a matrix game for Colonel Blotto game when m is equal to 4 and n is equal to 3. So, when Colonel Blotto has four regiments and his opponent has three regiments. On this slide, you can see a list of references where you could get more information about the zero-sum games and corresponding examples.
