We introduce a new mechanism for one-sided matching markets, inspired by procedures currently being used to match millions of students to public universities in Brazil and China. Unlike most options available in the literature, where students are asked for a full preference ranking over all colleges, they are instead sequentially asked to make choices among sets of colleges. These choices are used to produce, in each step, a tentative allocation. If at some point it is determined that a student cannot be accepted into a college, then she is asked to make another choice among those which would tentatively accept her. Participants following the simple strategy of choosing the most preferred college in each period is a robust equilibrium which yields the Student Optimal Stable Matching. We analyze the mechanism currently being used in Brazil and, based on data from 2016, we provide evidence that it suffers from shortcomings: it fails to provide reliable information to the students about the universities that they are able to attend; and it is subject to manipulation via cutoffs, a new type of strategic behavior. We also provide an extension in which after running the sequential mechanism for a number of steps students are asked to submit a ranking over the colleges that are still within reach. This constitutes a novel approach to matching mechanisms. We show that the initial sequential stage clears a substantial part of the market before the rankings submission. This finding, together with empirical and simulation results, makes our proposal an attractive alternative to sequential mechanisms currently being used and the standard Gale-Shapley Deferred Acceptance mechanism for practical applications.
In August 2012 the Brazilian federal government enacted a law mandating the implementation of affirmative action policies in public federal universities for candidates from racial minorities, low-income families, and those coming from public high schools. We show that the method proposed by the government transforms the students' affirmative action status into a strategic choice, and may in fact create situations where high-achieving students who belong to those groups are not accepted to a university they desire while a low-achieving student who does not belong to those groups is accepted. Data from university admissions in more than 3,000 programs in 2013 show evidence consistent with this type of unfairness in more than 49% of those programs' assignments. We propose a choice function for the colleges that removes any gain from strategizing over the privileges claimed, is fair and, under reasonable assumptions on the type distribution of the population, fully satisfies the diversity objectives expressed by the law. We also propose an incentive-compatible mechanism that matches students and colleges with the use of the proposed choice function.
In this paper we evaluate the policy goal of maximizing the number of individuals matched to individually rational assignments in matching markets. We show that assignment maximization is incompatible with both strategy-proofness and fairness, and impossible in equilibrium. We introduce two classes of mechanisms that maximize the number of assigned agents: the Efficient Assignment Maximizing mechanisms (EAM) and the Fair Assignment Maximizing mechanisms (FAM). EAMs maximize assignments and are Pareto efficient. We characterize the unique equilibrium of EAMs, which is Pareto efficient, and show that no mechanism can dominate – in terms of number of assignments – EAMs in equilibrium. FAMs maximize assignments and are fair for unassigned students (a weaker notion of fairness). We show that in equilibrium FAMs assign to schools weakly more than the number of students matched in any stable mechanism. We also provide some comparison of well-known mechanisms in terms of number of assignments and test our theoretical results by conducting computer simulations. Those show that the difference between the number of matched agents by EAM/FAM and other mechanisms in the literature is large and significant.
We consider a simple model of the competitive screening of students by schools and colleges. Students apply to schools which then perform costly screening procedures of the applicants to select those with high ability. Students who receive more than one offer may choose among those. Colleges select students and can observe the school which they attended. We show a channel through which students' preferences affect schools' screening decisions and outcomes: as schools increase the screening for high-ability students, a greater proportion of them is identified as such by multiple schools and are able to select one among them to attend. Schools' marginal gains from screening therefore depend on other schools' screenings and students' preferences. By focusing on the schools' screening choices (instead of the students' application decisions), we show how the competition for students between schools and colleges affect outcomes and students' welfare. We also show that, simply by observing which school a candidate attended, colleges can ``free-ride'' on the information produced by a fierce competition between schools for those students. Finally, we show that although colleges make full use of the information contained in the school a student attended, the extent to which students can improve the college that they are matched to by going to a (less desired) high-ranked school is fairly limited.
We run laboratory experiments where subjects are matched to colleges, and colleges are not strategic agents. We test the Gale-Shapley Deferred Acceptance (DA) mechanism versus the Iterative Deferred Acceptance Mechanism (IDAM), a matching mechanism based on a new family of procedures being used in the field, in which information about tentative allocations is provided while students make choices. We consider two variations of IDAM: one in which students are informed at each step of the tentative cutoff values for acceptance at each school (IDAM) and one in which they are only informed about whether they are tentatively accepted or not (IDAM-NC). A significantly higher proportion of stable outcomes is reached both under IDAM and IDAM-NC than under DA. The difference can be explained by a higher proportion of subjects following an equilibrium strategy akin to truthful behavior under IDAM and IDAM-NC than truthful behavior itself under DA. Moreover, the provision of intermediate cutoff values in IDAM leads to higher rates of equilibrium behavior than in IDAM-NC. Our findings provide substantial support for the rising practice of using sequential mechanisms in centralized college admissions in practice.
Ergin and Sönmez (2006) showed that for schools it is a dominant strategy
to report their preferences truthfully under the Boston mechanism,
and that the Nash equilibrium outcomes in undominated strategies of
the induced game are stable. We show that these results rely crucially
on two assumptions. First, schools need to be restricted
to reporting all students as acceptable. Second, students cannot observe
the preferences reported by the schools before submitting their own
preferences. We show that relaxing either assumption gives schools
an incentive to manipulate their reported preferences. We provide
a full characterization of undominated strategies for schools and
students for the simultaneous move game induced by the Boston mechanism.
Nash equilibrium outcomes in undominated strategies of that game may
contain unstable matchings. Furthermore, when students observe schools'
preferences before submitting theirs, the subgame perfect Nash equilibria
of the sequential game induced by the Boston mechanism may also contain
unstable matchings. Finally, we show that schools may have an incentive
to manipulate capacities only if students observe the schools' strategies
before submitting their own preferences.
Many school districts have objectives regarding how students of different races, ethnicity or religious backgrounds should be distributed across schools. A growing literature in mechanism design is introducing school choice mechanisms that attempt to satisfy those requirements. We show that mechanisms based on the student-proposing deferred acceptance may fail to satisfy those objectives, but that by using instead the school-proposing deferred acceptance together with a choice function used by the schools, which incorporates a preference for satisfying them, can optimally approximate the diversity objectives while still satisfying an appropriate fairness criterion. We provide analytical results which show that the proposed mechanism has a general ability to satisfy those objectives, as opposed to some currently proposed mechanisms, which may yield segregated assignments.
This work presents the results of many multiagent simulations of the n-Player Prisoner's Dilemma, using two different languages to represent the agents' strategies: finite automata and adaptive automata. We consider that a comparative analysis of the coevolution of strategies using these two languages may be seen as a framework to analyze the role of the complexity of the strategy representation language on the individual and global results of the agents. Hence, the numerical results of the simulation were analyzed in order to answer two questions: (i) does the ability to use more complex strategies lead to a different outcome for the society? (ii) How does this ability affect the sustainability of the cooperation in a society?
Research in Progress
Designing Heaven's Will: Assigning Civil Servants by Drawing Lots in Imperial China (with Li Chen)