Open access

Modeling Engineering Management Decisions with Game Theory

Written By

William P. Fox

Submitted: 29 June 2012 Published: 06 March 2013

DOI: 10.5772/54501

From the Edited Volume

Engineering Management

Edited by Fausto Pedro García Márquez and Benjamin Lev

Chapter metrics overview

2,802 Chapter Downloads

View Full Metrics

1. Introduction

Engineering management is a management process that blends of engineering and business processes. As such the ability to make decision as well as model the decision making process may be critical steps in the process. In game theory, we employ the process to gain insights into possible courses of action from each player assuming the players are rational, that is they want to maximize their gains.

In many business situations, two or more decision makers simultaneously and without communications choose courses of actions, and the action chosen by each affects the payoff or gains earned by all the other players. For example, consider a fast food chain such as Burger King. If they choose an advertising strategy with pricing not only do they help their payoffs but their choices affect all other fast food chains. Each company’s decision affect the revenues, profits, of loses of the other fast food chains.

Game theory is useful in analyzing decisions in cases where two or more decision makers have conflicting interest. Most of what we present here concerns only the two person game but we will also briefly examine the n-person game.

In two person games, each of the players has strategies or courses of action that they might choose. These courses of action lead to outcomes or payoffs to the decision maker and these payoffs might be any values (positive, negative, or zero). These payoffs are usually presented in a payoff matrix such as the general one presented in Table 1. In table 1 player 1, whom we will call Rose, might have m course of actions available and player 2, whom we will call Colin, may have n courses of actions available. These payoffs values might have come from ordinal utilities or cardinal utilities. For more information about obtaining payoff values please see the additional reading (Straffin, 2004; Von Neumann & Morgenstern, 2004).

Game theory is the branch of mathematics and decision theory concerned with strategic decisions when two or more players compete. The problems of interest involve multiple participants, each of whom has individual strategies related to a common system or shared resources. Because game theory arose from the analysis of competitive scenarios, the problems are called games and the participants are called players. But these techniques apply to more than just sport, and are not even limited to competitive situations. In short, game theory deals with any problem in which each player’s strategy depends on what the other players do. Situations involving interdependent decisions arise frequently, in all walks of life. A few examples in which game theory might be used include:

  • Friends choosing where to go have dinner

  • Couples deciding between going to ballet or a sporting event

  • Parents trying to get children to behave

  • Commuters deciding how best to travel to work

  • Businesses competing in a fair market

  • Diplomats negotiating a treaty

  • Gamblers betting in a game of chance

  • Military strategists weighing alternatives, such as attack or defend

  • Governmental diplomacy options for sanctions or actions

  • Pitcher-batter duel in baseball or penalty kicker-goalie duel in soccer

All of these situations call for strategic thinking, making use of available information to devise the best plan to achieve one’s objectives. Perhaps you are already familiar with assessing costs and benefits in order to make informed decisions between several options. Game theory simply extends this concept to interdependent decisions, in which the options being evaluated are functions of the players’ choices or their utility.

Player 1, Rose’s Strategies Player 2, Colin’s Strategies
Column 1 Column 2 Column n
Row 1 M1,1,N1,1 M1,2N1,2 M1,nN1,n
Row 2 M2,1N2,1 M22,N22 M2,n,N2,n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Row m Mm,1,Nm,1 Mm,2Nm,2 Mm,n,Nm,n

Table 1.

Payoff Matrix, M, of a two-person total conflict game

Consider the situation where two major discount stores want to come into the same region. We will call these two major discount stores, Target and Wal-Mart. Each store can decide whether to build their store in the region’s larger city or in the region’s smaller city. The stores desire the bigger market share of the consumers that yields more profits for their respective company. Experts have estimated the market share in the region for the larger and smaller city building options based upon 100% of the consumer market and income of the region. Based upon this market research, table 1, what decisions should each store make? As we will show later in this chapter, the best decision for each store is to locate in the larger city.

Wal-Mart
Large City Small City
Target Large City (60,40) (75,25)
Small City (50,50) (58,42)

Table 2.

Target versus Wal-Mart

Two types of games will be presented in this chapter: total conflict games and partial conflict games. Game theory then is the study of decisions where the outcome to the decision maker depends not only on what he does, but the decision of one or more additional players. We classify the games depending upon whether the conflict between the players is total or partial. A total conflict game is a game where the sum of values in each cell of the payoff matrix, Mij+Nij either always equals 0 or always equals the same constant for each ij pair. In a partial conflict game, this sum does not always equal 0 or the same constant. We begin our discussion with the total conflict game described in Table 1.

Advertisement

2. Two–person total conflict games

