Efficiency, incentives and computational tractability in MAS-Coordination

This paper focuses on market-like coordination mechanisms in multi-agent systems, with applications to business planning. Several fundamental criteria are derived in order to evaluate market-like coordination mechanisms. The central criterion is the efficient allocation of jobs to agents. Assuming a relationship between classes of operational planning problems and certain coordination mechanisms, business planning problems are classified on the basis of their relevant attributes. Coordination mechanisms for each of the classes are then introduced on the basis of auction theory and investigated with respect to the trade-off between efficiency and computational tractability. All of the mechanisms prove to have a common basis: the Vickrey Auction.