Min Zhu

College Admissions in China: A Mechanism Design Perspective

Keywords: college admissions in China, mechanism design, experiment Classification: C70, C92, D63, D78

This paper justifies the evolution of the college admissions system in China from a mechanism design perspective. The sequential choice algorithm and the parallel choice algorithm used in the context of China's college admissions system are formulated as the well-studied Boston mechanism and the Simple Serial Dictatorship mechanism. We review both theoretical and experimental mechanism design literature in similar assignment problems. Studies show that the Boston mechanism does not eliminate justified envy, is not strategy-proof and is not Pareto-efficient. The Simple Serial Dictatorship mechanism eliminates justified envy, is strategy-proof and is Pareto-efficient, thus outperforming the Boston mechanism in all three criteria. This result provides justification for the transition in recent years from the sequential choice algorithm to the parallel choice algorithm in China's college admissions practices.

Introduction

College admission (also called "Gaokao") has been a widely debated topic in China. Each year, millions of high school graduates compete for college seats in the summer. The competition is described as "a stampede of a thousand soldiers and ten horses across a single log bridge". Being admitted by a college has profound implications for a student's outcome in the labor market in the future and even determines the course of a student's life.

College admissions in China are centralized processes via standardized tests. Each province has a student placement office that assigns high school graduates to colleges slots. This office organizes a National College Entrance Examination for students planning to attend the colleges and ranks the students according to test scores. Students are also asked to report a list indicating preferences over colleges. Given the ranking of students via test scores and their reported preferences over colleges, the student placement office assigns students to college slots under a specific algorithm. The sequential choice algorithm used for years has been criticized by the public for unfairness as students with high test scores may have worse assignments and poor incentive as students manipulate their true preferences. To fix these problems, variants of the parallel choice algorithm have been implemented in many provinces, starting with Hunan province in 2003. The key innovation for the parallel choice algorithm is that students can put several "parallel" colleges for each choice in decreasing desirability, which presumably reduces risk with first choices. Field data show that this type of algorithm has achieved great success, alleviating unfairness and incentive problems.

While the reform of the assignment algorithm in China's college admissions was developed through a trial and error process, we propose a mechanism design approach to provide justification for this evolution. Mechanism design is the art of designing institutions that align individual incentives with overall social goals [START_REF] Chen | Mechanism design experiments[END_REF]. Within the past decades, economists have benefited from mechanism design theory and its field applications, gaining understanding of how existing institutions have evolved. The mechanism design approach has also been used to provide advice on a handful of real-life assignment problems, such as the design of the FCC spectrum auction [START_REF] Mcmillan | Selling spectrum rights[END_REF][START_REF] Milgrom | Putting auction theory to work: The simultaneous ascending auction[END_REF], the redesign of an entry-level labor market for new doctors [START_REF] Roth | The redesign of the matching market for american physicians: Some engineering aspects of economic design[END_REF], and the redesign of public school allocations (Abdulkadirouglu et al., 2005a,b), etc. Such rich research on similar assignment problems can provide excellent insights on the evolution of China's college admissions system, as well as on how to improve the current admissions processes.

In this paper, we formalize the college admissions in China as a mechanism design problem and review the studies of mechanism design theories and experiments with similar assignment problems to make a systematic comparison of the two algorithms (mechanisms) used in China's college admissions. The comparison follows three criteria: elimination of justified envy, strategyproofness, and Pareto efficiency. Elimination of justified envy is a basic fairness axiom, which in this case means that a student with a better test score should be assigned to a more preferred college. Strategy-proofness is the central notion of incentive compatibility, which means that revealing true preference is a weakly dominant strategy for each student. Pareto efficiency is on the welfare issue, which means that no other assignment should be possible that would make every student weakly better off and at least one student strictly better off. The studies on similar assignment problems justify recent reforms and debates regarding China's college admissions practices: the Boston mechanism does not eliminate justified envy, is not strategy-proof and not Pareto-efficient; the Simple Serial Dictatorship mechanism has desirable properties for the elimination of justified envy, strategy-proofness, and Pareto-efficiency.

The review is organized as follows. In section 2, we review college admissions in China and its historical evolution through the assignment algorithms. In section 3, we formalize the college admissions system in China as a mechanism design problem and formally describe the assignment mechanisms (algorithms). In section 4, we review what the mechanism design theories and exper-iments have shown about the performances of the two mechanisms to provide justification for the evolution of the admissions processes. Section 5 presents the conclusion and some suggestions on how to improve the current system from a mechanism design perspective.

2 College Admissions in China 2.1 College Admissions in China as Centralized Processes

College admissions in China are centralized processes via standardized tests. In each province, there is a student placement office that assigns resident students to colleges. Students planning to attend college are asked to take the National College Entrance Examination, which lasts for two or three consecutive days every summer. This examination usually consists of four component tests: a mathematics test, a Chinese test, a foreign language test, and a comprehensive science test (physics, chemistry and biology) in science category, or a comprehensive art test (history, geography and politics) in art category. Then, the student placement office in a given province separately ranks students in two categories according to their aggregate scores on the four component tests. 1Each student is also asked to submit a lexicographic list to the student placement office, indicating her preference over colleges and, for each college, her preference over faculties (e.g., business at Peking University is preferred to engineering at Peking University, which is preferred to engineering at Tianjin University which is preferred to business at Tianjin University, etc.). Given the students' test scores and their reported preference lists, two independent steps are required to allocate slots to students: In the first step, the student placement office assigns students to colleges under a certain assignment algorithm; in the second step, faculties are allocated within assigned college under a certain assignment algorithm predetermined by each college. During the process, colleges are treated as public goods and have no say for admission decisions. 2This centralized process was established in 1952 by the National Ministry of Education after years of decentralized examinations and admissions. Prior to 1950, each college organized its own entrance examination and admission system to admit students. Like other decentralized processes, these college admissions systems suffered from a coordination problem: Some qualified students had no time to apply for ordinary colleges after being rejected by the top colleges, and some ordinary colleges could not admit enough students at the same time. To fix this problem, 73 colleges formed three regional alliances in 1950, and each alliance implemented a centralized process for admissions. Subsequently, the Ministry of Education decided to organize the first National College Entrance Examination and to assign students via national centralized processes.

The transition from decentralized processes to centralized ones in China is far from unique. Many markets for the allocation of indivisible and heterogeneous goods face similar failures and have been fixed by the design of appropriate centralized clearing houses [START_REF] Roth | What have we learned from market design?[END_REF]. A representative example is the entry-level labor market for new doctors in the United States. The market for new doctors long suffered from the problem of the unraveling of appointment dates, in which offers by hospitals were made far in advance of actual employment, and later the problem of congestion, in which hospitals and new doctors had no time to accept and reject offers [START_REF] Roth | The evolution of labor market for medical interns and residents: A case study in game theory[END_REF]. Such market failures led to a reorganization of the market by means of a centralized clearing house, which then effectively resolved the problem.

The Evolution of College Admission Algorithms in China

