search

rahulsavani / bimatrix_solver

Enumerate all Nash equilibria of a bimatrix game (i.e. 2-player strategic-form game)
13 stars 2 forks source link

Will this work for games larger than 15x15---and what's the largest bimatrix game we can (feasibly) solve? #2

Open lieuzhenghong opened 4 years ago

lieuzhenghong commented 4 years ago

Dear Professor Savani,

I am interested in solving a modified Blotto game where players have heterogeneous resources and each battlefield has a maximum "capacity" (i.e. each player cannot assign more than a certain number of resources to that battlefield).

I was thinking of enumerating all pure strategies of the game to represent it as a strategic-form game, and then solving it with this bimatrix solver. The problem is that I believe the number of possible pure strategies in the Blotto game is very large and may even grow exponentially. I think, but I'm not sure, that the resulting strategic-form game might be hard to solve in the way you have defined.

In any case, I just wanted to ask whether this offline solver will work for games larger than 15x15, and also to ask your expertise on how large of a Blotto game I could feasibly solve with today's technology and algorithms. 100x100? 1000x1000? 10,000x10,000?

Thanks a lot!

rahulsavani commented 4 years ago

Your ability to solve larger games is only limited by your CPU and memory. Certainly much larger than 15x15 should be doable on a good modern computer, but it really depends on both the game and your computer. I suggest you just try -- it is not hard to install and use the solver. BTW, there's been quite some work on solving Blotto games, including in the last few years.