Research

We consider a group of voters that needs to decide between two candidates. We propose a novel family of neutral and strategy-proof rules, which we call sequential unanimity rules. By demonstrating their formal equivalence to the M-winning coalition rules of Moulin (1983), we show that sequential unanimity rules are characterized by neutrality and strategy-proofness. We establish our results by developing algorithms that transform a given M-winning coalition rule into an equivalent sequential unanimity rule and vice versa. The analysis can be extended to accommodate the full preference domain in which voters may be indifferent between candidates.


Consider a setting in which individual strict preferences need to be aggregated into a social strict preference relation. For two alternatives and an odd number of agents, it follows from May’s Theorem that the majority aggregation rule is the only one satisfying anonymity, neutrality and strategy-proofness (SP). For more than two alternatives, anonymity and neutrality are incompatible for many instances and we explore this tradeoff for strategy-proof rules. The notion of SP that we employ is Kemeny-SP (K-SP), which is based on the Kemeny distance between social orderings and strengthens previously used concepts in an intuitive manner. Dropping anonymity and keeping neutrality, we identify and analyze the first known nontrivial family of K-SP rules, namely semi-dictator rules. For two agents, semi-dictator rules are characterized by local unanimity, neutrality and K-SP. For an arbitrary number of agents, we generalize semi-dictator rules to allow for committees and show that they retain their desirable properties. Dropping neutrality and keeping anonymity, we establish possibility results for three alternatives. We provide a computer-aided solution to the existence of a locally unanimous, anonymous and K-SP rule for two agents and four alternatives. Finally, we show that there is no K-SP and anonymous rule which always chooses one of the agents’ preferences.

Vulnerability to manipulation is a threat to successful matching market design. However, some manipulation is often inevitable and the mechanism designer wants to compare manipulable mechanisms and pick the best. Real-life examples include reforms in the entry-level medical labor market in the US (1998), school admissions systems in New York (2004), Chicago (2009-2010), Denver (2012), some cities in Ghana (2007-2008), and England (2005-2010). We provide a useful criterion for these design decisions: we count the number of agents with an incentive to manipulate each mechanism under consideration during these reforms, and show that this number decreased as a result of the reforms. Our conclusion is robust to further additional strategic assumptions. 

 This paper studies a decentralized college admissions game with single application motivated by college admissions in many countries such as Japan, Russia, South Korea and United States. Students sequentially apply to colleges, one application for each student, and commit to attend whenever they are admitted. We introduce a natural equilibrium refinement and describe the equilibrium behavior. It is a simple strategy that consists of running the well-known student-proposing deferred acceptance algorithm for modified preferences. This game offers an alternative for solving important difficulties in college admissions. In particular, its outcomes according to the refinement are more efficient than deferred acceptance that is used for centralized college admissions.

Dozens of school districts and college admissions systems around the world have reformed their admissions rules in the recent years. As the main motivation for these reforms the policymakers cited the strategic flaws of the rules in place: students had incentives to game the system. However, after the reforms, almost none of the new rules became strategy-proof. We explain this puzzle. We show that the rules used after the reforms are less prone to gaming according to our criterion called “strategic accessibility”: each reform expands the set of schools wherein each student can never get an admission by manipulation. We also show that the existing explanation of the puzzle due to Pathak and Sonmez (2013) is incomplete.

Recently, many matching systems around the world have been reformed. These reforms responded to objections that the matching mechanisms in use were unfair and manipulable. Surprisingly, the mechanisms remained unfair even after the reforms: the new mechanisms may induce an outcome with a blocking student who desires and deserves a school which she did not receive.

However, as we show in this paper, the reforms introduced matching mechanisms which are more fair compared to the counterfactuals. First, most of the reforms introduced mechanisms that are more fair by stability: whenever the old mechanism does not have a blocking student, the new mechanism does not have a blocking student either. Second, some reforms introduced mechanisms that are more fair by counting: the old mechanism always has at least as many blocking students as the new mechanism.

These findings give a novel rationale to the reforms and complement the recent literature showing that the same reforms have introduced less manipulable matching mechanisms. We further show that the fairness and manipulability of the mechanisms are strongly logically related.

We introduce a class of rules for combining individual preferences over a set of alternatives into a collective ordering. Each of these augmented serial rules is parametrized by a list of agents (with possible repetition) and a committee voting rule. For a given preference profile, the collective ordering is determined as follows: The first agent's most preferred alternative becomes the top-ranked alternative in the collective ordering, the second agent's most preferred alternative (among those remaining) becomes the second-ranked alternative and so on until two alternatives remain --- which are ranked by the committee voting rule.

The main result establishes that these rules are succinctly characterized by neutrality and strategy-proofness under the lexicographic extension. Additional results show that these rules are strategy-proof under a variety of other reasonable preference extensions.

In 2009, the French Ministry of Higher Education implemented a centralized clearinghouse aimed at improving the matching of students to university school programs. In the French system, there are selective schools (which assign priority based on the student’s academic performance) and non-selective schools (which assign priority based on proximity to the student’s high-school district). Needless to say, the coarse priority used by non-selective schools creates many ties. In school choice, the popular practice is to break ties in the school priorities at random before applying deferred acceptance. The French system departs from this practice by relying on the students’ reported preferences to break ties (before applying deferred acceptance). While the French mechanism is manipulable, we show that it is less manipulable than the Boston mechanism. We show that in the environment of correlated preferences and correlated priorities, the equilibrium outcomes of the French mechanism are more efficient than deferred acceptance with random tie breaking (while the equilibrium outcomes of the Boston mechanism are not). Selective schools are also concerned with recruiting a qualified student body. To address this concern, we formulate a no strategic accessibility requirement, that no student be able to obtain a seat at a selective school via manipulation. We prove that the French mechanism satisfies this requirement. Additional results show that some transformations of ties into strict priorities induce mechanisms which become less manipulable on the domain of correlated preferences and for which schools become less strategically accessible.