Pecking Orders and "pecking games"

[Swammerdami]

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]

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.)

-	Scissors	Scissory Paper	Papery Paper	Rocky Paper	Scissory Rock	Papery Rock	Rocky Rock	-
Scissors	0	Scissors cut Paper	Scissors cut Paper	Scissors cut Paper	-1	-1	-1	9 ÷ 35
Scissory Paper	-1	0	Scissory cuts Papery	-1	Paper covers Rock	Paper covers Rock	-1	5 ÷ 35
Papery Paper	-1	-1	0	Papery covers Rocky	Papery Paper covers Rock	Papery Paper covers Rock	Papery Paper covers Rock	7 ÷ 35
Rocky Paper	-1	Rocky crushes Scissory	-1	0	-1	Paper covers Rock	Paper covers Rock	1 ÷ 35
Scissory Rock	Rock crushes Scissors	-1	-1	Scissory cuts Paper	0	Scissory cuts Papery	-1	1 ÷ 35
Papery Rock	Rock crushes Scissors	-1	-1	-1	-1	0	Papery covers Rocky	7 ÷ 35
Rocky Rock	Rock crushes Scissors	Rocky crushes Scissory	-1	-1	Rocky crushes Scissory	-1	0	5 ÷ 35

 

[lpetrich]

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.

 

[Swammerdami]

... 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]

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?

 

[lpetrich]

Let's say that Player 1 (Alice) makes any of several moves and Player 2 (Bob) can make any of those moves. For Alice making move a and Bob making move b, each player's payoff matrix is Wa(b,a) and Wb(b,a).

In this pecking problem, it is easy to show that it is zero-sum: Wb = - Wa and transpose(Wa) = - Wa.

Let's see if it's possible to choose a winning strategy for either player. Let's say that Alice chooses strategies with probabilities Pa(a) and Bob does likewise with probabilities Pb(b). Then Alice gets payoff Pb.Wa.Pa and Bob payoff Pb.Wb.Pa.

Let's find out what's the best strategy. We use the method of Lagrange multipliers: add La*sum(Pa) to Alice's and Lb*sum(Pb) to Bob's, since all these probabilities must add up to 1. Then,

La = Pb.Wa
Lb = Wb.Pa

So the best strategies are given by

Pa = Lb * linearsolve(Wb, 1's)
Pb = La * linearsolve(transpose(Wa), 1's)

where La and Lb are found from normalizing Pa and Pb.

In the zero-sum case, Pa = Pb = L * linearsolve(Wb, 1's) -- the same strategy

For rock-paper-scissors, one find the P's to be (1,1,1)/3.

Adding twine and drops gives (1,1,1,0,0)/3.

 

[lpetrich]

Let's see what happens to the payoff amounts in the zero-sum case with both players using the same strategy.

Alice's is P.Wa.P and Bob's P.Wb.P. Looking at Alice's, put in Wa = - transpose(Wa): - P.transpose(Wa).P = - P.Wa.P. Meaning that Alice gets payoff 0 and Bob does also.

 

[Swammerdami]

In the R,P,S,T,D game It is easy to see that strategy D is dominated by R; then with D excluded, T is dominated by S.

Adding twine and drops gives (1,1,1,0,0)/3.

Are you sure? Yes, the best strategy is 1:1:1:0:0 ÷ 3 ... BUT is that the solution you actually get with ordinary linear algebra?
I think you get 1:3:3:-1:1 ÷ 7 for the game (R,P,S,T,D). Of course choosing T (or any chicken) with a NEGATIVE probability is illegal, but that condition didn't factor into your algebra.

Because negative mixing probabilities are illegal, I don't think you can read out the solution directly with linear equations. First you must find and eliminate the dominated strategies by applying a ("linear programming"?) technique. In this example, two iterations are needed: T is not dominated UNTIL D is eliminated.