On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles

E. Boros, V. Gurvich

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

Let g be an n person positional game with perfect information modelled by a directed graph G=(V,E) which is finite but may have directed cycles. A local cost function f(i,e) is given for every player i∈I and for every move e∈E. The players are allowed only pure stationary strategies, that is the move in any position is deterministic, and may depend only on this present position, not on the preceding positions or moves. In this case the resulting play p is a directed path which begins in the initial position v0 and either (i) ends in a terminal position or (ii) results in a simple directed cycle. Given a play p, for each player i∈I the effective cost f(i,p) is defined as the sum of all local costs along the path f(i,p)=Σ e∈pf(i,e) in case (i), or as f(i,p)=+∞ in case (ii). The local cost function of and the corresponding game is called terminal if f(i,e)=0, unless e is a terminal move. The players wish to minimize their effective costs, in particular they should avoid cycles. A game is called Nash-solvable if it has a Nash equilibrium in pure stationary strategies and properly Nash-solvable if the corresponding play results in a final position, not in a cycle. It is easy to demonstrate that already zero-sum games with two players may not be solvable. However, Nash-solvability turns into an exciting open problem under the following simple additional condition: all local costs are non-negative, that is f(i,e)≥0 for all i∈I and e∈E, or under the seemingly weaker, but in fact equivalent, condition: Σe∈c f(i,e)≥0, for all i∈I and for each simple directed cycle c in G. In all examples, which we were able to analyze, games satisfying are properly Nash-solvable, yet, even the Nash-solvability of such games is an open problem. In this paper we prove proper Nash-solvability for the following special cases: (a) play-once games, that is the games in which every player controls only one position, (b) terminal games with two players, and (c) terminal games with only two terminal moves. We also show that in each of these cases a Nash equilibrium can be constructed in polynomial time in the size of the graph G.

Original languageEnglish (US)
Pages (from-to)207-241
Number of pages35
JournalMathematical social sciences
Volume46
Issue number2
DOIs
StatePublished - Oct 1 2003

All Science Journal Classification (ASJC) codes

  • Social Sciences(all)
  • Psychology(all)
  • Sociology and Political Science
  • Statistics, Probability and Uncertainty

Keywords

  • Backward induction
  • Cycle
  • Cyclic game
  • Directed cycle
  • Directed graph
  • Directed path
  • Effective cost
  • Local cost
  • Nash equilibrium
  • Perfect information
  • Positional game
  • Potentials
  • Pure strategies
  • Saddle point
  • Shortest path
  • Stationary strategies
  • Strong equilibrium

Fingerprint Dive into the research topics of 'On Nash-solvability in pure stationary strategies of finite games with perfect information which may have cycles'. Together they form a unique fingerprint.

  • Cite this