Algorithms for Computing Nash Equilibria

Project Level: Summer

Project Duration: 6 weeks

Hours of Engagement: 20-36 hours

Project Description:

How should we play a competitive game such as Kuhn poker? In many cases, there is no way of guaranteeing that the maximum possible reward can be achieved. The Nash equilibrium is the most commonly used notion of an “optimal” strategy in such cases. However, finding the Nash equilibria is often hard. Various algorithms have been developed for computing the Nash equilibria, but there is no single algorithm that works in all cases. This project aims to empirically compare algorithms for computing Nash equilibria for some popular games. The successful applicant will write code to implement some games, use existing solver implementations to solve the games, and perform experiments to compare the solvers.

Expected Outcomes:

• • Develop an understanding on Nash equilibrium and algorithms for computing it.

• Develop skills for writing code to compute the Nash equilibria for games.

• Develop skills in research design, implementation, experimentation, and communication.

• A report documenting the work done and the findings.

Suitable for:

Essential: interest in strategy games, knowledge on algorithms and programming skills.

Desirable: knowledge on game theory.

Contact for further information:

Dr Nan Ye: nan.ye@uq.edu.au