[Research] Studying heuristics to solve Bayesian Games through Linear Programs

Studying heuristics to solve Bayesian Games through Linear Programs

Bayesian Games are instances of a relatively simple class of games. They are decision-making model used to derive optimal strategies for incomplete information, they therefore represent a step in a partially observable markov decision processes (POMDP).

Optimal strategies in this games represent a Nash Equilibrium that can be found through solving a Linear Program. The resolution of such systems runs in polynomial time which is a limit to systems integrating this approach. Building a sequential decision making solver where each step is polynomial might indeed be challenging. Therefore, we propose to study the use of search heuristics to consider most probable states first.

Two heuristics were tested. Results show that, even though solving time was improved, solving complexity remains polynomial. Testing more complex heuristics could result in complexity decrease but nothing shows evidence of that here.

Read full report.

View Library homepage or code base