bimatrix_generators

[oyamad]

We have got a permission from the corresponding author of the paper "An Empirical Study of Finding Approximate Equilibria in Bimatrix Games" to include the classes of games studied there into our libraries Games.jl and quantecon.game_theory. The associated C code is now distributed under BSD3 license.

• [x] Colonel Blotto Games
• [x] Ranking Games
• [x] SGC Games
• [x] Tournament Games
• [x] Unit vector Games

[oyamad]

Work in the bimatrix-generators branch.

[shizejin]

Decide the option name for unit_vector_game:

1. allow_pure_nash
2. not_avoid_pure_nash
3. uniform_random
4. uniformly_random

[shizejin]

After some modifications, now unit_vector_game runs about 3 times faster than the version we discussed in the morning, and uses less than a half of allocation comparatively.

In details:

julia> for i in 1:3
           @time unit_vector_game(10, random=false)
       end
  0.000055 seconds (90 allocations: 9.156 KiB)
  0.000032 seconds (91 allocations: 9.203 KiB)
  0.000030 seconds (91 allocations: 9.203 KiB)

@oyamad

[oyamad]

Very good.

How does the C code handle the case where Player 2 has a dominant action?

[shizejin]

They choose row uniformly randomly, and return a game with pure Nash Equilibrium. here

[oyamad]

Will you open an issue at bimatrix-generators pointing out this possibility and asking whether it is what they did in their paper? (Note that such a case occurs with positive probability.)

[oyamad]

I propose to use n for the number of actions (in a symmetric game).

[oyamad]

@QBatista Question about the C code for ranking_game:

What is create_rand_score doing?

• The argument start is not used.
• When i=0, s[i-1] refers to the memory block before s?

[QBatista]

The purpose of this function is to create a step-wise, strictly increasing score function for each player. My understanding is that s[i-1] with i=0 indeed refers to the memory block before s but that it is somehow always equal to 0. I wasn't able to find a theoretical explanation, but running the following code a few time always outputs the value 0 for s[-1]:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a;
    int *b = malloc(3 * sizeof(int));
    printf("\n a=%p \t b=%p  \n",a,b);
    printf("%d", b[-1]);
}

Under this assumption, the code outputs the intended result. I don't think start serves any purpose here -- I am not sure why it is in the code.

[oyamad]

@QBatista Thanks for the explanation! Strictly speaking, I guess there is a possibility that *b points to the very first address of the memory, in which case the "memory block before b" does not exist.

Maybe the following was meant?

int *create_rand_score(int k, int start, int steps)
{
    int i;
    int *s = malloc(k * sizeof(int));

    s[0] = start;
    for (i = 1; i < k; ++i)
        s[i] = s[i-1]+ ((randint(steps) ) + 1);

    return s;
}

[oyamad]

If that's the case, these lines would mean that player 2 always wins if both players choose the first action (zero cost effort), and also player 2 is more likely to win on average (for the equal level of effort).

[QBatista]

I did not find any mention of this feature in the original paper or in the referenced paper, so I would guess that what was meant is:

int *create_rand_score(int k,  int steps)
{
    int i;
    int *s = malloc(k * sizeof(int));

    s[0] = (randint(steps) ) + 1;
    for (i = 1; i < k; ++i)
        s[i] = s[i-1]+ ((randint(steps) ) + 1);

    return s;
}

[oyamad]

@shizejin I took over your job on blotto_game: see https://github.com/oyamad/QuantEcon.py/commit/a6e1616e7fde0061c22121aa1ec5365cbc300fec.

Performance of this code (with 2002 actions):

h, T = 10, 5
rho = 0.5

%timeit gt.blotto_game(h, T, rho)

237 ms ± 26.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

@QBatista

• It seems that routines from QuantEcon have to be explicitly imported: see 070b0268f0003e1a22a107cb8374ddc4290dd175.

• I run your code:

  h, T = 10, 5
  rho = 0.5
  
  @time blotto_game(h, T, rho)
  @time blotto_game(h, T, rho)
  @time blotto_game(h, T, rho)

  86.155627 seconds (163.56 M allocations: 57.308 GiB, 69.34% gc time)
  80.163191 seconds (162.20 M allocations: 57.244 GiB, 74.75% gc time)
  79.738192 seconds (162.20 M allocations: 57.244 GiB, 74.20% gc time)

• Can you write an alternative version, referring to my Python code, that uses for-loops avoiding creating temporary arrays, and compare the performance?

[shizejin]

@oyamad I see. Actually I've written my code and been waiting for you to open a branch in QuantEcon.py and then submit it. Now as long as you have written it, I will discard my code. One question, shall we add the option for favoring players as we discussed in last Friday? Your code seems just uniformly randomly break the tie.

I've also written the code for ranking game, where should I push my code to?

[oyamad]

Let's pick the code, yours or mine, that runs faster.

For the ranking game, create a new branch, say ranking, and push your code there.

[shizejin]

A memo:

• [x] After rebasing this branch, change the doc/Structure as Game Generators: random, generators/bimatrix_generators before merging.

