Łukasiewicz games

Abstract

Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved. Boolean games provide a simple, compact, and theoretically attractive abstract model for studying multi-agent interactions in settings where players will act strategically in an attempt to achieve personal goals. A standard critique of Boolean games, however, is that the binary nature of goals (satisfied or unsatisfied) inevitably trivialises the nature of such strategic interactions: a player is assumed to be indifferent between all outcomes that satisfy his goal, and indifferent between all outcomes that do not satisfy his goal. In this paper, we introduce Lukasiewicz Games, which overcome this limitation by considering goals to be specified using finitely-valued Lukasiewicz logics. The significance of this is that formulae of Lukasiewicz logic can express every continuous piecewise linear polynomial function with integer coefficients over [0, 1]n, thereby allowing goal formulae in Lukasiewicz Games to naturally express a much richer range of utility functions. After introducing the formal framework of Lukasiewicz Games, we present a number of detailed worked examples to illustrate the framework, and then investigate some of the properties of Lukasiewicz Games. In particular, after investigating the complexity of decision problems in Lukasiewicz Games, we give a logical characterisation of the existence of Nash equilibria in such games.