A Convex Programming-based Algorithm for Mean Payoff
Stochastic Games with Perfect Information∗

arXiv:1610.06681v1 [] 21 Oct 2016

Endre Boros†

Khaled Elbassioni‡

Vladimir Gurvich§

Kazuhisa Makino¶

Abstract
We consider two-person zero-sum stochastic mean payoff games with perfect information, or
BWR-games, given by a digraph G = (V, E), with local rewards r : E → Z, and three types of
positions: black VB , white VW , and random VR forming a partition of V . It is a long-standing
open question whether a polynomial time algorithm for BWR-games exists, even when |VR | = 0.
In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial
solvability. In this short note, we show that BWR-games can be solved via convex programming
in pseudo-polynomial time if the number of random positions is a constant.

1

Introduction

We consider two-person zero-sum stochastic games with perfect information and mean payoff: Let
G = (V, E) be a digraph whose vertex-set V is partitioned into three subsets V = VB ∪ VW ∪ VR
that correspond to black, white, and random positions, controlled respectively, by two players, Min
- the minimizer and Max - the maximizer, and by nature. We also fix a local reward function
rP: E → Z, and probabilities p(v, u) > 0 for all arcs (v, u) going out of v ∈ VR . We assume that
u|(v,u)∈E p(v, u) = 1, for all v ∈ VR . Vertices v ∈ V and arcs e ∈ E are called positions and
moves, respectively. The game begins at time t = 0 in the initial position s0 = v0 . In a general
step, in time t, we are at position st ∈ V . The player who controls st chooses an outgoing arc
et+1 = (st , v) ∈ E, and the game moves to position st+1 = v. If st ∈ VR then an outgoing arc is
choses with the given probability p(st , st+1 ). We assume that every vertex in G has an outgoing
arc. In general, the strategy of the player is a policy by which (s)he chooses the outgoing arcs from
the vertices (s)he controls. This policy may involve the knowledge of the previous steps as well as
probabilistic decisions. We call a strategy stationary if it does not depend on the history and pure
if it does not involve probabilistic decisions. For this type of games, it will be enough to consider
only such strategies, since these games are known to be (polynomially) equivalent [BEGM13a] to
the perfect information stochastic games considered by Gillette [Gil57, LL69].
In the course of this game players and nature generate an infinite sequence of edges p =
(e1 , e2 , . . .) (a play) and the corresponding real sequence r(p) = (r(e1 ), r(e2 ), . . .) of local rewards.
There is a global payoff function φ that maps any local reward sequence to a real number, and it
is assumed that Min pays Max the amount φ(r(p)) resulting from the play. Naturally, Max’s aim
is to create a play which maximizes φ(r(p)), while Min tries to minimize it. (Let us note that the
local reward function r : E → R may have negative values, and φ(r(p)) may also be negative, in
∗ Part

of this research was done at the Mathematisches Forschungsinstitut Oberwolfach during a stay within the
”Research in Pairs” Program from July 26, 2015-August 15, 2015. The research of the third author has been partially
funded by the Russian Academic Excellence Project ’5-100’. The fourth author was partially supported by KAKENHI
Grant Numbers 24106002 and 26280001.
† MSIS Department and RUTCOR, Rutgers University, 100 Rockafellar Road, Livingston Campus Piscataway, NJ
08854, USA; (Endre.Boros@rutgers.edu)
‡ Masdar Institute of Science and Technology, P.O.Box 54224, Abu Dhabi, UAE; (kelbassioni@masdar.ac.ae)
§ MSIS Department and RUTCOR, Rutgers University, 100 Rockafellar Road, Livingston Campus Piscataway, NJ 08854, USA; and National Research University, Higher School of Economics, Moscow, Russia;
(Vladimir.Gurvich@gmail.com)
¶ Research Institute for Mathematical Sciences (RIMS) Kyoto University,
Kyoto 606-8502, Japan;
(makino@kurims.kyoto-u.ac.jp)

1

which case Max has to pay Min −φ(r(p)). Let us also note that r(p) is a random variable since
random transitions occur at positions in VR .) Here φ stands for the limiting mean payoff
φ(r(p)) = lim inf
T →∞

PT

i=1

E[r(ei )]
,
T

(1)

where E[r(ei )] is the expected reward incurred at step i of the play.
As usual, a pair of (not necessarily pure or stationary) strategies is a saddle point (or equilibrium)
if neither of the players can improve individually by changing her/his strategy. The corresponding
φ(r(p)) is the value µG (v0 ) of the game with respect to initial position v0 . Such a pair of strategies
are called optimal; furthermore, it is called uniformly optimal if it provides the value of the game for
any initial position. It is known [Gil57, LL69] that every such game has a pair of uniformly optimal
pure stationary strategies. A BWR-game is said to be ergodic if µG (v) = µ for all v ∈ V , that is,
the value is the same from each initial position.
This class of BWR-games was introduced in [GKK88]; see also [CH08]. The special case when
VR = ∅, BW-games, is also known as cyclic games. They were introduced for the complete bipartite
digraphs in [Mou76b, Mou76a], for all (not necessarily complete) bipartite digraphs in [EM79], and
for arbitrary digraphs1 in [GKK88]. A more special case was considered extensively in the literature
under the name of parity games [BV01a, BV01b, CJH04, Hal07, Jur98, JPZ06], and later generalized
also to include random positions in [CH08]. A BWR-game is reduced to a minimum mean cycle
problem in case VW = VR = ∅, see, e.g., [Kar78]. If one of the sets VB or VW is empty, we obtain
a Markov decision process (MDP), which can be expressed as a linear program; see, e.g., [MO70].
Finally, if both are empty, VB = VW = ∅, we get a weighted Markov chain. For BW-games several
pseudo-polynomial and subexponential algorithms are known [GKK88, KL93, ZP96, Pis99, BV01a,
BV01b, HBV04, BV05, BV07, Hal07, Sch09, Vor08]; see also [JPZ06] for parity games. Besides their
many applications (see e.g. [Lit96, Jur00]), all these games are of interest to Complexity Theory: It
is known [KL93, ZP96] that the decision problem “whether the value of a BW-game is positive” is in
the intersection of NP and co-NP. Yet, no polynomial algorithm is known for these games, see e.g.,
the survey by Vorobyov [Vor08]. A similar complexity claim can be shown to hold for BWR-games,
see [AM09, BEGM13a].

Main result
The computational complexity of stochastic games with perfect information is an outstanding open
question; see, e.g., the survey [RF91]. While there are numerous pseudo-polynomial algorithms
known for the BW-case, it is a challenging open question whether a pseudo-polynomial algorithm
exists for BWR-games, as the existence of such an algorithm would imply also the polynomial
solvability of this class of games [AM09].
In [BEGM13b, BEGM15], we gave a pseudo-polynomial algorithm for BWR-games when the
number of random positions is fixed. In this note we show that one can obtain a similar result via
convex programming, combined with some of the ideas in [BEGM13b, BEGM15].
For a BWR-game G let us denote by n = |VW | + |VB | + |VR | the number of positions, by k = |VR |
the number of random positions, and assume (without loss of generality) that all local rewards
are non-negative integers with maximum value U and all transition probabilities are rational with
common denominator D. The main result of this paper is as follows.
Theorem 1 A BWR-game G can be solved in poly(n, U, Dk ) time via convex programming.
This theorem extends the result by Schewe [Sch09], where it was shown that solving BW-games
can be reduced to solving linear programming problems with pseudo-polynomial bit length.
According to the results in [BEGM13b, BEGM15], to get a pseudo-polynomial algorithm for
BWR-games, it is enough to have pseudo-polynomial routines for: (i) solving BW-games; (ii) solving
1 In fact, BW-games on arbitrary digraphs can be polynomially reduced to BW-games on bipartite digraphs
[BEGM13a]; moreover, the latter class can further be reduced to BW-games on complete bipartite digraphs [CHKN14].

2

ergodic BWR-games; and (iii) finding the top and bottom classes in a non-ergodic BWR-game (that
is, the sets of positions with highest and lowest values).
There are several pseudo-polynomial algorithms for solving BW-games, e.g., [GKK88, Pis99,
ZP96]. One may also use the LP-based algorithm given in [Sch09]. For (ii) we show in Section 5 how
to obtain the top (resp., bottom) class in a BWR-game, and a pair of strategies solving the game
induced by the top (resp., bottom) class. This also provides an algorithm for ergodic BWR-games
as required in (iii).

2

Potential transformations and canonical forms

Given a BWR-game G = (G, p, r), let us introduce a mapping x : V → R, whose values x(v) will be
called potentials, and define the transformed reward function rx : E → R as:
rx (v, u) = r(v, u) + x(v) − x(u), where (v, u) ∈ E.

(2)

It is not difficult to verify that the obtained game G x and the original game G are equivalent
(see [BEGM13a]). In particular, their optimal (pure stationary) strategies coincide, and their value
functions also coincide: µG x = µG .
It is known that for BW-games there exists a potential transformation such that, in the obtained
game the locally optimal strategies are globally optimal, and hence, the value and optimal strategies
become obvious [GKK88]. This result was extended for the more general class of BWR-games in
[BEGM13a]: in the transformed game, the equilibrium value µG (v) = µG x (v) is given simply by the
maximum local reward for v ∈ VW , the minimum local reward for v ∈ VB , and the average local
reward for v ∈ VR . In this case we say that the transformed game is in canonical form. To define this
more formally, let us use the following notation throughout this section: Given functions f : E → R
and g : V → R, we define the functions M [f ], M [g] : V → R.

for v ∈ VW ,
 maxu|(v,u)∈E f (v, u),
min
f
(v,
u),
for v ∈ VB ,
M [f ](v) =
u|(v,u)∈E
 P
u|(v,u)∈E p(v, u) f (v, u), for v ∈ VR .

for v ∈ VW ,
 maxu|(v,u)∈E g(u),
min
g(u),
for v ∈ VB ,
M [g](v) =
u|(v,u)∈E
 P
p(v,
u)
g(u),
for
v ∈ VR .
u|(v,u)∈E
We say that a BWR-game G is in (strong) canonical form if there exist vectors µ, x ∈ RV such
that
(C1) µ = M [µ] = M [rx ] and,
(C2) for every v ∈ VW ∪ VB , every move (v, u) ∈ E such that µ(v) = rx (v, u) must also have
µ(v) = µ(u), or in other words, every locally optimal move (v, u) is globally optimal.
Theorem 2 ([BEGM13a]) For each BWR-game G there is a potential transformation x ∈ RV
that brings G to canonical form with kxk∞ ≤ L := nU k(2D)k . Furthermore, in a game in canonical
form we have µG = M [rx ].
In this paper, we will provide a convex programming formulation based on the existence of
potential transformations.
We will need the following upper bound on the required accuracy.
Lemma 1 ([BEGM10, BEGM15]) For any position v in the top (resp., bottom)
class in a BWR√
game G, the value µG (v) is a rational number with a denominator at most k2k/2 Dk+1 .
Lemma 2 Consider a BWR-game G and denote by 1 the vector of all ones. Then there exists a
potential vector x ∈ RV and t ∈ R such that M [rx ] ≥ t1 if and only if µG ≥ t1.

3

Proof Indeed, if Max (Min) applies a locally optimal strategy sW in the transformed game G x
then after every own move (s)he will get (pay) at least t, while for each move of the opponent the
local reward will be at least (at most) t, and finally, for each random position the expected local
reward is at least t. Thus, the expected local reward E[rx (ei )] at each step of the play is at least t.
Hence, by (1), strategy sW guarantees Max at least t from any starting position.
The other direction follows from Theorem 2.

A symmetric version of Lemma 2 can also be obtained by similar arguments.
Lemma 3 Consider a BWR-game G. Then there exists a potential vector x ∈ RV and t ∈ R such
that M [rx ] ≤ t1 if and only if µG ≤ t1.

3

The convex programs

The following simple facts relate the softmax (resp., softmin) to the maximimum (resp., minimum)
of a set of numbers.
Fact 1 For any numbers a1 , . . . , an ∈ R and b > 1:
P
(i) maxi ai ≤ logb i bai ≤ maxi ai + logb n;
P
(ii) mini ai ≥ − logb i b−ai ≥ mini ai − logb n.

Proof This follows from the fact the trivial inequalities bmaxi ai ≤

Fact 2 Let α1 , . . . , αn > 0 be given numbers such that
Q
n
αi
i=1 xi is concave for x ≥ 0.

Pn

i=1

P

i

bai ≤ nbmaxi ai .



αi = 1. Then the function f (x) =

Proof Note that for any x, y ∈ Rn+ , if for some i, xi = 0 then for any λ ∈ [0, 1],
λf (x) + (1 − λ)f (y) =(1 − λ)f (y)
n
n
Y
Y
((1 − λ)yi )αi
yiαi =
=(1 − λ)
i=1

≤

n
Y

i=1

i=1

αi

(λi xi + (1 − λ)yi )

= f (λx + (1 − λ)y).

Thus, it is enough to show that ∇2 f (x) is a negative semi-definite matrix for x > 0. Note that
∂f
αi
= f (x), for i = 1, . . . , n
∂xi xi
∂ 2 f αi (αi − 1)
=
f (x), for i = 1, . . . , n
∂x2i
x2i
αi αj
∂2f
=
f (x), for i, j = 1, . . . , n, i 6= j.
∂xi ∂xj xi xj
Consider any y ∈ Rn . Then



2
X
y
y
y
i j 
αi (αi − 1) i2 +
y T ∇2 f (x)y = 
αi αj
f (x)
x
x
xj
i
i
i
i6=j


!2
X  yi 2
X yi
 f (x) ≤ 0,
αi
−
αi
=
x
x
i
i
i
i
X

where the last inequality follows from Jensen’s inequality applied to the convex function f (w) = w2 .
4


Given t ∈ R, let us replace the max operator in the system M [rx ] ≥ t by the softmax approximation:
X
br(v,u)+x(v)−x(u) ≥ t,
for v ∈ VW ,
(3)
logb
u|(v,u)∈E

X

u|(v,u)∈E

r(v, u) + x(v) − x(u) ≥ t,

for u s.t. (v, u) ∈ E for v ∈ VB ,

(4)

p(v, u)(r(v, u) + x(v) − x(u)) ≥ t,

for v ∈ VR ,

(5)

where the constant b will be determined later. Defining the new variables y(v) := b−x(v) , we can
rewrite (3)-(5) as follows:
X

u|(v,u)∈E

Y

u|(v,u)∈E

br(v,u) y(u) ≥ bt y(v),

for v ∈ VW ,

(6)

br(v,u) y(u) ≥ bt y(v),

for u s.t. (v, u) ∈ E for v ∈ VB ,

(7)

for v ∈ VR .

(8)

(br(v,u) y(u))p(v,u) ≥ bt y(v),

Note that y(v) > 0 if and only if x(v) is finite. In fact, since we may assume by Theorem 2 that
kxk∞ ≤ L, we may add also the inequalities:
b−L ≤ y(v) ≤ bL ,

for v ∈ V.

Note that, without the lower bounds y(v) ≥ b−L , the system (6)-(8) is always feasible. As we shall
see later, it will be necessary to test the feasibility of the system with y(v) > 0 for some v ∈ V . For
convenience, let us write more generally the following set of upper and lower bounds, where V ′ ⊆ V
is to be chosen later:
0 ≤ y(v) ≤ bL ,

