WWW.THESIS.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Thesis, documentation, books
 
<< HOME
CONTACTS



Pages:     | 1 |   ...   | 17 | 18 || 20 | 21 |   ...   | 27 |

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

-- [ Page 19 ] --

Condon [Co92] was the first 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 effort (see [EJS93], [Lu95], [ZP96], [Sei96], [BCJLM97], [J00] and [BSV03a]). Some exponential algorithms for SSG’s are described in √ [MC90]. The first 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 first 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 different. They first 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 first 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 Payoff Games (MPG’s), and Discounted Payoff 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 definition 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 specific games they solved, we use only one unifying algorithm for all of these five games - the LP-type algorithm of [SW92].

11.2 Definitions and previous results In this section we review the definitions and the results known about SSG’s and review the definitions of Parity Games, Mean Payoff Games, and Discounted Payoff Games.

11.2.1 Simple Stochastic Games Although this section is self contained, it is strongly based upon the first 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 define 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 define 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 defined 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 definition 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 find 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 define ω : 2S →Λ in the following way

–  –  –

We note that due to Lemma 11.2.3, ω(S ) is well defined 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 sufficient 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 first 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 defined 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 definitions of σ(S ), τ (S ) and ω(S ) (S ⊆ S) we get that the Monotonicity Condition is satisfied.

(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).



Pages:     | 1 |   ...   | 17 | 18 || 20 | 21 |   ...   | 27 |


Similar works:

«Reason and Intuition* Charles Parsons In this paper I will approach the subject of intuition from a different angle from what has been usual in the philosophy of mathematics, by beginning with some descriptive remarks about Reason and observing that something that has been called intuition arises naturally in that context. These considerations are quite general, not specific to mathematics. The conception of intuition might be called that of rational intuition; indeed the conception is a much...»

«Causation and Culpability 1 Causation, Norm Violation and Culpable Control [forthcoming in the Journal of Philosophy] Mark D. Alicke Ohio University David Rose Carnegie Mellon University Dori Bloom Ohio University Causation and Culpability 2 Acknowledgements We would like to thank Josh Knobe, Chandra Sripada and Liane Young for their helpful comments on an earlier draft of this paper. We would also like to thank David Danks for his very helpful discussions. Causation and Culpability 3...»

«THE USE OF NEAR INFRARED SPECTROSCOPY (NIRS) TO DETERMINE THE VENTILATORY THRESHOLD AND THE RELATION BETWEEN SKELETAL MUSCLE OXYGENATION AND RPE by Kathryn Anne Tessmer Bachelor of Arts, Blackburn College, 2000 Masters of Science in Education, Southern Illinois University at Carbondale, 2002 Submitted to the Graduate Faculty of the School of Education in partial fulfillment of the requirements for the degree of Doctor of Philosophy University of Pittsburgh UNIVERSITY OF PITTSBURGH SCHOOL OF...»

«Name /oxc04/23973_u02 11/22/04 01:38PM Plate # 0-Composite pg 27 # 3 “Thou Shall Not Freeze-Frame” or How Not to Misunderstand the Science and Religion Debate Bruno Latour I have no authority whatsoever to talk to you1 about religion and experience because I am neither a predicator, nor a theologian, nor a philosopher of religion—nor even an especially pious person. Fortunately, religion might not be about authority and strength, but exploration, hesitation, and weakness. If so, then I...»

«High-throughput Experimental and Computational Studies of Bacterial Evolution Lars Barquist Queens’ College University of Cambridge A thesis submitted for the degree of Doctor of Philosophy 23 August 2013 Arrakis teaches the attitude of the knife – chopping off what’s incomplete and saying: “Now it’s complete because it’s ended here.” Collected Sayings of Muad’dib Declaration High-throughput Experimental and Computational Studies of Bacterial Evolution The work presented in...»

«SYNTHETIC AND MECHANISTIC INVESTIGATIONS OF A DIRUTHENIUM-CATALYZED C–H AMINATION REACTION A DISSERTATION SUBMITTED TO THE DEPARTMENT OF CHEMISTRY AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Mark Edwin Harvey December 2013 © 2014 by Mark Harvey. All Rights Reserved. Re-distributed by Stanford University under license with the author. This dissertation is online at:...»

«Diplomarbeit Titel der Diplomarbeit „Entstehung und Struktur des créole réunionnais im Fokus kreolistischer Theorien und Analysen“ Verfasserin Carina Auzinger angestrebter akademischer Grad Magistra der Philosophie (Mag. phil.) Wien, 2012 Studienkennzahl lt. Studienblatt: A 328 Studienrichtung lt. Studienblatt: Diplomstudium Allgem./Angew. Sprachwissenschaft (Stzw) Betreuer: Ao. Univ.-Prof. Dr. John Rennison Inhaltsverzeichnis Einleitung 1. Entwicklung der Kreolistik 1.1. Anfänge der...»

«THE PRINCIPLES OF SENTENCING VIOLENT OFFENDERS: TOWARDS A MORE STRUCTURED APPROACH Ivan Potas 1 Research Director Judicial Commission of New South Wales IN ORDER TO ACHIEVE CONSISTENCY OF APPROACH IN SENTENCING, IT IS desirable to have a structure or theoretical framework in which that objective can be promoted. However, there are many competing philosophies and many judicial officers from diverse backgrounds, with differing attitudes, and this task of achieving consistency of approach is not a...»

«Textual Community and Linguistic Distance in Early England by Emily Elisabeth Butler A thesis submitted in conformity with the requirements for the degree of Doctor of Philosophy Centre for Medieval Studies University of Toronto © Copyright by Emily Elisabeth Butler 2010 Textual Community and Linguistic Distance in Early England Emily Elisabeth Butler Doctor of Philosophy Centre for Medieval Studies University of Toronto Abstract This dissertation examines the function of textual communities...»

«Demonstrative Induction and the Skeleton of Inference P.D. Magnus October 9, 2008 This is the final author’s draft of a paper forthcoming in International Studies in the Philosophy of Science. Earlier versions were posted on the author’s website fecundity.com under the title ‘Eliminating Induction’, first in December 2005. P.D. Magnus is at the Department of Philosophy, University at Albany. Abstract It has been common wisdom for centuries that scientific inference cannot be...»

«Piracy, Globalization and Marginal Identities: Navigating Gender and Nationality in Contemporary Hispanic Fiction by Alana B. Reid A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Romance Language and Literature Spanish) in The University of Michigan Doctoral Committee: Professor Alejandro Herrero-Olaizola, Chair Associate Professor Jarrod L. Hayes Associate Professor Cristina Moreiras-Menor Assistant Professor Lawrence M. La...»

«Genetic Modification and Effector Functions of Natural Killer Cells in Acute Myeloid Leukemia Inauguraldissertation zur Erlangung der Würde eines Doktors der Philosophie vorgelegt der Philosophisch-Naturwissenschaftlichen Fakultät der Universität Basel von Uwe Siegler aus Schopfheim-Wiechs, Deutschland Basel, 2006 Genehmigt von der Philosophisch-Naturwissenschaftlichen Fakultät auf Antrag von Prof. Dr. phil. Niklaus Weiss Prof. Dr. phil. Aleksandra Wodnar-Filipowicz Prof. Dr. Antonius G....»





 
<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.