We introduce a new mechanism for matching students to schools or universities, denoted Iterative Deferred Acceptance Mechanism (IDAM), 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, IDAM is not a direct mechanism. Instead of requesting from each student a full preference over all colleges, the student is instead repeatedly asked to choose one college among those which would accept her given the current set of students choosing that college. Although the induced sequential game has no dominant strategy, when students simply choose the most preferred college in each period (denoted the straightforward strategy), the matching that is produced is the Student Optimal Stable Matching. Moreover, under imperfect information, students following the straightforward strategy is an Ordinal Perfect Bayesian Equilibrium. Based on data from 2016, we also provide evidence that, due to shortcomings which are absent in the modified version that we propose, the currently used mechanism in Brazil fails to assist the students with reliable information about the universities that they are able to attend, and are subject to manipulation via cutoffs, a new type of strategic behavior that is introduced by this family of iterative mechanisms and observed in the field.
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.
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.
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
Assignment Maximization (with Mustafa Oguz Afacan and Bertan Turhan)
Fair and consistent hiring by ranking and rules (with Azar Abizada)