Should You List Your Preferences Honestly?

When you submit your preferences for laboratory assignments, should you simply list the lab you want to join as your first choice? Or should you try to predict popularity and capacity and change your ranking? The answer depends on the assignment rules adopted by the university. The results will differ depending on whether priority is given to those who list a lab as their first choice, or whether the laboratory's own preferences are taken into account.

These rules do not exist naturally from the beginning; we humans create them according to our objectives. In addition to laboratory assignments, there are many matching opportunities in society, such as students and schools, medical residents and hospitals, and employees and departments. Since these often involve important turning points in life, it is necessary to design appropriate matching rules.

Matching theory is the mathematical study of combinations between people, between people and organizations, or between organizations themselves. The goal is to mathematically define the desirability of an assignment, design algorithms to find combinations that satisfy those criteria, and apply them to real-world problems. The field that utilizes these insights to design actual systems is called market design.

I evaluate matching systems from the perspective of participant incentives. Because the side operating the system does not know the participants' true preferences, they ask for a ranking. However, if misrepresenting one's preferences is advantageous, participants will not necessarily answer honestly. For this reason, matching theory emphasizes "strategy-proofness," which makes people feel they should report their preferences honestly. This is also important in real-world institutional design. For example, the "Boston mechanism" used for public school choice in Boston, USA, became problematic because it encouraged parents to submit false rankings. Consequently, the system was reviewed in 2005 and changed to a method that encourages honest reporting.

Here, I will introduce our research on strategy-proofness. One seemingly rational method is the rank-sum minimization mechanism. This method assigns 1 point for a first choice, 2 points for a second choice, and so on, and selects the assignment that minimizes the total score of all participants. While this looks like a rule that respects everyone's preferences, weaknesses emerge when analyzed from the perspective of incentives. Figure 1 shows the average percentage of participants who can make an advantageous false report when preferences are generated uniformly at random. Under the rank-sum minimization mechanism, this percentage reached about half, significantly exceeding the Boston mechanism that led to the system review. This does not mean that half of the people actually lie, but it indicates that the rank-sum minimization mechanism is potentially vulnerable to strategic behavior. For this computational experiment, we developed an algorithm to quickly determine advantageous false reports based on insights from discrete optimization and mathematically proved its correctness. This was a joint research project with Naoki Kokubo, who was a master's student in my laboratory at the time, and Professor Tomomi Matsui of Tokyo Institute of Technology (now Institute of Science Tokyo).

A good system is not just one that optimizes the sum of reported preference rankings. It is also important to consider whether participants have an incentive to report their true preferences. The goal of matching theory and market design is to design better rules by considering how people will behave under a given system.