Local vs Global Incentive Compatibility in Mechanism Design

Abstract

We study models in mechanism design theory where agents have private information (called a type) which has to be elicited by the mechanism designer. The cornerstone of the theory is the collection of incentive compatibility constraints which ensure that agents do not have incentives to misreport their types (or manipulate). The standard assumption in the theory is that the proposed mechanism must be immune to all possible misreports of agents. There is, however considerable experimental evidence that agents often choose to lie credibly by only misreporting to types that are “near” or “close to” their true types. Therefore, it is natural to consider models where an agent of a particular type can only misreport to an arbitrary set of pre-specified “local” types. We consider such models and provide answers to the following question: under what circumstances is immunity to misreporting via a “local” type (local incentive compatibility) equivalent to immunity to misreporting via an arbitrary type (incentive compatibility)? This thesis consists of five chapters. We provide a brief introduction of the chapters below. Chapter 2 considers a voting model where each voter’s type is her strict preference. The type graph for a voter is a graph whose vertices are the possible types of the voter. Two vertices are connected by an edge in the graph if the associated types are “local”. Local-Global equivalence (LGE) is satisfied if local strategy-proofness implies strategy-proofness for deterministic social choice functions. This chapter identifies a condition on the graph that characterizes LGE. Our notion of “localness” is perfectly general - we use this feature of our model to identify notions of localness according to which various models of multi-dimensional voting satisfy LGE. Finally, we show that LGE for deterministic social choice functions does not imply LGE for random social choice functions. Chapter 3 considers the same voting framework as in Chapter 2 except that each agent’s type is her weak preference, that is, preferences that can admit indifference. We provide a condition that is sufficient for LGE and another condition that is necessary. Moreover, the “gap” between the two conditions is small (in the sense that both conditions boil down to the single condition identified in Chapter 2 that characterizes LGE for the case of strict preferences). We use the sufficiency result to propose notions of localness according to which environments with the domain of single-plateaued preferences and the domain of all weak preferences, satisfies LGE. Chapter 4 identifies a condition on preference domains that ensures that every locally strategy- proof and unanimous random social choice function is also strategy-proof. Furthermore every unanimous, locally strategy-proof deterministic social choice function is also group strategy-proof. The condition identified is significantly weaker than the characterization condition for local-global equivalence without unanimity in Chapter 2. Chapter 5 considers standard mechanism design problem where a set of agents have valuations for each alternative in a finite set of alternatives. Based on these valuations, the planner has to select an alternative to be shared by all the agents and some payment for each agent. Such a decision scheme is called a 2 mechanism. Agents evaluate their net utilities by means of quasilinear utility functions. A mechanism is incentive compatible (IC) if no agent can increase his/her net utility by misreporting his/her type. We explore the equivalence of pointwise local incentive compatibility (PLIC) (as defined in Carroll [12]) and incentive compatibility (IC) in non-convex type-spaces. We provide a sufficient condition on a type-space called minimal richness for the said equivalence. Using this result, we show that PLIC and IC are equivalent on large class of non-convex type-spaces such as type-spaces perturbed by modularity and concave-modularity. The gross substitutes type-space and the generalized gross substitutes and complements type-space are important examples of type-spaces perturbed by modularity and concave-modularity, respectively. Finally, we provide a geometric property consisting of three conditions for the equivalence of PLIC and IC, and show that all the conditions are indispensable. Chapter 6 studies standard mechanism design problems when agents have quasi linear utility function. We consider ordinal type-spaces, that is, possible valuations of each agent come from an underlying preference structure. This chapter explores the relation between different notions of local incentive compatibility (LIC) and incentive compatibility (IC) on ordinal type-spaces. In this context, we introduce the notion of ordinal local global equivalent (OLGE) and cardinal local global equivalent (CLGE) environments. First, we establish the equivalence between the two environments on strict ordinal type-spaces. Next, we consider ordinal type-spaces admitting indifference. We introduce the notion of almost everywhere IC and strong LIC, and provide a necessary and sufficient condition on ordinal type spaces for their equivalence. Finally, we provide results on how to (minimally) check the IC property of a given mechanism on any ordinal type-space and show that local types along with the boundary types form a minimal set of incentive constraints that imply full incentive compatibility.