Solving Multi-Agent Games on Networks

Multi-agent games on networks (GoNs) have nodes that represent agents and edges that represent interactions among agents. Binary GoNs are composed of 2-Players games on each of their edges. Non binary GoNs have games that are played by all agents in each neighborhood.Solutions to games on networks are stable states (i.e., pure Nash equilibria), and in general one is interested in efficient solutions (i.e., of high social welfare).Incentives, in the form of side payments among agents, are known to promote increased-efficiency stable states. This study addresses the multi-agent aspect of games on networks - a system of multiple agents that compose a game and seek a solution. The agents playing the game are assumed to be strategic and the present study proposes an iterative distributed algorithm that lets the agents interact (i.e., negotiate) in neighborhoods in a process that guarantees the convergence of any multi-agent game on network to a stable state.The proposed algorithm treats the game as a repeated social choice action that takes place in one neighborhood at a time. A truthful enforcing mechanism is integrated into the process, collecting agents' valuations and computing incentives on the fly while eliminating strategic behavior. This method - the TECon algorithm - is proven to converge to solutions that are at least as efficient as the initial state, for any game on network.A specific version of the algorithm is given for the class of public goods games, where the main properties of the algorithm are guaranteed even when the strategic agents playing the game consider their possible future valuations when interacting.This opens an interesting new research direction on application-specific derivatives of TECon that, similarly to the case of public goods games, may lead to solutions of greater efficiency. An extensive experimental evaluation on randomly generated games on networks demonstrates that the TECon algorithm outperforms former solving methods on several classes of games on networks.