Efficiency and Equilibrium in Task Allocation Economics with Hierarchical Dependencies

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.