Механизмы распределения учеников по школам

Докажем сначала, что в отображении р нет ни одной проблемной пары из всех шагов механизма GSM (имеются ввиду те, что приводят к изменению списков предпочтений, то есть, грубо говоря, последние проблемные пары).

Доказывать будем по индукции.

База. В р нет проблемной пары шага 1.

И опять же от противного. Пусть есть. Обозначим эту пару за (i₁, s₁). Заметим, что так как i₁ был отвергнут школой s₁ на первом шаге работы алгоритма GSM, то школа s₁ заполнена отображением м₁. Значит, есть студент i₂, который попал в s₁ по результатам м₁, но не попал в s₁ по результатам р. Так как р Парето-доминирует м₁, значит, i₂ попал в более предпочтительную для себя школу s₂ по итогам р. Так как для i₂ школа s₂ более предпочтительна, чем s₁, значит, на первом шаге GSM он был отвергнут этой школой. Значит, она заполнена при м₁. Продолжаем аналогичное рассуждение, пока не образуется цикл - найдется студент i_m, который попал в школу s₁ по результатам р, которая для него более предпочтительна, чем s_m-1.

Таким образом, мы получили цикл студентов, каждый из которых предпочитает школу, в которую попал следующий по итогам м₁, и попал в эту школу по итогам р.

Тогда рассмотрим подробнее работу первого шага механизма GSM. Возьмем из студентов цикла того, кто был последним (или одним из нескольких последних - если они поступали в свои школы на одном этапе) принят школой из цикла (в которой он оказался в конце по итогам м₁). Обозначим его i. Студент из цикла, который предпочитал эту школу, уже был отвергнут этой школой (так как иначе, ему бы еще только предстояло поступать в свою конечную школу, что противоречит предположению о том, что рассматриваемый студент i был последним, поступающим в свою школу). Значит, данная школа заполнена на момент поступления рассматриваемого студента i. Но тогда, чтобы принять студента i, она должно отвергнуть какого-то другого студента j, что делает его смутьяном. Причем смутьян j был выгнан из школы позже, чем смутьян i₁ (который, как студент из цикла, уже поступил (или поступает на данном этапе) в свою конечную школу). Противоречие.

Таким образом, в р последний смутьян первого шага не распределяется в школу из проблемной пары. База доказана.

Переход. Пусть в р нет проблемных пар первых t шагов. Тогда в р нет проблемной пары шага t+1.

Доказывается абсолютно аналогично базе, добавляя тот факт, что никто из студентов полученного цикла не является смутьяном для школы, которую он предпочитает.

Таким образом, мы получили, что в р нет проблемных пар. Попробуем использовать то же рассуждение, что и раньше.

Так как р Парето-доминирует м, то есть студент i₁, для которого отображение р предлагает лучшую школу s₁, чем школа, куда его отправило м. Тогда он подавал заявку в м на последнем шаге механизма GSM (так как i₁ распределен в s₁ по итогам р и в р нет проблемных пар, то s₁ не была вычеркнута из списка предпочтений i₁) и был отвергнут, значит, школа s₁ заполнена при м, значит, есть студент i₂, поступивший в s₁ по итогам м и попавший в какую-то другую школу s₂ по итогам р, которая должна быть для него лучше, чем s₁ и т.д. Опять получаем цикл студентов. И так как никто из них не является смутьяном для школы, в которую он больше хочет попасть (школу из р), то он должен подавать в нее заявку при м. Тогда опять рассмотрим последнего принятого механизмом GSM студента i; так как в эту школу уже поступал студент из цикла, то она должна быть заполнена, значит, поступая, студент i “выгоняет” какого-то студента j, который становится смутьяном, что противоречит тому, что это последний шаг работы алгоритма.

Таким образом, противоречие, и мы доказали, что GSM - Парето-эффективен.

Свойство 3. Механизм GSM не является правдивым.

Док-во.

Чтобы показать, что механизм GSM не является правдивым механизмом достаточно привести пример, в котором агенту будет выгодно отклониться от правдивой стратегии.

Пусть есть 3 студента и 3 школы, в каждой по 1 месту. Предпочтения студентов задаются следующим образом:

i₁: s₂ s₃

i₂: s₃ s₁

i₃: s₃ s₁

Предпочтения школ задаются следующим образом:

s₁:

s₂: i₃ i₁

s₃: i₁ i₂ i₃

Если все агенты сообщают свои истинные предпочтения, то механизм GSM работает следующим образом:

Табл.6 -правдивые стратегии

Теперь предположим, что агент 3 решил сообщить следующие предпочтения:

i₃: s₃ s₂ (вместо s₃ s₁)

Тогда механизм GSM работает следующим образом:

Шаг 0.

Табл.7 - стимулы к отклонению от правдивой стратегии

Шаг 1.

Агент i₂ - смутьян, из его списка предпочтений выкидывается s₃. Заново запускается GS:

Табл.8 - стимулы к отклонению от правдивой стратегии

Работа алгоритма заканчивается. Заметим, что сообщив измененные предпочтения студент 3 оказался в перво-приоритеной школе, в то время как, сообщив правду - в школе второго приоритета. Таким образом, соврав, он улучшил свое благосостояние, а значит механизм не является правдивым.

Таким образом, мы построили Парето-эффективный механизм, доминирующий исходы механизма GS. К сожалению, при этом пришлось пожертвовать двумя другими свойствами - стабильностью и правдивостью.

