Dominated Options

In combinatorial game theory, a dominated option in an abstract game ``G`` is one of its options that may be removed without altering the value of ``G``, because some other option for the same player is at least as appealing to them.

This may be used to simplify a game as in:

`` {cancel color (DarkRed) 3, 4|-5, cancel color (DarkRed) (-4)} = {4|-5} ``

Table of contents Motivation By Charles Matthews By Tom Applications See also Notes Discussion

Motivation

By Charles Matthews

In CGT, making a 'move' is always conceived of as choosing between options (also called followers).

If a player has a dominated option, that means the same as a move without any possible motivation.^[1][4] In practical terms, 'why would you ever play that way?'

This comes down to the ordering of games: if `` G >= H `` ^[2] then under all possible circumstances one of the players (Left) will choose ``G`` rather than ``H``, whenever offered the choice;^[1] and the other (Right) naturally will choose ``H`` rather than ``G``.

The games may be numbers, in which case we are saying Left always prefers higher numbers, Right always lower numbers.

Therefore playing in a dominated option corresponds to what Go players would call 'taking an unconditional loss', measured against best play.^[1]

([99]) If two of the options are equal as games, then each makes the other a dominated option. In practical terms this means that you can remove one or the other from consideration.

Charles Matthews

By Tom

Tom: Another explanation.

A game ``G`` is a set `` {{:G^L:}_1,{:G^L:}_2,...} `` of left options (to which Left may move) and a set of `` {{:G^R:}_1,{:G^R:}_2,...} `` of right options (to which Right may move). Each of these options are games in their own rights. If ``{:G^L:}_1 >= {:G^L:}2 `` ^[2] (informally: Left prefers ``{:G^L:}_1`` ^[3]) then ``{:G^L:}_2`` is said to be a dominated option. Similarly, if `` {:G^R:}_1 >= {:G^R:}_2 `` then ``{:G^R:}_1`` is a dominated option.

This definition is useful because it has been proved that dominated options can be deleted without changing the value of the game. This accords with common sense, you would never^[1] make a move that, even locally, has a superior alternative. It follows that the game would have the same winner if the inferior move were not available.

Applications

Any game can be reduced to canonical form by repeatedly using:

• this process of deleting dominated options and
• eliding reversible options.

Games in canonical form are equal if they have the same options, up to equality of games.

See also

• Reversible options — another way to simplify games: options that can be replaced with the replies to one of the opponent’s replies

Notes

[1] Not so, as the inequality is not strict; see ^[2] and Charles’s last paragraph (^[99]).

[2] Note the loose inequality: “no better” rather than “worse”. This is as defined in ONAG (2001) page 110 and Winning Ways (2001) page 62.

This means that dominated options are those which may be removed, rather than those that should be removed. One might also consider defining strictly dominated with a strict inequality, but that may be a less useful concept.

Note that ``G <= H`` does not mean exactly “``G`` is no better for Left than ``H``”, but “Left can win `` G - H `` when playing second”.

[3] Actually, the player may be indifferent about which option to play.

[4] Note that games are only partially ordered. For instance, we cannot say that {5 | -2} is greater than or less than {4 | 0}. OC, they are not equal.

Discussion

Patrick Traill: Is the converse also true: if an option may be deleted without changing the value of a game, is it no better than some other?

¿ `` { G, H, cdots | K, cdots } = { H, cdots | K, cdots } => G <= H `` for some ``H in G^L`` ?