# «Discrete and Lexicographic Helly Theorems and their Relations to LP-Type Problems Thesis submitted for the degree of “Doctor of Philosophy” by ...»

Condon [Co92] was the ﬁrst to study SSG’s from a complexity theory point of view. She showed that the SSG decision problem is in NP ∩ co-NP (and even in UP ∩ co-UP [J98]), and hence is unlikely to be NP-complete, but at the same time it is not known to be in P, despite substantial eﬀort (see [EJS93], [Lu95], [ZP96], [Sei96], [BCJLM97], [J00] and [BSV03a]). Some exponential algorithms for SSG’s are described in √ [MC90]. The ﬁrst subexponential algorithm for the binary SSG decision problem was an eO( n) time ad-hoc algorithm obtained in 1995 by Ludwig [Lu95], for games with n vertices.

We show (see also [Hal01]) the ﬁrst subexponential solution for the (non-binary) SSG decision problem with n nodes and nn edges, in which the denominators of all the (rational) probabilities are at most l. The idea is to formulate the SSG as an LP-type problem, and then to solve its corresponding decision problem by the LP-type algorithm of [SW92]. Independently, Bj¨rklund et al [BSV03a] developed several ad-hoc o subexponential algorithms for this problem. Their approach is diﬀerent. They ﬁrst formulate the objective function of this problem as a special function (which they call either RLG, CLG or CU function). They then “adapt” the algorithm of [Lu95], as well as the LP-type subexponential algorithms √ [SW92, Kal92], to of O( n log n) ×C(n, nn, l) solve these functions. The algorithms of [Hal01, BSV03a] are randomized and run in e time, where C(x, y, z) is the time needed to solve a linear program with x variables, y constraints and l being the (binary) coding size of the input numbers. The best known algorithms for solving variable-dimensional LP problems (e.g., the one of Khachiyan [Kh79]) perform a polynomial number of operations in x, y and z. Since the number of operations they perform depends on the size of the input numbers, they are not strongly polynomial. This implies that the algorithms of [Hal01, BSV03a] are not strongly subexponential.

√ In this chapter we obtain the ﬁrst strongly eO( n log n) subexponential solution for SSG. This algorithm is faster than the previous algorithms when l is much greater than n.

SSG’s are a restriction of stochastic games introduced by Shapley [Sh53], some 50 years ago. Many variants of SSG’s have been studied since then (see Peters and Vrieze [PV87] for a survey). In the next section we describe three variants of SSG: Parity Games (PG’s), Mean Payoﬀ Games (MPG’s), and Discounted Payoﬀ Games (DPG’s).

SSG’s are a generalization of PG’s, MPG’s and DPG’s in the sense that there exists a polynomial time reduction from them to (non-binary) SSG’s that halt with probability 1 (See deﬁnition in Subsection 11.2.1.

See Puri [P95] for a reduction of PG to SSG, and Zwick and Paterson [ZP96] for a reduction of MPG and DPG to SSG). The decision problems corresponding to PG’s, MPG’s and DPG’s are also known to be in

As seen in the table, our algorithmic results improve upon the best known algorithms for SSG’s and DPG’s.

We also give alternate simple proofs for the best known upper bounds for PG’s, MPG’s and binary SSG’s.

While [Lu95, BSV03a, BSV03b, BSV04] developed ad-hoc algorithms for each of the speciﬁc games they solved, we use only one unifying algorithm for all of these ﬁve games - the LP-type algorithm of [SW92].

11.2 Deﬁnitions and previous results In this section we review the deﬁnitions and the results known about SSG’s and review the deﬁnitions of Parity Games, Mean Payoﬀ Games, and Discounted Payoﬀ Games.

11.2.1 Simple Stochastic Games Although this section is self contained, it is strongly based upon the ﬁrst two sections in [Lu95].

Let G = (V = N X A {v0, v1 }, E = S D AA) be a SSG. v0 is the 0-sink and v1 is the 1sink. N = {y1, y2,..., ym }, X = {x1, x2,..., xd } and A = {a1,..., ap } are the sets of min, max and average vertices, respectively. Let n = |V | = d + m + p + 2 be the number of vertices in the graph. For i = 1,..., d (i = 1,..., m; i = 1,..., p) let Xi (Ni, Ai ) be the set of edges outgoing from the max (min, average) vertex d m p xi (yi, ai ), respectively. Let S = i=1 Xi (D = i=1 Yi ; AA = i=1 Ai ) be the set of the edges outgoing from vertices of X (Y, A), respectively. For every i = 1,.., p, every edge e ∈ Ai is given a positive rational weight pr(e) 1 such that e∈Ai pr(e) = 1.