College admissions in China proceed sequentially in tiers. Colleges are categorized into different tiers in decreasing prestige:Key colleges (i.e., National 985 and 211 universities) belong to the first tier and admit students first; ordinary colleges belong to the second tier; and vocational training colleges are included in the third tier. Only when assignments in the first tier are finalized,admissions in the second tier start, and so on. During the whole process, a certain algorithm is executed across tiers which is predetermined by each province. The assignment algorithm that has been used for years in China's college admissions is called the sequential choice algorithm. In each tier, the algorithm works as follows: in the first round, all students compete for their first choice colleges; in the second round, students rejected in the first round compete for their second choice colleges, if those colleges have available slots, and so forth, until all chosen colleges are considered for unassigned students or there is no available college slot in the current tier. Under the sequential choice algorithm, allocation of college slots is primarily determined by the reported preferences of students: For a given college, slots are allocated among students who rank it the same in their preference lists, but students who rank it highly in the preference list have strict priority over those who do not.

This sequential choice algorithm has been criticized by the public for years for some serious deficiencies. The main criticism is the unfair assignments that the algorithm may generate. For instance, it is possible for students with higher test scores to receive worse assignments than those with lower test scores. This phenomenon is prevalent under the sequential choice algorithm. Each year, many stories such as the following can be found in the news after the end of college admissions: 3 My son participated in this year's college admissions. His test score was 658, which is higher than the cut-off score for the previous years of his first choice college. However, this year's cut-off score for his first choice college was 660, so he was rejected by his first choice college. As other choice colleges are filled and not accepted him, in the end, my son failed to be admitted by any good college although his test score is high enough for admission. He was so frustrated that he decided to quit it.

Empirical evidence further illustrates the severity of the problem: For example, in 2005, over 800 students failed to be admitted by first-tier colleges in Gansu province [START_REF] Nie | A game theoretic analysis of college admissions[END_REF].

By the sequential choice algorithm, students also take a risk in listing their first choices. If a student is rejected by her first choice college, she is very likely to be rejected by the next choice colleges as these colleges are filled with students who list them higher in their preference lists. Students therefore have to think over other students' strategies, carefully choosing safe college as the first choice and thus ensuring a higher chance of being admitted. Consequently, they are forced to play a complicated admission game induced by the sequential choice algorithm, and usually it is beneficial for them to manipulate their true preferences. This point has also been advocated by some researchers working on college admissions reform4

The sequential choice algorithm emphasizes the choices students make. Whether they are accepted by colleges does not only depend on students' own test scores, but also on how other students make choices.

The Ministry also provides some advice on how to strategize in the sequential choice algorithm on its official website for college admissions:5

Students should carefully make their first choices, choosing colleges for which their test scores are above the average of the past year's admission scores if the colleges have had stable admission scores in the past three years, and in the upper bound of the past year's admission scores if the colleges have had unstable admission scores in the past three years.

Students should have safe colleges for their second choices. The second choice colleges should be among those that had available slots in the second rounds in the previous years, so that students still have a chance of being admitted by their second choice colleges even if rejected by their first choice colleges.

To alleviate unfairness and students' incentive to game the system under the sequential choice algorithm, the education department in Hunan province became the first, in 2003, to replace the sequential choice algorithm with a new algorithm involving parallel choice. Later in 2005 and in 2007, this parallel choice algorithm was also introduced separately in Jiangsu province and Zhejiang province. Parallel choice means that students can list several "parallel" colleges in decreasing desirability for each choice. For example, a student's first choice could contain three colleges: Peking University, Tianjin University, and Xiamen University. Thus, among all parallel colleges, the assignment algorithm works as follows: The student with the highest test score is assigned to her first listed college in the reported preference list; and then the student with the next highest test score is assigned to her first listed college if it has available slots; if the college has no vacancy, this student is sent to her second listed college, and so forth, until all her parallel colleges have been considered. In this way, each college slot is sequentially allocated from the student with the highest test score to the student with the lowest test score.

In contrast to the sequential choice algorithm, the parallel choice algorithm values the ranking of students via test scores over their reported preferences. Thus, under the parallel choice algorithm, the priority for a college is given to students with high test scores, not to those who rank it highly in their preference lists. Empirical evidence shows that the implementation of the parallel choice algorithm greatly alleviates the problem of students with high test scores not being admitted to any college. For example, there was an 11.31 % and 6.71 % decreases from 2007 to 2008 in the number of students in science and art categories in Shanghai who fail to be admitted by first-tier colleges, with 2008 being the first year Shanghai implemented the parallel choice algorithm. 6The parallel choice algorithm also reduces risk in the listing of first choice colleges. As the parallel choice algorithm screens all of a student's parallel colleges before going to the next ranked student, more than one college is considered, which increases the student's chance of being admitted. This presumably reduces students' incentive for manipulation. The parallel choice algorithm is praised by one student in Shanghai when it is implemented in the first year:7 It really takes a risk for me to list Peking University as first choice. But thanks to the parallel choice algorithm, I could give Peking University a try. And the result was not so bad. Even though I failed to be admitted by Peking University, Fudan University accepted me in the end. This can be observed in changes to the advice given to students on the National Ministry of Education's official website for college admissions:8

When ranking colleges at a parallel choice, students can take a risk with the first listed college, list a proper college in the second position, and have safe colleges for other positions.

Due to the success of the parallel choice algorithm, the Chinese National Ministry of Education started in 2008 to endorse this algorithm nationwide. By 2013, 27 provinces have replaced the sequential choice algorithm with various forms of a parallel choice algorithm.

Thus far, we have reviewed China's college admissions processes, problems with the sequential choice algorithm and how the system evolved to resolve the problems through the introduction of a new algorithm. The evolution of the college admissions system has progressed through a "trial and error" process. A certain reform is first implemented in some small regions. If this reform succeeds, policy makers then promote it in broader regions and even nationwide. In this paper, however, we propose a mechanism design approach to provide justification for this evolution. Given the insights into the evolution of institutions that have been gained from mechanism design theory and its field applications, we believe this approach is helpful for analyzing some critical issues in the college admission problem in China.

3 The Mechanism Design Model

Mechanism Design and Matching

While traditional economic theory assumes institutions as a given, mechanism design, on the other hand, concerns itself with the question: "what is an optimal institution?" Using theoretical, experimental and empirical studies of economic systems, mechanism design not only provides insights into whether an institution can achieve desirable outcomes but also addresses the design of real-life institutions. The mechanism design approach has been successfully applied in many major domains of economics, including public goods, voting system, contract design, auction, and matching.

How to assign students to colleges is one type of matching problem. Matching is the part of economics concerned with who transacts with whom and how, particularly when scarce goods to be allocated are heterogeneous and indivisible [START_REF] Niederle | matching and market design[END_REF]. Typical matching markets include skilled labor markets in which skilled workers are matched with jobs (e.g., entry-level labor markets for new doctors, law school graduates, economics graduates, etc.), or situations in which indivisible objects with no price involved are allocated or exchanged (e.g., positions in public schools, courses, dormitory rooms, transplant organs, etc.).

