Discussion Paper No. 24

On Markov perfect equilibria in baseballAkifumi Kira
Keisuke Inakawa

March, 2014

Data Science and Service Research
Discussion Paper

Center for Data Science and Service Research
Graduate School of Economic and Management
Tohoku University27-1 Kawauchi, Aobaku
Sendai 980-8576, JAPANOn Markov perfect equilibria in baseballAkifumi KIRA
Graduate School of Economics and Management
Tohoku University

Keisuke INAKAWA
Faculty of Systems Science and Technology
Akita Prefectural University

Abstract
We formulate baseball as a ﬁnite Markov game with approximately 3.5 million states.
The manager of each opposing team is the player who maximizes the probability of theirteam winning. We derive, using dynamic programming, a recursive formula which is satisﬁedby Markov perfect equilibria and the value functions of the game for both teams. By solving
this recursive formula, we can obtain optimal strategies for each condition. We demonstratewith numerical experiments that these can be calculated in approximately 1 second per game.

Keywords Markov game, dynamic programming, optimal strategies in baseball.

1

Introduction

Similar to the various problems within corporations, even in sports, there are several successful
cases that have employed scientiﬁc methods. For example, using a technique known as Sabermetrics, Billy Beane, the general manager of Oakland Athletics in the Major League, built up
a powerful team on a low budget. And in Japanese professional baseball, making full use of
the information system BOS (Baseball Operation System) contributed to the successes of the
Hokkaido Nippon-Ham Fighters, who won the league four times, and became the top team inJapan once in the seven years after 2006.
On the other hand, a method exists for analyzing baseball that uses Markov chains, and has
been extensively studied by several authors (Bellman [1], Bukiet et al. [2], Cover and Keilers [3],Howard [5], Turocy [8], and others). The ﬁrst scholar to have applied Markov chains to Baseball,seems to be Howard [5]. He said that the discrete nature of events in baseball constituted anatural Markov model. He suggests the optimization of strategies (especially sacriﬁce bunts
and stolen bases), which maximizes the expected runs scored in one inning by using dynamic
programming. In other words, this is a Markov decision process (MDP) approach. Bellman [1]proposes a more detailed formulation. His model analyzes not only a batter-by-batter level, butalso a pitch-by-pitch level. He provided a subtle insight into strategies through a discussion basedon the two criteria of maximizing the expected number of runs scored, as well as the thresholdprobability of scoring at least k runs in one inning. However, due to the shortage of computing
capacity at the time, these approaches using dynamic programming were not implemented.
At the same time as the work of Bellman, in 1977, D’Esopo and Lefkowitz [4] propose ascoring index (SI) as an evaluation index for the expected number of runs scored in one inningassuming that the same player steps up to the plate repeatedly. Under the same assumption,
1

