Tech Reports

ULCS-05-009

Negotiation can be as hard as planning: Deciding reachability properties of distributed negotiation schemes

Paul E. Dunne and Yann Chevaleyre

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.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.