Negotiation Games
Negotiation Games
复制标题
DOI：
10.4204/eptcs.193.3
复制
发表时间：
2015-01-01
影响因子：
--
通讯作者：
Hoffmann, Philipp
中科院分区：
文献类型：
--
作者：
Hoffmann, Philipp
协商是一种以多方协商为原语的并发模型，最近在[5，6]中引入。我们开始研究这个模型的游戏。我们研究联盟的问题：可以一个给定的联盟的代理人的力量，谈判终止（分别。阻止谈判，使谈判永远进行下去）？联合部队能否确定谈判的结果？我们证明了任意协商的问题是EXPTIME完全的。然后，我们表明，声音和确定性，甚至弱确定性谈判的问题可以解决PTIME。请注意，问题的输入是一个协商，它可以比其状态空间呈指数级更紧凑。
Negotiations, a model of concurrency with multi party negotiation as primitive, have been recently introduced in [5, 6]. We initiate the study of games for this model. We study coalition problems: can a given coalition of agents force that a negotiation terminates (resp. block the negotiation so that it goes on forever)?; can the coalition force a given outcome of the negotiation? We show that for arbitrary negotiations the problems are EXPTIME-complete. Then we show that for sound and deterministic or even weakly deterministic negotiations the problems can be solved in PTIME. Notice that the input of the problems is a negotiation, which can be exponentially more compact than its state space.