Swammerdami
Squadron Leader
Recently I mentioned a "pecking order" in another thread.
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:
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
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 Rock, Paper and Scissors; 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 Twine which binds Paper, and a Drop_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:
Puzzle 4 is quite difficult (though a terse proof exists for those familiar with game theory and simple linear algebra).
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
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 Rock, Paper and Scissors; 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 Twine which binds Paper, and a Drop_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).