Task allocation problems under the aspect of algorithms and Game Theory

• Grant number: 08/03972-5
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: September 01, 2008
• End date: August 31, 2009
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Eduardo Candido Xavier
• Grantee: Leandro Medina de Oliveira
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project, we are interested in investigating task allocation problems under the aspect of game theory. We assume the tasks being controlled by autonomous, selfish beings, in the sense that they always seek the best solution for themselves. The task allocation problem (TAP) is a well-known computational problem. In the last few years, with the development of the area of Algorithmic Game Theory, the problem has received attention of the researchers according to this point of view. Under the aspect of game theory, we assume that the tasks are allocated by autonomous beings (players), always seeking to minimize a local objective function, which represents a selfish action. The tasks may be reallocated however many times the autonomous being might need, until it reaches its local optimum. Three questions arise in analyzing games of this sort: 1) Does the allocation converge to a state in which each player will not want to reallocate its task further? 2) If such equilibrium state exists, what is the maximum number of swaps needed to reach it; and 3) Considering a global objective function, how bad is an equilibrium solution in comparison with an optimal solution to the problem? Our objective in this project is the study of task allocation problems under the optics of Game Theory. It is also our interest the implementation of simulators of the studied games to evaluate practical results with theoretical ones available in literature. (AU)