RF-004 Hashimoto Naoyuki Suguru Ueda Atsushi Iwasaki Yosuke Yasuda Makoto Yokoo 1 [10] ( ). ( ) 1 ( ) 3 4 3 4 = 12 deferred acceptance (DA) [3, 7] [5] ( ) NP serial dictatorship with regional quotas (SDRQ) multi-stage DA with regional quotas (MSDARQ) ( ) 1 ( : KK: Kamada and Kojima, 2012, BFIM: Biro et al., 2010). Minimum quotas Maximum quotas individual hierarchical regions none DA KK/BFIM individual MSDA hierarchical MSDARQ open regions SDRQ general regions NP-complete general regions NPcomplete 49
2 (S, C, R, p, q, S, C, ML ) S = {s 1, s 2,..., s n } C = {c 1, c 2,..., c m } n = S m = C R = {r 1, r 2,...} r r 2 C \ p = (p r ) r R q = (q r ) r R r R 0 p r q r s s c c S = ( s ) s S C = ( c ) c C (Master List, ML) [6] [8, 9, 2] GPA TOEFL ML s 1 ML s 2 ML ML s n ( ). µ : S C S C : (i) s S µ(s) C, (ii) c C µ(c) S, (iii) s c s µ(c) µ(s) = c. : r, p r c r µ(c) q r c r regions(c) 1. µ, s, c s c : (i) c s µ(s), (ii) r regions(c), c r µ(c ) < q r, (iii) r regions(µ(s)), c r µ(c ) > p r. µ s µ(s) c s µ(s) c c c µ(s) µ(s) s c 2. µ s s s : µ(s ) s µ(s) s µ(s ) s. µ s µ(s) s µ(s ) µ(s ) s s s s [4]. ML ML 3. µ s s s : µ(s ) s µ(s), s µ(s ) s s ML s µ ML- s s ML (ML-) ( ) 3 3.1 n NP 1. S, C, R, p, q NP r R r 1, 2, 3 r = 3 p r 1 0 r = 3 q r 3 1 50
. NP 3-SAT 3-SAT X L l x 1 x 2 x 3 3 x X x 3-SAT x x x x 1 0 l L l 1 3 0 1 n X 3-SAT 3-SAT NP r p r r r = C \ r q r = n p r 2. S, C, R, p, q NP 3.2 NP [3, 7] 4 ( ). R r r r, r R : (i) r r =, (ii) r r, (iii) r r. [3, 7] [3, 7] c c, {c} R p {c} q {c} r > 1 r R p r q r ( 1). R R C R. 5 ( ). R T R : (i) C, (ii) {c} c C (iii) r C r R r r r r children(r) r = r children(r) r r R q r c r q {c} q r = r children(r) q r 6 ( ). r R p r r children(r) p r r = 1 7 ( ). r r p r r children(r) p r 51
3. S, C, R, p, q, T R T R. T R r R p r > q r p C n q C n r R p r > q r p C n q C T R 8 ( ). T R r R p r q r 9 ( ). n k ν T R T R 1. r p r max(0, p r c r ν(c) ) 2. {c} q {c} q {c} ν(c) 3. r q r c r q {c} 4. T R 4. ν T R T R c ν(c) q {c} c ν(c) > q {c} T R c ν(c) q {c} 7 9 p r q r 10 ( ). T R n p C n q C T R n 5. n T R k ν ν k n p C c ν(c) q {c} ν T R T R n k. 4 ν T R T R T R T R p C q C p C n k q C T R n k T R n p C n q C k n p C 9 ν k p C p C q C = q C k p C p C n k q C k = q C r 11 ( ). r a r : r a r = p r. a r = p r r children(r) p r. p C = r R a r p C 6. n T R s c ν ν T R T R n 1 Case 1: p C < n q C q {c} > 0 Case 2: p C = n q C, q {c} > 0 r regions(c), a r > 0. T R n 1 Case 1 5 T R n 1 Case 2 4 T R a r > 0 r regions(c) r a r = p r r children(r) p r > 0 c r p r > r children(r) p r > r children(r) p r p r > 0, p r > p r 1 p r > r children(r) p r p r max(0, p r 1, r children(r) p r ) p r > p r ν 52
p r = p r 1 r r r p r max(0, p r 1, r children(r ) p r ) p r p r p r > 0 r children(r ) r = r p r = p r 1 r r p r = p r p r < p r p r = p r 1 r C p C = p C 1 p C = n q C q C = q C 1 p C = n 1 q C T R n 1 q {c} 0 n < p C n > q C T R p C = n r regions(c), a r = 0 11 {c} p {c} = p {c} = 0 {c} {c} C p C = p C p C > n 1 T R n 1 4 4.1 (Serial Dictatorship with Regional Quotas, SDRQ) 6 ML s s µ k Stage k µ r R p 1 r = p r, q 1 r = q r, a 1 r = a r k = 1 Stage k 1 Step 1: Case 1: ML k s k p k C < n (k 1) s k (q k {c} > 0 ) c Case 2: p k C = n (k 1) s k q k {c} > 0 r regions(c), ak r > 0 c Step 2: µ k µ k (c) = {s k }, µ k (s k ) = Step 3: c µ k 9 p k+1 r, qr k+1, a k+1 r k = n k k + 1 Step 1 q k {c} = 0 c r regions(c), a k r = 0 c 1. 8 S = {s 1,..., s 8 } 4 C = {c 1, c 2, c 3, c 4 } R {{c 1, c 2, c 3, c 4 }, {c 1, c 2 }, {c 3, c 4 }, {c 1 }, {c 2 }, {c 3 }, {c 4 }} c, p {c} 1 c 1 q {c1} 1 c 1 4 p {c1,c 2} = 2 p {c3,c 4} = 4. a {c1,c 2} = 0 a {c3,c 4} = 2. s1, s2, s3, s4 : c 1 c 2 c 3 c 4, s5, s6, s7, s8 : c 2 c 1 c 4 c 3. c1, c2 : s 8 s 7 s 6 s 5 s 4 s 3 s 2 s 1, c3, c4 : s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8, ML : s 1 s 2 s 3 s 4 s 5 s 6 s 7 s 8. SDRQ Stage 1 s 1 p 1 C = 6 n (k 1) = 8 > 6 s 1 c 1 Stage 5 n (k 1) > p k C s 2 s 4 s 2, s 3, s 4 c 2 Stage 5 p 5 C = 4 n (k 1) = 4 s 5 c 1 c 2 s 5 c 4 Stage 6 8, : c 1 : s 1 c 3 : s 8 c 2 : s 2 s 3 s 4 c 4 : s 5 s 6 s 7 7. p C n q C SDRQ 6 7 8. SDRQ ML-. (Serial Dictatorship, SD) 53
SD [1]. SDRQ SD SDRQ s c s µ(s) c ML s c c ML s SDRQ ML- 4.2 DA DA (Multi-Stage Deferred Acceptance with regional quotas, MSDARQ) MSDARQ MSDA [5] SDRQ ( ) MSDARQ SDRQ DA DA MSDARQ ML MSDARQ E 1 E 0 \ E 1 (E 0 = S) DA E 1 = e 1 p C E 1 = {s n e1 +1, s n e1 +2,..., s n }, E 1 e 1 E 0 \ E 1 DA µ 1 µ 1 MSDARQ E 0 = S, e 1 = p C r R p 1 r = p r qr 1 = q r k = 1 Stage k 1 Step 1: E k = {s n ek +1, s n ek +2,..., s n } E k ML e k (a) E k 1 \ E k DA E k 1 \ E k (DA ) (b) E k 1 \ E k = E k SDRQ Step 2: Step 1 µ k p k+1 r, qr k+1, a k+1 r 9 e k+1 = p k+1 C k k + 1 Step 1 MSDARQ Step 1 (b) C C 0 E k DA 2. 1 MSDARQ Stage 1 6 E 1 = {s 3, s 4, s 5, s 6, s 7, s 8 } s 1 s 2 DA Stage 1 s 1 c 2 s 2 c 1 Stage 2 6 p 2 C = 4 E 2 = {s 5, s 6, s 7, s 8 } s 3 s 4 DA Stage 2 s 3 s 4 c 2 Stage 3 4 p 3 C = 4 E 3 E 2 SDRQ SDRQ Stage Case 2 s 5, s 6, s 7, s 8 c 3 c 4 : c 1 : s 2 c 3 : s 8 c 2 : s 1 s 3 s 4 c 4 : s 5 s 6 s 7 9. p C n q C MSDARQ. Step 1 (a) 5 MSDARQ Step 1 (b) SDRQ 7 10. MSDARQ ML-. DA SDRQ s SDRQ 54
ratio of students with envies 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 SDRQ MSDARQ AC-MSDA AC-DA 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 ratio of minimum quotas ratio of claiming students 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 SDRQ MSDARQ AC-MSDA AC-DA 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 ratio of minimum quotas ratio of students 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 SDRQ MSDARQ AC-MSDA AC-DA 5 10 15 20 25 rank 1 2 3 ML- Stage k s, c Stage k c ML s Stage k c c ML s Stage k c s c Stage k DA Stage k c c s Stage k SDRQ Stage k c ML s c ML c s ML- 5 SDRQ MSDARQ n = 512, m = 64 q {c} = 40 p {c} = 0 6 *1 r R a r 64 448 u c [0, 1] m u s [0, 1] m s α [0, 1] αu c + (1 α)u s α α 0.6 c ML s 1 ML ML s n *1 100 AC-DA AC-MSDA AC-DA 8 DA AC-MSDA r R a r/m, [5] MSDA AC-DA AC-MSDA 40 AC-DA 8 AC-MSDA AC-DA 1 ( ) x r R a r/n, AC-DA MSDARQ SDRQ AC-MSDA 2 x 1 MSDARQ SDRQ AC-DA AC-MSDA AC-DA 70% 3 (cumulative distribution functions, CDFs) MSDARQ x 5 0.8 80% 1 5 MSDARQ SDRQ 55
rank of students for schools 400 350 300 250 200 150 100 4 50 SDRQ MSDARQ AC-MSDA AC-DA 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 ratio of minimum quotas ) 1 open ML MSDARQ MSDARQ 70% 2 AC-DA AC-MSDA MSDARQ SDRQ 4 x 1 2 AC-DA AC-MSDA MSDARQ SDRQ MSDARQ MSDARQ ML ML AC-DA MSDARQ SDRQ SDRQ MSDARQ MSDARQ 6 SD MSDA ( [1] A. Abdulkadiroglu and T. Sonmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, Vol. 66, No. 3, pp. 689 702, 1998. [2] A. Abizada and S. Chen. The college admission problem with entrance criterion. 2011. mimeo. [3] P. Biro, T. Fleiner, R. W. Irving, and D. F. Manlove. The college admissions problem with lower and common quotas. Theoretical Computer Science, Vol. 411, No. 34-36, pp. 3136 3153, 2010. [4] L. Ehlers, I. E. Hafalir, M. B. Yenmez, and M. A. Yildirim. School choice with controlled choice constraints: Hard bounds versus soft bounds. 2012. mimeo. [5] D. Fragiadakis, A. Iwasaki, P. Troyan, S. Ueda, and M. Yokoo. Strategyproof matching with minimum quotas. 2012. mimeo (An extended abstract version appeared in AAMAS, pages 1327 1328, 2012). [6] R. W. Irving, D. F. Manlove, and S. Scott. The stable marriage problem with master preference lists. Discrete Applied Mathematics, Vol. 156, pp. 2959 2977, 2008. [7] Y. Kamada and F. Kojima. Stability and strategy-proofness for matching with constraints: A problem in the japanese medical match and its solution. American Economic Review, Vol. 102, No. 3, pp. 366 370, 2012. [8] N. Perach, J. Polak, and U. G. Rothblum. A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion. International Journal of Game Theory, Vol. 36, pp. 519 535, 2007. [9] N. Perach and U. G. Rothblum. Incentive compatibility for the stable matching model with an entrance criterion. International Journal of Game Theory, Vol. 39, pp. 657 667, 2010. [10] A. E. Roth and M. A. O. Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (Econometric Society Monographs). Cambridge University Press., 1990. 56