Random Zero-Sum Dynamic Games on Infinite Directed Graphs

Area of Science:

• Game Theory
• Probability Theory
• Graph Theory

Background:

• Two-player zero-sum dynamic games with perfect information are analyzed.
• Games are played on infinite directed graphs with vertex-assigned payoffs.
• Payoffs are distributed i.i.d. (independently and identically distributed) across vertices.

Purpose of the Study:

• To investigate the convergence of game values in random dynamic games.
• To analyze convergence rates on different classes of infinite directed graphs.
• To understand the impact of graph structure and game duration on game values.

Main Methods:

• Consideration of random two-player zero-sum dynamic games with perfect information.
• Analysis on classes of infinite directed graphs, including acyclic graphs and the infinite d-ary tree.
• Asymptotic analysis of game values as the duration of the game tends to infinity.

Main Results:

• For acyclic directed graphs with bounded degree and sub-exponential expansion, game values converge almost surely to a constant at an exponential rate.
• For the infinite d-ary tree, convergence of game values is shown to occur at a double-exponential rate.
• The convergence rate is dominated by the expansion properties of the graph.

Conclusions:

• The structure of the infinite directed graph significantly influences the convergence rate of game values.
• Exponential convergence is observed in graphs with controlled expansion, while faster double-exponential convergence occurs in the infinite d-ary tree.
• These findings provide insights into the asymptotic behavior of random dynamic games on complex graph structures.