We begin with characteristics of the two-person total conflict game:

  1. There are two persons (called the row player who we will refer to as Rose and the column player who we will refer to as Colin).

  2. Rose must choose 1 of m strategies and Colin must choose one of n strategies.

  3. If Rose chooses the ith strategy and Colin the jth strategy then Rose receives a payoff of aij and Colin loses an amount aij.

  4. There are two types of possible solutions. Pure strategy solutions are when each player achieves their best outcomes by always choosing the same strategy in repeated games. Mixed strategy solutions are when players play a random selection of their strategies in order to obtain their best outcomes in repeated games.

Games might be presented either in decision tree or payoff format. In a decision tree for sequential games, we look ahead and reason back. In simultaneous games, we use payoff matrices as shown in Table 1. This is a total conflict game if and only Mi,j+Ni,j equals either 0 or the same constant for all i and j.

For example, if a player wins x when the other player loses x then their sum is zero or in business marketing strategy based upon 100% if one player get x% of the market then the other player gets y% such that their sum is x%+y%=100. Given a simple payoff matrix we look for the Nash equilibrium as the solution first with movement diagrams.

Example 1 Target versus Wal-Mart

Suppose Large City is located near Small City. Now assume a smaller grocery store such as Target will locate a franchise in either Large City or Small City. Further, a “mega grocery store” franchise such as Wal-Mart is making the same decision – they will locate either in Large City or Small City. Analysts have estimated the market shares and we place both sets of payoffs in a single game matrix. Listing the row player’s payoffs first, we have the payoff as shown in Table 2. We apply the movement diagram, were we draw arrows in each row (vertical arrow) and column (horizontal arrow) from the smaller payoff to the larger payoff.

Table 3.

Payoff matrix for example 1

Note all arrows point into the payoff (60,40) at (Large City, Large City) strategies for both players and no arrow exits that outcome, see Table 3. This indicates that neither player can unilaterally improve their solution. This stable situation is called a Nash Equilibrium. Often payoff matrices and movement diagrams may get convoluted or the arrows do not point to one or more points. In those more complex two-person games we offer linear programming as the solution method.

Advertisement

3. Linear programming of total conflict games

Every total conflict game may be formulated as a linear programming problem. Consider a total conflict two person game in which maximizing player X has m strategies and minimizing player Y has n strategies. The entry (Mij,Nij) from the ith row and jth column of the payoff matrix represents the payoff for those strategies. We present the following formulation using the elements of M for the maximizing a player that provides results for the value of the game and the probabilities xi (Fox, 2010; Fox, 2012; Winston, 2003). We note that if there are negative values in the payoff matrix then we need a slight modification to the formulation. We suggest the method by Winston (2003) to replace any variable that could take on negative values with the difference in two positive variables, VjV'j. We only assume that the value of the game could be positive or negative. The other values we are looking for are probabilities that are always non-negative.

Maximize V

Subject to

N1,1x1+N2,1x2+...+Nm,1xnV0N2,1x1+N2,2x2+...+Nm,2xnV0...Nm,1x1+Nm,2x2+...+Nm,nxnV0x1+x2+...+xn=1NonnegativityE1

where the weights xi yields Rose’s strategy and the value of V is the value of the game to Colin.

Maximize v

Subject to

M1,1y1+M2,1y2+...+Mm,1ynv0M2,1y1+M2,2y2+...+Mm,2ynv0...Mm,1y1+Mm,2y2+...+Mm,nynv0y1+y2+...+yn=1NonnegativityE2

where the weights yi yield Colin’s strategy and the value of v is the value of the game to Rose.

Our two formulations for this problem are for Rose and Colin, respectively:

Maximize Vc

Subject to:

40 x1+50x2Vc025x1+42x2Vc0x1+x2=1x1,x2,Vc0

Maximize Vr

Subject to:

60 y1+75y2Vr050y1+58y2Vr0y1+y2=1y1,y2,Vr0

If we put our example into our two formulations and solve, we get the solution y1=1,y2=0 and Vr=60 from formulation (1) and x1=1,x2=0, and Vc=40 from formulation (2). The overall solution is (Large City, Large City) with value (60,40).

Advertisement

4. Constant–sum to zero–sum

The primal-dual only works in the zero-sum game format. We may convert this game to the zero-sum game format to obtain. Since this is a constant sum game, all outcomes sum to 100. This can be converted to a zero sum game through the positive linear function, y=x-20. Use any two pairs of points and obtain the equation of the line and then make the slope positive. Using this transformation x1=x-20 we can obtain the payoffs for the row player in the zero-sum game. The new zero-sum payoff matrix may be written as follows:

Table 4.

Add Caption

For a zero-sum game we can again look at movement diagrams, dominance, or linear programming. If one Rose’s information is present representing the zero sum game then only assume Colin’s values are the negative of Rose’s. We apply the movement diagram as before and place the arrows accordingly. The arrows point in and never leave 40. The large city, large city strategy is the stable pure strategy solution. We define dominance as:

A strategy A dominates a strategy B if every outcome in A is at least as good as the corresponding outcome in B, and at least one outcome in A is strictly better than the corresponding outcome in B. Dominance Principle: A rational player should never play a dominated strategy in a total conflict game.