Formally, a strategy for player 1 is a function σ : {1, 2,..., d} → V which indicates for every vertex xi ∈ X, an outgoing edge (xi, σ(i)) ∈ Xi that player 1 will choose. We deﬁne a strategy τ for player 0 similarly.

Let σ, τ be a pair of strategies for players 1 and 0. Construct the graph Gσ,τ = (V, Sσ ∪ Dτ ∪ AA) where Sσ = {(xi, σ(i)) | i = 1,..., d} and Dτ = {(yi, τ (i)) | i = 1,..., m}. A Simple Stochastic Game halts with probability 1 if and only if for all pairs of strategies σ, τ, every vertex in Gσ,τ has a path to a sink vertex.

In the results that follow, we restrict our discussion to games that halt with probability 1 (Lemma 11.2.2 below shows that this restriction can be applied to the decision problem without loss of generality).

We deﬁne the value of a vertex z ∈ V with respect to a pair of strategies σ, τ, denoted by vσ,τ (z), to be the probability that player 1 will win the game if the start vertex is z and the players use strategies σ and τ.

We say that a vertex xi ∈ X is stable with respect to a pair of strategies σ, τ if vσ,τ (xi ) = max{vσ,τ (z) | (xi, z) ∈ E}. Similarly, we say that a vertex yi ∈ N is stable with respect to a pair of strategies σ, τ if vσ,τ (yi ) = min{vσ,τ (z) | (yi, z) ∈ E}. We say that a vertex is unstable if it is not stable.

Let σ, τ be a pair of strategies for players 1 and 0. The strategy τ is said to be optimal with respect to σ if every min vertex is stable with respect to σ, τ. We will let τ (σ) denote an optimal strategy for player 0 with respect to the player 1 strategy σ. Optimal strategies for player 1 are deﬁned similarly. σ, τ are said to be optimal if each strategy is optimal with respect to the other.

The lemmas below were originally stated for binary SSG’s. Using the polynomial reduction of [ZP96] from SSG’s to binary SSG’s, they are valid also for SSG’s.

** Lemma 11.2.**

1 (Lemma 2 in [Lu95]) Let G = (V, E) be a Simple Stochastic Game that halts with probability 1. Then there is a pair of optimal strategies σ ∗, τ ∗ for players 1 and 0 for the game G.

The value of a SSG G is the value of the start vertex with respect to a pair of optimal strategies for the two players. For every vertex z ∈ V we denote by v(z) the value of the SSG G where the start vertex is z.

** Lemma 11.2.**

2 (Lemma 3 in [Lu95]) Given a Simple Stochastic Game G, we can construct a new game G in time polynomial in the size of G such that G has the same number of min and max vertices as G, the value of G is greater than 2 if and only if the value of G is greater than 1, and G halts with probability 1.

The next two lemmas show that the deﬁnition of “optimal” is suitable in the sense that an optimal strategy for either player optimizes the value of every vertex from that player’s point of view.

** Lemma 11.2.**

3 (Lemma 4 in [Lu95]) Let G = (V, E) be a Simple Stochastic Game that halts with probability 1, and let σ ∗, τ ∗ be a pair of optimal strategies. Then for all z ∈ V,

So all pairs of optimal strategies give the same probability for player 1 to win.

If the game consists only of max and average vertices (i.e., N = ∅) or only of min and average vertices (i.e., X = ∅), then Derman [De72] showed that a linear program can be constructed such that there is a one-to-one correspondence between basic feasible solutions and strategies. However, no such construction is known when the game consists of all three types of vertices. In the next section we will show that an LPtype (Linear Programming-Type) problem can be constructed such that there is a one-to-one correspondence between feasible solutions of the LP-type problem and strategies in the corresponding SSG.

We observe that the condition that H halts with probability 1 ensures the boundness of (1): for each i ∈ V, v(i) ≤ 1. Having the solution of the linear program (11.1) on hand, i.e., the value of the vertices in the graph, we ﬁnd an optimal strategy τ for player 0 in the following way. For every i = 1,..., m, τ (i) = j where (i, j) ∈ E and v(i) = v(j).

In Section 11.3 we use the following lemma for showing that the SSG can be formulated as an LP-type problem.

** Lemma 11.2.**

6 (Adaptation of Lemma 6 in [Lu95]) Let G = (V, E) be a Simple Stochastic Game that halts with probability 1, and let σ be a strategy for player 1 that is not optimal. Let xi ∈ X be a vertex that is unstable with respect to σ, τ (σ). Let σ be a strategy that is obtained from σ by changing the strategy at vertex xi such that ∀j = i, σ (j) = σ(j), (xi, σ (i)) ∈ E and vσ,τ (σ) (σ (i)) = max(xi,z)∈E vσ,τ (σ) (z). Then for all z ∈ V, vσ,τ (σ ) (z) ≥ vσ,τ (σ) (z), and for some z ∈ V, vσ,τ (σ ) (z) vσ,τ (σ) (z).

