Wednesday Jan 25, 2006 3:00pm-4:00pm in CSE 503

TITLE: Implementation with a bounded action space

Speaker: Liad Blumrosen, Hebrew University

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