Iterative Approximation of Nash Equilibrium Strategies for Multi-agent Systems

We present a technique for approximating Nash equilibrium strategies for multi-agents systems for resource allocation (MRAs). Agents in MRAs seek to maximise the frequency of reaching their resource allocation goals, which can be measured by means of a pay-off. A strategy is an \(\epsilon \) -approximation of a Nash equilibrium if no agent can multiply its pay-off by more than \(\epsilon \) via unilateral deviation, where \(\epsilon \) is a rational number. For small \(\epsilon \) ’s approximate Nash equilibria are practically useful and stable strategies since agents will only have a small incentive to change their strategic behaviour. Our technique is based on encoding the strategy synthesis problem in propositional logic with weighted ‘pay-off’ clauses and solving it via weighted maximum satisfiability solving. In our approach we initially synthesise a collectively optimal strategy and determine for each agent the improvement potential, which is the pay-off increase that can be achieved via unilateral deviation. We seek to iteratively reduce the improvement potentials of synthesised strategies: The weights of the ‘pay-off’ clauses associated with agents get adjusted such that agents with a currently high improvement potential will be favoured when solving the weight-adjusted strategy synthesis problem in the subsequent iteration. We show that our approach facilitates the synthesis of \(\epsilon \) -equilibrium strategies with small \(\epsilon \) ’s.