Wednesday, January 13, 2010

Symmetric Games?

While working on one of my submissions for FUN over break, I tried to use a definition I was certain was a standard part of CGT. Much to my surprise, I couldn't find the term "symmetric game" in any current literature.

Google was able to find the term under standard "economic" game theory. The Wikipedia definition I found is almost precisely what I was looking for:

In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric.

Instead of "payoff" however, we are comparing which strategy resulted in the game ending. Thus, if we switch which player uses which strategy, (and also swap which player goes first) then the player whose move ends the game should also switch.

More formally, in combniatorial game theory, we can say that a game G is symmetric if G = -G. (-G is recursively defined as: {-R | -L} where G = {L | R}.)

Is this already a known property for some games? Is this definition already named something else?

Where does this definition come into place? For many combinatorial games, the starting situation has this property. At the beginning of a game of Hex, for example, strategies for either side are equivalent. Both players have the same options for moves from that starting position: each child for the Red player is equivalent to the negative of a child for the Blue player.

Somehow, somewhere, this must already be defined! Please tell me where!

4 comments:

  1. Aren't Nimbers their own additive inverses?

    ReplyDelete
  2. If you also require that all followers of G are symmetric, you will get exactly all impartial games (which are in turn equivalent to the nimbers *n).

    If you do not require that followers are symmetric, like Hex, then we can construct an infinite family of symmetric games by taking any game G and forming H = {G|-G}.

    For cases where G is partizan, I'm not sure these have a name, but symmetric seems appropriate.

    ReplyDelete
  3. Rev. Slaughter,

    yes, and thus every impartial game is already symmetric.

    ReplyDelete
  4. A short game G such that G=-G is said to have order 2, because 2.G=0. All short games of finite order have even order, such as {0,^*|*,v}, which has order 4, as two copies of it equal *.

    ReplyDelete