“Axioms for Deferred Acceptance,” F. Kojima & M. Manea (2010)

Many allocation problems in economics deal with divisible objects that can be allocated using “money” in the broadest sense of the world. Not everything is this way, however. There are many interesting problems that involve indivisible goods (such as slots in a magnet school) and for which there are legal/ethical problems with using money to allocate (think of kidney exchanges). Given preferences over objects, “optimal” allocation given individual preferences is called the Assignment Problem, and has long been studied in economics and operations research. Gale and Shapley – mathematicians originally, though Shapley in particular is well known to economic theorists for his work on cooperative games – wrote an algorithm called the “deferred acceptance algorithm” in a 1962 paper about college admissions (though this paper is most famous for an example within about stable marriages). Today, much of the work on these types of indivisible allocation problems is associated with the Cambridge schools.

Deferred acceptance works as follows: everyone ranks the objects (strictly), possibly including “empty set”, which is some outside option, such as “marry no one”, and each object “ranks” the individuals, by which we mean something like “each public school has a priority list for who they wish to accept, ranked based on test scores”. In the first round, every individual “applies” to their top choice, and each object accepts, for the time being, the individuals highest in that object’s priority list until that object’s quota is filled (e.g., in the marriage market, the quota is 1), and rejects everyone else. In the 2nd round, everyone not yet assigned applies to their second choice, and objects select any individuals who apply and are higher in that object’s priority list than somebody who was selected in the first round. This continues until all agents are accepted by an object or by “empty set”, which has no quota. It has long been known that DA is Pareto-optimal among all stable matchings, where stable means that no two agents wish to switch objects, and that DA induces truthful revelation of preferences as a dominant strategy for all agents (this is pretty easy to see given how the algorithm works, though note that DA is strategy-proof for one side of a market; when you have an assignment problem where incentive problems crop up for both the individuals and the “objects”, then you will only have strategy proofness for the side that proposes matches, which are the individuals in the description above. For instance, Al Roth has pointed out in a series of papers that hospitals, when dealing with kidney transplants, and schools, when dealing with student allocation, also will game the system, and DA will not prevent this).

Kojima and Manea, unquestionably two of the biggest stars in the theory job market over the last few years, note in this recent Econometrica that despite the importance of DA, no one had yet given a representation theorem for DA in terms of more basic conditions on an allocation rule. They show that, even if we have no idea what the priority rule is (technically, as long as the priority rule is acceptant and substitutable, but these are nonworrisome), any allocation which is nonwasteful, meaning that if an agent prefers an object to “empty set” and that object has not filled its quota then the agent is assigned the object, and IR monotonic, meaning that if everyone’s preferences change such that some agents have fewer objects preferred to the empty set then no agent becomes worse off after preferences change, then the allocation rule must be DA. It’s indeed surprising that you can generate this result without reference to the structure of the object’s priority rules. An alternative characterization replaces IR monotonicity with “weak Maskin monotonicity” (which should sound familiar to you auction theorists) and a condition called population monotonicity and derives the same result. Finally, if you specify a priority C and an allocation rule, then as long as standard Maskin monotonicity is satisfied, the allocation rule will be Pareto efficient and strategy-proof even when groups can correlate their strategies.

(Sidenote: You may be wondering, at this point, why we need Maskin monotonicity to guarantee Pareto efficiency, since DA appears to always gives a “Pareto efficient” match. It is not terribly clear in the paper – perhaps this point is too obvious for theorists in this area – but DA only gives Pareto efficient allocations within the class of stable allocations. It says nothing about Pareto efficiency more generally.)

This paper also suggests that there are many, many other algorithms, or simplifications, or what have you, for which it would be nice to see representation theorems. I can think of one example in particular concerning knowledge diffusion, which I will write about further here when I have some better developed results. Less interesting to me, but perhaps to the behavioralists here, would be representation theorems for various heuristics. That is, if firms or individuals are using some rule of thumb, what exactly does that rule of thumb mean in terms of more general beliefs/behaviors/actions?

http://sites.google.com/site/fuhitokojimaeconomics/Fuhito-Kojima/ecta7443%286%29.pdf?attredirects=0

Advertisement