@InProceedings{sandholm98b,
  author =	 {Tuomas Sandholm},
  title =	 {Contract types for satisficing task allocation: I
                  theoretical results},
  booktitle =	 {{AAAI} Spring Symposium: Satisficing Models},
  year =	 1998,
  abstract =	 {We analyze task reallocation where individually
                  rational (IR) agents (re)contract tasks among
                  themselves based on marginal costs. A task
                  allocation graph is introduced as a tool for
                  analyzing contract types. Traditional single task
                  contracts always have a short path (sequence of
                  contracts) to the optimal task allocation but an IR
                  path may not exist, or it may not be short. We
                  analyze an algorithm for finding the shortest IR
                  path. Next we introduce cluster contracts, swaps,
                  and multiagent contracts. Each of the four contract
                  types avoids some local optima that the others do
                  not. Even if the protocol is equipped with all four
                  types, local optima exist. To attach this problem,
                  we indroduce OCSM-contract which combine the ideas
                  behind the four earlier types into an atomics
                  contract type. If the protocol is equipped with
                  OCSM-contracts, any sequence of finite number of
                  steps: an oracle--or speculation---is not needed for
                  choosing the path (no subser of OCSM-contracts
                  suffices even with an oracle). This means that the
                  multiagent search does not need to backtrack. This
                  is a powerful result for small problem
                  instances. For large ones, the anytime feature of
                  our multi-contract-type algorithm---with provable
                  monotonic improvement of each agent's solution is
                  more important.},
  keywords =     {multiagent negotiation},
  url =		 {http://jmvidal.cse.sc.edu/library/sandholm98b.pdf},
  googleid =	 {wJcVeTa89xQJ:scholar.google.com/},
  citeseer =	 {sandholm98contract.html},
  cluster = 	 {1510883142151804864}
}