Proofs of Lemmas 11.2.1, 11.2.2, 11.2.3, 11.2.4 and 11.2.6 can be found in Condon [Co92] (most of these are based on proofs by Shapley [Sh53], Howard [How60] and Derman [De72]). We conclude this section by stating a lemma proved by [Lu95]

11.3 Formulating the SSG as an LP-type problem Let G = (V = X∪N ∪A∪{v0, v1 }, E = S∪D∪AA) be a SSG. For every S ⊆ S with Xi ∩S = ∅, ∀i ∈ {1,..., d} we say that G(S ) = (V, S ∪ D ∪ AA) is a simple stochastic sub-game of G (with respect to edges outgoing from max vertices). We note that every non-sink vertex in G(S ) has at least one outgoing edge. We also note that if G halts with probability 1 then so does G(S ).

Let Λ = I ∪ {∞, −∞} be a set where ∞ (−∞) is a special maximal (minimal) element, respectively.

R Let σ(S ), τ (S ) be an arbitrary pair of optimal strategies in G(S ). Similarly to [Lu95], we deﬁne ω : 2S →Λ in the following way

We note that due to Lemma 11.2.3, ω(S ) is well deﬁned since for any z ∈ V the value of z with respect to any pair of optimal strategies, is the same.

We note that if σ, τ is a pair of strategies in the game G, and since it is not always true that Sσ ⊆ S ;

σ, τ is not necessarily a pair of strategies in G(S ). We also note that if σ, τ is a pair of optimal strategies in G(S ), it is a pair of strategies in G which is not necessarily optimal since the set of possible strategies for player 1 in G contains the one in G(S ) (an example of such G, G(S ), σ and τ can easily be constructed).

We observe that there is a suﬃcient condition that ensures the optimality of σ, τ in G.

Observation 11.3.1 Let G = (X ∪ N ∪ A ∪ {v0, v1 }, S ∪ D ∪ AA) be a Simple Stochastic Game that halts with probability 1. Let G(S ) = (X ∪ N ∪ A ∪ {v0, v1 }, S ∪ D ∪ AA) be a simple stochastic sub-game of G.

Let σ, τ be a pair of optimal strategies in G(S ). If ω(S) = ω(S ) then σ, τ is a pair of optimal strategies also in G.

Proof: We ﬁrst note that since the sets of outgoing edges from min vertices in G and G(S ) are identical (and equal to D), τ is an optimal strategy in G with respect to σ.

We now claim that σ is an optimal strategy in G with respect to τ. Suppose on the contrary that σ is not an optimal strategy in G with respect to τ. By the non-optimality of σ in G there is a vertex xi ∈ X that is unstable with respect to σ, τ. (That is, vσ,τ (xi ) = max(xi,z)∈S vσ,τ (z)). Let σ be a strategy that is obtained from σ by changing the strategy at vertex xi such that ∀j = i, σ (j) = σ(j), (xi, σ (i)) ∈ S and vσ,τ (σ) (σ (i)) = max(xi,z)∈S vσ,τ (σ) (z). Due to Lemma 11.2.6

If σ, τ (σ ) is a pair of optimal strategies in G we get that ω(S) ω(S ) in contradiction. Otherwise let σ ∗, τ ∗ be an arbitrary pair of optimal strategies in G. Let S = {σ : X → V } | ∀xi ∈ X (xi, σ(i)) ∈ S} (T = {τ : N → V } | ∀yi ∈ N (yi, τ (i)) ∈ D}) be the set of strategies for player 1 (player 2) in game G, respectively. By Lemma 11.2.3 we get that for all z ∈ V

Combining (11.4) and (11.5) together implies that vσ∗,τ ∗ (z) ≥ vσ,τ (σ ) (z), so from (11.3) we get again that ω(S) ω(S ) in contradiction.

We are now ready to show ** Lemma 11.3.**

2 A Simple Stochastic Game (V = X ∪N ∪A∪{v0, v1 }, S ∪D ∪AA) that halts with probability 1 is a d-dimensional LP-type problem (S, ω) where ω is as deﬁned in (11.2) and d = |X|.

Proof: Let us consider the abstract problem (S, ω). The aim of player 1 is to maximize his chances to win (i.e., maximize ω). We need to show that the Monotonicity and Locality Conditions are met. Directly from the deﬁnitions of σ(S ), τ (S ) and ω(S ) (S ⊆ S) we get that the Monotonicity Condition is satisﬁed.

(Adding more edges outgoing from vertices of the set X enlarges the set of possible strategies for player 1, and hence increases the probability of player 1 to win).