[shizejin]

random_tournament_digraph has been implemented in LightGraphs by JuliaGraphs/LightGraphs.jl#811 @oyamad.

[oyamad]

@shizejin Congratulation for your debut as a contributor to LightGraphs.

[shizejin]

Thanks!

The julia version of next_k_array! and k_array_rank has been implemented QuantEcon/QuantEcon.jl#199.

[shizejin]

As I posted in QuantEcon/QuantEcon.jl#199, as long as binomial(BigInt(n), BigInt(k)) <= typemax(typeof(n)) is checked at the beginning of tournament game generator, k_array_rank(typeof(n), a) shall work correctly. Is this true? @oyamad

[oyamad]

What is the relationship between your code and the maximum size of an array in Julia?

[shizejin]

I see your point. I was concerning about the overflow from k_array_rank, while you are talking about the maximum size of payoff arrays that might be reached? If the maximum size of an array in Julia is smaller than typeof(Int), then I think we don't need to concern about the overflow from k_array_rank.

I found this MAXINTVAL, not sure if it's the upper bound for Julia array size. But it seems to me that they are finding the maximal of the range of UInt in the OS.

[oyamad]

Right.

Something like the following should work:

m = zero(Csize_t)
try
    m = binomial(Csize_t(n), Csize_t(k))
catch InexactError
    ...
end

[shizejin]

As Csize_t = UInt has larger range than Int, should we also add a checking condition to avoid overflow from k_array_rank(a)?

Alternatively, we can modify this line to

k_array_rank(a::Vector{<:Integer}) = k_array_rank(UInt, a)

as ranking does not take negative values.

I prefer to the latter proposal.

[oyamad]

What's wrong with just using k_array_rank(Csize_t, a)?

I think I am against the latter proposal; I would be surprised if I see 0x0000000000000001 returned from k_array_rank([1, 2]) instead of just 1.

[shizejin]

I see. I think k_array_rank(Csize_t, a) should work properly.

[shizejin]

In the tournament_game, I use field fadjlist, so it's row-major, which should be consistent with Python version.

For example:

julia> g = random_tournament_digraph(4; seed=1234)
{4, 6} directed simple Int64 graph

julia> g.fadjlist
4-element Array{Array{Int64,1},1}:
 [3, 4] 
 [1, 3] 
 Int64[]
 [2, 3] 

julia> sparse(g)
4×4 SparseMatrixCSC{Int64,Int64} with 6 stored entries:
  [2, 1]  =  1
  [4, 2]  =  1
  [1, 3]  =  1
  [2, 3]  =  1
  [4, 3]  =  1
  [1, 4]  =  1

@oyamad

[oyamad]

• [x] Test for unit_vector_game: Add tol=0 to pure_nash: See https://github.com/oyamad/QuantEcon.py/commit/2cab4831964e9ced7db6637033ee1d67c7f8989b.

[oyamad]

Python version is ready.

• [x] Squash the commits into a few logically separate commits.

[oyamad]

Big improvement for tournament_game: d4dae5cb8f662e59bf98e1f8c36b73cb53943c30

jud = judge("Games", "d4dae5c", "df4e511")
PkgBenchmark.benchmarkgroup(jud)["bimatrix_generators"]["tournament_game"]

BenchmarkTools.TrialJudgement: 
  time:   -96.25% => improvement (5.00% tolerance)
  memory: -64.72% => improvement (1.00% tolerance)

[oyamad]

Maintain consistency with the Python version:

• blotto_game
  • [x] code
  • [x] test
  • [x] doc
• ranking_game
  • [x] code
  • [x] test
  • [x] doc
• tournament_game
  • [x] code
  • [x] test
  • [x] doc
• unit_vector_game
  • [x] code
  • [x] test
  • [x] doc

[oyamad]

blotto_game: ccd5c2a2aed15369121912860a7a28601033267f

jud = judge("Games", "ccd5c2a", "5dd37b4")
PkgBenchmark.benchmarkgroup(jud)["bimatrix_generators"]["blotto_game"]

2-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "(3, 62)" => TrialJudgement(-28.09% => improvement)
  "(4, 21)" => TrialJudgement(-29.65% => improvement)

[oyamad]

ranking_game: 950b4a3ff89a67ac55f4c0b532a9df563ec8a311

jud = judge("Games", "950b4a", "5fa100")
PkgBenchmark.benchmarkgroup(jud)["bimatrix_generators"]["ranking_game"]

BenchmarkTools.TrialJudgement: 
  time:   -78.10% => improvement (5.00% tolerance)
  memory: -68.78% => improvement (1.00% tolerance)

[oyamad]

unit_vector_game: f91e498537eaca165bf0cfd6f7e9aa21d68ea988

jud = judge("Games", "f91e498", "3542757")
PkgBenchmark.benchmarkgroup(jud)["bimatrix_generators"]["unit_vector_game"]

2-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "true" => TrialJudgement(-88.07% => improvement)
  "false" => TrialJudgement(-84.63% => improvement)