Contract type sequencing for reallocative negotiation

Abstract

The capability to reallocate items-e.g. tasks, securities, bandwidth slices, MW hours of electricity, and collectibles-is a key feature in automated negotiation. Especially when agents have preferences over combinations of items, this is highly nontrivial. Marginal cost based reallocation leads to an anytime algorithm where every agent's utility increases monotonically over time. Different contract types head toward different locally optimal task allocations, and contracts from a recently introduced comprehensive contract type, OCSM-contracts, head toward the global optimum. Reaching it can take an impractically long time, so it is important to trade off solution quality against negotiation time. To construct negotiation protocols that lead to the best achievable allocations in a bounded amount of time, we compared sequences of four contract types. Original, cluster, swap, and multiagent contracts. The experiments show that it is profitable to use multiple contract types in the sequence: significantly better solutions are reached, and faster, than if only one contract type is used. However, the best sequences only include original and cluster contracts. Swap and multiagent contracts lead to bad local optima quickly. Interestingly, the number of contracts using any given contract type does not always decrease over time: contracts play the role of enabling further contracts.