for v ∈ V, and y(v) ≥ b−L ,

for v ∈ V ′ .

(9)

Similarly, we replace the min operator in the system M [rx ] ≤ t by the softmin approximation:
r(v, u) + x(v) − x(u) ≤ t,
X
b−r(v,u)−x(v)+x(u) ≤ t,

for u s.t. (v, u) ∈ E for v ∈ VW ,

(10)

for v ∈ VB ,

(11)

p(v, u)(r(v, u) + x(v) − x(u)) ≤ t,

for v ∈ VR ,

(12)

− logb
X

u|(v,u)∈E

u|(v,u)∈E

and defining the new variables y(v) := bx(v) , we can rewrite (10)-(12) as follows:
b−r(v,u) y(u) ≥ b−t y(v),

for u s.t. (v, u) ∈ E for v ∈ VW ,

(13)

y(u) ≥ b y(v),

for v ∈ VB ,

(14)

(b−r(v,u) y(u))p(v,u) ≥ b−t y(v),

for v ∈ VR ,

(15)

X

b

−r(v,u)

u|(v,u)∈E

Y

u|(v,u)∈E

−t

together with the lower and upper bounds:
0 ≤ y(v) ≤ bL ,

for v ∈ V, and y(v) ≥ b−L ,
5

for v ∈ V ′ .

(16)

4

Solving the convex programs

We will use the ellipsoid method [Kha80, Kha84, GLS88]. For this we need to show that the
separation problem can be solved in polynomial time. For convenience, let us consider the following
relaxation of the convex programs (6)-(9) and (13)-(16):
X
br(v,u) y(u) ≥ bt y(v) − δ,
for v ∈ VW ,
(17)
u|(v,u)∈E

Y

(b

r(v,u)

br(v,u) y(u) ≥ bt y(v) − δ,

for u s.t. (v, u) ∈ E for v ∈ VB ,

(18)

≥ b y(v) − δ,

for v ∈ VR .

(19)

p(v,u)

y(u))

u|(v,u)∈E

0 ≤ y(v) ≤ bL + δ,
X

u|(v,u)∈E

Y

u|(v,u)∈E

t

for v ∈ V, and bL y(v) ≥ 1,

for v ∈ V ′ .

(20)

b−r(v,u) y(u) ≥ b−t y(v) − δ,

for v ∈ VW ,

(21)

b−r(v,u) y(u) ≥ b−t y(v) − δ,

for u s.t. (v, u) ∈ E for v ∈ VB ,

(22)

for v ∈ VR .

(23)

(b−r(v,u) y(u))p(v,u) ≥ b−t y(v) − δ,

0 ≤ y(v) ≤ bL + δ,

for v ∈ V, and bL y(v) ≥ 1,

for v ∈ V ′ .

(24)

where δ > 0 is a rational number that will be chosen appropriately. Let K and Kδ be the set of
y ∈ RE satisfying (6)-(9) and (17)-(20), respectively. Similarly, Let K ′ and Kδ′ be the set of y ∈ RE
satisfying (13)-(16) and (21)-(24), respectively.
In√our application, we will set b = n4Λ and t ∈ [0, U ] to be a rational number with denominator
Λ := k2k/2 Dk+1 . In particular, b±t is a rational number of bit length hb±t i = O(Λ log n). Also by
assuming without loss of generality (by scaling r and replacing U by U D) that r(v, u) is a multiple
of D, b±r(v,u) is a rational number of bit length hb±r(v,u) i = O(ΛU D log n).
Claim 1 For 0 < ǫ ≤ b−t δ and any y ∈ K (resp., y ∈ K ′ ), the box {y ′ ∈ Rn | y ≤ y ′ ≤ y + ǫ · 1} is
contained in Kδ (resp., Kδ′ ), where 1 is the n-dimensional vector of all ones. In particular, if K 6= ∅
(resp., K ′ 6= ∅) then Kδ (resp., Kδ′ ) is full-dimensional.
Proof We prove the statement for Kδ ; the proof for Kδ′ is similar. Clearly, K ⊆ Kδ for δ ≥ 0.
Furthermore, for any y ∈ K and S ⊆ V , the vector y ′ obtained from y by setting y ′ (u) := y(u) + ǫ
for u ∈ S and y ′ (u) := y(u) for u ∈ V \ S satisfies (6)-(9). Indeed, the left-hand sides of (17)-(19)
increase when y is increased in the components corresponding to S, while the right-hand sides are
at most bt y(v) + bt ǫ − δ ≤ bt y(v). Also by (9), y ′ (v) ≤ y(v) + ǫ ≤ bL + ǫ ≤ bL + δ, so y ′ satisfies
(17)-(20).