China's college admissions system is closely related to the student placement problem in the literature on matching, which was proposed by [START_REF] Balinski | A tale of two mechanisms: Student placement[END_REF] in their study of the Turkish college admissions procedure. Like in China, the college admissions system in Turkey also uses a centralized clearing house to assign students to colleges. There is a central authority that offers a number of standardized tests and ranks students in a number of skill categories according to test scores. Each student is required to submit a preference list of faculties in colleges she is willing to attend. The authority then assigns students to college slots using a certain assignment mechanism. The only difference between the two processes is that, in Turkey, different colleges (or skill categories) have different priority rankings for students while, in China, all the colleges have the same priority ranking.9 In fact, China's college admissions system can be treated as a special case of student placement problem with one skill category.

Another two related problems are the college admission problem [START_REF] Gale | College admissions and the stability of marriage[END_REF] and the school choice problem [START_REF] Abdulkadirouglu | School choice: A mechanism design approach[END_REF], which have been extensively studied in matching literature with findings successfully applied in some entry-level labor markets and the allocation of public school seats in Boston and New York City. [START_REF] Sonmez | Matching, allocation, and exchange of discrete resources[END_REF] have made a systematic classification of three similar problems: In the college admissions problem, both students and colleges are strategic agents who have preferences over the other side and whose welfare are taken into consideration. Meanwhile, in the student placement problem and in the school choice problem, the only strategic agents are students, and colleges are merely objects to be consumed, having no preferences over students. However, in the latter two problems, colleges have priority rankings for students, which can be treated as the colleges' preferences in the associated college admissions problem. The key difference between the student placement problem and the school choice problem is related to the priority ranking of students. In the student placement problem, colleges' priority rankings are strictly determined by the score profiles of students, which play a central role, while in the school choice problem, priority rankings are exogenously determined by geography and demographics, which usually have lots of ties.

Formal Model

We next formulate China's college admissions system from a mechanism design perspective, providing mathematical definitions for some important notions to be discussed.

A China's college admission problem consists of the following: 1. a finite set of students S = {s 1 , ..., s n }, with a general element in S denoted by s. 2. a finite set of colleges C = {c 1 , ..., c m } ∪ {∅}, where ∅ denotes a student's outside option, or so-called null college. A general element in C is denoted by c.

3. a quota vector q = (q c 1 , ..., q cm ) ,where q c is the quota of college c. Also let q ∅ = ∞. 4. a list of strict student preferences P = (P s ) s∈S where P s is a strict preference relation of student s over colleges and no-college option.

5. a vector of students' test scores t = (t s ) s∈S where t s is the test score of student s, and there is no other student s ∈ S\{s} such that t s = t s . This will induce a strict ranking of students.

Let R s denote the at-least-as-good-as relation associated with P s . Formally, we assume that R s is a linear order, i.e., a complete, transitive, anti-symmetric binary relation on C. That is, for any c, c ∈ C, cR s c if and only if c = c or cP s c . We sometimes write P s : c 1 c 2 c 3 to denote that student s prefers college c 1 to college c 2 to college c 3 . And s 1 -s 2 -s 3 represents the strict ranking of students via test scores in which s 1 is ranked first, s 2 is ranked second and s 3 is ranked third.

Thus a China's college admission problem is a pair (P = (P s ) s∈S , t = (t s ) s∈S ). Let R be the set of all problems. A matching is an allocation of college slots to students such that no student occupies more than one college slot. Formally, it is a function µ : S → C, such that |µ -1 (c)| ≤ q c for all c ∈ C. Let M be the set of all matchings. A mechanism ϕ is a systematic procedure that determines a matching for each China's college admission problem. Formally, it is a function ϕ : R → M. Let ϕ(P, t) denote the matching chosen by ϕ for problem (P, t) and let ϕ s (P, t) denote the assignment of student s at this matching.

This model is simplified compared to its real-life counterpart. First, in real-life practice, each province has an independent process. Prior to the examination, colleges allocate quotas for students in each province, which are fixed in the process, and students in a given province only compete with each other. This model considers college admission in a given province where quotas are fixed. Second, there exist students with the same aggregate test score. Colleges use additional rules to break ties, such as ranking these students according to their mathematics scores or their comprehensive science scores. As a result, we still have a strict ranking for admissions. The last concern is the limit in the number of colleges students can submit on their preference list. Students are usually allowed to submit a preference list containing up to 16 colleges and up to 6 faculties for each college. This constraint influences students' behavior [START_REF] Haeringer | Constrained school choice[END_REF]. However, in this model, we assume that student will submit a complete list of colleges, and we leave the constrained case for future research. We next formally describe the two algorithms used in China's college admission as mechanisms.

The Sequential Choice Algorithm

The sequential choice algorithm is the Boston mechanism with tiers [START_REF] Chen | From boston to chinese parallel to deferred acceptance:theory and experiments on a family of school choice mechanisms[END_REF], which is the popular and widely debated mechanism in the school choice problem. For simplicity we consider the case with one tier10 , which is equivalent to the Boston mechanism and can be formalized as follows: Rank all the students from highest to lowest according to their test scores.

Round 1: For each college, only consider the students who have listed it as their first choice; assign slots to these students according to the ranking until all slots are filled and reject the rest students. Round 2: The rejected applications are sent to their second choice colleges; if a college still has available slots remaining from Round 1, it accepts the students highly ranked until all slots are filled, and the remaining students are rejected. ... In general at Round k: The students who are rejected by their k-1 choice are sent to their kth choice colleges; if a college still has available slots remaining from Round k -1, it accepts the students highly ranked until all slots are filled, and the remaining students are rejected.

This algorithm terminates when all students have been matched or when no college slots remain.

The following example demonstrates how the algorithm works.

Example 1. Let S = {s 1 , s 2 , s 3 , s 4 , s 5 } be the set of students, C = {c 1 , c 2 , c 3 } be the set of colleges, and q = (1, 2, 1) be the college capacity vector, t = (90, 55, 40, 70, 80) be the vector of students' test scores. Thus the ranking of students is s 1 -s 5 -s 4 -s 2 -s 3 . Students' true preferences are as follows:

s 1 : c 1 c 3 c 2 s 2 : c 2 c 1 c 3 s 3 : c 2 c 1 c 3 s 4 : c 1 c 3 c 2 s 5 : c 1 c 2 c 3
Student s 1 prefers c 1 to c 3 to c 2 . The same goes for the other students. Suppose all student submit their true preferences. In that case, the algorithm works as follows:

Round 1: a. Only the first choices of students are considered. For college c 1 , student s 1 , s 4 and s 5 are considered. For college c 2 , student s 2 and s 3 are considered. For college c 3 , no students are considered because no student chooses it as first choice. b. Then each college slot is allocated to these chosen students according to their ranking until the college's capacity is reached.

For college c 1 , the ranking is s 1 -s 5 -s 4 , and there is one slot available in college c 1 . Thus student s 1 is assigned to college c 1 , student s 5 and s 4 are rejected. Similarly, both s 2 and s 3 are assigned to college c 2 . Round 2:

a. Rejected student s 5 and s 4 are sent to their second choice colleges. b. As there is no slot left in college c 2 , student s 5 is rejected directly and sent into the next round. Student s 4 is assigned to her second choice college c 3 .

As there is no available college slot, student s 5 is left with no match. The algorithm terminates. Therefore, the outcome (matching) is:

