Efficient and Strategy-Proof Mechanisms for Task Allocation with Interdependent Valuations

Ayman Ghoneim (ANU - Research School of Computer Science)

CS HDR MONITORING

DATE: 2011-05-20
TIME: 10:00:00 - 11:00:00
LOCATION: NICTA Boardroom
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
Classical mechanism design normally assumes that an agent's value of any determined outcome depends only on its private information. In many practical instances (e.g., interdependent task allocation, multiagent planning), this assumption is violated, and agents have interdependent valuations. In interdependent valuations settings, an agent's value of an outcome depends not only on its privately known type - as in classical mechanism design, but as well on the actual types of other agents. Efficient and strategy-proof mechanisms for such settings have not been proposed yet for any domain, and when such mechanisms are possible is still an open research question.

In this talk, we briefly introduce the main concepts of mechanism design and interdependent valuations settings. Then, toward addressing the previously mentioned research question, we consider the interdependent task allocation (ITA) problem, where interdependent tasks are to be assigned to self-interested agents based on what they report about their privately known capabilities and costs. Since selfish agents may strategically misreport their private information in order to increase their payments, mechanism design is used to determine a payment schema that guarantees truthful reporting. Misreported information may cause tasks to fail during their execution, creating interdependencies between the agents' valuations. In this talk, we will consider a general model for the ITA problem, and show that it is impossible to design efficient and strategy-proof mechanisms. Then, we show that designing such mechanisms for the ITA problem is possible for two special models. The first, implicitly model the agent's privately known cost for performing a task as a privately known duration in which the task is performed. While the second, considers the reassignment of failing tasks. We extend our work to consider assigning tasks that may incur negative social welfare, and show that we can still design strategy-proof mechanisms, but the center rationality property is lost.