Why Is Being Truthful A Good Thing?
In the context of stable matching problems
Jamie Morgenstern is a researcher into machine learning, economics, and especially mechanism design.
Today Ken and I would like to discuss a joint paper of hers on the classic problem of matching schools and students.
The paper is titled, “Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy).” It is joint with Sampath Kannan, Aaron Roth, and Zhiwei Wu. Let’s call this paper (KMRW). She gave a talk on it at Georgia Tech last year.
The Classic Matching Problems
There are various instances of matching-type problems, but perhaps the most important is the NRMP assignment of graduating medical students to their first hospital appointments. In 2012 Lloyd Shapley and Alvin Roth—Aaron’s father—were awarded the Nobel Prize in Economics “for the theory of stable allocations and the practice of market design.”
The original matching problem was that of marrying females and males, on which we just posted about a recent joint paper of Noam Nisan. Here is a standard description of the stable matching problem (SMP):
Assume there are men and women. Further each has a linear ranking of the members of the opposite sex. Find a way to marry all the men and all the women so that the assignment is stable. This means that no two people would both rather marry each other instead of the partners they are assigned to.
In 1962, David Gale and Shapley proved that any SMP always has a solution, and even better, they gave a quadratic time algorithm that finds it. SMP as stated is less practical than the problem that results if the men are also allowed to marry each other, likewise the women, with everyone ranking everyone else as partners. But in the same famous paper, Gale and Shapley solved an even more realistic problem:
The hospitals/residents problem—also known as the college admissions problem—differs from the stable marriage problem in that the “women” can accept “proposals” from more than one “man” (e.g., a hospital can take multiple residents, or a college can take an incoming class of more than one student). Algorithms to solve the hospitals/residents problem can be hospital-oriented (female-optimal) or resident-oriented (male-optimal). This problem was solved, with an algorithm, in the original paper by Gale and Shapley, in which SMP was solved.
Let’s call this the college admissions problem (CAP).
Gaming the System
Consider adding another condition to CAP. Stability is clearly an important requirement—without it there would be students and colleges that would prefer to swap their choices. Having stability which avoids such a situation is quite nice. It does not force the assignment to be perfect in any sense, but does make it at least a “local” optimal solution. This is important, and it is used in real assignment problems today.
Yet there is a possibility that students, for example, could “game” the system. What if a student selected a strange ordering of schools that they claim they wish to attend. But the list is not really what they want. Why would they do this? Simply they may be able to lie about their preferences to insure that they get their top choice.
The basic point seems easiest to illustrate in the non-gender, single-party case, so let’s say need to form two pairs. They have circular first choices and second choices in the opposite circle:
Let’s say happens. and got their second choices, but it is not to their advantage to room together. They could have had their first choices under the also-stable configuration but there was no way to force the algorithm to choose it. However, let’s suppose and lie and declare each other to be their second choices:
The algorithm given these preferences sees as unstable since would join with , and the resulting as unstable because and would prefer each other. The resulting stable now gives and their first choices. Given what they may have known about ‘s and ‘s preference lists, there was no danger they’d actually have to pair up. Examples in the two-gender and student-college cases need six actors but the ideas are similar.
Systematizing the Game
The basic Gale-Shapley algorithm for the two-party case actually has two “poles” depending on which party has its preferences attended to first. The current NRMP algorithm favors the applicants first. In college admissions one can imagine the schools going first. Alvin Roth proved that the poles had the following impact on truthfulness:
Theorem 5. In the matching procedure which always yields the optimal stable outcome for a given one of the two sets of agents (i.e., for or for ), truthful revelation is a dominant strategy for all the agents in that set.
Corollary 5.1. In the matching procedure which always yields the optimal stable outcome for a given set of agents, the agents in the other set have no incentive to misrepresent their first choice.
A dominant strategy here means a submitted list of preferences that the individual has no motive to change under any combination of preferences submitted by the other agents (on either side). The upshot is that the favored side has no reason to deviate from their true preferences, but the non-favored side has motive to spy on each other (short of colluding) and lie about their second and further preferences.
There has been much research on improving fairness by mediating between the “poles” but this has not solved the truthfulness issue. Can we structure the algorithm so that it still finds stable configurations but works in a way that both parties have incentive to be truthful and use their real orderings?
Unfortunately, Roth’s same paper proved that there is no method to solve SMP or CAP that is both stable and truthful. Only the above conditions on one side or the other are possible.
Can We Handle Truth?
Judge Randolph: Consider yourself in contempt!
Kaffee: Colonel Jessup, did you order the Code Red?
Judge Randolph: You don’t have to answer that question!
Col. Jessup: I’ll answer the question!
Col. Jessup: You want answers?
Kaffee: I think I’m entitled to.
Col. Jessup: You want answers?
Kaffee: I want the truth!
Col. Jessup: You can’t handle the truth!
However, a recurring theme in theory especially since the 1980s is that often we can work around such negative results by:
- randomizing so that requirements hold “with high probability” or “in expected case,” and/or
- accepting approximations, and/or
- making results (more) asymptotic, and/or
- fencing off undesirable cases in some way.
Recall that in the college admissions case where the schools act first, the schools have no motive to do other than declare their true preferences, but the students might profit if they submit bogus second, third, and further preferences to the algorithm. The new KMRW paper states the following:
We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals, which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst- case preferences (for schools and students) in large markets.
Approximation and Truth
By “approximately stable” the KMRW paper means a relaxation of the third of three conditions on a function that maps students to colleges plus the “gap year” option . If left off his or her application list, that is read as preferring to . Symmetrically, may have an admission threshold that some students fall below.
- The set of students mapped to is no greater than the capacity of .
- For every student mapped to and student in a college it is not the case that listed over and ranked over .
- For every college with an opening, i.e. , and student who listed as a possibility, either is below the admission threshold of or prefers to .
The relaxation is that for some fixed , colleges may hold on admitting qualified students who might prefer them if they are within of their capacity:
3′. Same as 3. but with in place of the first condition.
There is also an approximation condition on the potential gain from lying about preferences. This requires postulating a numerical utility for student to attend college that is monotone in the true preferences. Given , say the preference list submitted by is -approximately dominant if for all other lists by —and all lists submitted by other students which induce the mappings with and with —we have
In fact, KMRW pull the randomization lever by stipulating the bound only on the difference in expected values over matchings produced by the randomized algorithm they construct. Then this says that no student can expect to gain more than utility by gaming the system.
Confining the utility values to ensures that any is larger than some differences if the number of colleges is great enough, so this allows some slack compared to strict dominance which holds if . It also enables the utility values to be implicitly universally quantified in the condition by which and “mesh” with , the number of students, and the minimum capacity of any college:
Theorem 1 Given and , there are universal constants and an efficient randomized algorithm that with high probability produces a feasible -approximately stable solution in which submitting the true preferences is -approximately dominant in expected value for each student, provided that and
This is an informal statement. The mechanism underlying the proof also works for not fixed: provided grows faster than , the approximate stability and probable-approximate truth-telling dominance can be achieved with and both tending toward . It is neat that the approximations are achieved using concepts and tools from differential privacy, which we have posted about before. By analogy with PAC, we might summarize the whole system as being “probably approximately truthful.”
Should We Handle Truth?
The notion of truth is fundamental. In logic the notion of truth as applied to mathematical theories is central to the Incompleteness Theorems of Kurt Gödel and Alfred Tarski.
In economics the notion of truth is different but perhaps even more important. Imagine any set of agents that are involved in some type of interaction: it could be a game, an auction, or some more complex type of interaction. Typically these agents make decisions, which affect not only what happens to them, but also to the other agents. In our “” example above, the further point is that “gaming the system” by and lowered the utility for and . But and could have tried the same game.
The effect on others highlights that this is a basic problem. It seems best when the interaction does not reward agents that essentially “lie” about their true interests. This speaks our desire for a system that rewards telling the truth—and takes the subject into the area of algorithmic mechanism design which we also featured in the post on Nisan. Indeed truth is addressed in his Gödel Prize-winning paper with Amir Ronen, for instance defining a mechanism to be strongly truthful if truth-telling is the only dominant strategy.
That paper follows with a sub-sub-section 4.3.1 on “basic properties of truthful implementations”—but what I’m not finding in these papers are theorems that tell me why truthfulness is important in economic interactions. It sounds self evident, but is it? There are many papers that show one cannot force agents to be truthful, and there are other results showing cases in which the agents’ individual best interests are to be truthful after all. I understand why a solution to a matching problem should be stable, but am not convinced that it needs to be truthful. In mathematics we can define a property that we add to restrict solutions to some problem, but we usually need to justify the property. If we are solving a equation, we may restrict the answers to be integers. The reason could be as simple as non-integer answers making no sense, such as buying 14.67 cans of Sprite for a party.
I get that being truthful does stop some behavior that one might informally dislike. What I feel as an outsider to the research into matching problems is simple: where is the theorem that shows that adding truthful behavior has some advantage? It is true in the analogous case of auctions that they can be designed so that truthful bidding is provably a dominant strategy, and plausibly this matters to competitors agreeing to and paying for the auction mechanism. Perhaps there is a “meta” game level where mechanism designs are strategies and there is a communal payoff function, in which truth-inducing mechanism designs may be optimal strategies. But overall I am puzzled. Perhaps this just shows how naive I am about this line of work.
What are your reactions on the importance of inducing truth-telling? To show at least dewy diligence on our part, here are a few good references. What would Gödel—who conveyed certain of his own mechanism design opinions to his friend Oskar Morgenstern (no relation)—say?