Rationalizing Path-Independent Choice Rules

1/26

Isa E. Hafalir

(U. of Technology Sydney)

Koji Yokote

(U. of Tokyo)

Fuhito Kojima

(U. of Tokyo)

M. Bumin Yenmez

(Washington U.)

• Two-sided matching, e.g., school choice, job matching.
• Primitive: agents’ behavior when faced with possible alternatives.
• Two approaches to formulating behavior.

2/26

• Specifies available alternatives and chosen ones.
• Sufficient condition for existence of stable matching: path-independence

• Gives higher values to more preferred alternatives.

rationalizes

Main result

​

​

​

• Contributions.
• Build a bridge between utility-based and choice-based approaches.
• Enable to transfer techniques in discrete math to matching (e.g., Hafalir-Kojima-Yenmez-Yokote 2023, Fujishige-Kojima-Yokote 2024).
• Give a recipe for checking whether stable matching exists in the target problem.

3/26

Theorem: A choice rule satisfies path independence if and only if it is rationalizable by a utility function that satisfies ordinal concavity.

Concavity notion in discrete convex analysis.

Model

4/26

Path independence

5/26

Result (Blair 1988): If every school’s choice rule satisfies path independence, then the DA algorithm produces a stable matching.

Substitutability

6/26

Result (Aizerman & Malishevski 1981): A choice rule satisfies path independence if and only if it satisfies substitutability and IRC.

Utility function

7/26

Sub

IRC

?

Rationalize

Ordinal concavity

8/26

Q: why “concave”? why “ordinal”?

9/26

10/26

First main theorem

• Proof: Omitted due to time constraints

11/26

Law of aggregate demand

12/26

Result (Hatfield & Milgrom 2005): If every school’s choice rule satisfies substitutability and LAD, then DA is strategy-proof for students.

New concavity

13/26

Second main theorem

• Proof: Omitted due to time constraint

14/26

Application: minority reserves

• School choice: students’ merit and diversity matter.
• Minority reserves policy: schools reserve seats for minority students.
• Theory: Hafalir & Yenmez & Yildirim 2013.
• Used in the real world (e.g., Chile, India).

​

• Construct a utility function that embodies this policy.
• ordinally concave and size-restricted concave.

​

​

​

15/26

Application: minority reserves

16/26

Application: minority reserves

17/26

Application: minority reserves

18/26

Conclusion

• “Well-behaved” combinatorial choice rules are rationalizable by a “well-behaved” utility function
• Substitutability of choice rule is closely related to concavity of utility function

​

• May enlarge applicability
• local optimality = global optimality
• Fast computation

​

19/26

Appendix: How to construct orders in AM’s theorem?

20

Appendix: Proof of Theorem 1

21/26

22

23/26

24/26

25/26

26/26

27/26

28/26

QED.

Appendix: Proof of Theorem 2

29/26

30/26

31/26

32/26