Contract Complexity

We study the complexity required for the implementation of multi-agent contracts under a variety of solution concepts. A contract is a mapping from strategy profiles to outcomes. Practical implementation of a contract requires it to be ”simple”, an illusive concept that needs to be formalized. A major source of complexity is the burden involving verifying the contract fulfillment (for example in a court of law). Contracts which specify a small number of outcomes are easier to verify and are less prone to disputes. We therefore measure the complexity of a contract by the number of outcomes it specifies. Our approach is general in the sense that all strategic interaction represented by a normal form game are allowed. The class of solution concepts we consider is rather exhaustive and includes Nash equilibrium with both pure and mixed strategies, dominant strategy implementation, iterative elimination of dominated strategies and strong equilibria.

Some interesting insights can be gained from our analysis: Firstly, our results indicate that the complexity of implementation is independent of the size of the strategy spaces of the players but for some solution concepts (but not all) grows with the number of players. Second, the complexity of unique implementation is sometimes slightly larger, but not much larger than non-unique implementation. Finally and maybe surprisingly, for most solution concepts implementation with optimal cost usually does not require higher complexity than the complexity necessary for implementation at all.