1
$\begingroup$

I am working on a game theory assignment where a game $G$ is played on a graph. Let $G = (V,E)$ where $V$ is a set of all vertices and $E$ a set of all edges connecting said vertices. Two players Adam and Eve take alternating turns moving from vertex to vertex along the existing edges. More information about the game exists but is not relavant for my question.

An infinite play $P$ is won by Eve if some position (a vertex that they moved to) repeats infinitely often, otherwise Adam is the winner. I want to write this condition down as formally as I can and I came up with the following

$$\forall p\in V, \sum_{i \in P:i=p}^\infty 1 = \infty$$

Is this a valid notation? Is there a better/more efficient/more easily understandable way of writing the winning condition?

Forgive me if I got the formatting wrong, this is my first time posting anything math related on any stack exchange community.

$\endgroup$
  • $\begingroup$ You would need to formalise the notion of position and make sense of phrases infinitely often and eventually. Your proposed condition is incomprehensible as it is. $\endgroup$ – Alvin Lepik Sep 7 '19 at 11:52
  • $\begingroup$ @AlvinLepik Thanks for the feedback, a position is a vertex that is part of the play. In other words, they moved to or from that vertex at some point during their play. Infinitely often in this case means that the number of times that the position occurs in the play is equal to infinity. $\endgroup$ – yarwest Sep 7 '19 at 12:08
  • 1
    $\begingroup$ It seems like you want to say $\exists p$ instead of $\forall p$. As it is, it says that every position occurs infinitely often. $\endgroup$ – saulspatz Sep 7 '19 at 13:48
  • $\begingroup$ @saulspatz you're right, I suppose I was more looking at as a for each loop logic, but that does make sense. $\endgroup$ – yarwest Sep 7 '19 at 13:54
  • 2
    $\begingroup$ "Formally" is not the same thing as "without using words". If you say "An infinite play is won by Eve if some position repeats infinitely often, otherwise Adam is the winner", that's formal. "If you say $\exists \sum p \sum i \mathbin{\forall} \infty$" or whatever, that's shorthand. You would use it if you're trying to state the condition as concisely as possible. $\endgroup$ – Misha Lavrov Sep 7 '19 at 14:00
1
$\begingroup$

The first thing you should do is to give a formal definition of a play. It could be defined as a sequence $(v_n)_{n \geqslant 0}$ of vertices of your graph such that, for each $n$, $(v_n, v_{n+1})$ is an edge of the graph. Thus a play is just an infinite path $p = v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \dotsm\ $ in the graph. You can now define $$ \text{Inf}(p) = \{v \in V \mid v \text{ occurs infinitely often in the sequence $(v_n)_{n \geqslant 0}$} \} $$ Now your winning condition is usually expressed as a condition on $\text{Inf}(p)$.

$\endgroup$
  • $\begingroup$ Really nice answer, very clear and seems to cover all bases. $\endgroup$ – yarwest Sep 11 '19 at 11:10
  • $\begingroup$ you're welcome. $\endgroup$ – J.-E. Pin Sep 11 '19 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.