The number line game

Riddler puzzle from August 17, 2018 — Solution by Laurent Lessard (using JuliaPro 0.6.2.1)

Ariel, Beatrice and Cassandra — three brilliant game theorists — were bored at a game theory conference (shocking, we know) and devised the following game to pass the time. They drew a number line and placed \$1 on the 1, \$2 on the 2, \$3 on the 3 and so on to \$10 on the 10.

Each player has a personalized token. They take turns — Ariel first, Beatrice second and Cassandra third — placing their tokens on one of the money stacks (only one token is allowed per space). Once the tokens are all placed, each player gets to take every stack that her token is on or is closest to. If a stack is midway between two tokens, the players split that cash.

How will this game play out? How much is it worth to go first?

A grab bag of extra credits: What if the game were played not on a number line but on a clock, with values of \$1 to \$12? What if Desdemona, Eleanor and so on joined the original game? What if the tokens could be placed anywhere on the number line, not just the stacks?

To change the problem data, modify the block immediately below and run all remaining blocks. This code allows you to change:

  • Ni: number of stacks of money. The default is Ni=10
  • M : number of players in the game.
  • periodic : whether the numbers wrap around or not as in the clock bonus question
  • Nbetween : number of inter-stack slots. Default is zero. If larger, this allows tokens to be placed in between stacks as a proxy for the continuous problem.
In [64]:
# PROBLEM DATA

Ni = 10   # number of integer spots (number line is 1:Ni)
M  = 3    # number of players (players play in the order 1,2,...,M)

periodic = false    # whether the numbers wrap around or not (as in numbers on a clock)
Nbetween = 0        # number of slots between each token (set to zero for standard problem)
;
In [65]:
# HELPER FUNCTIONS

using Combinatorics

# change actual N based on whether we're inserting extra slots between numbers or not
if periodic
    N = Nbetween*Ni + Ni
else
    N = Nbetween*(Ni-1) + Ni
end

# function for computing everybody's score given the locations of the tokens (which should be distinct)
function get_score_sorted(t)
    eps = 1e-4
    s = zeros(length(t)) # vector that stores the scores
    if periodic
        tnew = t/(Nbetween+1)
    else
        tnew = (t-1)/(Nbetween+1)+1
    end
    for i = 1:Ni
        if periodic
            d = min.( abs.(tnew-i), Ni-abs.(tnew-i) )  # distance function for periodic problem (clock)
        else
            d = abs.(tnew-i) # vector of distances for (1-10) problem
        end
        q = sortperm(d)
        if length(q)==1 || d[q[1]] + eps < d[q[2]]
            s[q[1]] += i
        else
            s[q[1]] += i/2 # if tied, split the winnings
            s[q[2]] += i/2
        end
    end
    s
end

# tabulate scores for every strategy (only tabulate for sorted inputs)
sorted_strategies = combinations(1:N,M)
sorted_scores = Dict()
for strat in sorted_strategies
    sorted_scores[strat] = get_score_sorted(strat)
end

# function that returns the score of any strategy (even unsorted)
function get_score(strat)
    p = sortperm(strat)
    mm = length(p)
    pp = eye(Int,mm)[p,:]'*(1:mm)  # inverse permutation
    x = get( sorted_scores, sort(strat), zeros(M) )
    x[pp]
end

# retun all indices for the max value of an array of any size
function argmaxes(A)
    dims = size(A)
    optval = maximum(A)
    optix = find(A .== optval)
    ixxs = []
    for ix in optix
        push!(ixxs, ind2sub(dims,ix))
    end
    ixxs
end
;
In [66]:
# COMPUTE OPTIMAL STRATEGIES ITERATIVELY

# given what players 1,...,k-1 have played (sorted), nash_strats is a Dict of
# all possible nash-optimal moves for players k,k+1,...,M.
nash_strats = Array{Any}(M)
for k = 1:M
    nash_strats[k] = Dict()
end

# nash strategies for the last player
deviation_scores = zeros(N)
for strat in combinations(1:N,M-1)   # possible strategies for first M-1 players
    dx = Nbetween+1
    for i = 1:N
        deviation_scores[i] = get_score([strat...,i])[M]
    end
    ixxs = argmaxes(deviation_scores)   # get all the nash optimal points
    nash_strats[M][strat] = ixxs
end

# nash strategies for the rest of the players iteratively
for k = M-1:-1:1
    deviation_scores = zeros(N)
    for strat in combinations(1:N,k-1)    # possible strategies for first M-2 players
        dx = Nbetween+1
        for i = 1:N
            ixxs = get(nash_strats[k+1], sort([strat...,i]), zeros(k))
            deviation_scores[i] = get_score([strat...,i,ixxs[1]...])[k]
        end
        jxxs = argmaxes(deviation_scores)    # get all nash optimal points
        nash_strats[k][strat] = []
        for jx in jxxs
            cstrat = sort([strat...,jx...])
            ixxs = nash_strats[k+1][cstrat]
            for ixx in ixxs
                append!(nash_strats[k][strat], [[jx...,ixx...]])
            end
        end
    end
end
In [67]:
# PRINT OUT OPTIMAL MOVE SEQUENCES

println("Nash-optimoal strategies and corresponding payouts:")
for s in nash_strats[1][Int[]]
    if periodic
        snew = s/(Nbetween+1)
    else
        snew = (s-1)/(Nbetween+1)+1
    end
    if Nbetween==0
        snew = convert(Array{Int,1},snew)
    end
    println(snew, " ↦ ", get_score(s))
end
Nash-optimoal strategies and corresponding payouts:
[5, 9, 8] ↦ [21.0, 19.0, 15.0]
In [ ]: