Strategic Games in Normal Form PDF 2024-25

STRATEGIC GAMES IN NORMAL FORM Francis Kiraly Newcastle University, UK 2024-25 1 Introduction As discussed, any proper economics story revolves around the incentives of two (or more) parties to get tog...

STRATEGIC GAMES IN NORMAL FORM Francis Kiraly Newcastle University, UK 2024-25 1 Introduction As discussed, any proper economics story revolves around the incentives of two (or more) parties to get together and talk or trade, given that there is a positive surplus from doing so. A positive surplus means at least one party could end up being better o¤ from the exchange (and most of the time, both of them better o¤). Crucially however, any exchange settlement (agreement) carries within the tension of con‡icting interests: the more one party obtains, the less the other party has. Obviously, this tension carries through to situations where three (or more) parties interact, such as two …rms competing for customers: there is a demand (room for cooperation), but the surplus is fought over both by buyers and …rm(s), and …rms competing with each other. Two crucial questions arise. First, what are the potential agreements/…nal allocations? Second, how do the parties reach a particular agreement (if they do at all!): how does the …nal trade re‡ect the cooperation/competition between parties? To examine each question we need a "horses for courses" approach: The …rst question was examined using the framework of coalitional games. The line of attack was to abstract away from actual explicit actions and 1 the nitty-gritty of how binding agreements are actually reached: we ignored "transaction costs", and focused (using the concept of core) only on …nding the set of …nal e¢ cient allocations that could in principle emerge from an exchange situation. Answering the second question is more delicate, and it naturally depends on the full description of the interaction between parties, with details of their possible actions, informational setup, etc. This approach dispenses with the luxury of simply assuming that all mutually bene…cial exchanges are possible and implemented through binding commitments, and it instead attempts to …nd the actual …nal allocation (if any!!) as reached by players’ explicit interaction. For this, we need the framework of strategic games. The above distinction is so crucial it is worth repeating. With coalitional games, we concentrated on issues such as the value of various groups of play- ers (coalitions) getting together, and possible ways of sharing the surplus they create (allocations that are mutually bene…cial). This so-called "cooperative game theory" contained an implicit assumption of credible communication between parties, and that all agreements were enforceable (the e¢ cient ones in particular!). Parties could (pre)commit to any deal, without any "trans- action costs". But this approach did not explicitly consider any actions or strategies. Our next task is to spell out the strategies of players in any scenario where agents (players) interact, and where ex-ante communication, (pre)commitments and enforceable contractual agreements are not possible, either because of the nature of the interaction, or due to various "transaction costs". The mathematical language that captures such interactive decision mak- ing is called non-cooperative game theory, and the strategic situations them- selves are called strategic games. Note: the word "non-cooperative" has no ethical connotation: it simply denotes the fact that players cannot pre- commit to a …nal settlement; there are no binding contracts, and …nal allo- cations are the result of strategic interplay between players who may sense the possibility of bene…cial exchange but are also fully aware of con‡icting interests. Before we are able to investigate some familiar situations and institutions of exchange, we need to gain a basic training in non-cooperative game theory, 2 i.e. the general formal way of capturing and analysing any situation of strategic interaction between agents. Strategic interaction: a situation where the utility (payo¤) of a player depends not only on the actions of that player, but also on the actions and beliefs of the other players involved. The crucial thing is that all players are aware of this and are conscious of the fact that others players are aware of them, their possible actions and resulting potential outcomes. It is easy to see then that in the absence of a binding contract between the parties all human interaction (economic or otherwise) is strategic to some degree, and therefore a strategic game of some sort. Strategic games provide a simple "skeleton" for many economic stories involving human interaction. It is for this reason that game theory was such a major intellectual break- through. Recall the three main components of any strategic game: - the players (interactive decision makers); - each player’s set of strategies (available choices or actions); - the payo¤s: cardinal utilities that re‡ect the outcome for each player under all possible strategy combinations. There are two steps in formalising and analysing any real-world situation that is characterised by human interaction: Step 1. Consider the available strategies of each player and construct the payo¤s associated with each potential outcome. Strategies will either be simple one-o¤ actions or a sequence of actions (lumped together or detailing their sequence). In turn, the payo¤s are either calculated explicitly in the context of the story (as utilities, pro…ts etc.), or they are just numbers that simply re‡ect the ranking of various outcomes from the perspective of each player. NOTE: The strategies and payo¤s implicitly capture the incentives of players, and we will allow for a wide range of such incentives (i.e. we are NOT judgemental or prescriptive). But always remember that once chosen, the payo¤ measures o¤er a complete ranking of outcomes: changing these payo¤s by changing the ranking leads to a di¤erent game! 3  Step 2. "Solve" the game: that is, …nd and characterise the so-called strategic equilibrium. Naturally, this means trying to understand the resulting behaviour pat- tern and subsequent outcome of the strategic interaction between players. But this is done as carefully as possible: we will need to respect the players’ incentives (and hence their freedom!), and avoid predicting any action for a player that is sub-optimal given what she/he thinks the others think and do. All pretty intuitive, yet quite delicate (as you will see below). 2 Strategic games in normal form Strategic games in normal form capture the players and possible outcomes of their interaction, where strategies are also included, albeit still at a possibly general level. To grasp the basics, think of only two palyers. In all scenarios we now rule out any ex-ante communication and binding agreements. The normal form is appropriate when: a. The players move simultaneously (without coordinating), OR b. Although players act one after the other, but the player who moves second cannot observe the initial move, OR c. There are a series of actions, but we ignore the details of the respective sequential moves - we lump them together. To make this clearer, and illustrate Step 1 above, consider the following stories and examples (some already familiar): G1. Two team games (I warmly recommend the …lm True Blue, about a famous Boat Race...) GAME A: - two student rowers in the same boat; - assume the opposition is weak, and they win as long as at least one of them pulls hard; - they choose e¤ort (either high or low) without coordinating; - cost of high e¤ort is 4, low e¤ort is costless; - if both pull hard, the winning margin is greater, and the utility from a win is 6 to each; 4  - if only one of them pulls hard, the winning margin is smaller, and the utility from a win is 3 to each; - they lose the race (utility zero to each) if neither puts in high e¤ort. GAME B: Same as above, but now assume low e¤ort is considered shame- ful, and bears a utility penalty of 6. G2. Bertrand duopoly –two …rms, with same technology: marginal costs c - …rms choose prices without coordinating; - only the cheapest seller gets customers G3. Cournot duopoly - two …rms with same technology: marginal cost c - …rms choose production levels without coordination; - market demand: P (Q) = a Q = a (q1 + q2 ) where a > c Now Step 1: let us try to capture the above stories (economic examples) in appropriate normal game forms: G1. GAME A I = fstudent 1, student 2g is clearly the set of players. S1 = S2 = fA (high e¤ort), B (low e¤ort)g: both players have the same strategy set. Payo¤s: obviously, with two actions available to each rower, there are four potential outcomes 1 (A; A) = 2 and 2 (A; A) = 2: if both pull their weight, a win is worth 6 to each, but at cost 4 to each, and 5  1 (A; B) = 1 and 2 (A; B) = 3: the win is worth only 3, meaning the student who rowed hard gets a net utility of 1, while the free-riding student gets 3; 1 (B; A) = 3 and 2 (B; A) = 1 same as before, with roles reversed; 1 (B; B) = 0 and 2 (B; B) = 0: in this case, they lose. Note the clear ranking of the four potential outcomes, as measured by payo¤s. With a …nite/discrete number of actions/strategies (here two for each player) - we can represent Game A in a convenient bi-matrix form: [We will throughout keep to the following convention: Player 1’s strategies are to the left of the matrix, and her payo¤ is always the …rst number in each cell. Clearly, each payo¤ cell corresponds to (and describes) the outcome of potential strategy combinations (pro…les).] One can also depict the set of possible payo¤s for our two players on a Cartesian diagram, where each point represents a payo¤ pair - one for each player. Furthermore, one could link these four points such that we …ll out the resulting geometric form as much as we can, and then consider all the other many many payo¤s within the shaded area. As we will see, all payo¤s within this geometric shape are in fact feasible given the strategies of our two students. Diagrammatically: Figure 6  GAME B: What changes?? On the surface, not much, except that any payo¤ that re‡ects the utility of a rower who puts in low e¤ort needs to be re-calibrated to include the disutility of "shame": we simply substract 6 from these payo¤s: Figure G2. I = fFirm 1, Firm 2g; S1 = S2 = (c; +1) (any price that is higher than marginal cost) (p1 c)D(p1 ) if p1 < p2 1 (p1 ; p2 ) = 0 if p1 > p2 (p2 c)D(p2 ) if p2 < p1 2 (p1 ; p2 ) = 0 if p2 > p1 Note: the payo¤ (pro…t here!) functions re‡ect the fact that only the …rm with a lower price will sell. G3. I = fF irm1; F irm2g; S1 = S2 = 0 > 2), so we conclude that the unique equilibrium obtained by relying on CKD only is (U; R). Now check for the Nash equilibrium. Using the elimination method (i.e. checking every strategy pair as to whether unilateral deviations are prof- itable), we …nd that the unique NE is (U; R). Unsurprising of course: if it exists, an equilibrium obtained through dele- tion of strictly dominated strategies must be also a strategic (Nash) equi- librium. But the reverse is not true: a Nash equilibrium does not have to be obtained through deletion of strictly dominated strategies - as said be- fore, such games are in fact relatively rare. Again, we can appreciate the helpfulness of the concept of Nash equilibrium. NOTE 3: Before you get too excited about how easy it is to follow the "cook book" provided, bear in mind that sometimes you might in fact want to use the elimination method even with a continuous strategy set (see below). G6. Hotelling Duopoly Story: - two shops simultaneously locate on a ”line”(street); - sellers compete for consumer base, knowing that buyers go to the nearest seller. Although the strategy set is continuous (locate anywhere on the line), the way to …nd the (unique) NE is by using the elimination method (b). Doing so, we …nd that the equilibrium has both shops locating in the middle of the line. Why? 18  We proceed peacemeal, by eliminating other natural candidates. One that springs to mind is with shops located at each end. Clearly, they would then share equally the customer base (each gets the nearest half of street). BUT: if the rival is at the other end, each shop could do better than this by "deviating" and moving away from the end of the street. Say, consider the shop at the extreme right end. It could attract more shoppers if it moved farther to the left: it would still keep shoppers to its right, and now half of the consumer base in-between the two of them ("eating into" the other’s consumer base). Measure this out on the above picture to see this. Similar logic destroys any equilibrium candidate with the two shops lo- cated at any separate point on the street. (Check this too!). However, if both of them locate in the middle (see picture), this turns out to be the (unique) Nash equilibrium. Both get half of customer base (1/2) as consumers do not care where they shop. If one moves away (to the left or right), while the other one stays put, the deviating shop attracts everybody for whom this shop suddenly becomes the nearest, but only half of the customers between the two shops. The unilateral deviation would not therefore be pro…table! G2. Bertrand Duopoly Again, the choice variable is continuous (any price higher than marginal cost)...so: - Try the reaction function approach (but you will probably give up soon); - Use common sense and apply the elimination procedure (b)...to …nd that the unique NE of this game has: p1 = p2 = p = c Check!! [Hint: consider what happens if …rm 1 deviates and sets a slightly higher price than p1 ; or possibly sets a lower price...]. 19  To understand better, consider what happens if say......both choose equal prices but both prices are higher than marginal cost, or...if they were to set di¤erent prices...etc. etc. The battle cry is "eliminate, eliminate!" This, of course, is the famous Bertrand Paradox where …rms (although with considerable market power) end up with zero pro…ts! No real paradox of course: it is the power of direct competition. Note: so far, we only considered games with a unique strategic equilib- rium, and one (G5) apparently without one. But some games have more than one equilibrium... G7. Co-ordination games and multiple equilibria Although I gave no description of the story behind this game, its struc- ture was …rst analysed in the context of the so-called "Battle of the Sexes" scenario: A couple try to coordinate, but without communication. Going to the rugby match or theatre are the options. The payo¤s re‡ect that the boyfriend is happiest if at the match, together with his girlfriend. For her, the best outcome would be theatre, with him. The worst outcome (for both) is if they end up in separate places. Being together, even if you are not at your favourite venue, is better. It turns out that this game has two Nash equilibria (A; A) and (B; B) - a case of multiple equilibria. (We know how to hunt them down by now, so practice/indulge please.) This simple example highlights two important issues. First, it shows the potential fragility of the outcome: here, whether one or the other equilibrium 20 is played out depends purely on players’beliefs about what the other does: if I think you play A, I will play A, and vice-versa. Or, we think and play B. Second, it reminds one of the richness of social interactions in terms of possible competing outcomes. The multiplicity of equilibria could point to the need to be aware of and include other relevant details in the description of the game, which would then select one equilibrium. For example, what if the coordination between them takes place on a horrible windy and rainy day?...Would they coordinate on Theatre? (...BUT be careful: recall that this really amounts to changing the payo¤s, possibly reducing the pleasure of going to rugby - we would NOT then be solving the same game as above). Furthermore, sometimes it is possible to rank multiple equilibria accord- ing to the Pareto criterion (not here though, as they both result in same combined payo¤ for the players). In that case, coordinating on the "nice" equilibrium appears likely(?). Indeed, the game with payo¤s (100; 100) in- stead of (3; 1) in the …rst cell "smells" very di¤erent.... Additional details (possibly carelessly left out), or obviously ranked payo¤ structures could then act as "focal points" - the importance of these was stressed by T. Schelling (NP). G8. A(nother) game without an equilibrium? Check that this game has no Nash equilibria - well, no equilibrium in so-called pure strategies (i.e. the way we considered strategies up to now!). This was also true for game G5, and I don’t blame you if you feel slightly betrayed at this point: after all, we said that the N E always exists! Well......What if players can randomise, and use mixed strategies? What if each player believes that the other player is choosing each of their strategies with a certain probability? Note: such "mixing things up a bit" type of strategy or behaviour is widespread - just think of sports (penalties in football, or bowling/batting in cricket). 21  Let’s formalise this idea. Assume that player 1 plays T with probability p and B with probability 1 p; whereas player 2 plays L with probability q and R with probability 1 q. Can such reciprocal randomisation be an equilibrium behaviour? For player 1 to want to randomise at all, she has to be indi¤erent between playing T or B, and this happens if: q1 + (1 q)( 2) = q( 4) + (1 q)2 That is, her expected payo¤ E 1 (T ) from playing T is the same as her expected payo¤ E 1 (B) from playing B (Note: "expected" since it depends on what player 2 does, and his way of randomising!). Here, we obtain that player 1 is indi¤erent if PLAYER 2 (!!) randomises with q = 4=9 (and 1 q = 5=9 respectively). Similarly, player 2 will want to randomise if indi¤erent between playing Lor R, that is E 2 (L) = E 2 (R) : p( 3) + (1 p)5 = p(3) + (1 p)2...and this happens if PLAYER 1 (!!) randomises with p = 1=3 (and 1 p = 2=3 respectively). With (p ; q ) as obtained above, each player is indi¤erent between their two strategies and the way they randomise makes the other player indi¤erent too. In other words, the way they randomise constitutes a pattern of best responses: we have a mixed strategy Nash equilibrium. Please check that the expected payo¤s from either strategy for both play- ers are indeed equal. One does this by simply substituting back into the above expected payo¤s the equilibrium values of p and q. Overall, what are the expected payo¤s for the two players? Simply put everything together: what they each do, and what they can expect to get under all scenarios: 1 = p [q (1) + (1 q )( 2)] + (1 p )[q ( 4) + (1 q )2] = 2=3 2 = q [p ( 3) + (1 p )(5)] + (1 q )[p (3) + (1 p )(2)] = 7=3 22  Diagrammatically: Now, apart from the four payo¤ pairs possible in principle when only pure strategies our played out, the use of mixed strategies leads to many more: any of the remaining payo¤ pairs (points in the geometric shape constructed by linking the four pure strategy payo¤ combinations). You may wish to highlight this set of feasible payo¤s with a shaded area. Indeed, the equilibrium expected payo¤s calculated above represent a point in your shaded area: please pick it out on the diagram! Also note that in this game the set of possible payo¤ combinations is not convex : some corners "stick out". Nonetheless, one can convexify it and construct the so-called convex hull, by linking the two payo¤ points that "stick out" and joining them. This additional convexi…ed area contains further feasible payo¤s obtainable through all kinds of randomisations of our four pure strategies. What about G5??? Well, as we suspect by now, this game may not have a N E in pure strategies, but it is sure to have one in mixed strategies. However, as it is not a 2 2 game (i.e. two players with two strategies each), we will not compute it. It would be perfectly possible with three strategies (as here), tedious with more, but you will only be asked to look into mixed N E for 2 2 games. Incidentally, in games with many many players (so-called population games) the interpretation of mixed strategies is even more intuitive: it describes the proportion (fraction/measure/mass) of players playing particular strategies. Some students will encounter such games in ECO3032 this year. A …nal practical insight. Any 2 2 has an odd number of Nash equilibria: either one mixed N E, or one pure N E, or one mixed N E with two pure N E. Handy to remember when you solve such simple games. 23