Deterministic Graphical Games.

Abstract

This paper gives a simple algorithm for solving a class of graphical games where infinite play is possible. A Deterministic Graphical (DG) game is a two person zero sum game played on a directed graph with n > o nodes. Nodes are of two kinds: terminal and continuing. Terminal nodes are those with no successors, and have a payoff to player 1 associated with them. Continuing nodes have at least one successor, and are labelled to indicate which player chooses the successor. Play begins at some specified node, and continues until a terminal node is reached. If no terminal node is ever reached, the payoff is by convention O. The author's main intention in this paper is to describe an algorithm for solving DG games in o(n cubed) steps.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1986
Accession Number
ADA168045

Entities

People

  • Alan R. Washburn

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Classification
  • Computations
  • Game Theory
  • Guarantees
  • Information Science
  • Mathematics
  • New York
  • Notation
  • Operations Research
  • Polynomials
  • Schools
  • Technical Information Centers
  • Terminals
  • United Kingdom
  • Universities

Readers

  • Game Theory.
  • Graph Algorithms and Convex Optimization.
  • International Relations and Conflict Resolution