On the Equivalence of Strategy-proofness and Directed Local Strategy-proofness under Preference Extensions

We consider a model in which outcomes are bundles of alternatives, each of size at most a fixed (but arbitrary) number. Each agent's type is a strict preference over individual alternatives, which is then lexicographically extended to induce a strict preference over outcomes. A social choice function assigns an outcome to each type profile of agents. A social choice function is said to be locally strategy-proof if no agent can benefit by misreporting her type to another type that the designer considers plausible. The main departure from existing literature lies in the asymmetry of type misreports, which is captured using a directed graph that encodes the designer’s beliefs about feasible misreports. An environment is said to satisfy Directed-Local-Global Equivalence (DLGE) property if every locally strategy-proof social choice function defined on it is, in fact, (globally) strategy-proof. In this paper, we provide a complete characterization of DLGE environments via a property we refer to as Property Strong DL. Additionally, we derive necessary and sufficient conditions for DLGE under several specific notions of locality, such as adjacent, k-push-up, k-push-down, and k_1-push-up and k_2-push-down (some of which were studied in Altuntaș et al. (2023)) both in the setting where outcomes are individual alternatives and where any subset of alternatives may constitute a feasible outcome. Our analysis also extends to single-peaked domains as well. The main result in Cho and Park (2023) and several main results in Altuntaș et al. (2023) follow as corollaries of our framework.