2014/05/27 by Javier Esparza, Esparza, Javier, Philipp Hoffmann +1 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Game Theory and Applications #Game Theory and Voting Systems #cs.LO
paper · pdf · doi:10.48550/arxiv.1405.6820
arxiv created 2015/07/29 · arxiv updated 2015/07/30
Negotiations, a model of concurrency with multi party negotiation as primitive, have been recently introduced in arXiv:1307.2145, arXiv:1403.4958. 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.