s 1 s 2 s 3 s 4 s 5 c 1 c 2 c 2 c 3 0
The main idea of using this mechanism is to give students their first choices to the greatest extent possible. This is intuitively represented in the Chinese name for the mechanism: "preference first". This mechanism is, in fact, a priority matching mechanism [START_REF] Roth | A natural experiment in the organization of entry-level labor markets: Regional markets for new physicians and surgeons in the united kingdom[END_REF]: Any studentcollege pair that ranks each other first has the highest match priority and such a match is referred to as a (1, 1) match. Similarly a (k, l) match is a match in which the student ranks the college k th in her preferences and she has the l th priority at the college. The sequential choice mechanism first forms any feasible (1, 1) match, next any feasible (1, 2) match up to any feasible (1, n) match, next any feasible (2, 1) match, next any feasible (2, 2) match up to any feasible (2, n) match, next any feasible (3, 1) match, and so on, with the last pair in the hierarchy being any feasible (m, n) match. Obviously the match priority is lexicographic under the sequential choice mechanism: It first considers the students' preferences and only then the ranking of students via test scores.

The Parallel Choice Algorithm

The parallel choice algorithm is, in fact, the Simple Serial Dictatorship mechanism with tiers [START_REF] Wei | A design for college and graduate school admission[END_REF]. For simplicity, we consider the case with one tier, making it equivalent to the Simple Serial Dictatorship mechanism, which can be formalized as follows: Rank all the students from highest to lowest according to their test scores.

Round 1: a. Only consider the first student in the ranking. b. For this first student, assign her first choice. c. This student and her assignment are removed from the system. Round 2:

a. Only consider the second student in the ranking. b. For this second student, assign her first choice among the remaining college slots. c. This student and her assignment are removed from the system. ... In general at Round k:

a. Only consider the kth student in the ranking. b. For this kth student, assign her first choice among the remaining college slots. c. This student and her assignment are removed from the system. This algorithm terminates when all students have been matched or when no college slots remain.

The following example demonstrates the algorithm.

Example 2. (Using the same notations as in Example 1) Suppose all students submit their truthful preferences. In that case, the algorithm works as follows:

Round 1: a. Only consider student s 1 , the first student in the ranking. b. For s 1 , assign her first choice c 1 . c. This student s 1 and her assignment c 1 are removed from the system. Round 2:

a. Only consider the second student s 5 in the ranking. b. For s 5 , as her first choice c 1 is filled, assign her first choice among the remaining college slots, which is c 2 . c. This student s 5 and her assignment c 2 are removed from the system.

Similarly, in Round 3, third ranked student s 4 is assigned her first choice among the remaining college slots, which is c 3 ; in Round 4, fourth ranked student s 2 is assigned to c 2 ; and in Round 5, last ranked student s 3 is left with no match.

Therefore, the outcome (matching) is:

s 1 s 2 s 3 s 4 s 5 c 1 c 2 0 c 3 c 2
This mechanism allows the students to be sequentially assigned to their first choices among the remaining college slots. So, in contrast to the sequential choice mechanism, the parallel choice mechanism first considers the ranking of students via test scores and only then their preferences.

What is the Optimal Mechanism?

In the economics literature, assignment mechanisms are generally evaluated based on three criteria. The primary criterion is the elimination of justified envy, which is a basic fairness axiom in problems of priority-based indivisible goods allocation [START_REF] Abdulkadiroglu | Matching markets: Theory and practice[END_REF]. A matching eliminates justified envy if no students s and s exist such that µ(s )P s µ(s) and t s > t s . That is, in the context of China's college admissions, a student with a better test score should be assigned to a more preferred college. A mechanism eliminates justified envy if it always selects a matching that eliminates justified envy. Normatively, students with identical rights should have equal chances for admission; thus, students with higher priority should have higher chances for admission. Correspondingly, if a student prefers another college to her assignment and this more preferred college has admitted some student who has lower test score than her, it is regarded as unfairness. In the school choice problem, such students can take justified legal action against the school district. This is why the criterion is called elimination of justified envy. Although students in China's college admissions processes have no right to take legal action in cases of justified envy, long-time criticism of unfair assignments has led directly to the replacement of the sequential choice mechanism with the fair parallel choice mechanism.

The second criterion is strategy-proofness. A mechanism ϕ is strategy-proof if there is no student s such that ϕ s (R s R -s )P s ϕ s (R s R -s ). [START_REF] Azevedo | Strategyproofness in the large as a desideratum for market design[END_REF] give five reasons for why strategy-proofness is appealing in mechanism design practice: First, strategy-proof mechanisms are detail free for the designer. Second, strategy-proof mechanisms are strategically simple for participants. Third, with this simplicity comes a measure of fairness, i.e., agents' outcomes do not depend on their ability to game the system. Fourth, strategy-proof mechanisms can generate information about participants' true preferences that may be useful to policy makers. Fifth, Bayesian approaches have simply not yet proven tractable for a number of important market design problems. As a result, under a strategy-proof mechanism, students do not have to form belief about others' behaviors and calculate their best response, which provides simplicity and security for everyone. This is especially important in a market with an extremely large number of participants as in China's college admissions because, with such a large population, it is impossible to coordinate on Nash equilibrium [START_REF] Sonmez | Matching, allocation, and exchange of discrete resources[END_REF]. Additionally, as students' outcomes do not depend on their ability to game the system, the strategy-proof mechanism levels the playing field.

The third criterion is Pareto efficiency. A matching µ is Pareto efficient if there is no other matching µ such that µ (s)R s µ(s) for all s ∈ S and µ (s )P s µ(s ) for some student s ∈ S. A mechanism ϕ is Pareto-efficient if it always chooses Pareto-efficient matching. In China's college admissions problem, only students are strategic agents. Thus, only the welfare of students is considered for Pareto efficiency in this context, and the mechanism should promote students welfare to the greatest extent possible. How should the three criteria be ranked? No doubt the first required criterion in the context of China's college admissions is the elimination of justified envy, i.e., fairness. China has a long history of using a national examination to select talent for government positions. The College Entrance Examination and admissions system in China carry on this tradition. To select talents on test scores, which is a good proxy for comparative advantage and motivation, gives all students an equal chance to compete with each other, no matter rich or poor, family social status or other factors. It is also regarded as fair if compared to other way of assignment (e.g., the buying and selling of positions). Thus, it is natural to require that the admissions process respect test scores and students with higher test scores be assigned to better positions. Policy makers should, then, select a strategy-proof and Pareto-efficient mechanism from all fair ones. If there is a conflict between elimination of justified envy and the other two criteria, elimination of justified envy should take precedence.

4 What Can We Learn from the Mechanism Design Literature?

