Starting Date: Summer 2021
Prerequisites: None formal. To be comfortable with the mathematical side of computer science and curious about Algorithmic Game Theory
Will results be assigned to University: No
Net Coordination Games form a special class of many-player games with
several applications in Theoretical Computer Sciene, Multi Agent Systems,
and Semi Supervised Learning. Nash equilibria correspond to the stable
outcomes and they are the prominent solution concept in games. It is known that Net Coordination Games possess a pure Nash equilibrium, but unfortunately, it is shown that find such an equilibrium is intractable. On the other hand, it is open whether a mixed Nash equilibrium can be efficiently computed.
The goal of this project is to evaluate two well known, simple, algorithms (Fictitious Play (FP) and Counterfactual Regret Minimization (CRM)) for computing a mixed Nash equilibrium in Net Coordination Games. The project consists of several different components.
– Implementation of FP and CRM
– Evaluation of their performance on different subclasses of games
– Evaluation of these algorithms in Semi Supervised Learning scenaria
I will explain to you the basics of Game Theory and Net Coordination games and help you to understand the concepts of Nash equilibria and the two aforementioned algorithms. Depending on the outcome of the project, we can submit our findings to a conference related to Algorithmic Game Theory, or Machine Learning.
If you have any questions, feel free to ask me!