Cover and Keilers [3] in 1977 propose a similar index, the OERA (Oﬀensive Earned-Run Average)
value, as an index to evaluate the expected number of runs scored in a single game. In the
OERA model, the baseball rules are simpliﬁed to apply the absorbing Markov chain model inthe calculation of the expected runs scored. Bukiet et al. [2] in 1997 take into considerationof the batting order. They give an algorithm to calculate the expected runs scored in a gameassuming the nine players constituting the team step up to the plate in a given order. Further,a method for approximately computing the winning percentage is also proposed. These studies
can be classiﬁed as Markov chain approaches with matrix analysis.
In 2008, Turocy [8] produces a model to also couple the strategies of the opposing team with
the Bellman’s approach by using a Markov game, which is a multi-agent extension of MDPs (e.g.
see Shapley [7] and Zachrisson [9]). Here, the manager of each opposing team maximizes theprobability of their team winning. Since the model adopts the MLB rule to play extra innings
until a winner is determined, the states for an extra inning can be identiﬁed as being the same as
for the ninth inning. In addition, by establishing an upper limit of 30 runs for the run diﬀerence(mercy-rule), his stochastic game has a ﬁnite number of states, and a ﬁnite number of actions,and so a Markov perfect equilibrium (MPE) exists. The total number of states in this case isapproximately 2.13 million. Turocy performed numerical experiments using backward induction(dynamic programming) from the start of the game up to the completion of the eighth inning,
and using a ﬁxed-point approximation by a value-function iteration for the ninth inning. The
details of such as the recursive formula and the algorithm are omitted in the paper, but hestates that the values of the game (the equilibrium winning percentages for both teams) could
be solved with high accuracy in less than a minute.
In this paper, similar to Turocy, we consider a game-theoretic approach for baseball. Baseballis formulated as a ﬁnite Markov game with approximately 3.5 million states. Here, whereas
Turocy counts the combination of all the states including those that are unreachable, in ourmodel, only the states which are reachable are counted. We also suppose that the manager of
each team maximizes the probability of their team winning. The principal diﬀerences comparedto Turocy’s model are the two points that, (a) in order to consider the success rate with stolenbases in more detail, the identity of the runner on ﬁrst base is stored in the state, and (b) therule from Japanese baseball that extra innings are restricted to a maximum of three is included,
so the game may end in a draw. Because of the mercy-rule and the ﬁniteness of the numberof extra innings, the length of the game also becomes ﬁnite. Hence, at least one pure-strategy
MPE does exist in our model, and they can be found using backward induction. We derive arecursive formula that is satisﬁed by the MPEs and the value functions of the game, and carryout numerical experiments to solve it.
In Section 2, we provide a ﬁnite Markov game as a formulation for baseball. States, actions,state transitions with simplifying rules, and payoﬀ functions are all deﬁned in detail. Here, we
make use of the MDP methodology, which reduces a probability criterion down to an expectation
criterion (e.g. Kira et al. [6]). In Section 3, we deﬁne MPEs and the value functions of thegame, and derive the recursive formula that is satisﬁed by them. By solving this, the optimal
strategies for each state are obtained, such as a sacriﬁce bunt or a stolen base. Section 4 performs
computational experiments. We calculate the recursive formula for just reachable states fromthe initial state by implementing the depth-ﬁrst search of the game tree. In this way, the valuefunctions of the game for both teams and a pure-strategy MPE can be found in about 1 second.
The results obtained from numerical examples in this study are described. Concluding remarks
and future direction are discussed in Section 5.

2

Formulation as a Markov gameIn this section, baseball is formulated as a Markov game.
2

2.1

StatesLet S be the state space. A state s = (ι, τ, ω, λ, r, b) ∈ S is made up of 6 components. Eachcomponent is deﬁned as follows:
1. ι ∈ {1, 2, . . . , 12} represents the current inning. ι = 9 is the ﬁnal inning, and for a tie,
extra innings are played up to a maximum of ι = 12.
2. τ ∈ {0, 1} represents oﬀense in the top half of the inning (τ = 0) or oﬀense in the bottom
half of the inning (τ = 1).
3. ω ∈ {0, 1, 2, 3} represents the current number of outs.
4. λ is the current run diﬀerence and represents the value found by subtracting the runs of
the home team (last-batting team) from the runs of the away team (ﬁrst-batting team).
5. r = (r3 , r2 , r1 ) represents the state of the runners.
• r3 ∈ {0, 1} takes a value 0 if there is no runner on third base, and a value 1 if a runneris present.
• r2 ∈ {0, 1} takes a value 0 if there is no runner on second base, and a value 1 if arunner is present.
• r1 ∈ {0, 1, . . . , 9} takes a value 0 if there is no runner on ﬁrst base, and the samevalue as the batting order of the runner if a runner is present.
Only r1 distinguishing between runners is in order to take into account the success rate,
which is dependent on the runner when performing a stolen base from ﬁrst to second base.
In this paper, neither a stolen base from second to third base, nor a stolen base from third
to home base, are considered.
6. b = (b1 , b2 ) indicates to which batter the batting order rotates.
• b0 ∈ {1, 2, . . . , 9} indicates to which batter the batting order of the ﬁrst-batting teamrotates. It represents, when in oﬀense (τ = 0), that the b0 -th batter steps up to theplate. When in defense (τ = 1), it means that the leadoﬀ hitter in the next inning is
the b0 -th batter.
• b1 ∈ {1, 2, . . . , 9} similarly indicates to which batter the batting order of the lastbatting team rotates.
The initial state s0 at the start time of the game is as follows:s0 = (ι, τ, ω, λ, r, b)0 = (1, 0, 0, 0, (0, 0, 0), (1, 1)).
SQ denotes the total states (absorbing states) at the end of the game:
0
1
2
3
SQ := SQ
∪ SQ
∪ SQ
∪ SQ
,

