• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2008
Journal name
Theoretical Computer Science
Volume
396
Number
1-3
Publisher
Elsevier
Pages
113-144
Publication identifier
http://dx.doi.org/10.1016/j.tcs.2008.01.031
Metadata
Show full item record
Author(s)
Dunne, Paul
Chevaleyre, Yann
Abstract (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 negotiation

Related items

Showing items related by title and author.

  • Thumbnail
    Negotiating can be as hard as Planning: deciding reachability properties of distributed negotiation schemes 
    Dunne, Paul; Chevaleyre, Yann (2005) Document de travail / Working paper
  • Thumbnail
    Restricted Classes of Utility Functions for Simple Negotiation Schemes: Sufficiency, Necessity and Maximality 
    Maudet, Nicolas; Endriss, Ulle; Chevaleyre, Yann (2008) Chapitre d'ouvrage
  • Thumbnail
    Reaching Envy-Free States in Distributed Negotiation Settings 
    Chevaleyre, Yann; Endriss, Ulle; Estivie, Sylvia; Maudet, Nicolas (2007) Communication / Conférence
  • Thumbnail
    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é
  • Thumbnail
    On maximal classes of utility functions for efficient one-to-one negotiation 
    Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2005) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo