• Home
  • News
  • Technology
  • Research
  • Teaching
  • Business
  • Jobs
  • Home
  • News
  • Technology
  • Research
  • Teaching
  • Business
  • Jobs
Contact
  • de
  • en

  • Home
  • News
  • Technology
  • Research
  • Teaching
  • Business
  • Jobs
Contact
  • de
  • en

A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games

A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games

Christoph Roch, Thomy Phan, Sebastian Feld, Robert Müller, Thomas Gabor, Carsten Hahn, Claudia Linnhoff-Popien
Abstract

We introduce Q-Nash, a quantum annealing algorithm for the NP-complete problem of finding pure Nash equilibria in graphical games. The algorithm consists of two phases. The first phase determines all combinations of best response strategies for each player using classical computation. The second phase finds pure Nash equilibria using a quantum annealing device by mapping the computed combinations to a quadratic unconstrained binary optimization formulation based on the Set Cover problem. We empirically evaluate Q-Nash on D-Wave’s Quantum Annealer 2000Q using different graphical game topologies. The results with respect to solution quality and computing time are compared to a Brute Force algorithm and the Iterated Best Response heuristic.

Published in 20th International Conference on Computational Science (ICCS 2020), 2020, p. 12. doi:10.1007/978-3-030-50433-5_38

PDF Download


QAR-Lab – Quantum Applications and Research Laboratory
Ludwig-Maximilians-Universität München
Oettingenstraße 67
80538 Munich
Phone: +49 89 2180-9153
E-mail: qar-lab@mobile.ifi.lmu.de

© Copyright 2021

General

Team
Contact
Legal notice

Social Media

Twitter
Linkedin
Github

Language

  • de
  • en