False-name-proof facility location on discrete structures

DOI10.3233/FAIA200097MaRDI QIDQ4999238zbMATH OpenOpenAlexFDO

Authors Taiki Todo, Nodoka Okada, Makoto Yokoo

Publication date 6 July 2021

Full work available at URL https://arxiv.org/abs/1907.08914

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Social choice (91B14)

Abstract: We consider the problem of locating a single facility on a vertex in a given graph based on agents' preferences, where the domain of the preferences is either single-peaked or single-dipped. Our main interest is the existence of deterministic social choice functions (SCFs) that are Pareto efficient and false-name-proof, i.e., resistant to fake votes. We show that regardless of whether preferences are single-peaked or single-dipped, such an SCF exists (i) for any tree graph, and (ii) for a cycle graph if and only if its length is less than six. We also show that when the preferences are single-peaked, such an SCF exists for any ladder (i.e., 2-by-m grid) graph, and does not exist for any larger hypergrid.

Recommendations

• Rename and false-name manipulations in discrete facility location with optional preferences
• Strategy-proof location on a network
• Strategy-proof location of public facilities
• Unfolding the mystery of false-name-proofness
• Strategy-proof location functions on finite graphs

Cited in

(6)

• Rename and false-name manipulations in discrete facility location with optional preferences
• Unfolding the mystery of false-name-proofness
• False-name-proof voting with costs over two alternatives
• Strategy-proof location functions on finite graphs
• False-name-proof and strategy-proof voting rules under separable preferences
• Parameterized voter relevance in facility location games with tree-shaped invitation graphs

This page was built for publication: False-name-proof facility location on discrete structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4999238)