Contract Types for Satisficing Task Allocation: II, Experimental Results

Satisficing Models

Volume

Satisficing Models

Contents

We provide experimental results for a task allocation problem where serf-interested, individually rational agents (re)contract tasks among themselves. TraditionaJ contract types allow only one task to be transferred between agents at a time (original contracts). In this paper the original and four other contract types are studied: cluster-, swap-, multiagent, and OCSMcontracts. The OCSM-contracts will reach the global optimum even if the agents are individually rational, but in large-scale problems the number of steps required can be prohibitively large, albeit finite. In such cases it is more important to find the best solution reachable in a bounded amount of time. To construct algorithms that achieve that we study different contract types evaluate their performance. This paper discusses tile quality of local optima reached by the different contract types, and how quickly they are reached. It is shown how environmental characteristics such as the number of agents and the number of tasks affect these results. This analysis is used as a basis for making prescriptions about which contract types agents should use in different environments. Out of original-, cluster-, swap-, and multiagent-contracts, either original-contracts (if the ratio agents to tasks is great) or cluster-contracts (if the same ratio is small) reach a local optimum with a higher social welfare than the others.