In this case the small city strategy payoffs for Rose are dominated by the large city strategy payoffs, thus we would never play small city. For Colin, the large city is better than the small city, so the large city dominates. Since large city, large city is the dominate strategy the solution is (40,-40).

If we use linear programming we only need a single formulation of the linear program. The row player maximizes and the column player minimizes with rows’ values. This constitutes a primal and dual relationship. The linear program used for Rose in the zero-sum games is:

Maximize V

Subject to:

a1,1x1+a1,2x2+...+a1,nxnV0a2,1x1+a2,2x2+...+a2,nxnV0...am,1x1+am,2x2+...+am,nxnV0x1+x2+...+xn=1V,xi0E3

where V is the value of the game, am,n are payoff-matrix entries, and x’s are the weights (probabilities to play the strategies). We place these payoffs into our formulation:

Max Vr

Subject to:

40x1+30x2Vr055x1+38x2Vr0x1+x2=1x1,x2,Vr0

The optimal solution strategies found are identical as before with both players choosing Large City as their best strategy. This indicates that neither player can unilaterally improve, a stable situation that we refer to as a Nash Equilibrium.

A Nash equilibrium is an outcome where neither player can benefit by departing unilaterally from its strategy associated with that outcome.

We conclude our discussion of total conflict games with the analysis that linear programming may always be used all total conflict games but is most suitable for large games between two players each having many strategies (Fox, 2010; Fox 2012).

Advertisement

5. Two–person partial conflict games

In the previous example, the conflict between the decision makers was total in the sense that neither player could improve without hurting the other player. If that is not the case, we classify the game as partial conflict as illustrated in the next example. Assume we have new market share analysis for our two stores as shown in Table 3 where the sums are not all equal to same constant.

Wal-Mart
Large City Small City
Large City 65, 25 50, 45
Target
Small City 55, 40 62, 28

Table 5.

Revised market shares

We begin with the movement diagram where the arrows do not find a stable point. In those cases, we need to find the equalizing strategies to find the Nash equilibrium. Other solution methods are found in the additional reading, we will describe only the use of linear programming as the method to use when the movement diagram fails to yield a stable point. Additionally, Gillman and Housman (2009) state that every partial conflict game also has equalizing strategy equilibrium even if it also has a pure strategy equilibrium.

Since both players are maximizing their payoffs we use the linear programming formulation presented as equation (1) and (2).

This yields two separate linear programs.

Maximize V

Subject to:

65 y1+ 50 y2V055 y1+ 62 y2V0y1+y2=1y1,y2, V0

The solution is y1=6/11, y2=5/11 and V=58.182

The other second LP formulation is

Maximize v

Subject to:

25 x1+ 40 x2v045 x1+ 28 x2v0x1+x2=1x1,x2, v0

The solution is x1=17/32, x2=15/32 and v=34.375.

The results state that the two stores must play their two strategies each a proportion of the time that they compete in order to obtain their best outcomes.

Another option available in partial conflict games is to consider allowing cooperation and communications between the game’s players. This allows for first moves, threats, promises, and combinations of threats and promises in order to obtain better outcomes. We call this strategic moves (Straffin, 2004).

Advertisement

6. Moving first or committing to move first

We now assume both players can communicate their plans or their moves to the second player. If Target can move first they can choose Large City or Small City. Examining the movement diagram, they should expect Wal-Mart’s responses as follows:

If Target plays Large City, Wal-Mart plays Small City resulting in the outcome (50,45).

If Target plays Small City, Wal-Mart plays Large City plays resulting in the outcome (55,40).

Target prefers 55 to 50 so they would play Small City. If Target forces Wal-Mart to move first then the choices are between (65,25) and (62,28) of which Wal-Mart prefers (62,28). Having Wal-Mart to move first gets Target a better outcome. How to get this to occur as well as the credibility of the first move is a concern.

Advertisement

7. Issuing a Threat

In general we describe the concept of issuing a threat. Rose may have a threat to deter Colin from playing a particular strategy. A threat must satisfy three conditions:

Conditions for a Threat by Rose

  1. Rose communicates that she will play a certain strategy contingent upon a previous action of Colin.

  2. Rose’s action is harmful to Rose.

  3. Rose’s action is harmful to Colin.

In our game example there is no valid threat.

We present the classic game of chicken to show a valid threat.

Colin
Swerve Not Swerve
Swerve (3, 3) (2,4)
Rose
Not Swerve (4, 2) (1, 1)

Table 6.

Chicken Game

In the game of Chicken, Rose wants Colin to play Swerve. Therefore she makes the threat on Colin’s Not Swerve to deter him from choosing that strategy. Examining the movement diagram,

Normally, if Colin plays Not Swerve, Rose plays Swerve yielding (2, 4)

In order to harm herself, Rose must play Not Swerve. Thus the potential threat must take the form:

