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

Kumar, Ujjwal and Roy, Souvik (2025): On the Equivalence of Strategy-proofness and Directed Local Strategy-proofness under Preference Extensions.

Abstract

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.

• Item Type: MPRA Paper
• Language: English
• Keywords: Local strategy-proofness; (global) strategy-proofness; directed-local-global-equivalence; lexicographic preference extension function
• Subjects: D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations

References

ALTUNTA S¸ , A., W. PHAN, AND Y. TAMURA (2023):“Some characterizations of generalized top trading cycles,” Games and Economic Behavior.

CARROLL, G. (2012): “When are local incentive constraints sufficient?” Econometrica, 80, 661–686.

CHO, W. J. AND C. PARK (2023): “The Local-global Equivalence on General Networks,” https://papers.ssrn.com/sol3/papers.cfm? abstract_id=4551159, unpublished manuscript.

KUMAR, U., S. ROY, A. SEN, S. YADAV, AND H. ZENG (2021): “Local-global equivalence in voting models: A characterization and applications,” Theoretical Economics, 16, 1195–1220.

MISHRA, D., A. PRAMANIK, AND S. ROY (2016): “Local incentive compatibility with transfers,” Games and Economic Behavior, 100, 149–165.

MOULIN, H. (1980): “On strategy-proofness and single peakedness,” Public Choice, 35, 437–455.

SATO, S. (2013): “A sufficient condition for the equivalence of strategy-proofness and nonmanipulability by preferences adjacent to the sincere one,” Journal of Economic Theory, 148, 259–278.