A distributed asynchronous solver for Nash Equilibria in hypergraphical games

Thumbnail Image
2621.pdf(383.13 KB)
Published Version
Wahbi, Mohamed
Brown, Kenneth N.
Journal Title
Journal ISSN
Volume Title
IOS Press
Research Projects
Organizational Units
Journal Issue
Hypergraphical games provides a compact model of a network of self-interested agents, each involved in simultaneous subgames with its neighbors. The overall aim is for the agents in the network to reach a Nash Equilibrium, in which no agent has an incentive to change their response, but without revealing all their private information. Asymmetric Distributed constraint satisfaction (ADisCSP) has been proposed as a solution to this search problem. In this paper, we propose a new model of hypergraphical games as an ADisCSP based on a new global constraint, and a new asynchronous algorithm for solving ADisCSP that is able to find a Nash Equilibrium. We show empirically that we significantly reduce both message passing and computation time, achieving an order of magnitude improvement in messaging and in non-concurrent computation time on dense problems compared to state-of-the art algorithms.
Constraints , ABT
Wahbi, M. and Brown, K. N. (2016) ‘A distributed asynchronous solver for Nash Equilibria in hypergraphical (from proceedings of the Twenty-second European Conference on Artificial Intelligence (ECAI 2016),The Hague, The Netherlands, 29th August - 2nd September), Frontiers in Artificial Intelligence and Applications, 285, pp. 1291-1299. doi:10.3233/978-1-61499-672-9-1291
Link to publisher’s version