If Colin plays Not Swerve, then Rose plays Not Swerve yielding (1, 1).

Is it a threat? It is contingent upon Colin choosing Not Swerve. Comparing (2, 4) and (1, 1), we see that the threat is harmful to Rose and is harmful to Colin. It is a threat and effectively eliminates the outcome (2, 4) making the game,

Table 7.

Chicken game with a threat.

Colin still has a choice of choosing Swerve or Not Swerve. Using the movement diagram, he analyzes his choices as follows:

If Colin selects Swerve, Rose chooses Not Swerve yielding (4, 2).

If Colin chooses Not Swerve, Rose chooses Not Swerve yielding (1, 1) (because of Rose’s threat).

Thus Colin’s choice is between a payoff of 2 and 1. He should choose Swerve yielding (4, 2). If Rose can make her threat credible, she can secure her best outcome.

Advertisement

8. Issuing a promise

In our Target versus Wal-Mart game there is no promise, so again we illustrate with the classic game of chicken. Again, if Colin has the opportunity to move first or is committed to (or possibly considering) Not Swerve, Rose may have a promise to encourage Colin to play Swerve instead. A promise must satisfy three conditions:

Conditions for a Promise by Rose

  1. Rose communicates that she will play a certain strategy contingent upon a previous action of Colin.

  2. Rose’s action is harmful to Rose.

  3. Rose’s action is beneficial to Colin.

In the game of Chicken, Rose wants Colin to play Swerve. Therefore she makes the promise on Colin Swerve to sweeten the pot so he will choose Swerve. Examining the movement diagram,

Normally, if Colin plays Swerve, Rose plays Not Swerve yielding (4, 2).

In order to harm herself, she must play Swerve. Thus the promise takes the form:

If Colin plays Swerve, then Rose plays Swerve yielding (3, 3).

Is it a promise? It is contingent upon Colin choosing Swerve. Comparing the normal (4, 2) with the promised (3, 3), we see that the promise is harmful to Rose and is beneficial to Colin. It is a promise and effectively eliminates the outcome (4, 2) making the game,

Colin
Swerve Not Swerve
Swerve (3, 3) (2, 4)
Rose
Not Swerve Eliminated by Promise (1, 1)

Table 8.

Chicken game with a promise.

Colin still has a choice of choosing Swerve or Not Swerve. Using the movement diagram, he analyzes his choices as follows:

If Colin selects Swerve, Rose chooses Swerve yielding (3, 3) as promised.

If Colin chooses Not Swerve, Rose chooses Swerve yielding (2, 4).

Thus Colin’s choice is between payoffs of 3 and 4. He should choose Not Swerve yielding (2, 4). Rose does have a promise. But her goal is for Colin to choose Swerve. Even with the promise eliminating an outcome, Colin chooses Not Swerve. The promise does not work. If both make a promise then perhaps (3, 3) is the outcome.

In summary, the game of Chicken offers many options. If the players choose conservatively without communication, the maximin strategies yields (3, 3), which is unstable: both players unilaterally can improve their outcomes. If either player moves first or commits to move first they can obtain their best outcome. For example, Rose can obtain (4, 2) which is a Nash equilibrium. If Rose issues a threat, she can eliminate (2, 4) and obtain (4, 2). A promise by Rose eliminates (4, 2) but results in (2, 4) which does not improve the (3, 3) likely outcome without communication.

Advertisement

8. 1. A combination threat and promise

Consider the following game:

Table 9.

Rose versus Colin payoffs.

The movement diagram shows that (2,4). is the Nash equilibrium. Without communication, Colin gets his best outcome, but can Rose do better that (2, 4) with a strategic move?

Rose First If Rose moves R1, Colin should respond with C1 yielding (2, 4). If Rose moves R2, Colin responds with C1 yielding (1, 2). Rose’s best choice is (2, 4), no better than the likely conservative outcome without communication.

Rose Threat Rose wants Colin to play C2. Normally, if Colin plays C1, Rose plays R1 yielding (2, 4). To hurt herself she must play R2 yielding (1, 2). Comparing the normal (2, 4) and (1, 2), the threat is contingent upon Colin playing C1, hurts Rose and hurts Colin. It is a threat and effectively eliminates (2, 4) yielding

Colin
C1 C2
R1 eliminated (3, 3)
Rose
R2 (1, 2) (4, 1)

Table 10.

Result of threat alone by Rose.

Does the threat deter Colin from playing C1? Examining the movement diagram, If Colin plays C1 the outcome is (1, 2). If Colin plays C2 the outcome is (4, 1). Colin’s best choice is still C1. Thus there is a threat, but it does not work. Does Rose have a promise that works by itself?

Rose Promise Rose wants Colin to play C2. Normally, if Colin plays C2, Rose plays R2 yielding (4, 1). To hurt herself she must play R1 yielding (3, 3). Comparing the normal (4, 1) with the promised (3, 3), the move is contingent upon Colin playing C2, hurts Rose and is beneficial to Colin. It is a promise and effectively eliminates (4, 1) yielding

Colin
C1 C2
R1 (2, 4) (3, 3)
Rose
R2 (1, 2) eliminated

Table 11.

Result from promise alone by Rose.

Does the promise motivate Colin to play C2? Examining the movement diagram, if Colin plays C1 the outcome is (2, 4). If Colin plays C2 the outcome is (3, 3). Colin’s best choice is still C1 for (2, 4). Thus there is a promise, but it does not work. What about combining both the threat and the promise?

Combination Threat and Promise We see that Rose does have a threat that eliminates an outcome but does not work by itself. She also has a promise that eliminates an outcome but does not work by itself. In such situations, we can examine issuing both the threat and the promise to eliminate two outcomes to determine if a better outcome results. Rose’s threat eliminates (2, 4), and Rose’s promise eliminates (4, 1). If she issues both the threat and the promise, the following outcomes are available.

Colin
C1 C2
R1 eliminated (3, 3)
Rose
R2 (1, 2) eliminated

Table 12.

Result of combination of threat and promise.

If Colin plays C1 the result is (1, 2), and choosing C2 yields (3, 3). He should choose C2, and (3, 3) represents an improvement for Rose over the likely outcome without communication (2, 4).

Credibility Of course, commitments to first moves, threats and promises must be made credible. If Rose issues a threat, and Colin chooses to Not Swerve anyway, will Rose will carry out her threat and crash (1, 1) even though that action no longer promises to get her the outcome (4, 2)? If Colin believes that she will not carry through on her threat, he will ignore the threat. In the game of Chicken, if Rose and Colin both promise to Swerve and Colin believes Rose’s promise and executes Swerve, will Rose carry out her promise to Swerve and accept (3, 3) even though (4, 2) is still available to her? One method for Rose to gain credibility is to lower one or more of her payoffs so that it is obvious to Colin that she will execute the stated move. Or, if possible, she may make a side payment to Colin to increase his selected payoffs in order to entice him to a strategy that is favorable to her and is now favorable to him because of the side payment. These ideas are pursued further in the exercises.

An inventory of the strategic moves available to each player is an important part of determining how a player should act. Each player wants to know what strategic moves are available to each of them. For example if Rose has a first move and Colin has a threat, Rose will want to execute her first move before Colin issues his threat. The analysis requires knowing the rank order of the possible outcomes for both players. Once a player has decided which strategy he wants the opposing player to execute, he can then determine how the player will react to any of his moves.

As alluded earlier maybe the better option is to go to arbitration. We discuss that next.

Advertisement

9. Nash arbitration

In the bargaining problem, Nash (1950) developed a scheme for producing a single fair outcome. The goals for the Nash arbitrations scheme are that the result will be at or above the status quo point for each player and that the result must be “fair”.

Nash introduced the following terminology:

Status Quo Point (We will typically use the intersection of Rose’s Security Level and Colin’s Security Level; the Threat positions may also be used).

Negotiation Set: Those points in the Pareto Optimal Set that are at or above the “Status Quo” of both players.

We use Nash’s four axioms that he believed that a reasonable arbitration scheme should satisfy rationality, linear invariance, symmetry, and invariance. A good discussion of these axioms and can be found in Straffin (2004, p.104-105). Simply put the Nash Arbitration point is the point that follows all four axioms. This leads to Nash’s Theorem stated below:

Nash’s Theorem: There is one and only one arbitration scheme which satisfies Axioms 1 through 4. It is this: if the status quo SQ=(x0,y0), then the arbitrated solution point N is the point (x,y) in the polygon with xx0 and yy0 which maximizes the product: (xx0)(yy0).

Let’s examine this geometrically first as it will provide insights into using calculus methods. We produce the contour plot of our nonlinear function: (xx0)(yy0) when our status quo point is assumed to be (0,0). It is obvious that the northeast (NE) corner of quadrant 1 is where this function is maximized. This is illustrated in figure 1 below.

Figure 1.

Contour plot for (x*y). We note that the direction of maximum increase is NE as indicated by the arrow.

We need a few more definitions to use this Nash Arbitration.

In his theory for the arbitration and cooperative solutions, Nash (1950) stated the “reasonable” solution should be Pareto optimal and will be at or above the security level. The set of outcomes that satisfy these two conditions is called the negotiation set. The line segments that join the negotiation set must form: a convex region as shown in Nash’s proof. Methodologies for solving for this point use basic calculus, algebra, and geometry.

For any game theory problem, we next overlay the convex polygon onto our contour plot. The most NE point in the feasible region is our optimal point and the Nash Arbitration point. This will be where the feasible region is tangent to the hyperbola. It will always be on the line segment that joins the negotiation set. This is simply a constrained optimization problem. We can convert to a single variable problem as we will illustrate later in our example.

In our example, we will use the security value as the status quo point to use in the Nash arbitration procedure. We additionally define the procedure to find the security value as follows:

