Design of Incentive Compatible Mechanisms for Stackelberg Problems

This paper takes the first steps towards designing incentive compatible mechanisms for hierarchical decision making problems involving selfish agents. We call these Stackelberg problems. These are problems where the decisions or actions in successive layers of the hierarchy are taken in a sequential way while decisions or actions within each layer are taken in a simultaneous manner. There are many immediate applications of these problems in distributed computing, grid computing, network routing, ad hoc networks, electronic commerce, and distributed artificial intelligence. We consider a special class of Stackelberg problems called SLRF (Single Leader Rest Followers) problems and investigate the design of incentive compatible mechanisms for these problems. In developing our approach, we are guided by the classical theory of mechanism design. To illustrate the design of incentive compatible mechanisms for Stackelberg problems, we consider first-price and second-price electronic procurement auctions with reserve prices. Using the proposed framework, we derive some interesting results regarding incentive compatibility of these two mechanisms.