False-name-proof matching

Matching a set of agents to a set of objects has many real applications. One well-studied framework is that of priority-based matching, in which each object is assumed to have a priority order over the agents. The Deferred Acceptance (DA) and Top-Trading-Cycle (TTC) mechanisms are the best-known strategy-proof mechanisms. However, in highly anonymous environments, the set of agents is not known a priori, and it is more natural for objects to instead have priorities over characteristics (e.g., the student's GPA or home address). In this paper, we extend the model so that each agent reports not only its preferences over objects, but also its characteristic. We derive results for various notions of strategy-proofness and false-name-proofness, corresponding to whether agents can only report weaker characteristics or also incomparable or stronger ones, and whether agents can only claim objects allocated to their true accounts or also those allocated to their fake accounts. Among other results, we show that DA and TTC satisfy a weak version of false-name-proofness. Furthermore, DA also satisfies a strong version of false-name-proofness, while TTC fails to satisfy it without an acyclicity assumption on priorities.

• Publication year

  2013

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2013-05-06

• Fields of study

  Computer Science

• Identifiers
  DOI 10.65109/hubo7828
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An alternative characterization of top trading cycles

  2013cited by this paper
• College Admissions and the Stability of Marriage

  2013cited by this paper
• Housing Markets with Indifferences: A Tale of Two Mechanisms

  2012cited by this paper
• False-name-proof mechanism design without money

  2011cited by this paper
• The Role of Priorities in Assigning Indivisible Objects : A Characterization of Top Trading Cycles

  2010cited by this paper
• Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

  2010cited by this paper
• Anonymity-Proof Voting Rules

  2008cited by this paper
• On two competing mechanisms for priority-based allocation problems

  2006influential reference
• The effect of false-name bids in combinatorial auctions: new fraud in internet auctions

  2004cited by this paper
• On Houseswapping, the Strict Core, Segmentation, and Linear Programming

  2004cited by this paper
• Efficient Resource Allocation on the Basis of Priorities

  2002cited by this paper
• Strategy-proofness and population-monotonicity for house allocation problems

  2002cited by this paper
• A Tale of Two Mechanisms: Student Placement

  1999influential reference
• Comparative statics in matching markets

  1991cited by this paper
• Partially Verifiable Information and Mechanism Design

  1986cited by this paper
• On cores and indivisibility

  1974cited by this paper

• Boost+: Equitable, Incentive-Compatible Block Building

  2026cites this paper
• Inequality in the Age of Pseudonymity

  2025cites this paper
• False-name-proof and strategy-proof voting rules under separable preferences

  2024influential citation
• Manipulation-resistant false-name-proof facility location mechanisms for complex graphs

  2022cites this paper
• Mechanism Design for Housing Markets over Social Networks

  2021cites this paper
• Personalised rating

  2020cites this paper
• Split Manipulations in Cost Sharing of Minimum Cost Spanning Tree

  2020cites this paper
• Mechanism Design with Uncertainty

  2020cites this paper
• SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location

  2019cites this paper
• False-Name-Proof Facility Location on Discrete Structures

  2019cites this paper
• The Complexity of Bribery in Network-Based Rating Systems

  2018cites this paper
• A False-Name-Proof Protocol for Multicast Routing Auctions

  2018cites this paper
• A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences

  2018cites this paper
• Rename and False-Name Manipulations in Discrete Facility Location with Optional Preferences

  2017cites this paper
• False-Name-Proof Locations of Two Facilities: Economic and Algorithmic Approaches

  2016cites this paper
• False-Name-Proof Recommendations in Social Networks

  2016cites this paper
• Fairness and False-Name Manipulations in Randomized Cake Cutting

  2015cites this paper
• A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences

  2015cites this paper
• Exchange of Indivisible Objects with Asymmetry

  2015cites this paper
• A study of sybil manipulations in hedonic games

  2014cites this paper
• False-name-proof Combinatorial Auction Design via Single-minded Decomposition

  2014cites this paper
• Strategyproof Exchange with Multiple Private Endowments

  2014cites this paper
• Fictitious students creation incentives in school choice problems

  2014influential citation
• Coexistence of utilitarian efficiency and false-name-proofness in social choice

  2014influential citation
• Etude des attaques Sybil sur les jeux hédoniques

  2013cites this paper