Mechanism design for resource bounded agents

The theory of mechanism design deals with the design of protocols for non-cooperative multi-agent systems. A major task of this theory is the design of protocols that will maximize the social welfare of the agents. An ideal mechanism will optimize social welfare and will be strategy-proof, i.e. the dominant strategy of each agent will be to participate in the mechanism and to reveal his true goal and worth, as well as budget-balanced, i.e., the mechanism should not impose any payments from the center/organizer to the agents. Indeed, E. Clarke´s (1971) mechanism, which is central to information economics and to games with incomplete information satisfies these properties. However, we show that the Clarke´s mechanism employs the use of procedures for optimizing social welfare, which are NP-hard. Hence, these procedures should be replaced by heuristics. We present a set of natural properties (axioms) of such heuristics that, when satisfied, enable us to obtain the desired strategy-proofness and budget balance properties. Our result enables us to extend the central protocol of the theory of mechanism design to the context of resource-bounded agents