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