Efficiency and Equilibrium in Task Allocation Economies with Hierarchical Dependencies

Abstract

We analyze economic efficiency and equilibrium properties in decentralized task allocation problems involving hierarchical dependencies and resource contention. We bound the inefficiency of a type of approximate equilibrium in proportion to the number of agents and the bidding parameters in a particular market protocol. This protocol converges to an approximate equilibrium with respect to all agents, except those which may acquire unneeded inputs. We introduce a decommitment phase to allow such agents to decommit from their input contracts. Experiments indicate that the augmented market protocol produces highly efficient allocations on average. 1 Introduction We consider task allocation problems in which competing agents desire to accomplish tasks, which may require complex chains of production activity. In order to perform a particular task, an agent may need to achieve some subtasks, which may in turn be delegated to other agents, forming a supply chain through a hierarchy of task a...