Pecking orders are extremely simple, yet lead to interesting theorems. They are relevant to the theories of tournaments, whether round-robin or elimination, but I will relate them only to "pecking games."The Rock < Paper < Scissors (< Rock) game is an example of such a 3-cycle in a pecking-order graph. A famous military analog is pikemen > horse_riders > archers > pikemen which becomes light_infantry > motorized_infantry > artillery > light_infantry in a modern context.

I'll introduce the topic by speaking of "chickens," "pecking" and "flocks" but please treat these as purely mathematical abstractions.

Given chickens

*x*and

*y*, exactly one of the following holds:

*x = y**x pecks y**y pecks x*

*x>y*(or

*y<x*) to denote

*x pecks y*.

A

__flock__is a set of chickens.

The chicken

*x in flock F*is a

__king__in

*F*if and only if

*for all y in F*, at least one of the following holds

*x = y**x pecks y**there exists a chicken z in F such that x pecks z and z pecks y*

I now describe a

*pecking game*. Given a flock F and two players — Alice and Bob — who each know the pecking orders in the flock, each player picks a chicken, writing its name in secret. At a signal the players reveal their choices; the player whose chicken pecks the other player's chicken wins the prize (e.g. the last piece of chocolate in the case where Alice and Bob are children). The game is drawn if both players pick the same chicken.

In the classic pecking game, the flock has size three; the chickens are named

__R__ock,

__P__aper and

__S__cissors; and the pecking orders are

*S>P, P>R, R>S*. There is one and only one strategy guaranteed to (at least) break even in the long run. That strategy will be to pick R, P and S each with probability 33.3%. The game is symmetric so Alice and Bob each have the same guaranteeing strategy. (I won't call it the "optimal" strategy since it does NOT win on average. To win you will need to guess your opponent's strategy and risk losing if outguessed.)

Since the

__guaranteeing strategy__requires choosing among R, P and S, each with some non-zero probability, we will say that R, P and S are

__contenders__.

Let's add two more chickens and bring the flock size up to five. Chickens R, P, S are as before, but we also have

__T__wine which binds Paper, and a

__D__rop_of_Rain which loses to all other chickens except Scissors which it ruins with rust. The pecking orders are

*R>S,T,D ; P>R,D ; S>P,T ; T>P,D ; D>S*

I may post more later, but for now I'll just leave you with a few puzzles. In ascending order of difficulty:

- What is the guaranteeing strategy in the pecking game on {R, P, S, T, D} with the orders just described? Which chickens are contenders? (A chicken is a
__contender__if chosen with non-zero probability in the guaranteeing strategy.) Which chickens are kings?

(The remaining puzzles require proofs valid for all flocks.) - Prove that all contenders must be kings.
- Prove that a flock can never have exactly two kings.
- Prove that the number of contenders is always odd.

Puzzle 4 is quite difficult (though a terse proof exists for those familiar with game theory and simple linear algebra).