| EPSRC Reference: |
EP/X039862/1 |
| Title: |
NAfANE: New Approaches for Approximate Nash Equilibria |
| Principal Investigator: |
Deligkas, Dr A |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Royal Holloway, Univ of London |
| Scheme: |
New Investigator Award |
| Starts: |
01 January 2024 |
Ends: |
31 December 2026 |
Value (£): |
500,163
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
24 Apr 2023
|
EPSRC ICT Prioritisation Panel April 2023
|
Announced
|
|
|
Summary on Grant Application Form |
The main goal of this proposal is to develop new techniques with the aim of identifying the precise cut-off between tractable and intractable approximations of Nash equilibria (NE), the foundational solution-concept in Game Theory and Economics. A Nash equilibrium is a situation where no player can increase their payoff by unilaterally deviating. Ultimately our target is to develop new approaches that will enhance our understanding of equilibrium computation, the most fundamental problem in Algorithmic Game Theory.
We will settle the tractability frontier of equilibrium computation for three general classes of games that are of interest to a wide variety of researchers within the communities of Economics, Mathematics, Artificial Intelligence, Machine Learning, and Computer Science.
- Bimatrix Games: This is the fundamental class of games, played between two players, that has been studied extensively over the years.
- Polymatrix Games: This class captures many-player games with an underlying network structure, where every node corresponds to a player, and every player interacts with the players in their neighborhood as defined by the network.
This type of games received a lot of attention due to numerous applications ranging from building-blocks to hardness reductions, to applications in protein function prediction and semi-supervised learning.
- Bayesian Games: This is the foundational class of games with incomplete information. We will focus on the cornerstone subclass of two-player Bayesian games. This family of games is closely related to polymatrix games, since it can be represented as a polymatrix game over a bipartite network.
While there exist several results, both positive and negative, for finding approximate equilibria in the above-mentioned classes of games, the gaps between intractability and polynomial-time approximability are still large. In addition, there exist several ``well-behaved'' families of these games that cannot be captured by the current inapproximability results. These families of games could admit a polynomial-time algorithm that has not been discovered yet.
The objective of this proposal is to rectify this situation: close the gaps between lower bounds and upper bounds, and identify parameters for each class of games that allow for polynomial-time algorithms.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
|