Publication - Learning the Task Allocation Game

Authors: Abdallah, Sherief; Lesser, Victor
Title: Learning the Task Allocation Game
Abstract: The distributed task allocation problem occurs in domains like web services, the grid, and other distributed systems. In this problem, the system consists of servers and mediators. Servers execute tasks and may differ in their capabilities, e.g. one server may take more time than the other in executing the same task. Mediators act on behalf of users, which can potentially be other mediators, and are responsible for receiving tasks from users and allocating them to servers.

This work introduces a new gradient ascent learning algorithm that outperforms state of the art multiagent learners on this problem. We experimentally show that our algorithm converges faster and is less sensitive to tuning parameters than other algorithms. We also provide an informal proof that WPL has the same convergence guarantee as the best known algorithm, GIGA-WoLF.

We also show that our algorithm converges in Jordan`s and Shapley`s games where many other algorithms fail to converge. Finally, we verify the practicality of our algorithm in the distributed task allocation domain, comparing its performance to an optimal global solution.
Keywords: Learning, Multi-Agent Systems, Task Distribution
Publication: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. 850 - 857
Location: Hakodate, Japan
Publisher: ACM Press
Date: 2006
Sources: PDF: http://mas.cs.umass.edu/~shario/papers/aamas06.pdf
Reference: Abdallah, Sherief; Lesser, Victor. Learning the Task Allocation Game. Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multi-Agent Systems, ACM Press, pp. 850-857. 2006.
bibtex: 
@inproceedings{Abdallah-431,
  author    = "Sherief Abdallah and Victor Lesser",
  title     = "{Learning the Task Allocation Game}",
  booktitle = "Proceedings of the Fifth International Joint
               Conference on Autonomous Agents and Multi-Agent
               Systems",
  publisher = "ACM Press",
  pages     = "850-857",
  year      = "2006",
  address   = "Hakodate, Japan",
  url       = "http://mas.cs.umass.edu/paper/431",
}