Broadcast slices

[Brandon Taylor]

Is there a way to slice two or more arrays along the same dimension, broadcast a function over the slices, then put the results back together again along the sliced dimension? Essentially, broadcast_slices?

[Steven G. Johnson]

At some point, it is simpler to just write loops than to try and express a complicated operation in terms of higher-order functions like broadcast.

[Brandon Taylor]

I guess, but I'm trying to write a generic program where I don't know the size of the array? I'm trying to find Nash Equilibrium for an n dimensional array, where the player strategies are along dimensions 1:n-1, and the players are along dimension n. So:

equals_max(x) = x .== maximum(x)

best_response_dimension(payoff_matrix, dimension) =
    mapslices(equals_max, payoff_matrix, dimension)

I'd want to do something like this:

player_dimension = ndims(payoff_matrix)
other_dimensions = repeat([1], inner = player_dimension - 1)
number_of_players = size(payoff_matrix)[player_dimension]


players = reshape(1:number_of_players, other_dimensions..., number_of_players)

broadcast_slices(best_response_dimension, payoff_matrix, players)

[Brandon Taylor]

Or I guess that should be

broadcast_slices(best_response_dimension, player_dimension, payoff_matrix, players)

[Dan]

Have you found the right implementation?

Fiddling a bit, I tend to agree with Steven G. Johnson `for` loops would be the most efficient and probably the most understandable implementation.

Also, would it not be easier to have the first index in the `payoff_matrix` determine which player's payoff are we using?

Finally, following is an implementation using `mapslices` which seems to work:

nplayers = last(size(payoff_matrix));

bestresponse = cat(nplayers+1,(mapslices(x->fill(indmax(x),size(payoff_matrix,i)), payoff_matrix[fill(:,nplayers)...,i],i) for i=1:nplayers)...)

The `bestresponse` array is the same shape as `payoff_matrix`, with each entry in `bestresponse[..,..,..,..,i]` denoting the strategy number which is a best response to the others choices for player `i` (chosen in the last index). The other player's strategies are determined by all the `..,...,..` indices before, with the choice of player `i` immaterial (since a single best response is chosen by the `indmax` function.

This is a good exercise, perhaps another question on Stackoverflow would yield interesting variations.   

[Brandon Taylor]

For now, I have an array of arrays. 1 payoff array for each player. The arrays can be zipped to get the strategy profiles. It seems to work, but having everything in 1 array just seems so much more neat. Which is why I was looking for a neat implementation of broadcast_slices to match.

[Dan]

OK. So, to get the array to have the first dim as the player selector, you can go:

cat(1,map(x->reshape(1,size(x)),array_of_arrays)

Anyway, keeping with the same payoff_matrix as before, I realized you might just want a boolean array which is true if entry is a best response (for the appropriate player according to last dim). It is the same flavor of my previous one-liner, with `maximum` replacing `indmax` and a `.==`:

isbr = payoff_matrix .== cat(nplayers+1,(mapslices(x->fill(maximum(x),size(payoff_matrix,i)), payoff_matrix[fill(:,nplayers)...,i],i) for i=1:nplayers)...)

Anyway, gotta go now. Have a good one.

[Dan]

Oops, that `cat` code was supposed to be:

cat(1,map(x->reshape(x,1,size(x)...),array_of_array)...)

Mew!

[Brandon Taylor]

Cool! The implementation I have is:

equals_max(x) = x .== maximum(x)

best_response_dimension(payoff_matrix, dimension) =
    mapslices(equals_max, payoff_matrix, dimension)

is_nash_equilibrium(payoffs) = @chain begin
    payoffs
    broadcast(best_response_dimension, _, 1:length(_) )
    zip(_...)
    map(all, _)
end

[Dan]

Nice.

It is easier when the payoffs are in vector form. My last iteration:

is_nash_equilibrium(po) = !reduce(|,falses(po[1]),(broadcast(<,po[i],mapslices(maximum,po[i],i)) for i=1:length(po)))

A one-liner :)

[Davide Lasagna]

Hi Brandon, 

you might find some inspiration from this package.

Davide

[Steven G. Johnson]

On Saturday, September 24, 2016 at 9:38:55 PM UTC-4, Brandon Taylor wrote:

I guess, but I'm trying to write a generic program where I don't know the size of the array? I'm trying to find Nash Equilibrium for an n dimensional array, where the player strategies are along dimensions 1:n-1, and the players are along dimension n.

See http://julialang.org/blog/2016/02/iteration