@Article{	  shehory98a,
  author =	 {Onn Shehory and Sarit Kraus},
  title =	 {Methods for Task Allocation via Agent Coalition
                  Formation},
  googleid =	 {Wo06V_P7nWsJ:scholar.google.com/},
  journal =	 {Artificial Intelligence},
  year =	 1998,
  volume =	 101,
  number =	 {1-2},
  pages =	 {165--200},
  month =	 {May},
  abstract =	 {Task execution in multi-agent environments may
                  require cooperation among agents. Given a set of
                  agents and a set of tasks which they have to
                  satisfy, we consider situations where each task
                  should be attached to a group of agents that will
                  perform the task. Task allocation to groups of
                  agents is necessary when tasks cannot be performed
                  by a single agent. However it may also be beneficial
                  when groups perform more efficiently with respect to
                  the single agents' performance. In this paper we
                  present several solutions to the problem of task
                  allocation among autonomous agents, and suggest that
                  the agents form coalitions in order to perform tasks
                  or improve the efficiency of their performance. We
                  present efficient distributed algorithms with low
                  ratio bounds and with low computational
                  complexities. These properties are proven
                  theoretically and supported by simulations and an
                  implementation in an agent system. Our methods are
                  based on both the algorithmic aspects of
                  combinatorics and approximation algorithms for
                  NP-hard problems. We first present an approach to
                  agent coalition formation where each agent must be a
                  member of only one coalition. Next, we present the
                  domain of overlapping coalitions. We proceed with a
                  discussion of the domain where tasks may have a
                  precedence order. Finally, we discuss the case of
                  implementation in an open, dynamic agent system. For
                  each case we provide an algorithm that will lead
                  agents to the formation of coalitions, where each
                  coalition is assigned a task. Our algorithms are
                  any-time algorithms, they are simple, efficient and
                  easy to implement. },
  keywords =     {multiagent coalitions},
  comment =	 {Gives a greedy-style algorithm, mostly based on a
                  classic set covering (partitioning) algorithm, for
                  coalition formation, which is the same as task
                  allocation. The algorithm only considers coalition
                  of size $k$ or smaller. They also study overlapping
                  coalitions. Algorithms are anytime.},
  url =		 {http://jmvidal.cse.sc.edu/library/shehory98a.pdf},
  created =	 1001877526,
  cluster = 	 {7754631155960941914}
}