In a non-zero-sum game, Rose’s optimal strategy in Rose’s game is called Rose’s Prudential Strategy, the value is called Rose’s Security level. Colin’s optimal strategy in Colin’s game is called Colin’s Security level. We will illustrate this during the solution to find the Nash arbitration point in the following example.

Colin
C D
Rose A (2,6) (10,5)
B (4,8) (0,0)

Table 13.

Finding the security levels in a non-zero sum game

To find the security level (status quo point) we look at the following two separate games extracted from the original game and use movement diagrams, dominance, or our linear programming method to solve each game for those players’ values.

In a prudential strategy, we allow a player to find their optimal strategy in their own game. For Rose, she would need to find her optimal solution in her own game. Rose’s game below has a mixed strategy solution; V=10/3.

Colin
C D
Rose A 2 10
B 4 0

Table 14.

Rose’s game for finding her Prudential strategy.

For Colin, he would need to find his optimal solution in his own game. Colin’s game below has a pure strategy solution, V=6.

Colin
C D
Rose A 6 5
B 8 0

Table 15.

Colin’s game for finding his Prudential strategy.

The status quo point or security level from the Prudential strategy is found to be (10/3, 6). We will use this point in the formulation of the Nash arbitration.

10. Finding the Nash arbitration point

We use the nonlinear programming method described by Fox (2010,2012). We set up the convex polygon (constraints) for the function that we want to maximize, which is (x103)(y6). The convex polygon is the convex set from the values in the pay-off matrix. Its boundary and interior points represent all possible combinations of strategies. Corner points represent pure strategies. All other points are mixed strategies. Occasionally, a pure strategy is an interior point. Thus, we start by plotting the strategies from our payoff matrix set of values { (2,6), (4,8), (10,5), (0,0)}, see figure 2.

Figure 2.

Payoff Polygon,

We note that our convex region has four sides whose coordinates are our pure strategies. We use the point-slope formula to find the equations of the line and then test points to transform the equations to inequalities. For example, the line form (4,8) to (10,5) is y =

-.5 x + 10. We rewrite as y +.5x =10. Our test point (0, 0) shows that our inequality is

0.5x + y ≤10. We use this technique to find all boundary lines as well as add our security levels as lines that we need to be above.

The convex polygon is bounded by the following in equalities:

.5x+y103x+y00.5xy0x+y4xx*yy*

where x* and y* are the security levels (10/3,6).

The NLP formulation (Winston, 2003; Fox, 2012) to find the Nash arbitration value following the format of equation is as follows:

Maximize

(x103)(y6)E4

Subject to:

0.5x+y103x+y00.5xy0x+y4x103y6

We display the feasible region graphically in Figure 3 The feasible region is the solid region. From the figure we can approximate the solution as the point of tangency between the feasible region and the hyperbolic contours in the NE region.

Figure 3.

Convex polygon and function contour plot.

Since we visually see that the solution must fall along the line segment y=-0.5 x+ 10. We may use simple calculus.

Maximize (x103)(y6)

Subject to: y=.5x+10

We substitute to obtain a function of one variable,