Более того, можно сказать, что GSM строится на нарушении стабильности. Мы нарушаем стабильность в пользу эффективности. Механизм может создавать на каждом шаге блокирующие пары для улучшения итогового исхода. Рассмотрим блокирующую пару (i, s) и студента j, который имеет меньший приоритет в школе s, чем i, но попал в нее. Да, студента i не взяли в школу, в которой он более приоритетен. Но при обычном GS его бы тоже туда не взяли. GSM не ухудшает результат для всех индивидов, но может и улучшить (если работает больше 1 шага, то есть, если есть хоть одна проблемная пара). Тот же студент i в результате работы GSM хоть и не попадет в s, но он может попасть в лучший для себя вариант, чем тот, в который его определит GS, а может даже и в лучший, чем s. И назвать его зависть студенту j, которого в итоге определили в лучшую для i школу, “обоснованной” (ссылаясь на термин elimination of justified envy) неправильно. Данный механизм просто улучшил результат для j сильнее, чем для i (с точки зрения предпочтений студента i, но необязательно с точки зрения предпочтений студента j). нэш парето студент

Несмотря на нарушение правдивости, хочется отметить, что, не зная предпочтений других студентов и школ, данным механизмом почти невозможно манипулировать (особенно на больших примерах). Сообщив не свои истинные предпочтения, студент рискует проиграть. Студент i₃ в приведенном примере (пример 9) знал, предпочтения и всех других агентов, и всех школ, и только это позволило ему подгадать, какие предпочтения лучше заявить. Не обладая данной информацией, сделать это было бы намного труднее.

Заключение

В современном мире многие города, такие как Нью-Йорк, Бостон (в основном, американские) используют централизованную систему распределения учеников. С учетом растущей популярности таких систем, значение метода распределения, который применит район, велико.

И хотя пока применение механизмов распределения распространено в основном в США, со временем, вероятно, все города (районы) будут использовать четкие эффективные системы распределения.

В этой работе строится механизм распределения учеников по школам, исход которого лучше или такой же для каждого ученика, чем исход существующего механизма GS. Распределения, создаваемые данным механизмом, - Парето-эффективны. Хотя данный механизм не обладает двумя другими свойствами, рассматриваемыми в данной области, - стабильностью и правдивостью - нужно отметить, что манипулировать данным механизмом очень сложно, а стабильность жертвуется в пользу эффективности.

В заключение, хотелось бы также отметить, что программа расчета распределения, основанная на предложенном алгоритме, хоть и сложна, но будет работать за полиномиальное время (механизм GS работает за полиномиальное время, данный механизм включает в себя линейное количество GS, каждый студент может быть смутьяном не более чем S раз (если S - количество школ), студентов не больше I, таким образом, “отлов” смутьянов занимает также полиномиальное время).

Список литературы

1. Abdulkadiroрlu, A., Pathak, P.A., Roth, A.E. Strategy-proofness versus efficiency in matching with indifferences: redesigning the NYC High School match // American Economic Review, 99, 2009, P. 1954-78.

2. Abdulkadiroрlu, A., Sцnmez, T. School choice: a mechanism design approach // American Economic Review, 93, 2003, P. 729-747.

3. Budish, E., Cantillon, E. The multi-unit assignment problem: theory and evidence from course allocation at Harvard // American Economic Review, 102, 2012, P. 2237-71.

4. Budish, E., Che, Y., Kojima, F., Milgrom P. Designing random allocation mechanisms: theory and applications // American Economic Review, 103, 2013, P. 585-623.

5. Dubins, L. E., Freedman, D. A. Machiavelli and the Gale-Shapley algorithm // American Mathematical Monthly, 88, 1981, P. 485-494.

6. Fujishima, S. Evolutionary implementation and congestion games with heterogeneous cost functions, 2011.

7. Fujishima, S. Evolutionary implementation of optimal number and size of cities, 2011.

8. Gale, D., Shapley, L.S., College admissions and the stability of marriage // American Mathematical Monthly, 69, 1962, P. 9-15.

9. Ghosh, I. Applying mechanism design theory to allocation problems in universities // Journal of Economics & Economic Education Research, 14, 2013, P. 49-64.

10. Hamada K, Iwama K, Miyazaki S. The hospitals/residents problem with quota lower bounds // Algorithms - ESA 2011, P. 180-191.

11. Han, D., Yang H., Yuan, X. A practical trial-and-error implementation of marginal-cost pricing on networks // Journal of Industrial and Management Optimization, 6, 2010, P. 299-313.

12. Kakutani, S. A generalization of Brouwer's fixed point theorem // Duke Mathematical Journal, 8, 1941, P. 457-459.

13. Kominers, S. D., Ruberry, M., llman, J. Course allocation by proxy auction // Lecture Notes in Computer Science, 6484, 2010, P. 551-558.

14. Nisan, N. Algorithmic mechanism design (through the lens of multi-unit auctions) // Handbook of Game Theory, IV, 2014.

15. Pathak, P.A. The mechanism design approach to student assignment // Annual Review of Economics, 3, 2011, P. 513-536.

16. Rosenthal, R. W. A class of games possessing pure-strategy Nash equilibria // International Journal of Game Theory, 2, 1973, P. 65-67.

17. Roth, A. E., Postlewaite A. Weak versus strong domination in a market with indivisible goods // Journal of Mathematical Economics, 4, 1977, P. 131-139.

18. Roth, A. E. The economics of matching: stability and incentives // Mathematics of Operations Research, 7, 1982, P. 617-628.

19. Sandholm, W. H. Evolutionary implementation and congestion pricing // Review of Economic Studies, 69, 2002, P. 667-689.

20. Sandholm, W. H. Negative externalities and evolutionary implementation // Review of Economic Studies, 72, 2005, P. 885-915.

Размещено на Allbest.ru