Now we consider the (semi-weak) separation problem for Kδ (resp., Kδ′ ):
Given ȳ ∈ Qn and 0 < δ ′ ∈ Q, either assert that ȳ ∈ Kδ (resp., ȳ ∈ Kδ′ ) or find a vector c ∈ Qn
such that cT y + δ ′ ≥ cT ȳ for all y ∈ Kδ (resp., y ∈ Kδ′ ).
Claim 2 The separation problems for Kδ and Kδ′ can be solved in poly(U, D, Λ, log n, hȳi, hδ ′ i) time.
Proof We present the proof for Kδ ; the proof for Kδ′ is similar. Clearly, we can check in
poly(hȳi, hbt i, hδi, n) time if ȳ satisfies the linear inequalities (17), (18) and (20); if one is violated,
the corresponding hyperplane defines a (exact) separator c ∈ Qn and we are done. Assume therefore
that ȳ satisfies (17), (18) and (20). Let us now consider an inequality of the form (19) corresponding
6

Q
to v ∈ V violated by ȳ. Let f (y) = u|(v,u)∈E (br(v,u) y(u))p(v,u) − bt y(v) := A · g(y) − B · y(v),
Q
Q
where A := u|(v,u)∈E br(v,u)p(v,u) , B := bt and g(y) := u|(v,u)∈E y(u)p(v,u) . Note that f (ȳ) < −δ
if and only if AD · g(ȳ)D < (B · ȳ(v) − δ)D , which can be checked in poly(hȳi, hδi, n, log D) time,
3
as both AD and B D are non-negative integers2 . Without loss of generality
, we assume
that for


p(v,u)
every u ∈ V there is exactly one edge (v, u) ∈ E. Then ∇f (y) := A · y(u) : u ∈ V g(y) − B1v ,
where 1v is the unit dimensional vector with 1 in position v. Then the inequality −δ ≤ f (y) ≤
f (ȳ) + ∇f (ȳ)T (y − ȳ) < −δ + ∇f (ȳ)T (y − ȳ), valid for all y ∈ Kδ by concavity of f (y), gives a
separating inequality:
∇f (ȳ)T y > ∇f (ȳ)T ȳ for all y ∈ Kδ .
(25)
Note that the vector ∇f (ȳ) can be irrational (it is irrational whenever
 g(ȳ) is). We
 define a
p(v,u)
δ′
rational approximation g̃ such that g̃ ≥ g(ȳ) ≥ g̃ − A and c := A · ȳ(u) : u ∈ V g̃ − B1v .

Since r(v, u) is assumed to be integer multiple of D, A is an integer and hence g̃ is a rational
number of bit length hg̃i = hAi + hδ ′ i. It follows also that c is a rational vector of bit length
poly(U DΛ log n, hȳi, hδ ′ i). Note that
T

T

c y − ∇f (ȳ) y = A ·



p(v, u)
: u∈V
ȳ(u)

T

y · (g̃ − g(ȳ)) ≥ 0 for all y ∈ Kδ ,

(26)

while
cT ȳ − ∇f (ȳ)T ȳ = A ·



p(v, u)
: u∈V
ȳ(u)

T

ȳ · (g̃ − g(ȳ)) ≤ δ ′

It follows from (25), (26), and (27) that cT y + δ ′ ≥ cT ȳ for all y ∈ Kδ .

(27)



Lemma 4 Given t ∈ R and δ ∈ (0, 1) we can decide in time poly(n, U, Dk , log δ1 ) if the system
(6)-(9) (resp., (13)-(16)) is infeasible, or find y(v) ∈ [b−L , bL + δ], for v ∈ V ′ and y(v) ∈ [0, bL + δ],
for v ∈ V \ V ′ , such that the left hand sides of (6)-(8) (resp., (13)-(15)) are at least bt y(v) − δ (resp.,
b−t y(v) − δ), for all v ∈ V .
Proof Let us consider the equivalent system (6)-(9); the proof for (21)-(24) is similar. Given a
polynomial-time algorithm for the separation problem for the convex set Kδ , a circumscribing ball
of radius H for Kδ , and any ǫ′ > 0, the ellipsoid method terminates in N := O(n log ǫ1′ + n2 | log H|)
calls to the separation algorithm using δ ′ = 2−O(N ) , and either (i) finds a vector y ∈ Kδ , or (ii)
asserts that vol(Kδ ) ≤ ǫ′ ; see, e.g., Theorem 3.2.1 in [GLS88]. In the first case, we get a vector y
satisfying the conditions in the statement of the lemma. In the second case, we conclude that Kδ and
hence K is empty if ǫ′ < (b−t δ)n . Indeed by Claim 1, if K 6= ∅ and ǫ := b−t δ, then vol(Kδ ) ≥ ǫn > ǫ′ ,
given a contradiction to the assertion in (ii).
By (20), the radius of the bounding ball can be chosen as H := 2bL . Furthermore, the ellipsoid
method works only with numbers having precision of O(N ) bits. By Claim 2, the separation problem

can be solved in time poly(n, U, Dk , log 1δ ).
Remark 1 By raising to inequalities (8) and (15) to power D, we obtain systems of polynomial inequalities. Khachiyan [Kha83, Kha84] gave a polynomial-time algorithm for (approximately) solving
a system of convex polynomial inequalities. However, it is not possible to use this algorithm directly
to solve the convex programs (6)-(9) and (13)-(16), since the polynomials obtained after raising in√
equalities (8) and (15) to power D are not necessarily convex. For instance, the function xy − z
2
is concave for x, y, z ∈ R+ , while the function xy − z is not.
2

