Beauty and the Geek Game Theory: Answering the Freakonomics Challenge

In the August 15, 2008 Freakonomics Blog entry, guest author Alon Nir poses the question of determining the best strategy for the game Beauty and the Geek, as seen on TV. Roughly, the rules of Nir's version of the game is as follows:

Nir poses the question of what is the best strategy for the team with strength 2. But to answer that question we have to determine the best strategy for the other teams as well. We assume that each team has at least one rational player, so all teams will use near-rational strategies (although not perfectly rational, since the exact computation is difficult). Nir hypothesizes that revenge may be important: if one team sends you to the elimination round, you may be inclined to send them later, should you get the chance. But we can't assume that teams will choose revenge; most of all they want to optimize their chance of winning.

To answer the question, I first built a simulator that plays the game, given the strategies for each player. Rather than compute exact probabilities, I used simulation over 10,000 games to estimate the probabilities of winning under each compbination of strategies. That means I had to enumerate some possible strategies. I chose eight:

Results

Below we will see the output of my program, in the form of a game matrix. This is tricky because there are 7 players (teams) in the game, but under the assumption that players are rational, we can assume that all players of the same strength use the same strategy (since there is nothing to distinguish them). That leaves us with only three distinct teams, the strong, weak, and medium. The game matrix below shows strong/weak strategy as the label for each row on the left, and medium strategy as the label for each column on top. Each entry shows the percentage chance of winning for strong/weak/medium. An earlier version of this table was incorrect, because of a bug in my code spotted by Rob Shearer, an Oxford researcher working on description logics (demonstrating once again the value of code reviews in general and of making code open source so that many eyes can catch errors). We can observe the following:
  1. There are no dominant strategies. That is, there is no strategy that works best regardless of what the other players do.
  2. There are a few dominated strategies: strategies that do not work as well as another strategy on any combination of other players strategies. For example, for the medium player (the focus of Nir's question), the strategy BOTH is dominated (there are no stars next to it), and thus should not be played.
  3. The strong players do best when they play weak or WEAK, getting 30 to 32% wins in those cases, and only 17 to 28% when they play another strategy.
  4. Assuming the strong players use i>weak or WEAK, the medium player will win 4 to 8% of the time. It looks like medium has the best chance by playing strong or STRONG.
  5. The poor weak players will only get 0 to 1% of the wins; it looks like they should play strong or STRONG, but that won't help much.
  6. Revenge does not seem to be a major factor.

Here is the output from my program:

TABLE OF PERCENTAGE OF WINS FOR BEAUTY AND THE GEEK PLAYERS.
Strategy for player "me" on X axis.
Strategy for Strong/Weak players on Y axis.
Strategies say who the player will target.
UPPERCASE letters means take revenge first.

Consider the second row, labelled random/RANDOM, and the final column,
labelled BOTH. It has value 27/3/10, where the first number, 27, is
the expected percentage of wins for a strong player, the second, 3,
for weak, and the third, 10, for the medium player (me), assuming
that the strong players target "random" players, the weak players
target "RANDOM" and takes revenge when possible (that is what the
"random/RANDOM" second row header means) and the me player targets "BOTH" 
and seeks revenge when possible (that is what the "BOTH" column header means). 
Numbers do not sum to 100% because there are multiple strong and weak players.
A star after a player's score means that this is the best strategy for that
player, given the other two player's strategies.

              | random        RANDOM        strong        STRONG        weak          WEAK          both          BOTH         
random/random | 28/2/9        28/2/9        27/3/10       27/3/10*      29/2/9        29/2/8        27/3/10       27/3/9       
random/RANDOM | 28/2/9        28/2/9        27/3/10       26/3/11*      29/2/8        28/2/9        27/3/9        27/3/10      
random/strong | 26/3/11       26/4/11       25/5*/12      25/5*/11      28/3/10       27/3/10       25/4*/12*     25/4*/11     
random/STRONG | 26/3/10       26/4*/11      25/4/12*      25/5/12       28/3*/9       27/3*/10      25/4/11       25/4/12      
random/weak   | 29/2/8        29/2/8        28/2/10*      28/2/9        30/1/7        29/1/8        29/2/9        28/2/9       
random/WEAK   | 29/2/8        29/2/9        28/2/9        28/2/10       30/1/8        29/1/8        28/2/10*      28/2/9       
random/both   | 26/3*/11      26/3/11       25/4/11       25/5/12       28/2/10       27/3/10       25/4/12*      26/4/11      
random/BOTH   | 26/3/11       27/3/11       25/4/12       25/4/12*      28/2/10       28/3/10       25/4/11       25/4/11      
RANDOM/random | 27/3/10       27/3/10       26/4/9        26/4/10       28/2/10       28/2/10*      27/4/9        27/4/9       
RANDOM/RANDOM | 27/3/10       27/3/10       26/4/9        26/4/10*      28/2/10       28/2/9        26/4/10       27/4/9       
RANDOM/strong | 26/4*/12      25/4/12       24/5*/11      24/5*/12      26/3*/12*     27/3/12       24/5*/11      25/5/11      
RANDOM/STRONG | 26/4/12       25/4*/11      24/5/11       24/5/11       27/3/11       26/3/12*      25/5/11       25/5*/11     
RANDOM/weak   | 28/2/9        28/2/9        27/3/9        27/3/9        28/2/9*       29/2/9        28/3/9        28/3/9       
RANDOM/WEAK   | 28/2/9        28/3/9        27/3/9        27/3/9        28/2/10*      28/2/9        28/3/9        28/3/9       
RANDOM/both   | 26/4/12       26/4/11       24/5/11       24/5/12       27/3/12       26/3*/12*     25/5/11       25/5/11      
RANDOM/BOTH   | 26/4/11       26/4/12       25/5/11       25/5/11       27/3/12       26/3/12*      25/5/11       25/5/11      

strong/random | 22/8/11       21/8/12       20/9/12       20/9/11       23/6/12       23/7/12*      20/9/12       20/9/12      
strong/RANDOM | 22/8/12       22/8/11       20/9/12       20/9/12       23/6/12*      22/7/11       20/9/12       20/9/11      
strong/strong | 18/12*/12     17/12*/12     16/14*/10     16/14/11      19/10*/13*    19/11*/12     16/14*/10     16/13*/11    
strong/STRONG | 18/11/12      18/12/11      16/13/11      16/14*/10     20/9/13       19/10/13*     16/14/10      16/13/11     
strong/weak   | 24/5/13       23/6/14       22/7/14       22/7/15       25/4/14       24/5/15*      22/7/14       22/7/15      
strong/WEAK   | 24/6/13       23/6/14       22/7/14       22/7/14       25/4/13       24/5/13       21/7/15*      21/7/15      
strong/both   | 18/11/12      18/12/12      16/13/11      16/13/11      19/10/13*     19/10/13      16/13/11      16/13/11     
strong/BOTH   | 18/11/12      18/11/12      16/13/11      16/13/11      20/9/13       19/10/13*     16/13/11      17/13/11     
STRONG/random | 22/7/12       22/8/12       21/9/12       21/9/11       23/6/13*      23/7/12       20/9/11       21/9/11      
STRONG/RANDOM | 22/7/12       22/8/11       20/9/11       20/9/12       23/6/12       23/7/12*      21/9/11       21/9/12      
STRONG/strong | 18/11*/13     18/11*/13     17/12/12      17/13/12      20/8*/15      19/9/15*      17/13/11      17/12/12     
STRONG/STRONG | 19/10/13      18/10/14      17/13*/12     17/13*/12     20/8/15*      19/9*/14      17/13*/11     17/13*/12    
STRONG/weak   | 24/5/12       24/5/13       22/7/14*      22/7/13       25/4/14       24/5/14       22/7/13       22/7/13      
STRONG/WEAK   | 24/5/12       23/6/12       22/7/13       22/7/13       25/4/13       24/5/14*      22/7/13       22/7/13      
STRONG/both   | 19/10/14      18/10/14      17/12/12      17/13/12      20/8/15       19/9/15*      17/12/13      17/12/12     
STRONG/BOTH   | 19/10/13      18/10/14      17/12/13      17/12/13      20/8/15*      20/9/14       17/12/13      17/12/12     

weak  /random | 31/0/5        32*/0/5       31*/0/6       31/0/6*       32/0/4        32*/0/4       31/0/6        31*/0/5      
weak  /RANDOM | 31/0/5        31/0/5        31/0/6*       31*/0/6       32/0/4        32/0/4        31/0/6        31/0/6       
weak  /strong | 31/0*/7       31/1*/7       30/1/8        30/1*/8*      32*/0*/5      31*/0*/5      30/1/8        30/1*/8      
weak  /STRONG | 31/0/7        31/0/7        30/1*/8       30/1*/8*      32*/0/5       32*/0/5       30*/1*/7      30/1/8       
weak  /weak   | 32/0/4        32*/0/4       32/0/5*       32*/0/4       32/0/3        32/0/3        32/0/4        32/0/4       
weak  /WEAK   | 32*/0/4       32/0/4        31/0/6        31/0/6*       32/0/4        32*/0/3       31/0/5        32/0/5       
weak  /both   | 31*/0/6       31*/0/6       30/1/8*       30/1/8        32*/0/4       32/0/5        30*/1/7       30/1/7       
weak  /BOTH   | 31/0/6        31/0/6        30/1/8        30/1/8*       32*/0/4       31/0/5        30/1/8        30/1/8       
WEAK  /random | 32*/0/4       32/0/4        31/1/5*       31*/1/5       32*/0/3       32/0/4        31*/0/5       31/1/5       
WEAK  /RANDOM | 31*/0/5       31*/0/5       31*/1/5       31/1/6*       32*/0/4       32*/0/4       31*/1/5       31*/1/5      
WEAK  /strong | 31*/1/6       31*/1*/6      30*/1/7       30*/1/7*      31/0/5        31/0*/5       30*/1/7       30*/1*/7     
WEAK  /STRONG | 31*/1*/6      31*/1/6       30*/1*/7      30*/1*/7*     31/0*/5       31/0/5        30/1*/7       30*/1/7      
WEAK  /weak   | 32*/0/4       32/0/4        32*/0/4*      32/0/4        32*/0/3       32*/0/3       32*/0/4       32*/0/4      
WEAK  /WEAK   | 32/0/5        32*/0/4       31*/0/5       31*/0/5*      32*/0/3       32/0/4        32*/0/4       32*/0/5      
WEAK  /both   | 31/1/6        31/1/6        30*/1/7       30*/1/7*      32/0/4        32*/0/5       30/1/6        30*/1/6      
WEAK  /BOTH   | 31*/0/6       31*/0/6       30*/1/7*      30*/1/6       32/0/5        32*/0/4       30*/1/7       30*/1/7      

both  /random | 22/6/16       22/6/16       20/9/14       20/8/15       23/5/16       23/5/17*      20/8/14       20/8/15      
both  /RANDOM | 22/6/16       21/7/16       20/8/15       20/8/15       23/5/17*      23/5/17       20/9/15       20/8/15      
both  /strong | 18/10*/16     18/10/16      16/13*/13     16/12*/14     20/7*/18*     19/8/18       16/12/14      16/12/14     
both  /STRONG | 19/9/16       18/10*/15     16/13/13      16/12/14      20/7/17*      20/8*/16      16/12*/14     16/13*/14    
both  /weak   | 23/4/18       23/4/18       21/6/19       21/6/18       24/3/19*      24/3/19       21/6/18       22/6/18      
both  /WEAK   | 23/4/18       22/5/18       21/6/19       21/6/19       24/3/19*      24/3/19       21/6/18       22/6/18      
both  /both   | 19/9/16       18/10/16      16/12/14      16/12/13      20/7/18*      20/8/18       16/12/14      16/12/14     
both  /BOTH   | 18/9/17       19/10/16      16/12/15      16/12/15      20/7/18*      20/8/17       17/12/15      16/12/14     
BOTH  /random | 22/6/15       22/6/16       21/8/14       20/8/15       24/4/17       23/5/17*      21/8/14       21/8/14      
BOTH  /RANDOM | 22/6/15       22/6/15       20/8/14       21/8/14       23/4/17*      23/5/17       21/8/14       21/8/15      
BOTH  /strong | 19/9*/18      19/8/18       17/11*/16     17/11/16      20/6*/21*     20/7*/21      17/11/15      17/11/16     
BOTH  /STRONG | 19/8/18       19/9*/18      17/11/16      17/11*/16     21/6/19       20/6/20*      17/11*/15     17/11*/16    
BOTH  /weak   | 24/4/16       23/4/17       22/6/17       22/6/16       25/2/19*      24/3/19       22/6/17       22/6/16      
BOTH  /WEAK   | 24/4/16       23/5/18       22/6/16       22/6/16       25/3/19       24/3/19*      22/6/16       22/6/17      
BOTH  /both   | 19/8/19       19/8/18       17/11/16      17/11/17      21/6/20*      20/6/20       17/11/16      17/11/16     
BOTH  /BOTH   | 19/8/19       19/8/17       17/11/16      17/11/16      21/6/20*      21/6/19       18/10/17      17/11/16     

Checking dominance...
Dominance checks done.

Additional Commentary

Rob Shearer makes an interesting point: would it be advantageous for one of the strong players to deviate from the weak strategy, attacking the other strongs instead? My program limits each strong player to having the same strategy (on the grounds that each is equally rational and has the same information, thus should come to the same conclusion). But my program does not account for a level of meta-reasoning: once the strong players have concluded what their strategy should be, should they then use that information to switch to a different strategy? Not surprisingly, the answer is yes. Here is a table of estimated win percentage when player strong1 switches to the strong strategy:

Strong1 defects; others use revenge.
25.8 strong1   strong_strategy
21.6 strong3   WEAK_STRATEGY
21.5 strong2   WEAK_STRATEGY
14.4 me        STRONG_STRATEGY
5.6  weak1     STRONG_STRATEGY
5.6  weak2     STRONG_STRATEGY
5.4  weak3     STRONG_STRATEGY

We see that player strong1 does indeed gain an advantage over strong2 and strong3 --- but overall strong1 loses ground, going from the 30 to 32% with the weak strategy down to 26%. The beneficiaries of this change in tactics are the weak players. So there is no prisoner's dilemma here: there is no incentive for any of the strong players to defect.

But recall that we were uncertain whether players should use the revenge strategy or not. The results above assume the other players are using revenge. What if they don't?

Strong1 defects, others do not use revenge.
31.8 strong1   strong_strategy
21.2 strong3   weak_strategy
20.8 strong2   weak_strategy
13.9 me        strong_strategy
4.3  weak1     strong_strategy
4.0  weak2     strong_strategy
3.9  weak3     strong_strategy

Now it is less clear; does 31.8% represent a gain for strong1 or not? It is certainly close; let's run a simulation where each player uses the near-equilibrium strategies that we uncovered above, with and without revenge:

The near equilibrium strategy combination with revenge.
30.4 strong2   WEAK_STRATEGY
29.9 strong1   WEAK_STRATEGY
28.9 strong3   WEAK_STRATEGY
7.4  me        STRONG_STRATEGY
1.2  weak3     STRONG_STRATEGY
1.2  weak1     STRONG_STRATEGY
1.1  weak2     STRONG_STRATEGY

The near equilibrium strategy combination without revenge.
30.4 strong2   weak_strategy
29.6 strong1   weak_strategy
29.4 strong3   weak_strategy
8.2  me        strong_strategy
0.9  weak1     strong_strategy
0.8  weak3     strong_strategy
0.8  weak2     strong_strategy

It looks like it is a little better for strong1 to defect if the others are not using revenge, but it is not clear-cut.

Program

Here is the program that generated the matrix and the results inspired by Shearer:
"""Functions to decide the best strategy for the game Beauty and the Geek,
as defined by the Freakonomics Blog, August 15, 2008."""

import random
from collections import defaultdict

################ Strategy functions:

## A strategy function returns a player chosen to send to elimination.
## It takes as input five parameters:
##   me: the player doing this pick
##   other: the player making the other pick (might be me)
##   prev_choice: who the other player picked, or None if not picked yet
##   revenge: revenge[P] is the list of players that chose P for elimination
##   players: the players left in the game

def random_strategy(me, other, prev_choice, revenge, players):
    "Pick a player at random"
    candidates = [P for P in players if P is not me and P is not prev_choice]
    return random.choice(candidates)

def strong_strategy(me, other, prev_choice, revenge, players):
    "Pick one of the strongest players"
    candidates = [P for P in players if P is not me and P is not prev_choice]
    strongest = max(strengths[P] for P in candidates)
    return random.choice([P for P in candidates if strengths[P]==strongest])

def weak_strategy(me, other, prev_choice, revenge, players):
    "Pick one of the weakest players"
    candidates = [P for P in players if P is not me and P is not prev_choice]
    weakest = min(strengths[P] for P in candidates)
    return random.choice([P for P in candidates if strengths[P]==weakest])

def both_strategy(me, other, prev_choice, revenge, players):
    "Pick strong, except when given two choices pick 1 strong, 1 weak."
    if me == other and prev_choice is not None:
        return weak_strategy(me, other, prev_choice, revenge, players)
    else:
        return strong_strategy(me, other, prev_choice, revenge, players)

def revenge_meta_strategy(strategy):
    def s(me, other, prev_choice, revenge, players):
        return strategy(me, other, prev_choice, revenge,
                        ([P for P in revenge[me] if P is not prev_choice and P in players]
                         or players))
    s.func_name = strategy.func_name.upper()
    return s

################ Playing the Game

## strengths maps from player name to his relative probability to win an e contest
strengths = dict(weak1=1,weak2=1,weak3=1, strong1=4,strong2=4,strong3=4, me=2)
## players is the list of player names
players   = strengths.keys()
## strategies maps from a player name to a strategy
strategies = defaultdict(lambda: random_strategy)

def game(players=players, strategies=strategies, verbose=False):
    "Eliminate one by one until 2 players left, then find winner among the two."
    players = players[:] ## Make a copy
    revenge = defaultdict(list)
    while len(players) >  2:
         C1, C2 = winner(players), winner(players)
         if verbose: print C1, C2, 'win challenges'
         E1 = strategies[C1](C1, C2, None, revenge, players)
         E2 = strategies[C2](C2, C1, E1, revenge, players)
         revenge[E1].append(C1)
         revenge[E2].append(C2)
         if verbose: print E1, E2, 'chosen;\n  revenge:', dict(revenge)
         loser = E1 if winner([E1, E2]) is E2 else E2
         players.remove(loser)
         if verbose: print loser, 'eliminated,', players, 'remain'
    return winner(players)

def winner(players):
    "Who wins an contest from a pool of players."
    return random.choice([p for p in players for _ in range(strengths[p])])

def games(players, N, strategies):
    "Report on a series of N games with fixed strategies."
    results = defaultdict(int)
    for _ in range(N):
        results[game(players, strategies)] += 100./N
    for (n, p) in reversed(sorted((n, p) for (p, n) in results.items())):
        print '%-4.1f %-9s %s' % (n, p, strategies[p].func_name)

WEAK = revenge_meta_strategy(weak_strategy)
STRONG = revenge_meta_strategy(strong_strategy)

def near_equilibrium1(N=10000):
    print '\nThe near equilibrium strategy combination with revenge.'
    games(players, N, dict(strong1=WEAK, strong2=WEAK, strong3=WEAK, me=STRONG,
                           weak1=STRONG, weak2=STRONG, weak3=STRONG))

def near_equilibrium2(N=10000):
    print '\nThe near equilibrium strategy combination without revenge.'
    games(players, N, dict(strong1=weak_strategy, strong2=weak_strategy, 
                           strong3=weak_strategy, me=strong_strategy,
                           weak1=strong_strategy, weak2=strong_strategy, 
                           weak3=strong_strategy))
def shearer1(N=10000):
    print '\nStrong1 defects; others use revenge.'
    games(players, N, dict(strong1=strong_strategy, strong2=WEAK, strong3=WEAK, me=STRONG,
                           weak1=STRONG, weak2=STRONG, weak3=STRONG))

def shearer2(N=10000):
    print '\nStrong1 defects, others do not use revenge.'
    games(players, N, dict(strong1=strong_strategy, strong2=weak_strategy, 
                           strong3=weak_strategy, me=strong_strategy,
                           weak1=strong_strategy, weak2=strong_strategy, 
                           weak3=strong_strategy))


################ Charting the Results

def tournament(players, strategies, N):
    "Return a dict of percentage of winning for each player strength."
    results = defaultdict(int)
    for _ in range(N):
        winner = game(players, strategies)
        split_between = sum(strengths[p]==strengths[winner] for p in players)
        results[strengths[winner]] += (100.0/N)/split_between
    return results

def table(players, N=10000, base_strategies=
          [random_strategy, strong_strategy, weak_strategy, both_strategy]):
    "Compute and print matrix of probabilities of winning."
    all_strat = []
    for s in base_strategies:
        all_strat.extend([s, revenge_meta_strategy(s)])
    ## Compute results
    results = {}             
    for strong_s in all_strat:
        for weak_s in all_strat:
            for me_s in all_strat:
                d = {4:strong_s, 2:me_s, 1:weak_s}
                strategies = dict((p, d[strengths[p]]) for p in players)
                results[strong_s, weak_s, me_s] = tournament(players, strategies, N)

    ## Print results as a table
    def label(strategy): 
        return '%-6s'%strategy.func_name.split('_')[0]
    def resultstring(s, w, m): 
        d = results[s, w, m]
        max_s = max(results[ss, w, m][4] for ss in all_strat)
        max_w = max(results[s, ww, m][1] for ww in all_strat)
        max_m = max(results[s, w, mm][2] for mm in all_strat)
        def component(i, maxi):
            return '%d%s' % (round(d[i]), ('*' if d[i]==maxi else ''))
        return '%s/%s/%s' % (component(4, max_s), component(1, max_w), component(2, max_m))
    print 'TABLE OF PERCENTAGE OF WINS FOR BEAUTY AND THE GEEK PLAYERS.'
    print 'Strategy for player "me" on X axis.'
    print 'Strategy for Strong/Weak players on Y axis.'
    print 'Strategies say who the player will target.'
    print 'UPPERCASE letters means take revenge first.'
    print
    S, W, M = all_strat[0], all_strat[1], all_strat[-1]
    r = results[S,W,M]
    rs = resultstring(S, W, M)
    print 'Consider the second row, labelled random/RANDOM, and the final column,'
    print 'labelled BOTH. It has value %s, where the first number, %d, is' % (rs, r[4])
    print 'the expected percentage of wins for a strong player, the second, %d,'%r[1]
    print 'for weak, and the third, %d, for the medium player (me), assuming' % r[2]
    print 'that the strong players target "random" players, the weak players'
    print 'target "RANDOM" and takes revenge when possible (that is what the'
    print '"random/RANDOM" second row header means) and the me player targets "BOTH" '
    print 'and seeks revenge when possible (that is what the "BOTH" column header means). '
    print 'Numbers do not sum to 100% because there are multiple strong and weak players.'
    print 'A star after a player\'s score means that this is the best strategy for that'
    print 'player, given the other two player\'s strategies.'
    print
    print ' '*13, '|', ' '.join([('%-13s'%label(m)) for m in all_strat])
    # s,w,m range over all strategies for strong,weak,me players
    for s in all_strat:
        for w in all_strat:
            print '%s/%s |' % (label(s), label(w)),
            for m in all_strat:
                print '%-13s' % resultstring(s, w, m),
            print
    ## See if any strategies are dominant.
    ## A strategy s is dominant for player p if, for all possible strategies by 
    ## the other players, there is no better strategy for p.
    others = [(s2, s3) for s2 in all_strat for s3 in all_strat]
    print
    print 'Checking dominance...'
    def dominance(strategy, i, name):
        'Strategy %s is dominant for player %s (%d)!' % (label(strategy), name, i)
    for s in all_strat:
        if all(results[s, s2, s3][4] >= results[s1, s2, s3][4] for s1 in all_strat):
            dominance(s, 4, 'strong')
        if all(results[s2, s, s3][1] >= results[s2, s1, s3][1] for s1 in all_strat):
            dominance(s, 1, 'weak')
        if all(results[s2, s3, s][2] >= results[s2, s3, s1][2] for s1 in all_strat):
            dominance(s, 2, 'me')
    print 'Dominance checks done.'

################ Output
            
table(players)
near_equilibrium1()
near_equilibrium2()
shearer1()
shearer2()



Peter Norvig