Plans regarding socalled "simple graph games".
More...
Go to the source code of this file.
Detailed Description
Plans regarding socalled "simple graph games".
 Todo:
 Connections
 Todo:
 The general setting

Here "simple graph games", abbreviated "sigrga", are defined.

Input is a directed graph with loops G = [V,E], where the vertices are natural numbers, together with a map P(v), which assigns to every vertex v in V the number 0 or 1 (for "player 0" resp. "player 1").

It is assumed furthermore that the outdegree of every vertex is at least 1.

So for input I = [G,P] validity of the input is determined by the following predicate:
sigrga_p(I) := if not listp(I) or not length(I) = 2 then false else
block([G : I[1], V, P : I[2]],
if not dgl_p(G) then false else (
V : G[1],
every_s(lambda([v], integerp(v) and is(v >= 1) and elementp(P(v), {0,1})),
V) and
min_vertex_outdegree_dgl(G) >= 1
)
)$

A "game" is a sequence g = (v_n)_{n in NN} of vertices describing a path in G; the "repeated vertices" are those vertices which occur infinitely often in g, and the "winner" of g is the player i in {0,1} such that for the minimum repeated vertex v (using that vertices are natural numbers) it holds P(v) = i.

A game g is "played" in such a way that for a given start vertex v_1 the vertices v_2, ..., v_i, ... are chosen by player P(v_{i1}).

A "memoryless strategy" is a map s which assigns to every vertex v one of its outneigbhours.

Every vertex v yields now a game g_s(v) := v, s(v), s(s(v)), ..., and as such is qualified as winning for player 0 or player 1.

So w.r.t. s we have a map W_s(v), which assigns to every vertex v the player in {0,1} winning the game g_s(v).

W_s is computable by considering G restricted to the choices of s, where now every vertex has outdegree 1, and which is thus a functional graph (representing a transformation of V), where each (weakly) connected component has the structure of one (directed) cycle with additional paths leading to it. The owner of the minimal vertex on such a cycle is the winner of all the nodes of the connected component.

And given W_s, we can derive a strategy s_W (with W_s = W_{s_W}) by choosing for each node v with W(v) = P(v) a node also won by P(v), while otherwise we make an arbitrary choice.

There exists now an optimal strategy s_opt, characterised by the condition that for every vertex v as start, any alteration of s_opt w.r.t. the moves by player 1W_{s_opt}(v) (the "looser") do not change the outcome of the game (player W_{s_opt}(v) always wins).

All these optimal strategies coincide in their determination of which player wins any vertex, and so we have a unique winnerdetermination W_opt(v) in {0,1} for v in V.

So for given input [[V,E], P] the output is either an optimal strategy s_opt (a map from V to V), or the winner determination W_opt (a map from V to {0,1}).
 Todo:
 Implementing the recursive algorithm according to [AB, Moller]

According to [Beckmann, Moller].

Input is a sigrga [G,P], output the winner determination.
Definition in file SimpleGraphGames.hpp.