We introduce and study non-zero-sum multi-player games with weighted multiple objectives. In these games, the objective of each player consists of a set \(\alpha \) of underlying objectives and a weight function \(w: 2^\alpha \rightarrow \mathbb {Z}\) that maps each subset X of \(\alpha \) to the utility of the player when exactly all the objectives in X are satisfied. We study the existence and synthesis of stable outcomes with desired utilities for the players. The problem generalizes rational synthesis and enables the synthesis of outcomes that satisfy wellness, fairness, and priority requirements. We study the extension of the game by payments, with which players can incentivize each other to follow strategies that are beneficial for the paying player. We show how such payments can be used in order to repair systems. We study the complexity of the setting for various classes of weight functions. In particular, general weight functions are related to Muller objectives, and the synthesis problem for them is PSPACE-complete. We study non-decreasing, additive, positive, and other classes of weight functions, and the way they affect the memory required for the players and the complexity of the synthesis problem.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Non-Zero-Sum Games with Multiple Weighted Objectives

  • Yoav Feinstein,
  • Orna Kupferman,
  • Noam Shenwald

摘要

We introduce and study non-zero-sum multi-player games with weighted multiple objectives. In these games, the objective of each player consists of a set \(\alpha \) of underlying objectives and a weight function \(w: 2^\alpha \rightarrow \mathbb {Z}\) that maps each subset X of \(\alpha \) to the utility of the player when exactly all the objectives in X are satisfied. We study the existence and synthesis of stable outcomes with desired utilities for the players. The problem generalizes rational synthesis and enables the synthesis of outcomes that satisfy wellness, fairness, and priority requirements. We study the extension of the game by payments, with which players can incentivize each other to follow strategies that are beneficial for the paying player. We show how such payments can be used in order to repair systems. We study the complexity of the setting for various classes of weight functions. In particular, general weight functions are related to Muller objectives, and the synthesis problem for them is PSPACE-complete. We study non-decreasing, additive, positive, and other classes of weight functions, and the way they affect the memory required for the players and the complexity of the synthesis problem.