case of Kδ′ , they are rational numbers of denominator at most nΛD U
this part of the proof we can consider the restriction of y to the set of positions reachable from v by one move.
We can also replace parallel edges by one edge; if v is a position of chance then the transition probability of this edge
is the sum of the transition probabilities of all corresponding parallel edges.
2 in

3 For

7

5

A Pseudo-polynomial algorithm for k = O(1)

Let G be a BWR-game. Let tmax := maxv∈V µG (v) and tmin := minv∈V µG (v). Define the top and
bottom classes of G as T := {v ∈ V | µG (v) = tmax } and B := {v ∈ V | µG (v) = tmin }, respectively.
Proposition 1 Top and bottom classes necessarily satisfy the following properties.
(i) There exists no arc (v, u) ∈ E such that v ∈ (VW ∪ VR ) ∩ B, u 6∈ B;
(ii) there exists no arc (v, u) ∈ E such that v ∈ (VB ∪ VR ) ∩ T , u 6∈ T ;
(iii) there exists no arc (v, u) ∈ E such that v ∈ VW \ T , u ∈ T ;
(iv) there exists no arc (v, u) ∈ E such that v ∈ VB \ B, u ∈ B;
(v) for every v ∈ VW ∩ T , there exists an arc (v, u) ∈ E such that u ∈ T ;
(vi) for every v ∈ VB ∩ B, there exists an arc (v, u) ∈ E such that u ∈ B;
(vii) for every v ∈ (VB ∪ VR ) \ T , there exists an arc (v, u) ∈ E such that u 6∈ T ;
(viii) for every v ∈ (VW ∪ VR ) \ B, there exists an arc (v, u) ∈ E such that u 6∈ B.
Proof All claims follow from the existence of a canonical form for G, by Theorem 2. Indeed, the
existence of arcs forbidden by (i), (ii), (iii) and (iv), or the non-existence of arcs required by (v),
(vi), (vii) and (viii) would violate the value equations (C1) of the canonical form.

Lemma 5 Consider the convex program defined by (6)-(8) (resp., (13)-(15)). Then for t := tmax
(resp., t := tmin ), there is a feasible solution with y(v) ≥ b−L for all v ∈ T (resp., v ∈ B).
Proof Consider the game G[T ] (resp., G[B]) induced by the top class T (resp., the bottom class
B). Let x ∈ RT (resp., x ∈ RB ) be the potential vector guaranteed by Theorem 2 for the game G[T ]
(resp., G[B]). Set y(v) := b−x(v) for v ∈ T (resp., y(v) := bx(v) for v ∈ B) and y(v) = 0 for v ∈ V \ T
(resp., v ∈ V \ B). Then y(v) ≥ b−L for all v ∈ T (resp., v ∈ B). It is easy to verify by Proposition 1
that the system is feasible. Indeed, (6) is satisfied for every position v ∈ VW ∩ T (resp., v ∈ VB ∩ B)
by the definition of x and Fact 1:
X
br(v,u)+x(v)−x(u)
tmax ≤ max (r(v, u) + x(v) − x(u)) ≤ logb
u|(v,u)∈E

(resp., − tmin ≤ −

u|(v,u)∈E

min (r(v, u) + x(v) − x(u)) ≤ − logb

u|(v,u)∈E

X

b−r(v,u)−x(v)+x(u) ).

u|(v,u)∈E

Moreover, for v ∈ (VB ∪ VR ) ∩ T (resp., v ∈ (VW ∪ VR ) ∩ B) we have (7) and (8) (resp., (14) and (15))
satisfied by the definition of x and Proposition 1-(ii) (resp., Proposition 1-(i)), while for v ∈ V \ T
(resp., v ∈ V \ B) (6)-(8) (resp., (13)-(15)) are trivially satisfied.

In the following we set δ(t) := 12 b−t−L (1 − n1 ), where ε :=

√

1
.
k2k/2+1 Dk+1

2

Note that b := n ε .

Lemma 6 The values tmax and tmin can be found in time poly(n, U, Dk ).
Proof We only show how to find tmax ; in a similar fashion we can determine tmin . We apply
Lemma 4 in a binary search manner to check the feasibility of the system (13)-(16) for t ∈ [0, U ] and
δ(t) as specified above. Note that, by Lemma 1, tmax ∈ [0, U ] can be written as a rational number
1
1
with denominator at most 2ε
. So we may restrict our search steps to integer multiples of 2ε
. We
1
stop the search when the length of the search interval becomes a constant multiple of 2ε , and then
apply linear search for the remaining small interval.
8

Suppose that the convex program (13)-(16) is infeasible. Then Theorem 2 implies that tmax >
t. On the other hand, if y ∈ RV is a δ(t)-approximately feasible solution for (13)-(16), then as
δ(t) ≤ 12 b−L , the new vector y ′ := 2y satisfies y ′ (v) ∈ [b−L , 2bL + b−L ] for all v ∈ V . Also,
y ′ satisfies (13)-(15) within an error of 2δ(t), that is, the left-hand sides of (13)-(15), when y is
replaced by y ′ , are at least b−t y ′ (v) − 2δ(t) = b−t y ′ (v) − b−t−L (1 − n1 ) ≥ b−t−logb n y ′ (v). Set
x(v) := logb y ′ (v). Then x satisfies (10)-(12) with t replaced by t + logb n. This in turn implies by
Fact 1 that M [rx ] ≤ (t + 2 logb n)1 = (t + ε)1. It follows then from Lemma 3 that tmax ≤ t + ε.
Recall that we assume both t and tmax are multiples of 2ε; hence, tmax ≤ t.
U
= O(k log(U D)) and each step requires
Since the number of binary search steps is at most log 2ǫ
1
k

