The complexity of deciding reachability properties of distributed negotiation schemes
Dunne, Paul; Chevaleyre, Yann (2008), The complexity of deciding reachability properties of distributed negotiation schemes, Theoretical Computer Science, 396, 1-3, p. 113-144. http://dx.doi.org/10.1016/j.tcs.2008.01.031
Type
Article accepté pour publication ou publiéDate
2008Journal name
Theoretical Computer ScienceVolume
396Number
1-3Publisher
Elsevier
Pages
113-144
Publication identifier
Metadata
Show full item recordAbstract (EN)
Distributed negotiation schemes offer one approach to agreeing an allocation of resources among a set of individual agents. Such schemes attempt to agree a distribution via a sequence of locally agreed ‘deals’–reallocations of resources among the agents–ending when the result satisfies some accepted criteria. Our aim in this article is to demonstrate that some natural decision questions arising in such settings can be computationally significantly harder than questions related to optimal clearing strategies in combinatorial auctions. In particular we prove that the problem of deciding whether it is possible to progress from a given initial allocation to some desired final allocation via a sequence of “rational” steps is pspace-complete.Subjects / Keywords
Straight-line program; pspace-completeness; Computational complexity; Multiagent resource allocation; Distributed negotiationRelated items
Showing items related by title and author.
-
Dunne, Paul; Chevaleyre, Yann (2005) Document de travail / Working paper
-
Maudet, Nicolas; Endriss, Ulle; Chevaleyre, Yann (2008) Chapitre d'ouvrage
-
Chevaleyre, Yann; Endriss, Ulle; Estivie, Sylvia; Maudet, Nicolas (2007) Communication / Conférence
-
Simple Negotiation Schemes for Agents with Simple Preferences: Sufficiency, Necessity and Maximality Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2010) Article accepté pour publication ou publié
-
Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2005) Communication / Conférence