(Generalised Consensus Game Sample Clauses

(Generalised Consensus Game. Consider the tuple given by 7GC = ⟨G, X, T, Γ, φ, β, ψ, σ, A⟩ to be the set of rules of a Flag Coordination Game played in a (non-dynamic) graph G = (V, E), where X = {x0, . . . , x|Γ|−1}. Also, Γ = {γ0, γ1, . . . , γ|Γ|−1}, such that, for a given pair (v, x), where v ∈ V and x ∈ X, there exists exactly one γ ∈ Γ with γ(v) = x. We define β(v) = X and ψ(v, t) = 0 for all v ∈ V and all t ∈ T. For undirected graphs, the visibility φ(v, t) of each vertex v is, for any t ∈ T, the set of neighbours of v, denoted by N (v). For directed graphs, φ(v, t) = v+ := {u | (v, u) ∈ E}. Finally, for each v, the algorithm αv consists in choosing on round t a neighbour of v according to some probability function,ii say u, then observing which γ ∈ Γ is the one such that γ(u) = St(u). We then define the value St+1(v) = γ(v). The algorithm above is well defined because, for each pair (v, x), where x = s(v), there is only one goal configuration in which v takes colour x. We use the term generalised consensus because, assuming the nodes know where they are and which other nodes they can see, they adhere to the winning configuration that the ran- domly chosen neighbour belongs to. In particular, if for a given k, 0 ≤ k < |Γ|, γk(v) = xk, ∀v ∈ V , then we have a consensus problem in the usual way. Either in usual consensus problems or in anti-consensus problems in bipartite graphs, the ∈ iRecall (Definition 2.4.2) that G is a bipartite graph with partitions V1 and V2, denoted by G = (V1, V2, E), if V1 ∪ V2 = V , V1 ∩ V2 = ∅ and ∀(u, v) ∈ E, either u ∈ V1 and v ∈ V2 or v ∈ V1 and u V2. iiThat may possibly depend on the current colours of v and its neighbours. assumption that nodes know their place (and of their neighbours) in the network can be lifted. Example 3.2.2 (Generalised Consensus Game). Consider a generalised con- sensus game played in G = C4 and such that X = { , , } with the set of goal configurations given by