where

0 = {s ∈ S | ι ≥ 9, τ = 1, ω = 3, λ > 0},SQ
1 = {s ∈ S | ι = 9, τ = 0, ω = 3, λ < 0} ∪ {s ∈ S | ι ≥ 9, τ = 1, λ < 0},
SQ
2 = {s ∈ S | ι = 12, τ = 1, ω = 3, λ = 0},
SQ
3 = {s ∈ S | λ ≤ −30} ∪ {s ∈ S | λ ≥ 30}. (mercy-rule)
SQ

0 and S 1 correspond to a victory for the ﬁrst-batting team and a victory for the last-batting
SQ
Q
2 corresponds to a tie in the 12th inning after playing extra innings. We
team, respectively. SQ

3note that the mercy-rule refers to the establishment of a called game during the inning. By
adopting both the Japanese professional baseball rules (i.e., the number of extra innings is
ﬁnite) and the above mercy-rule, we get a ﬁnite Markov game. In addition, we equate the states, such that ω = 3 and s ∈/ SQ , with the corresponding state after the inning is over.

2.2

Actions

The manager of each team is the player maximizing the probability of their team winning. For
each state s ∈ S, if τ = 0 (the top half of the inning) then the ﬁrst-batting team can choose
their actions. Conversely, if τ = 1 (the bottom half of the inning) then the last-batting team canchoose. Here, we let S0 and S1 be the sets of states of moves for, respectively, the ﬁrst-batting
team and the last-batting team. Namely,
S0 = {s ∈ S | τ = 0, s ∈/ SQ },
S1 = {s ∈ S | τ = 1, s ∈/ SQ }.
In this paper, the action space is deﬁned as
A = {batting, stolen base, sacriﬁce bunt}.
Let us consider a point-to-set valued mapping A : S → 2A \ {ϕ}. A(s), called the feasible action
space, represents the set of all actions in state s. In this paper, we deﬁne them in the following
manner:batting ∈ A(s), ∀s ∈ S,
stolen base ∈ A(s) ⇐⇒ r2 = 0, r1 ≥ 1,
sacriﬁce bunt ∈ A(s) ⇐⇒ ω = 0 or 1, r3 + r2 + r1 ≥ 1.
Hence, stolen bases are feasible if and only if there is no second base runner and there is a runnerpresent on ﬁrst base, and sacriﬁce hits are feasible if and only if a runner is present with 0 or 1
outs.
Deﬁnition 2.1 (Markov policy). A mapping π0 : S0 → A is called a (deterministic) Markov
policy for the ﬁrst-batting team if π0 (s) ∈ A(s) for all s ∈ S0 . Similarly, a mapping π1 : S1 → A
is called a Markov policy for the last-batting team if π1 (s) ∈ A(s) for all s ∈ S1 .
We denote the set of all deterministic Markov policies for the ﬁrst-batting team and thelast-batting team by Π0 and Π1 , respectively.

2.3State transitions

