Time-Quality Tradeoffs in Reallocative Negotiation with Combinatorial Contract Types

Abstract

The capability to reallocate items---e.g. tasks, securities, bandwidth slices, Mega Watt 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 payoff increases monotonically over time. Different contract types head toward different locally optimal allocations of items, and OCSM-contracts head toward the global optimum. Reaching it can take impractically long, so it is important to trade off solution quality against negotiation time. To construct negotiation protocols that lead to good allocations quickly, we evaluated original (O), cluster (C), swap (S), and multiagent (M) contracts experimentally. O-contracts led to the highest social welfare when the ratio of agents to tasks was large, and C-contract were best when that ratio was small. O-contracts led to the largest number of co...