Throughout the past decades, the mechanism design approach has been used to advice on a handful of real-life assignment problems. Successful examples include FCC spectrum auctions [START_REF] Mcmillan | Selling spectrum rights[END_REF][START_REF] Milgrom | Putting auction theory to work: The simultaneous ascending auction[END_REF], entry-level labor markets for new doctors in the United States [START_REF] Roth | The redesign of the matching market for american physicians: Some engineering aspects of economic design[END_REF], the assignment of students to public schools in Boston and New York City (Abdulkadirouglu et al., 2005a,b), and live-donor kidney exchange systems in the United States and Britain [START_REF] Roth | Kidney exchange[END_REF](Roth et al., , 2005b[START_REF] Roth | Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences[END_REF]. Such rich research on similar assignment problems and the two relevant mechanisms can provide excellent insights regarding the evolution of China's college admissions system and scientific judgments on the current algorithms.

In this section, we primarily review the studies on mechanism design theory and experiments on assignment problems similar to our own case. As the sequential choice algorithm is the Boston mechanism with tiers and the parallel choice algorithm is the Simple Serial Dictatorship mechanism with tiers, we make systematic comparisons of the Boston mechanism and the Simple Serial Dictatorship mechanism. The comparisons follow the three criteria defined in section 3: strategyproofness, elimination of justified envy, and Pareto efficiency.

Theoretical Results

The Boston mechanism, first addressed by [START_REF] Abdulkadirouglu | School choice: A mechanism design approach[END_REF], is one of the most popular school choice mechanisms used for assigning students to public schools in the United States. Criticism of the poor incentives generated by the mechanism, i.e., its vulnerability to strate-gic manipulation, led the Boston Public Schools (BPS) to replace it in 2005 with the Gale-Shapley student-proposing deferred acceptance mechanism [START_REF] Gale | College admissions and the stability of marriage[END_REF], which is strategyproof and stable. The following examples and theorems formally display the properties of the Boston mechanism based on our three criteria.

The critical deficiency of the Boston mechanism is its lack of strategy-proofness (Abdulkadirouglu and [START_REF] Abdulkadirouglu | School choice: A mechanism design approach[END_REF]. Giving precedence to students' reported preferences, i.e., assigning students to their first choice colleges as much as possible and then to second choice colleges as much as possible, etc., the Boston mechanism gives students a strong incentive to manipulate their preference lists. This is because, if a student is rejected by her first choice college, she may find that her next choice colleges are already filled with students who listed them as first choices. Hence, her chance of being admitted to a next choice college is greatly diminished. The following simple example clearly demonstrates the manipulation.

Example 3. There are three students {s 1 , s 2 , s 3 } and two colleges {c 1 , c 2 }, each with one seat.

The ranking of students is s 1 -s 2 -s 3 . Students' preferences are given as follows:

s 1 : c 1 c 2 s 2 : c 1 c 2 s 3 : c 2 c 1
Let the students report their true preferences, the Boston mechanism produces the following matching:

s 1 s 2 s 3 c 1 0 c 2
Given others are truth-telling, if s 2 reports her preferences as c 2 c 1 instead of true preference, the Boston mechanism produces the following matching:

s 1 s 2 s 3 c 1 c 2 0
Thus, student s 2 could benefit from submitting a false preference list. The Boston mechanism gives students an incentive to manipulate true preferences by placing a safe college in a higher position on their preference list. Moreover, as truth telling is not a weakly dominant strategy, students and parents have to form a correct belief about others' behaviors and best respond to them in the preference revelation game induced by the Boston mechanism.

Recent studies have focused on testing whether profitable manipulation will vanish in the larger markets for non-strategy-proof mechanisms. [START_REF] Azevedo | Strategyproofness in the large as a desideratum for market design[END_REF] propose a criterion of approximate strategy-proofness, which is called "strategy-proofness in the Large (SP-L)." A mechanism is SP-L if it only has manipulations that vanish with market size. They have shown that some non-strategy-proof mechanism such as the Walrasian mechanism, double auctions, uniform-price auctions, and deferred-acceptance mechanisms are SP-L. As the number of students is extremely large in China's college admissions, it is natural to ask whether manipulability will vanish in a large market under the Boston mechanism. Unfortunately, the Boston mechanism is not SP-L [START_REF] Kojima | Incentives and stability in large two-sided matching markets[END_REF][START_REF] Azevedo | Strategyproofness in the large as a desideratum for market design[END_REF], and the poor incentive problem still perseveres in a large market. The empirical evidence discussed in Section 2 provides some support for this argument as, in this large matching process, preference manipulation is often advocated by the local press and even by the official website of the Ministry of Education for college admissions.

Manipulation under the Boston mechanism also raises a concern for unfairness, i.e., it may create a disadvantage for students who do not strategize or do not strategize well. The field practice of assigning children to public high schools has shown that there are different levels of sophistication among parents [START_REF] Abdulkadiroglu | Changing the boston school choice mechanism[END_REF][START_REF] He | Gaming the boston school choice mechanism in beijing[END_REF]. [START_REF] Pathak | Leveling the playing field: Sincere and sophisticated players in the boston mechanism[END_REF] show theoretically that, in a complete information environment, when there are both sophisticated students and sincere students, the sophisticated students may benefit from the Boston mechanism while sincere students may be worse off under the Boston mechanism. Moreover, students with less access to information and advice for better manipulation may be harmed by students whose families have more resources. Such unfairness due to different sophistication levels led directly to the Boston Public Schools (BPS) decision to replace the Boston mechanism with the strategy-proof Gale-Shapley mechanism as the later "levels the playing field." For a similar reason, in England the Boston mechanism and similar "first preference first" mechanisms were banned with the 2007 Admissions Code [START_REF] Pathak | School admissions reform in chicago and england: Comparing mechanisms by their vulnerability to manipulation[END_REF], as the "first preference first criterion made the system unnecessarily complex to parents." The field experiences in the above examples justify the use of a strategy-proof mechanism in the context of China's college admissions.

The Boston mechanism does not eliminate justified envy either, which is the essential criterion in the context of China's college admissions. According to Example 3, given truth telling, student s 2 prefers student s 3 assignment c 2 to no assignment, and she also ranks higher than s 3 . Like China's college admissions, fairness is also a crucial notion in many other real-life students assignment applications. For example, the essential requirement for the mechanism used in Turkish college admissions is fairness [START_REF] Balinski | A tale of two mechanisms: Student placement[END_REF], and Chicago Public Schools officials gave up a version of the Boston mechanism based on the fair concern in 2009 [START_REF] Pathak | School admissions reform in chicago and england: Comparing mechanisms by their vulnerability to manipulation[END_REF].

Even though the Boston mechanism does not eliminate justified envy, its equilibrium outcomes eliminate justified envy with respect to true preferences. Thus, the Boston mechanism will lead to fair assignment if coordination on equilibrium.

Theorem 1 [START_REF] Ergin | Games of school choice under the boston mechanism[END_REF]): When priorities are strict, the set of Nash equilibrium outcomes of the preference revelation game induced by the Boston mechanism is equal to the set of stable matchings of the associated college admissions game under true preferences.

Theorem 1 shows that all Nash equilibrium outcomes of the preference revelation game induced by the Boston mechanism are stable. As stability in the associated college admissions implies elimination of justified envy (i.e.,fairness) [START_REF] Balinski | A tale of two mechanisms: Student placement[END_REF], the Boston mechanism will result it assignment that eliminates justified envy in equilibrium. Furthermore, this theorem illustrates that, if (s, c) is a blocking pair with respect to truthful preferences, then student s can guarantee herself a slot at college c by top-ranking that college, given that other students' strategies are unchanged [START_REF] Ergin | Games of school choice under the boston mechanism[END_REF].

The Boston mechanism is also not Pareto efficient. The outcome of the Boston mechanism is Pareto efficient, provided that students truthfully reveal their preferences [START_REF] Ergin | Games of school choice under the boston mechanism[END_REF]. However, truthful preference revelation is rarely the Nash equilibrium strategies for students, thus efficiency loss is expected.

A Serial Dictatorship mechanism is commonly used in the real-life object allocation, such as office allocation for professors, Harvard housing allocation, etc. The mechanism is simple to use: decide the ranking of applications and then allocate the objects according to this ranking. The Simple Serial Dictatorship mechanism is the serial dictatorship mechanism induced by priority ranking, which is based on test scores in the context of China's college admission problem. It has many desirable properties. The following theorem shows that the Simple Serial Dictatorship mechanism is strategy-proof.

Theorem 2 (Sonmez and Unver 2009): A Simple Serial Dictatorship mechanism is strategyproof.

The economic intuition is straightforward: Because, under the Simple Serial Dictatorship mechanism, assignment is determined by priority ranking, the best strategy for students is to report their most preferred colleges in sequence. Regardless of the behavior of others, the student simply needs to truthfully reveal preference, which is the dominant strategy.

In the context of China's college admissions, the Simple Serial Dictatorship mechanism also eliminates justified envy. It is easy to find out that in the associated college admission problem when all colleges have the same preference, there is a unique, stable matching: the student with the highest test score is assigned her most preferred college, the student with the second highest score is assigned her most preferred college among the remaining college slots, and so on. This is exactly the procedure of the Simple Serial Dictatorship mechanism with respect to true preferences.

The following theorem provides formal support for the mechanism.

Theorem 3 [START_REF] Balinski | A tale of two mechanisms: Student placement[END_REF]: The Simple Serial Dictatorship mechanism eliminates justified envy.

The economic intuition for Theorem 3 is as follows. By assigning students one after another according to ranking, the central authority will not go to the next student without considering all choices of the higher ranked students. Thus, if one student s prefers another college c to her assignment µ(s), her test score must be lower than the student µ -1 (c) assigned to college c.

The Simple Serial Dictatorship mechanism is also Pareto-efficient in the context of China's college admissions because all colleges have the same ranking for students. The proof is simple:11 Under the Simple Serial Dictatorship mechanism, the student with the highest test score can not be better off because she gets her most preferred college, and any change in her assignment would make her worse off, as there is a strict preference. Given the highest-scoring student's assignment, the student with the second highest test score can not be better off because she gets her most preferred college among remaining college slots, and any change in her assignment would make her worse off; as there is a strict preference. Similarly, given any assignment of students with 1th, ...kth highest test scores, student with the k + 1th test score cannot be better off, and any change in her assignment would make her worse off, as there is a strict preference. Therefore, no student is strictly better off by changing to any other mechanism from the Simple Serial Dictatorship mechanism. In fact, as mentioned by [START_REF] Balinski | A tale of two mechanisms: Student placement[END_REF], this Simple Serial Dictatorship mechanism is the only mechanism that eliminates justified envy and is Pareto efficient when there is only one ranking for all students.

Theorem 4 (Balinski and Sonmez 1999): There is a unique mechanism that eliminates justified envy and is Pareto efficient if there is only one category (and hence only one ranking): The Simple Serial Dictatorship mechanism induced by this ranking.

In addition to the three appealing properties, the Simple Serial Dictatorship mechanism also stands out for its simplicity, which is one of the most important features for the success of a mechanism in real-life applications [START_REF] Roth | What have we learned from market design?[END_REF]. In fact, in the context of China's college admissions (i.e., the student placement problem with one category), the Simple Serial Dictatorship mechanism is equivalent to the Top Trading Cycles mechanism [START_REF] Shapley | On cores and indivisibility[END_REF] and the Gale-Shapley deferred acceptance mechanism [START_REF] Balinski | A tale of two mechanisms: Student placement[END_REF], the two most appealing and well-studied mechanisms in the practice of matching markets design. Comparing the other two mechanisms, the Simple Serial Dictatorship mechanism is much simpler and intuitive for students and parents to understand.

Consequently, the Simple Serial Dictatorship mechanism theoretically outperforms the Boston mechanism by satisfying all three criteria in the context of China's college admissions, which provides strong justification for the transition from the sequential choice algorithm to the parallel choice algorithm in recent years. While theory assumes that rational agents can compute equilibrium strategies via introspection, the theoretical properties of the mechanisms may not hold when facing boundedly rational individuals in real life. Thus, it is important to check how real people respond to the mechanisms in a real decision-making environment and evaluate the performances of the mechanisms correspondingly.

Experimental Results

As a complement to the theoretical findings, we review, in this section, the related mechanism design experiments for assignment problems similar to our own. A mechanism design experiment recreates theoretical mechanisms in a simple environment in the laboratory with human being as economic agents [START_REF] Chen | Mechanism design experiments[END_REF]. In a typical mechanism design experiment, human subjects (usually students) are recruited to an economics laboratory and are randomly assigned to different mechanism treatments. During the experiment, subjects play a preference revelation game induced by the mechanism. They are asked to make several decisions (e.g., to report preferences over schools in a school choice experiment) and are paid according to their decisions as well as other member's decisions in the same group at the end of experiment. In such an experiment, the economic environment and the assignment mechanism (i.e., algorithm) are well controlled by the experimenter. Thus, human subjects' behaviors are observed, and the real performance of theoretical mechanism can be systematically evaluated.

Laboratory experiments mainly serve two purposes in the study of matching problems: First, to test new mechanisms before implementing them in the real world; and second, to demonstrate how existing institutions evolved. This type of experimentation provides at least two desirable advantages over other methodologies: Compared to theoretical modeling and computational simulation, it can examine the real performances of mechanisms when implemented in a real decision-making environment with boundedly rational agents; and compared to other empirical studies, it is replicable and well controlled by researchers, so as to clearly identify the effect of different mechanisms within the same environment. In Alvin [START_REF] Roth | What have we learned from market design?[END_REF] words:

Experiments can play a role in diagnosing and understanding market failures and successes, in testing new designs, and in communicating results to policy makers.

Along with theoretical discussions, mechanism design experiments on assignment problems try to examine the real performances of the mechanisms based on the three criteria discussed previously: to check the extent to which subjects recognize dominant strategies if the mechanism is theoretically strategy-proof or the extent to which subjects manipulate true preferences if the mechanism is theoretically not strategy-proof; to evaluate the proportion of subjects who do not have justified envy (or the proportion of stable pairs); and to measure the level of efficiency the mechanisms can achieve in real decision-making situations.

There have been several experimental studies to examine the Boston mechanism in the laboratory. The Boston mechanism is usually compared with two other theoretically appealing mechanisms in the context of the school choice problem: the Gale -Shapley student-proposing deferred acceptance mechanism and the Top Trading Cycle mechanism. [START_REF] Chen | School choice: an experimental study[END_REF] present the first experimental study of this type. Motivated by [START_REF] Abdulkadirouglu | School choice: A mechanism design approach[END_REF] theoretical findings, they conducted a laboratory experiment to compare the real performances of the Boston mechanism, the Gale -Shapley mechanism and the Top Trading Cycle mechanism. In the experiment, they used a relatively large group, with 36 subjects to be assigned to 7 different schools, to simulate the complex real-life situation. The experiment is a one-shot game with incomplete information in which subjects only know their own preferences. Their study revealed a higher preference manipulation rate under the Boston mechanism compared to the Gale Shapley mechanism and the Top Trading Cycle mechanism, which is consistent with theory.

Follow-up experiments are intended to fill in gaps where some important details regarding actual mechanisms have been ignored in the literature. For instance, [START_REF] Calsamiglia | Constrained school choice: An experimental study[END_REF] consider the real-life situation in which there are a limited number of schools that students are allowed to submit. They replicate [START_REF] Chen | School choice: an experimental study[END_REF] experiment by adding additional constrained treatments in which students can only submit up to three colleges in preferences lists. Their experiment results show that such a constraint further increases manipulation and reduces efficiency and stability. [START_REF] Pais | School choice and information: An experimental study on matching mechanisms[END_REF] investigate the role of information on performances of the Boston mechanism, the Top Trading Cycle mechanism, and the Gale-Shapley mechanism, finding a significant effect of information on decision making. In the experiment they construct four different information settings, from a zero information condition (in which subjects only know their own preferences and no information on school priorities) to a complete information condition (in which preferences and school priorities are common knowledge). They show that information has a significant effect on truthful preference revelation, where having no information will lead to a higher proportion of truth telling than other information treatments. [START_REF] Featherstone | School choice mechanisms under incomplete information: An experimental investigation[END_REF] create an incomplete information setting in which subjects know their own preferences as well as the distribution of all other subjects' preferences so that it is possible to compute Bayesian Nash equilibrium. They also find a higher manipulation rate under the Boston mechanism. However, when truth telling is an equilibrium strategy under the Boston mechanism, it has the same truth-telling rate as the strategy-proof Gale-Shapley mechanism. [START_REF] Klijn | Preference intensities and risk aversion in school choice: A laboratory experiment[END_REF], on the other hand, study whether changes in cardinal preferences will affect individual behavior and the performances of the Boston mechanism and the Gale-Shapley mechanism. In the experiment, they design a simple, stylized environment with a clear theoretical prediction about subject behavior in terms of undominanted strategies. They find that the Boston mechanism is more sensitive than the Gale-Shapley student proposing deferred acceptance mechanism to changes in cardinal preferences which is consistent with [START_REF] Abdulkadiroglu | Resolving conflicting preferences in school choice: The boston mechanism reconsidered[END_REF] argument that the Boston mechanism induce students to reveal their cardinal preferences when they have the same ordinal preferences. They also find that subjects with a higher degree of risk aversion are more likely to play safer strategies under the Gale-Shapley mechanism but not under the Boston mechanism.

In a recent paper, [START_REF] Chen | From boston to chinese parallel to deferred acceptance:theory and experiments on a family of school choice mechanisms[END_REF] provide the first theoretical and experimental investigations of the Chinese parallel mechanism. They characterize a parametric family of applicationrejection school choice mechanism, including the Boston mechanism and the Gale-Shapley mechanism as two extremes and the Chinese parallel mechanism, sandwiched between the other two mechanisms. They formulate the Chinese parallel mechanisms in school choice problem and make a systematic comparison between the three mechanisms. Experimental results show that subjects are less likely to manipulate true preferences under the Chinese parallel mechanism than under the Boston mechanism, and the former is also more stable than the Boston mechanism. The Gale-Shapley mechanism still stands out for the least manipulable and most stable mechanism among the three mechanisms. However, efficiency comparisons between the three mechanisms vary across environments. Their paper differs from our current model in two ways: first, they compare the three mechanisms in the context of school choice problem in which there are multiple rankings for students, but there is a single ranking for all colleges in the context of China's college admissions. Second, the parallel choice algorithm is formulated into a family of application-rejection mechanisms, but it is interpreted as the Simple Serial Dictatorship mechanism with tiers in this paper. However, when there is a unique ranking of students as in the context of China's college admissions, the Serial Dictatorship mechanism is equivalent to the Gale-Shapley mechanism.

With different purposes and various design environments, these experimental studies show robustly that the Boston mechanism is more manipulable compared to other strategy-proof mechanisms, which is consistent with theoretical findings. However, the efficiency comparison of the Boston mechanism with other theoretically superior mechanisms varies with economic environments. For example, [START_REF] Chen | School choice: an experimental study[END_REF] show that efficiency under the Boston mechanism is significantly lower than those under the other two mechanisms in a designed environment, but there is no significant difference in efficiency between the Boston mechanism and the Gale-Shapley mechanism in a random environment. [START_REF] Pais | School choice and information: An experimental study on matching mechanisms[END_REF] show that when the Top Trading Cycles mechanism yields a significantly higher level of efficiency than the other two mechanisms in partial and full information environments, there is no significant difference in the efficiency of the three mechanisms in low information environment. [START_REF] Klijn | Preference intensities and risk aversion in school choice: A laboratory experiment[END_REF] show that, while the Gale-Shapley mechanism outperforms the Boston mechanism in terms of efficiency in an unconstrained environment, the Boston mechanism has a higher efficiency level than the Gale-Shapley mechanism in a constrained environment. Furthermore, motivated by [START_REF] Abdulkadiroglu | Resolving conflicting preferences in school choice: The boston mechanism reconsidered[END_REF] theoretical paper, [START_REF] Featherstone | School choice mechanisms under incomplete information: An experimental investigation[END_REF] purposely designed a special symmetric environment in which truth-telling is an equilibrium strategy under the Boston mechanism and showed that there is a significantly higher level of efficiency under the Boston mechanism than under the Gale-Shapley mechanism in the laboratory.

There are several experimental papers that we are aware of investigating the relevant Serial Dictatorship mechanism, although the Simple Serial Dictatorship mechanism is not directly examined. Well studied mechanism is the Random Serial Dictatorship mechanism (RSD) with squatting rights which is commonly used in the on-campus housing allocation problem. For example, [START_REF] Chen | Improving efficiency of on-campus housing: An experimental study[END_REF] and [START_REF] Chen | An experimental study of house allocation mechanisms[END_REF] studied the RSD mechanism with squatting rights and the Top Trading Cycles mechanism in the on-campus housing allocation problem in incomplete information setting and complete information setting. In their experiments there are twelve participants to be assigned to twelve houses of eight types. They show that the RSD mechanism is significantly less efficient than the Top Trading Cycles mechanism, and these results are robust for changes of size, environment and also information settings. Their results are consistent with theoretical predictions and provide a strong suggestion for replacing the RSD mechanism with squatting rights with the Top Trading Cycles mechanism. Other variant of the Serial Dictatorship mechanism is also examined in some literature. For example, [START_REF] Olson | An experimental examination into the design of decentralized methods to solve the assignment problem with and without money[END_REF] compare the generalized versions of the Vickrey and the English auctions, the Serial Dictatorship mechanism and the Chit mechanism in the one-sided matching problem. They find that the Serial Dictatorship mechanism is significantly less efficient in assignments. Notably, the RSD mechanism studied in the two experiments differs from the Simple Serial Dictatorship mechanism discussed in this paper, as the former uses a random lottery to generate ranking and the latter uses predetermined ranking, such as ranking via test scores.

The above experiments independently investigate the Boston mechanism or the Serial Dictatorship mechanism in different assignment problems. However, no study directly compares the two mechanisms in the context of China's college admissions problem in which there is one predetermined ranking of students. Thus, an experiment of this type is required for the future study.

Conclusion

The evolution of college entrance examinations and admissions in China has gone through several phases over the past sixty years. One most significant change has been the transition from decentralized processes to a centralized clearing house where a central authority is in charge of the assignment of high school graduates via test scores. Another central issue is the assignment mechanism used. The parallel choice algorithm was discovered by the field practitioners and has been successfully implemented in many provinces to replace the old sequential choice algorithm, which was criticized for unfairness and for the prevalent practice of gaming the system. In this paper, we justify this evolution from a mechanism design perspective. Our review of studies on mechanism design theory and experiments on similar assignment problems shows that: first, a centralized process such as college admissions in China is a common way to organize similar assignment problems in which indivisible and heterogeneous goods are allocated and price hardly plays a role (matching problems), as it has merits for making markets thick and uncongested and for avoiding unraveling. Second, the parallel choice algorithm is one variant of the Simple Serial Dictatorship mechanism, and the literature shows that this mechanism eliminates justified envy, is strategy-proof and is Pareto efficient, while the sequential choice algorithm is one variant of the Boston mechanism which has been criticized for not eliminating justified envy (unfairness), not being strategy-proof in small and large markets, and also not being Pareto efficient. Third, we argue that experiment is one essential tool in this field of research because experiments can evaluate the performances of theoretical mechanisms in real decision-making environments in which agents are boundedly rational. The mechanism design experiments show robust results that the Boston mechanism is more manipulable and unstable in school choice experiments, but further experiments are still needed to directly compare the Boston mechanism and the Simple Serial Dictatorship mechanism in the context of China's college admissions problem.

Mechanism design has emerged as one of the most important research fields in microeconomics, covering many major topics such as public goods, voting system, auction and matching, etc. It not only provides insights into how economic institutions have evolved but also serves to guide the design and redesign of real economic institutions. Many real-life institutions have been successfully implemented with the help of the mechanism design approach. One prominent feature of this field is the fact that economists are actively involved, using theoretical, experimental, empirical and case study approaches to provide scientific advice on the design of practical institutions. For example, several economists, including the 2012 Nobel Laureate Alvin Roth, were invited to help redesign the Boston and New York City public school choice systems. In 2003, [START_REF] Abdulkadirouglu | School choice: A mechanism design approach[END_REF] published their seminal paper in which they note that the mechanism used in the Boston public school choice program (the Boston mechanism) has the serious problem of giving parents incentives to game the system. They propose two theoretically superior mechanisms as replacements: the Top Trading Cycle mechanism and the Gale-Shapley mechanism. They were then invited by the Boston Public Schools (BPS) planning team to present their theoretical results and experimental support [START_REF] Chen | School choice: an experimental study[END_REF], and after two years of intensive discussion and analysis, the Boston School Committee voted in 2005 to replace the Boston mechanism with the Gale-Shapley mechanism. The New York City public high school program had a similar story. The Department of Education was aware of the successful design of the entry-level labor market for new doctors in the United States and asked economists to help them design a similar system. Alvin Roth and his colleges showed that the decentralized process used by the NYC public school system had a congestion problem and advised the leaders to orga-nize a centralized clearing house and implement the Gale-Shapley mechanism for assignment. The education department of New York City took their advice and adopted the new system in 2003.

Some aspects of the current college admissions system in China can still be improved. Currently, variants of the algorithms have been used across different provinces: the sequential choice algorithm, the parallel choice algorithm, and the hybrid algorithm falling between the sequential choice and the parallel choice algorithms. While both empirical evidence and mechanism design studies support the use of the parallel choice algorithm, which form of the parallel choice algorithm should be used is still under debate. Many questions remain to be answered, such as what number of parallel options is optimal, whether the parallel choice algorithm performs better than the hybrid algorithm. The current choices made by each province seem arbitrary. For example, students in Shanghai can submit up to four parallel colleges in the first tier, but this number is five in Hunan province. In Beijing, only one college can be submitted as first choice in the first tier, and the second choice in the first tier can include three parallel colleges. Another nontrivial debate on the current system is the timing for students to submit preference lists. Currently, each province has a different rule regarding the timing for submission: prior to examination, prior to score announcement, or after score announcement. The timing represents different information scenarios for decision making. In the first two scenarios, students face uncertainty regarding test scores when making choices; while in the latter scenario, students have complete information about test scores when making choices. As a result, for the practical application of China's college admissions system, among different forms of parallel choice and timing for reporting preferences, which mechanism should be chosen is an important question. We believe that the mechanism design approach, with the involvement of economists in designing the system, will be extremely beneficial for policy makers.

In this paper, we only consider the simple case of first-step admissions in assigning students to colleges. In fact, the lexicographic two-step admissions process, with college acceptance first and faculty allocation second will complicate the model and cause efficiency loss. For example, a given student's true preference is engineering at Peking University which is preferred to engineering at Tianjin University which is preferred to business at Peking University which is preferred to business at Tianjin University, etc. By the two-step admission process, with college acceptance first and faculty allocation second, the student takes a risk in revealing true preferences over faculties. Many other practices for assigning students to college slots use so-called "multiple categories". For example, in Turkey, faculties are classified into different skill categories with different combination of tests. Thus, a given student can take several tests and has different priority ranks in different skill categories (faculty types), and submit preferences over faculties instead of lexicographic preferences. (For example, a student takes mathematics, physics, and verbal aptitude tests, and has two separate ranks in two skill categories: one in the engineering category, which requires mathe-matics and science tests, and one in the business category, which requires mathematics and verbal aptitude tests.) Such "multiple categories" could not only improve on the lexicographic structure, but also provide more options for both students and faculties according to their own comparative advantages.

Students are classified into two categories: science and art. Each student either takes comprehensive science test if in science category or comprehensive art test if in art category, and is ranked accordingly. For example, a student is ranked highly among students in science category if she takes the science test and has a high aggregate score.

In this paper "have no say" mainly means colleges are not active agents and their welfare is not considered.

See http://learning.sohu.com/20070918/n252207517.shtml, retrieved on 01/13/2013.

See http://gaokao.chsi.com.cn/gkxx/zjsd/201003/20100311/65908711.html, retrieved on 1/15/2013.

See http://gaokao.chsi.com.cn/gkxx/zytb/201106/20110616/214533410-2.html, retrieved on 01/15/2013.

Zhendong Li, "Refocus on the Parallel Choice Algorithm", College Admission, February 18, 2009.

Zhendong Li, "Refocus on the Parallel Choice Algorithm", College Admission, February 18, 2009.

See http://gaokao.chsi.com.cn/gkxx/zytb/201106/20110616/214542618.html, retrieved on 02/03/2013.

More precisely, there are two independent rankings, one of which is in science category and the other is in art category. A given student is ranked in only one category.

The admissions process in each tier is independent.

We are grateful to the referee for pointing out mistakes and providing proof.