time poly(n, U, log b, log δ ) = poly(n, U, ), the bound on the running time follows.
Lemma 7 We can find the top class T (resp., bottom class B) in time poly(n, U, Dk ).
Proof We can check if a vertex w ∈ V belongs to the top class (resp., bottom class) as follows.
We write the convex program (6)-(8) (resp., (13)-(15)) with t := tmax (resp., t = tmin ) and with
the additional constraint that y(w) ≥ b−L and y(v) ≥ 0 for all v ∈ V \ {w}. Then we check the
feasibility of this system. If the system is infeasible then we know by Lemma 5 that w 6∈ T (resp.,
w 6∈ B).
Suppose, on the other hand, that y ∈ RV is a δ(tmax )-approximately (resp., δ(tmin )-approximately)
feasible solution for (6)-(8) (resp., (13)-(15)). Then as in the proof of Lemma 6, the new vector
y ′ := 2y satisfies y ′ (w) ≥ b−L > 0, and the left-hand sides of (6)-(8) (resp., (13)-(15)), when y is
replaced by y ′ , are at least bt−logb n y ′ (w) (resp., b−t−logb n y ′ (w)).
Now we claim that V + := {v ∈ V : y(v) > 0} ⊆ T (resp., V + := {v ∈ V : y(v) > 0} ⊆ B),
which would in turn imply that w ∈ T (resp., w ∈ B). Indeed, constraints (6)-(8) (resp., (13)-(15)),
applied to y replaced by y ′ , imply that (i) if v ∈ VW ∩ V + then there exists an arc (v, u) ∈ E such
that u ∈ V + ; (ii) if v ∈ (VB ∪ VR ) ∩ V + then all arcs (v, u) ∈ E must that u ∈ V + (resp., (i) if
v ∈ VB ∩ V + then there exists an arc (v, u) ∈ E such that u ∈ V + ; (ii) if v ∈ (VW ∪ VR ) ∩ V + then
all arcs (v, u) ∈ E must that u ∈ V + ). These imply that the game induced by V + is well-defined
and, by Lemma 2 (resp., Lemma 3), all its positions have value at least tmax (resp., at most tmin ).
The lemma follows.

Finally, given the top and bottom classes, we can find an optimal pair of strategies in the games
induced by T and B, as stated in the next lemma.
Lemma 8 We can find optimal pairs of strategies in the games induced by the top class T and
bottom class B in time poly(n, U, Dk ).
Proof We prove the lemma only for T ; the proof for B can be done similarly. We solve two
(feasible) systems, S1 defined by (6)-(9) on G[T ] and S2 defined by (13)-(15) on G[T ], with t := tmax
to within an accuracy of δ(tmax ). Let y 1 , y 2 ∈ RT be the δ(tmax )-approximate solutions to S1 and
S2 , respectively. By the same arguments as in Lemma 6, the corresponding potential vectors x1 , x2
(defined by x1 (v) := − logb (2y 1 (v)) and x2 (v) := logb (2y 2 (v))) ensure that M [rx1 ] ≥ (tmax − ε)1 and
M [rx2 ] ≤ (tmax + ε)1. Since ε is sufficiently small, by Lemmas 2 and 3, the locally optimal strategies
defined by the operator M with respect to x1 and x2 give optimal strategies for Max and Min in
G[T ], respectively.

Finally, we obtain Theorem 1 by combining the above lemmas with the algorithm in [BEGM13b,
BEGM15].

References
[AM09]

D. Andersson and P. B. Miltersen. The complexity of solving stochastic games on
graphs. In ISAAC, pages 112–121, 2009.

9

[BEGM10]

E. Boros, K. Elbassioni, V. Gurvich, and K. Makino. A pumping algorithm for ergodic
stochastic mean payoff games with perfect information. In Proc. 14th IPCO, pages
341–354, 2010.

[BEGM13a] E. Boros, K. Elbassioni, V. Gurvich, and K. Makino. On canonical forms for zero-sum
stochastic mean payoff games. Dynamic Games and Applications, 3(2):128–161, 2013.
[BEGM13b] Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. A
pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and a few random positions. In Automata, Languages, and Programming - 40th
International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings,
Part I, pages 220–231, 2013.
[BEGM15]

E. Boros, K. Elbassioni, V. Gurvich, and K. Makino. A pseudo-polynomial algorithm
for mean payoff stochastic games with perfect information and few random positions.
CoRR, abs/1508.03431, 2015.

[BV01a]

E. Beffara and S. Vorobyov. Adapting gurvich-karzanov-khachiyan’s algorithm
for parity games: Implementation and experimentation. Technical Report 2001020, Department of Information Technology, Uppsala University, available at:
https://www.it.uu.se/research/reports/#2001, 2001.

[BV01b]

