Comparing the notions of optimality in strategic games and soft constraints

Contents

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of two formalisms used for different purposes in reasoning about multi-agent systems. One of them are strategic games that are used to capture the idea that agents interact with each other while pursuing their own interests. The other are soft constraints that are used to express preferences in presence of constraints and uncertainty. To relate the notions of optimality in these formalisms we define two mappings. We show for a natural mapping from soft constraints to strategic games that in general no relation exists between the notions of an optimal solution and Nash equilibrium. However, for a class of soft constraints that includes weighted constraints every optimal solution is a Nash equilibrium. In turn, for a natural mapping from strategic games to soft constraints the notion that coincides with optimality for soft constraints is that of Pareto efficient joint strategy.