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=10M
: number of players in the game.periodic
: whether the numbers wrap around or not as in the clock bonus questionNbetween
: 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.# 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)
;
# 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
;
# 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
# 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]