On strategy improvement algorithms for simple stochastic games

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n²/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(²0.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

Formulating an <Emphasis Type="Italic">n</Emphasis>-person noncooperative game as a tensor complementarity problem

In this paper, we consider a class of n-person noncooperative games, where the utility function of every player is given by a homogeneous polynomial defined by the payoff tensor of that player, which is a natural extension of the bimatrix game where the utility function of every player is given by a quadratic form defined by the payoff matrix of that player. We will call such a problem the multilinear game. We reformulate the multilinear game as a tensor complementarity problem, a generalization of the linear complementarity problem; and show that finding a Nash equilibrium point of the multilinear game is equivalent to finding a solution of the resulted tensor complementarity problem. Especially, we present an explicit relationship between the solutions of the multilinear game and the tensor complementarity problem, which builds a bridge between these two classes of problems. We also apply a smoothing-type algorithm to solve the resulted tensor complementarity problem and give some preliminary numerical results for solving the multilinear games.     

A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph.We identify a new “controlled” version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP∩CONP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shortest paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity , which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).     

Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian

We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm is given for the problem of finding a Hamiltonian cycle in graphs with bounded spectral gaps which has complexity of order n ^{cln n} .     

Hitting time results for Maker‐Breaker games

We study Maker‐Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \begin{align*}\mathcal{P}\end{align*}. We focus on three natural target properties for Maker's graph, namely being k ‐vertex‐connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k ‐vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojakovi? and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Stationary equilibria in cyclic games: Search and structure

The existence of optimal stationary strategies for a cyclic game played on the vertices of a bipartite graph up to the first cycle with the payoff of one player to the other equaling the sum of the maximal and minimal local payoffs on this cycle is proved. This result implies that the problem belongs to the class NP ∩ co-NP; -a polynomial algorithm that yields optimal strategies for ergodic extensions of matrix games is given. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 913–921, June, 2000.     

Computing solutions for matching games

A matching game is a cooperative game (N, v) defined on a graph G = (N, E) with an edge weighting w: E? \mathbb R₊{w: E\to {\mathbb R}_+}. The player set is N and the value of a coalition S í N{S \subseteq N} is defined as the maximum weight of a matching in the subgraph induced by S. First we present an O(nm + n ² log n) algorithm that tests if the core of a matching game defined on a weighted graph with n vertices and m edges is nonempty and that computes a core member if the core is nonempty. This algorithm improves previous work based on the ellipsoid method and can also be used to compute stable solutions for instances of the stable roommates problem with payments. Second we show that the nucleolus of an n-player matching game with a nonempty core can be computed in O(n ⁴) time. This generalizes the corresponding result of Solymosi and Raghavan for assignment games. Third we prove that is NP-hard to determine an imputation with minimum number of blocking pairs, even for matching games with unit edge weights, whereas the problem of determining an imputation with minimum total blocking value is shown to be polynomial-time solvable for general matching games.     

Quitting games – An example

Quitting games are multi-player sequential games in which, at every stage, each player has the choice between continuing and quitting. The game ends as soon as at least one player chooses to quit; each player i then receives a payoff r _S ⁱ, which depends on the set S of players that did choose to quit. If the game never ends, the payoff to each player is zero.? We exhibit a four-player quitting game, where the “simplest” equilibrium is periodic with period two. We argue that this implies that all known methods to prove existence of an equilibrium payoff in multi-player stochastic games are therefore bound to fail in general, and provide some geometric intuition for this phenomenon. Received: October 2001     

An efficient algorithm to solve connectivity problem on trapezoid graphs

The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs withn vertices andm edges takesO(K(G)mn ^1.5) time, whereK(G) is the vertex connectivity ofG. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takesO(n ²) time andO(n) space for a trapezoid graph.     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems

In this paper we present an algorithm for finding a Nash equilibrium in a noncooperative normal formN-person game. More generally, the algorithm can be applied for solving a nonlinear stationary point problem on a simplotope, being the Cartesian product of several simplices. The algorithm solves the problem by solving a sequence of linear stationary point problems. Each problem in the sequence is solved in a finite number of iterations. Although the overall convergence cannot be proved, the method performs rather well. Computational results suggest that this algorithm performs at least as good as simplicial algorithms do.For the special case of a bi-matrix game (N=2), the algorithm has an appealing game-theoretic interpretation. In that case, the problem is linear and the algorithm always finds a solution. Furthermore, the equilibrium found in a bi-matrix game is perfect whenever the algorithm starts from a strategy vector at which all actions are played with positive probability.This research is part of the VF-program Co-operation and Competition, which has been approved by the Netherlands Ministery of Education and Sciences.     

Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph

We describe an O((log n)²) time parallel algorithm, using n processors, for finding the lexicographically first depth first search tree in the random graph G _{n, p}, with p fixed. The problem itself is complete for P, and so is unlikely to be efficiently parallelizable always.     

Membrane Computing to Enhance Time Efficiency of Minimum Dominating Set

Graph theory is widely used in numerous fields, such as, engineering, physics, social and biological sciences; linguistics etc. The minimum dominating set (MDS) problem is one of the main problems of algorithmic graph theory and has numerous applications especially in graph mining. Since it is NP-hard to solve the MDS problem approximately, much work has been dedicated to central and distributed approximation algorithms for restricted graph classes. In recent research exponential time \(O(k^{n})\) algorithms are used for some graph classes for solving the MDS problem. In the approach of using the algorithmic tile self-assembly model, the MDS problem has been solved in \(O(n^{2})\) steps. On the other hand, in the area of membrane computing, P systems introduce two levels of parallelism: every membrane works concurrently with other membranes,and, rules are applied in parallel in each membrane. This paper introduces an algorithm based on the parallelism feature of the P systems model for solving the MDS problem in linear time O(n).     

On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems

Various special motion-planning problems involving arbitrarily many degrees of freedom are shown to admit relatively simple solutions by techniques based on the connectivity graph approach described by Schwartz and Sharir. The solutions exploit the particularly simple configuration space structure of the robot systems considered. A typical problem is that of planning motions for a 2-dimensional robot system consisting of several arms all jointed at one common endpoint and free to rotate past each other. The algorithm given for solving this problem runs in time O(n^k+4), where k is the number of arms.     

An algorithm for finding the nucleolus of assignment games

Assignment games with side payments are models of certain two-sided markets. It is known that prices which competitively balance supply and demand correspond to elements in the core. The nucleolus, lying in the lexicographic center of the nonempty core, has the additional property that it satisfies each coalition as much as possible. The corresponding prices favor neither the sellers nor the buyers, hence provide some stability for the market. An algorithm is presented that determines the nucleolus of an assignment game. It generates a finite number of payoff vectors, monotone increasing on one side, and decreasing on the other. The decomposition of the payoff space and the lattice-type structure of the feasible set are utilized in associating a directed graph. Finding the next payoff is translated into determining the lengths of longest paths to the nodes, if the graph is acyclic, or otherwise, detecting the cycle(s). In an (m,n)-person assignment game withm = min(m,n) the nucleolus is found in at most 1/2·m(m + 3) steps, each one requiring at mostO(m·n) elementary operations.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

The existence theorem of absolute equilibrium about games on connected graph with state payoff vecto

By introducing state payoff vector to every state node on the connected graph in this paper, dynamic game is researched on finite graphs. The concept of simple strategy about games on graph defined by Berge is introduced to prove the existence theorem of absolute equilibrium about games on the connected graph with state payoff vector. The complete algorithm and an example in the three-dimensional connected mesh-like graph are given in this paper.     

Polytope Games

Starting from the definition of a bimatrix game, we restrict the pair of strategy sets jointly, not independently. Thus, we have a set , which is the set of all feasible strategy pairs. We pose the question of whether a Nash equilibrium exists, in that no player can obtain a higher payoff by deviating. We answer this question affirmatively for a very general case, imposing a minimum of conditions on the restricted sets and the payoff. Next, we concentrate on a special class of restricted games, the polytope bimatrix game, where the restrictions are linear and the payoff functions are bilinear. Further, we show how the polytope bimatrix game is a generalization of the bimatrix game. We give an algorithm for solving such a polytope bimatrix game; finally, we discuss refinements to the equilibrium point concept where we generalize results from the theory of bimatrix games.