For any a ∈ A, let us deﬁne X (a), the set of all results that can occur stochastically when theaction a is chosen, as follows:{{out, single, double, triple, home run, walk} if a = batting
X (a) =
{success, fail}otherwise.
We denote the graph of A(·) by Gr (A). Namely,
Gr (A) = {(s, a) | a ∈ A(s), s ∈ S}.
For any (s, a) ∈ Gr (A) and any x ∈ X (a), p(x| s, a) represents the conditional probability withwhich the result x occurs, given that action a is chosen in state s.
p(· | s, a) : X (a) → [0, 1], ∀(s, a) ∈ Gr (A),∑p(x | s, a) = 1, ∀(s, a) ∈ Gr (A).
x∈X (a)4

Now, with the deﬁnition of the state, the state s = (ι, τ, ω, λ, r, b) includes information about
the inning number, whether it is the top or bottom half, the out count, the run diﬀerence, thebatting order of the batters, whether there are runners present or not, and also, the battingorder of the runner if one is present on ﬁrst base. Therefore, the transition probability generally
depends on all of these states. However, in the numerical experiments carried out in Section
4, we assume that the transition probability depends only on the players that make a hit, or
perform sacriﬁce hits or stolen bases, and does not depend on those other components which
comprise the state.
This paper simpliﬁes baseball in a similar manner to previous research. The simplifying rules
used in this paper are as below.
“Simplifying rules”
1. With a mishit (an out), neither a batter nor a runner can advance bases.
2. A single advances a runner on ﬁrst base to third base, and runners on second and thirdbase reach the home plate.
3. A double and a triple allows all runners to reach the home plate.
4. It is assumed that there are no double plays.
5. For a successful stolen base, the runner on ﬁrst base advances to second base.
6. For an unsuccessful stolen base, the runner on ﬁrst base is out.
7. For a successful sacriﬁce hit, the runners advance one base forward, and the batter performing the sacriﬁce hit is out.
8. For an unsuccessful sacriﬁce hit, the runner closest to the home plate is out, the otherrunners advance one base forward, and the batter is then the runner on ﬁrst base.
If these simplifying rules are followed, then the next state s′ is determined uniquely when instate s, action a is chosen, and result x occurs. We denote this next state bys′ = t(s, a, x).

2.4

Payoﬀ function

Since, for any Borel set B and any random variable X, we know the relation{
1 if X is in B,
Pr( X is in B ) = E[ 1B (X) ], 1B (X) =0 otherwise .
The approach, using this relation to reduce a probability criterion to an expectation criterion,
is often used in the ﬁeld of Markov decision processes (see Kira et al. [6]). Thus, we deﬁne
the terminal payoﬀ functions r0 , r1 : SQ → {0, 1} for the last-batting team and the ﬁrst-batting
team as follows:{{
1 λ > 0,0 λ ≥ 0,r0 (s) =r1 (s) =0 λ ≤ 0,1 λ < 0.
If the game is won, a payoﬀ of 1 is acquired, whereas a loss or a tie is a payoﬀ of 0. Supposethat Markov policies π0 ∈ Π0 and π1 ∈ Π1 are employed by the ﬁrst-batting team and the lastbatting team, respectively. In this case, the Markov game commencing from each state s can

5be regarded as a Markov chain. In other words, if we let Xn be the state after n step transition
from the initial state s0 , then {Xn } is the Markov chain satisfying p(x | s, πi (s)) if s ∈ Si , s′ = t(s, πi (s), x),1
if s ∈ SQ , s′ = s,Prπ0 ,π1 (Xn+1 = s′ | Xn = s) =0otherwise.
Let T be the arrival time of {Xn } to SQ . Namely,
T := min{n | Xn ∈ SQ } < ∞.
We can deﬁne the probabilities of the ﬁrst-batting team winning and the last-batting teamwinning, denoted by v0 (s; π0 , π1 ) and v1 (s; π0 , π1 ) respectively, as follows:
v0 (s; π0 , π1 ) = Eπ0 ,π1 [r0 (XT ) | X0 = s] ,v1 (s; π0 , π1 ) = Eπ0 ,π1 [r1 (XT ) | X0 = s] .

3Markov perfect equilibria and dynamic programming

In this section, we deﬁne a Markov perfect equilibrium and the value functions of the game, andderive the recursive formula for eﬀectively computing them.
A Markov perfect equilibrium is a proﬁle of Markov policies that yields a Nash equilibriumin every proper subgame.
Deﬁnition 3.1 (Markov perfect equilibrium, MPE). A proﬁle of (deterministic) Markov policies(π0∗ , π1∗ ) for the ﬁrst-batting team and the last-batting team is called a (pure-strategy) MPE if it
is a subgame perfect equilibrium. Namely, it satisﬁes
v0 (s; π0 , π1∗ ) ≤ v0 (s; π0∗ , π1∗ ),∀s ∈ S,∀π0 ∈ Π0 ,v1 (s; π0∗ , π1 ) ≤ v1 (s; π0∗ , π1∗ ),∀s ∈ S,∀π1 ∈ Π1 .

Remark 3.1 (existence of the equilibria). In the most general context, the action chosen by apolicy in each state may be randomized. However, it is well-known that at least one pure-strategy
MPE exists for a ﬁnite Markov game with perfect information. We thus restrict our attention
to the class of pure-strategy MPEs.
Deﬁnition 3.2 (the value functions of the game). Let (π0∗ , π1∗ ) be a Markov perfect equilibrium,and for any state s ∈ S, let V0 (s) and V1 (s) be the probabilities of the ﬁrst-batting team winningand the last-batting team winning when in state s, respectively. That is,
V0 (s) = v0 (s; π0∗ , π1∗ ),s ∈ S,V1 (s) = v1 (s; π0∗ , π1∗ ),s ∈ S.

Then the functions V0 and V1 are called the value functions of the game for the ﬁrst-batting teamand the last-batting team, respectively.
Remark 3.2 (uniqueness of the value functions). It is also well-known that the value functionof the game for each team is unique. In other words, all equilibria must result in the sameprobability of the team winning.

6

Theorem 3.1 (Bellman equation). The value functions satisfy the following recursive formula.
r0 (s)s ∈ SQ ,



∑


 Max
V0 (t(s, a, x))p(x|s, a)s ∈ S0 ,a∈A(s)V0 (s) =x∈X (a)∑
V0 (t(s, π1∗ (s), x))p(x|s, π1∗ (s)) s ∈ S1 .
∗x∈X (π1 (s))


r1 (s)



∑



V1 (s) =s ∈ SQ ,V1 (t(s, π0∗ (s), x))p(x|s, π0∗ (s)) s ∈ S0 ,∗x∈X (π0 (s))

∑



Max
V1 (t(s, a, x))p(x|s, a) a∈A(s)s ∈ S1 .

x∈X (a)π0∗ (s) ∈ arg max∑

V0 (t(s, a, x))p(x|s, a),s ∈ S0 .

(1)V1 (t(s, a, x))p(x|s, a),s ∈ S1 .

(2)a∈A(s) x∈X (a)π1∗ (s) ∈ arg max∑a∈A(s) x∈X (a)Theorem 3.2. The proﬁle (π0∗ , π1∗ ) of a Markov policy for the ﬁrst-batting team satisfying (1),and a Markov policy for the last-batting team satisfying (2) is an MPE.

4

Computational results

Table 1 shows the probability parameters for the starting order of the Fukuoka Softbank Hawks,
and was compiled based on the values achieved in Japan’s professional baseball 2013 season [10].
Some of the stolen base success rates and sacriﬁce hit success rates for players with extremely
small numbers of attempted stolen bases and sacriﬁce hits have been adjusted. Speciﬁcally, forthe success rate of stolen bases for players with less than 4 attempted stolen bases over the year,
the minimum of 0.7 and the actual value was adopted. Similarly, the minimum of 0.8 and theactual value was adopted for the sacriﬁce hit success rate for players with less than 4 attemptedsacriﬁce hits over the year. The numbers in the Lineup column indicate the batting order forthe players. Lineup A is the actual batting order which had been established by the closing
stage of the 2013 season. Lineup B is a batting order created by shuﬄing them at random.
Table 1: Probability parameters

A computational experiment was performed to ﬁnd a MPE and the values of the games
between lineup A and lineup B. The experimental results are as shown in Table 2.
7

Table 2: Values of the games
Bad ﬁrst v.s. ﬁeld fast
Pr(A wins)
Pr(B wins)
1 0.5008
2 0.4893
Lineup A v.s. B⃝⃝
3 0.5046
4 0.4856
Lineup B v.s. A⃝⃝
3 −⃝1 0.0038 ⃝2 −⃝4 0.0037
Advantage of ﬁeld fast ⃝Pr(tie game)
0.00990.0098—• CPU Time: 1.26 sec / game
R CoreTM i7-3770K 16GB memory installed• Environment: a desktop PC with Intel⃝

And the winning percentages, under the conditions where there is a tie in the 8th inning andthe both teams in the 9th inning start with batter number 1, are given in Table 3.
Table 3: Values of the games starting in the 9th inning
Bad ﬁrst v.s. ﬁeld fast
Pr(A wins)
Pr(B wins) Pr(tie game)1
2 0.4373
Lineup A v.s. B⃝ 0.5079⃝
0.0548
3 0.5172
4 0.4284
Lineup B v.s. A⃝⃝
0.05443 −⃝1 0.0093 ⃝2 −⃝4 0.0089
Advantage of ﬁeld fast ⃝—In computational experiments, while performing a depth-ﬁrst search of the “game tree” as anextensive form game of baseball, the recursive formula of Theorem 3.1 was solved for just thosestates that were reachable from the initial state s0 . Changing the run diﬀerence established in acalled game from 30 runs to 60 runs and once again performing the computational experiments,
the diﬀerence in the values of the game V0 (s0 ) and V1 (s0 ) were less than 10−10 . It follows that
we can reasonably consider the error from using the mercy-rule as practically zero.
We note that when the manager of each team makes decisions about hits, stolen bases, andsacriﬁce hits, the runs scored by the opposing team (the run diﬀerence) must be considered towin. For both lineup A and lineup B, if we subtract the winning percentage for each team whenbatting ﬁrst from the winning percentage when batting last, then we get a positive value. This
coincides with the result by Turocy [8]. Further, this diﬀerence appears to be more signiﬁcantfrom the 9th inning onwards. This is because the last-batting team always has one more inning’s
worth of information to study about the opposing team’s runs.

5

Summary and Future Challenges

In this paper, baseball has been formulated as a ﬁnite Markov game with approximately 3.5
million states. We demonstrated that the Markov perfect equilibria and the values of the games,
where both teams’ managers maximize the probabilities of their respective team winning, canbe computed in about one second per game.
In the future, we think that a raised level of analysis will be the object of the research, andnot just the optimization of such strategies as sacriﬁce hits and stolen bases. For example, theauthors are conﬁdent that the model given in this paper can be utilized to predict how theteam’s winning percentage would change with the introduction and release of players, and in
the sensitivity analysis of a player’s performance and the team’s winning percentage. At thesame time as applying these using more detailed actual data, we would also like to investigate
it’s use in other topics as challenges for the future.

8References[1] Bellman, R., Dynamic Programming and Markovian Decision Processes, with Application
to Baseball in Optimal Strategies in Sports, S.P. Ladany and R.E. Macol(eds.), ElsevierNorth Holland, New York, (1977), 77–85.
[2] Bukiet, B., Harold, E.R. and Palacios, J. L., A Markov Chain Approach to Baseball, Operations Research, 45(1), (1997), 14–23.
[3] Cover, T. M. and Keilers, C. W., An Oﬀensive Earned-Run Average for Baseball, , Operations Research, 25(5), (1977), 729–740.
[4] D’Esopo, D. A. and Lefkowitz, B., The Distribution of Runs in the Game of Baseball in
Optimal Strategies in Sports, S.P. Ladany and R.E. Macol(eds.) , Elsevier North-Holland,(1977), 55–62.
[5] Howard, R.A., Dynamic Programming and Markov Processes , M.I.T. Technology Press
and Wiley, Cambridge, Mass, (1960).
[6] Kira, A., Ueno, T., and Fujita, T., Threshold probability of non-terminal type in ﬁnite
horizon Markov decision processes, Journal of Mathematical Analysis and Applications,vol. 386, (2012), 461–472.
[7] Shapley, L. S., Stochastic games, Proceedings of the National Academy of Sciences of theUnited States of America, 39, (1953), 1095-1100.
[8] Turocy, T. L., In Search of the “Last-Ups” Advantage in Baseball: A Game-Theoretic
Approach, Journal of Quantitative Analysis in Sports, 4(2) , (2008), Article 5.
[9] Zachrisson, L. E., Markov games. Annals Math. Studies, 52. Advances in Game Theory,
M. Drescher, L.S. Shapley and A.W. Tucker(eds.), Princeton University Press, Princeton,
1964.
[10] Let’s enjoy baseball data! (in Japanese), ⟨http://baseballdata.jp/⟩, Accessed 2014 Mar 25.

9