• Welcome to the new Internet Infidels Discussion Board, formerly Talk Freethought.

Pecking Orders and "pecking games"

Swammerdami

Squadron Leader
Staff member
Joined
Dec 16, 2017
Messages
3,286
Location
Land of Smiles
Basic Beliefs
pseudo-deism
Recently I mentioned a "pecking order" in another thread.
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.
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."

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
We will write 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 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:
  1. 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.)
  2. Prove that all contenders must be kings.
  3. Prove that a flock can never have exactly two kings.
  4. Prove that the number of contenders is always odd.
Puzzle 3 may be a fun challenge.
Puzzle 4 is quite difficult (though a terse proof exists for those familiar with game theory and simple linear algebra).
 

Swammerdami

Squadron Leader
Staff member
Joined
Dec 16, 2017
Messages
3,286
Location
Land of Smiles
Basic Beliefs
pseudo-deism
The applause for this thread wasn't deafening, but I'm going to go ahead and make 2 or 3 more posts. First a less trivial Pecking Game than the usual Rock-Paper-Scissors. This game has seven contenders, with the optimal strategy mixture having the ratios 9:5:7:1:1:7:5.

It may be fun to think of mnemonic names for the different strategies. I ended up using prosaic names based on the usual Rock-Paper-Scissors, but not before considering other possibilities, including {Christian,Arab} {Infantry,Cavalry,Artillery} with the 7tn contender, Jesus, ruling the Christians but killed on sight by the Arabs! (I decided this would be too much even on an atheist board.)

-ScissorsScissory PaperPapery PaperRocky PaperScissory RockPapery RockRocky Rock-
Scissors0Scissors cut PaperScissors cut PaperScissors cut Paper-1-1-19 ÷ 35
Scissory Paper-10Scissory cuts Papery-1Paper covers RockPaper covers Rock-15 ÷ 35
Papery Paper-1-10Papery covers RockyPapery Paper covers RockPapery Paper covers RockPapery Paper covers Rock7 ÷ 35
Rocky Paper-1Rocky crushes Scissory-10-1Paper covers RockPaper covers Rock1 ÷ 35
Scissory RockRock crushes Scissors-1-1Scissory cuts Paper0Scissory cuts Papery-11 ÷ 35
Papery RockRock crushes Scissors-1-1-1-10Papery covers Rocky7 ÷ 35
Rocky RockRock crushes ScissorsRocky crushes Scissory-1-1Rocky crushes Scissory-105 ÷ 35
 

lpetrich

Contributor
Joined
Jul 28, 2000
Messages
20,712
Location
Eugene, OR
Gender
Male
Basic Beliefs
Atheist
Sorry for not responding :( I tried to solve these puzzles, but I wasn't very successful.

For the king one about x, if there is some y that violates the first and second conditions, then x < y. But it must satisfy the third condition, x > z > y, meaning that x, y, z form a cycle: x > y > z > x.
 
Last edited:

Swammerdami

Squadron Leader
Staff member
Joined
Dec 16, 2017
Messages
3,286
Location
Land of Smiles
Basic Beliefs
pseudo-deism
... for now I'll just leave you with a few puzzles. In ascending order of difficulty:
  1. 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.)
  2. Prove that all contenders must be kings.
  3. Prove that a flock can never have exactly two kings.
  4. Prove that the number of contenders is always odd.
Puzzle 3 may be a fun challenge.
Puzzle 4 is quite difficult (though a terse proof exists for those familiar with game theory and simple linear algebra).
Puzzle 1 should be straightforward. If you wish, start with prob(R) = prob(P) = prob(S) = 1/3 and see if it makes sense to add T and/or D to the strategy mix.
For Puzzle 2, one way to proceed is to come up with an equivalent definition for Not-a-King ("x is Not a King if there exists y ...") and then show that y is always a better pick than x for the pecking game. (Also convenient to prove is the fact that every non-null Flock has at least one King. Also note that any subset of a flock is itself a flock.)

Puzzle 3 is VERY nifty in my opinion! There is an easy-to-prove Lemma which leads directly to an easy proof of #3. But proving #3 may be difficult until you guess what that Lemma is.

Puzzle 4 may be too difficult for non-specialists. It was 55 years ago that I was introduced to game matrixes, "saddle points" and the Minimax Theorem. The math professor I mentioned earlier said that my own proof was the most elegant proof of #4 he'd ever seen. I think it was the only time in my life I ever explicitly used determinants (not counting implicit use invoking Numerical Recipes).

Sorry for not responding :( I tried to solve these puzzles, but I wasn't very successful.

For the king one about x, if there is some y that violates the first and second conditions, then x < y. But it must satisfy the third condition, x > z > y, meaning that x, y, z form a cycle: x > y > z > x.
Yes, puzzles 2 and 3 come down to simple observations about x,y,z.
 

Swammerdami

Squadron Leader
Staff member
Joined
Dec 16, 2017
Messages
3,286
Location
Land of Smiles
Basic Beliefs
pseudo-deism
In post #2 I show a Pecking Game with seven contenders. The right-most column shows the probability that contender should be selected for the optimal (or "guaranteeing") saddle-point mixed strategy.

Deriving those optimal probabilities can be very tedious if done by hand, but I've already done that and show them in the table. Do you see how to confirm quickly that those probabilities are the correct ones?
 
Top Bottom