Maximize (x10/3)((.5x+106) or

Maximize 5x2+ 34/6 x  40/3

We find dfdx=0=-x+34/6.

We find x=17/3

The second derivative test confirms we found a maximum.

We substitute x= 17/3 back into y=-.5x+10 to obtain y= 43/6. This point (17/3, 43/6) is the Nash Arbitration point. Our optimal solution, the Nash arbitration point is found to be x =5.667 and y = 7.167 and the value of the objective function payoff of 2.72.

How do we obtain this value in a particle manner? An arbitrator plays the strategies BC (4,8) and AD (10,5) as follows described below.

We can solve two equations and two unknowns from our strategies BC and AD equal to our Nash arbitration point.

41085xy=5.6677.167

We solve and find x = 0.27777 or (5/18) y = 0.72222 or 13/18.

Example 2: Management-Labor Arbitration (Straffin, 2004 p 115-117)

Labor
Concedes
Nothing C A CA
Nothing (0,0) (4,-1) (4,-2) (8,-3)
Management
Concedes
P (-2,2) (2,1) (2,0) (6,-1)
R (-3,3) (1,2) (1,1) (5,0)
PR (-5,5) (-1,4) (-1,3) (3,2)

Table 16.

Management-versus Labour problem

The convex polygon is graphed from the constraints below (see the plots in figures 4):

x+y00.5x+y00.25x+y1x+y50.5x+y3.50.25x+y154

The status quo point (our security level) is (0,0), making the function to maximize simply x* y.

Our formulation is:

Maximize x*y

Subject to::

x+y00.5x+y00.25x+y1x+y50.5x+y3.50.25x+y154

The product is xy=6 and the values are x=3 and y=2.

Figure 4.

The graphical NLP problem for the Management-Labor Arbitration.

This optimal point is the point (3,2) on the line that is tangent to the contours in the direction of the NE increase.

10. N–person games

We restrict our discussion to the three person games. We suggest placing the payoffs into payoff matrices as shown in Table 17. We will continue to use Rose and Colin but introduce Larry as our third player. We show with only two strategies each but the concept can be expanded.

Larry, L1 Larry, L2
Colin Colin
C1 C2 C1 C2
Rose R1 (r1,c1,l1) (r1,c2,l1) R1 (r1,c1,l2) (r1,c2,l2)
R2 (r2,c1,l1) (r1,c2,l1) R2 (r2,c1,l2) (r2,c2,l2)

Table 17.

Three-person game.

Again if ri+ci+li = 0 or the same constant for all i we have a total sum game otherwise we have a partial sum game.

Movement diagram may again be used to examine the game for pure strategy solution. Arrow point from the small values to the larger values. The new arrows belong to Larry. Between Larry 1 and Larry 2 we draw arrows from smaller to larger by an arrow out from one matrix and an arrow in to the other. We will illustrate with an example. Regardless if there is a pure solution or solutions or not, we will still consider coalitions. A coalition will be one two players joins together to gain an advantage of a third player. We consider all such coalition in our analysis.

Example Three Person Total Conflict

Consider the following three person total conflict game between Rose, Colin, and Larry. We provide the payoffs and the movement diagram with all arrows.

Table 18.

Movement diagram for our three person game example.

Our movement arrows indicate two stable pure strategies, R2C1L1 (3,-4,1) and R1C1L2 (-1,0,1). These results are very different and not all players are satisfied at one or the other points. We now consider coalitions. We completely illustrate one coalition and provide the results for the others.

Let’s assume that Larry and Colin form a coalition against Rose. Our new payoff matrix would look as follows:

Colin & Larry
Rose C1L1 C2L1 C1L2 C2L2
R1 2,-2 -1,1 -1,1 -2,2
R2 3,-3 2,-2 -2,2 2,-2

Table 19.

Colin and Larry coalition payoffs.

As a zero-sum game we may just list Rose’s values.

Colin & Larry
Rose C1L1 C2L1 C1L2 C2L2
R1 2 -1 -1 -2
R2 3 2 -2 2

Table 20.

Colin and Larry coalition payoffs as a zero-sum game.

We can use linear programming to obtain our solution for Rose. Since payoffs are negative so that we solution can negative we employ the transformation of Vr to

Vr1Vr2.

Maximize Vr1-Vr2

Subject to:

2y1y2y32y4 Vr1Vr2r03y1+2y22y3+2y4 Vr1Vr20y1+y2+y3+y4=1yi,Vr1Vr20

We find the optimal solution is Vr1=0, V=1.2 so Vr=-1.2 when y1=0, y2 =0, y3=4/5 and y4=1/5. Thus, the coalition of Colin-Larry gains 1.2 units where we find Larry get 21/25 of the share and Colin gets 9/25 of the share.

For the other coalitions, we may use the same procedures. Also, we may use the same procedures if we have a three person partial conflict game. However, for those coalitions we must use the (M,N) formulations since M+N does not equal zero.

References

  1. 1. Aumann, R. J. (1987). Game theory. The New Palgrave: A Dictionary of Economics, London, UK.: Palgrave Macmillan.
  2. 2. Bazarra, M. S., H. D. Sherali, and C. M . Shetty. (2006). Nonlinear Programming. 3rd Ed. New York, NY: John Wiley.
  3. 3. Braun, S. J. (1994). Theory of moves, American Scientist, 81, 562-570.
  4. 4. Camerer, C. (2003). Behavioral game theory: experiments in strategic interaction, Russell Sage Foundation, Description and Introduction, 1– 25.
  5. 5. Chiappori, A., Levitt, S.& Groseclose, P . (2002).Testing mixed-strategy equilibria when players are heterogeneous: the case of penalty kicks in soccer., American Economic Review, 92(4), 1138-1151.
  6. 6. Crawford, V. (1974). Learning the optimal strategy in a zero-sum game. Econometrica 42(5), 885–891.
  7. 7. Danzig, G. (1951). Maximization of a linear unction of variables Subject to: linear inequalities. In T.Koopman (Ed), Activity Analysis of Production and Allocation Conference Proceeding (pp. 339–347). New York, NY. John Wiley.
  8. 8. Danzig, G. (2002). Linear programming, Operations Research, 50(1), 42–47.
  9. 9. Dixit, A. & Nalebuff, B. (1991). Thinking strategically: The competitive edge in business, politics, and everyday life. New York, NY: W.W. Norton.
  10. 10. Dorfman, Robert. (1951). Application of the simplex simplex method method to a game game theory theory problemproblem. In T. Koopman (Ed), Activity Analysis of Production and Allocation Conference Proceeding. (pp. 348–358). New York, NY. John Wiley Publishers. pp.339-347.
  11. 11. Dutta, P. (1999). Strategies and games: theory and practice, Cambridge, MA.: MIT Press.
  12. 12. Fox, W. P. (2008). Mathematical modeling of conflict and decision making: The writer’s guild strike 2007–2008, Computers in Education Journal, 18(3), 2–11.
  13. 13. Fox, W. P. (2012). Mathematical modeling with Maple. Boston, MA.: Cengage Publishers.
  14. 14. Fox, W.P. (2010). Teaching the applications of optimization in game theory’s zero-sum and non-zero sum games, International Journal of Data Analysis Techniques and Strategies, 2(3), 258-284.
  15. 15. Gale, D., H. Kuhn, and A. Tucker. (1951). Linear programming and the theory of games. In T. Koopman (Ed), Activity analysis of production and allocation conference proceeding (pp. 317–329), New York, NY: John Wiley.
  16. 16. Gillman, R., & Housman, D. (2009). Models of conflict and cooperation. Providence, RI.: American Mathematical Society.
  17. 17. Gintis, H. (2000). Game theory evolving: a problem-centered introduction to modeling strategic behavior. Princeton, N.J.: University Press.
  18. 18. Giordano, F., Fox, W., & Horton, S. (2013) A First Course in Mathematical Modeling, 5th Ed. Boston, MA.: Brooks-Cole.
  19. 19. Harrington, J. (2008). Games, strategies, and decision making. New York, NY: Worth Publsihers.
  20. 20. Isaacs, R. (1999). Differential games: A mathematical theory with applications to warfare and pursuit, control and optimization. New York, NY. Dover Publications.
  21. 21. Klarrich, E. (2009). The mathematics of strategy. Classics of the Scientific Literature. October 2009 from www.pnas.org/site/misc/classics5.shtml.
  22. 22. Koopman (Ed), Activity Analysis of Production and Allocation Conference Proceeding (pp. 348–358). New York, NY. John Wiley.
  23. 23. Kuhn, H. W., and A.W. Tucker. (1951). Nonlinear programming. Proceedings of the Second Berkley Symposium on Mathematical Statistics and Probability, J. Newman (Ed.). Berkeley, CA.: University of California Press.
  24. 24. Leyton-Brown, K.& Shoham, Y (2008), Essentials of game theory: A concise, multidisciplinary introduction, San Rafael, CA.: Morgan & Claypool Publishers.
  25. 25. Miller, J. (2003). Game theory at work: how to use game theory to outthink and outmaneuver your competition, New York, NY.: McGraw-Hill.
  26. 26. Myerson, Roger B. (1991). Game theory: analysis of conflict. Cambridge, MA.: Harvard University Press.
  27. 27. Nash, J. (1950). The bargaining problem, Econometrica, 18, 155–162.
  28. 28. Nash, J. (1951). Non-cooperative games, Annals of Mathematics, 54, 289–295.
  29. 29. Nash, J. (2009). Lecture at NPS. Feb 19, 2009.
  30. 30. Nash, John (1950), Equilibrium points in n-person games", Proceedings of the National Academy of Sciences of the United States of America. 36 (1): 48–49.
  31. 31. Osborne, M. (2004). An introduction to game theory. Oxford, UK: Oxford University Press,.
  32. 32. Papayoanou, P. (2010., Game theory for business, e-book, Probabilistic Publishing, http://www.decisions-books.com/Links.html.
  33. 33. Rasmusen, Eric (2006). Games and information: An introduction to game theory. (4th ed.), New York, NY: Wiley-Blackwell .
  34. 34. Shoham, Y. &; Leyton-Brown, K. (2009). Multiagent systems: Algorithmic, game- theoretic, and logical foundations. New York, NY: Cambridge University Press.
  35. 35. Smith, J.M. & Price, G. (1973). The logic of animal conflict, Nature 246, 5427, 15–18.
  36. 36. Smith, M. (1982). Evolution and the theory of games. Cambridge, UK: Cambridge University Press.
  37. 37. Straffin, P. (1980). The prisoner’s dilemma. UMAP Journal. 1, 101-113.
  38. 38. Straffin, P. (1989). Game theory and nuclear deterrence, UMAP Journal. 10, 87-92.
  39. 39. Straffin, P. D. (2004). Game theory and strategy. Washington, DC: Mathematical Association of America.
  40. 40. Von Neumann, J., & Morgenstern, O. (2004). Theory of games and economic behavior (60th anniversary ed.). Princeton, NJ.: Princeton University Press.
  41. 41. Webb, James N. (2007). Game theory: decisions, interaction and evolution. London, UK: Springer .
  42. 42. Williams, J. D. (1986). The Compleat Strategyst. New York, NY: Dover Press.
  43. 43. Winston, W. L. (2003). Introduction to Mathematical Programming. 4th Ed. Belmont, CA: Duxbury Press.

Written By

William P. Fox

Submitted: 29 June 2012 Published: 06 March 2013