E. Beffara and S. Vorobyov.
Is randomized gurvich-karzanov-khachiyan’s algorithm for parity games polynomial?
Technical Report 2001-025, Department of Information Technology, Uppsala University,
available at:
https://www.it.uu.se/research/reports/#2001, 2001.

[BV05]

H. Björklund and S. Vorobyov. Combinatorial structure and randomized subexponential algorithm for infinite games. Theoretical Computer Science, 349(3):347–
360, 2005.

[BV07]

H. Björklund and S. Vorobyov. A combinatorial strongly sub-exponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics,
155(2):210–229, 2007.

[CH08]

K. Chatterjee and T. A. Henzinger. Reduction of stochastic parity to stochastic meanpayoff games. Inf. Process. Lett., 106(1):1–7, 2008.

[CHKN14]

K. Chatterjee, M. Henzinger, S. Krinninger, and D. Nanongkai. Polynomial-time algorithms for energy games with special weight structures. Algorithmica, 70(3):457–492,
2014.

[CJH04]

K. Chatterjee, M. Jurdziński, and T. A. Henzinger. Quantitative stochastic parity
games. In SODA ’04, pages 121–130, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.

[EM79]

A. Eherenfeucht and J. Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8:109–113, 1979.

[Gil57]

D. Gillette. Stochastic games with zero stop probabilities. In A.W. Tucker M. Dresher
and P. Wolfe, editors, Contribution to the Theory of Games III, in Annals of Mathematics Studies, volume 39, pages 179–187. Princeton University Press, 1957.

[GKK88]

V. Gurvich, A. Karzanov, and L. Khachiyan. Cyclic games and an algorithm to find
minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics, 28:85–91, 1988.

[GLS88]

M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial
Optimization. Springer, New York, 1988.

10

[Hal07]

N. Halman. Simple stochastic games, parity games, mean payoff games and discounted
payoff games are all LP-type problems. Algorithmica, 49(1):37–50, 2007.

[HBV04]

S. Sandberg H. Björklund and S. Vorobyov. A combinatorial strongly sub-exponential
strategy improvement algorithm for mean payoff games. DIMACS Technical Report
2004-05, DIMACS, Rutgers University, 2004.

[JPZ06]

M. Jurdziński, M. Paterson, and U. Zwick. A deterministic subexponential algorithm
for solving parity games. In SODA ’06, pages 117–123, New York, NY, USA, 2006.
ACM.

[Jur98]

M. Jurdziński. Deciding the winner in parity games is in UP ∩ co-UP. Inf. Process.
Lett., 68(3):119–124, 1998.

[Jur00]

M. Jurdziński. Games for Verification: Algorithmic Issues. PhD thesis, Department
of Computer Science, University of Aarhus, Denmark, 2000.

[Kar78]

R. M. Karp. A characterization of the minimum cycle mean in a digraph. Discrete
Math., 23:309–311, 1978.

[Kha80]

L. Khachiyan. Polynomial algorithms in linear programming. U.S.S.R. Comput. Math.
Math. Phys., 20:53–72, 1980.

[Kha83]

L. Khachiyan. Convexity and complexity in polynomial programming. In Proceedings
of the International Congress of Mathematicians, Warsaw, page 15691577, 1983.

[Kha84]

L. Khachiyan. Complexity of convex problems of real and integer programming. PhD
thesis, The second thesis, manuscript, Computer Center of the USSR Academy of
Sciences (in Russian), Moscow, 1984.

[KL93]

A. V. Karzanov and V. N. Lebedev. Cyclical games with prohibition. Mathematical
Programming, 60:277–293, 1993.

[Lit96]

M. L. Littman. Algorithm for sequential decision making, CS-96-09. PhD thesis, Dept.
of Computer Science, Brown Univ., USA, 1996.

[LL69]

T. M. Liggett and S. A. Lippman. Stochastic games with perfect information and
time-average payoff. SIAM Review, 4:604–607, 1969.

[MO70]

H. Mine and S. Osaki. Markovian decision process. American Elsevier Publishing Co.,
New York, 1970.

[Mou76a]

H. Moulin. Extension of two person zero sum games. Journal of Mathematical Analysis
and Application, 5(2):490–507, 1976.

[Mou76b]

H. Moulin. Prolongement des jeux à deux joueurs de somme nulle. Bull. Soc. Math.
France, Memoire, 45, 1976.

[Pis99]

N. N. Pisaruk. Mean cost cyclical games.
24(4):817–828, 1999.

[RF91]

T. E. S. Raghavan and J. A. Filar. Algorithms for stochastic games: A survey. Mathematical Methods of Operations Research, 35(6):437–472, 1991.

[Sch09]

Sven Schewe. From parity and payoff games to linear programming. In Mathematical
Foundations of Computer Science 2009, 34th International Symposium, MFCS 2009,
Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings, pages 675–
686, 2009.

[Vor08]

S. Vorobyov. Cyclic games and linear programming. Discrete Applied Mathematics,
Special volume in Memory of Leonid Khachiyan (1952 - 2005), 156(11):2195–2231,
2008.
11

Mathematics of Operations Research,

[ZP96]

U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theoretical
Computer Science, 158(1-2):343–359, 1996.

12

