Paper Info
Title
The complexity of deciding reachability properties of distributed negotiation schemes
Abstract
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.
Year
DOI
Venue
2008
10.1016/j.tcs.2008.01.031
Theor. Comput. Sci.
Keywords
DocType
Volume
negotiation scheme,Computational complexity,pspace -completeness,Distributed negotiation,natural decision question,Multiagent resource allocation,combinatorial auction,reachability property,accepted criterion,final allocation,individual agent,initial allocation,Straight-line program
Journal
396
Issue
ISSN
Citations 
1-3
Theoretical Computer Science
6
PageRank 
References 
Authors
0.55
17
2
Name
Order
Citations
PageRank
Paul E. Dunne11700112.42
Yann Chevaleyre284861.76