Implementation with a Bounded Action Space

Liad Blumrosen

Hebrew University

 

***Wednesday***    Feb. 1st, 4:15 PM, 5130 Upson

 

 

 

The field of Mechanism Design considers the design of algorithms in environments where the input for the algorithms is provided by self-interested agents. Such agents may manipulate the algorithm for their own benefit. For achieving the desired system-wide outcomes, the algorithm designer should design a protocol where each agent will have the incentive to choose an action that truthfully reveals her private information (her "type"). Handling the incentive issues must be taken together with other constraints, for example, with computational or communication constraints.

While traditional mechanism design typically assumes isomorphism between the agents' type- and action spaces, in many situations the agents face strict restrictions on their action space. These restrictions may be caused by, e.g., technical, behavioral or regulatory reasons. Under this restriction, a "direct revelation" of the players' private information will no longer be feasible.

We devise a general framework for the study of mechanism design in single-parameter environments with restricted action spaces. We characterize settings where the information-theoretically optimal solutions are dominant-strategy implementable, and we measure the loss in these optimal mechanisms. Our results apply to various economic and computational settings, and we demonstrate their applicability to signaling games, public-good models and routing in networks.

Joint work with Michal Feldman