Диссертация (1137447), страница 22
Текст из файла (страница 22)
95. –– P. 376–380.15751. Roth A.E., Sonmez T., Unver M.U. Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences //American Economic Review. –– 2007. –– Vol. 97, no. 3. –– P. 828–851.52. The Need for (long) Chains in Kidney Exchange / I. Ashlagi,D. Gamarnik, M.A. Rees, A.E. Roth. –– 2012.53. Niederle M., Roth A.E. The Gastroenterology Fellowship Match:How it failed, and why it could succeed once again // Gastroenterology. –– 2004. –– Vol.
127. –– P. 658–666.54. Niederle M., Roth A.E. Relationship Between Wages and Presence ofa Match in Medical Fellowships // Journal of the American MedicalAssociation. –– 2003. –– Vol. 290, no. 2. –– P. 1153–1154.55. Haruvy E., Roth A.E., Unver M.U. The Dynamics of Law ClerkMatching: An Experimental and Computational Investigation of Proposals for Reform of the Market // Journal of Economic Dynamicsand Control. –– 2006. –– Vol. 30. –– P. 457–486.56. The New Market for Federal Judicial Law Clerks / C. Avery, C. Jolls,R.A.
Posner, A.E. Roth // University of Chicago Law Review. ––2007. –– Vol. 74. –– P. 447–486.57. Luce D. Semiorders and a Theory of Utility Discrimination // Econometrica. –– 1956. –– Vol. 24, no. 2. –– P. 178–191.58. Aleskerov F. Simple and Simplest Semiorders // Dokl. Mathematics. –– 2002. –– Vol. 387. No. 2. –– P. 175–177.59. Aleskerov F., Bouyssou D., Monjardet B. Utility Maximization,Choice and Preference. –– Berlin : Springer Verlag, 2007.15860. Алескеров Ф.Т. Простые и простейшие полупорядки в задаче экстремизационного выбора с аддитивной погрешностью // Автоматика и телемеханика.
— 2002. — Т. 2. — С. 137–145.61. Fishburn P.C. Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. –– New York: Wiley, 1985.62. A supply and demand framework for two-sided matching markets :Rep. / Harvard University Working Paper ; Executor:E.M. Azevedo, J. Leshno : 2012. –– URL: http://fmwww.bc.edu/ec-j/SemF2011/azevedo.pdf.159Приложение AДоказательство утверждений овыборе абитуриентовАбитуриент должен выбрать 5 ВУЗов так, чтоб максимизироватьсвою ожидаемую полезность.
Упорядочим ВУЗы в наборе так, что напервом месте будет стоять лучший ВУЗ из 5, а на пятом месте худший. Тогда процесс выбора ВУЗов может быть описан как задача динамического программирования из 5 шагов. Будем решать этузадачу с конца, начиная с выбора самого слабого ВУЗа в наборе.Шаг 5Выбор наименее предпочтительного ВУЗа в нашем наборе зависитот предпочтений абитуриентв и от того, какой ВУЗ был выбран на4-ом шаге (т.к. ВУЗ на 5-ом шаге не может быть лучше 4-го и неможет совпадать с ним). Выбирать ВУЗ из категории хуже, чем i,абитуриент не может. Поэтому выбор абитуриента будет решением160следующей задачи:(2−5 * (5 +4 +4≥ 5 +4 ≥ 555 2) )+1(A.1)5 ≥ 1 ≤ 5 ≤ 5 , 5 при каждых заданных 4 , 4 , и .
Максимум целевой функции этойзадачи без учета ограничений, связанных с решением на шаге 4, достигается в точке 5 = , 5 = при всех ≥ 2. Поскольку выборболее одного ВУЗа из категории j=i заведомо невыгоден (поступлениев ВУЗ категории i абитуриент считает гаратированным). Следовательно, какими бы ни были решения на первых четырех шагах, в качествепятого ВУЗа будет выбран гарантированный ВУЗ из категории .Шаг 4Итак, мы знаем, что на пятом шаге все абитуриенты из категорий ≥ 2 выберут любимый ВУЗ из числа тех, поступление в которыйсчитают гарантированным.
Тогда на 4-ом шаге нужно выбрать ВУЗ(заведомо из категории более высокой, чем i), удовлетворяющий сле-161дующим условиям:(2( − 4 ) * (4 +3 +3≥ 4 +4+4)+ (1 − 2−4 ) * ( + 1)2 )13 ≥ 4(A.2)4 ≥ + 11 ≤ 4 ≤ 4 , 4 Экстремум задачи без учета ограничений, связанных с решением, принятым на более ранних шагах, достигается при 4 = + 2, 4 = .При всех решениях предыдущих шагов, таких что 3 ≥ + 3, на четвертом шаге будет сделан выбор 4 = + 2, 4 = 1, т.к. эта точкаявляется глобальным экстремумом в дискретном случае.Если на предыдущем шаге был выбран ВУЗ 3 = + 1, 3 = − , тоединственно возомжным решение остается 4 = + 1, 4 = − − 1.Если же на предыдущем шаге было выбрано 3 = + 2, 3 = − , то глобальный экстремум целевой функции уже не может бытьрешением задачи, т.к. не будет удовлетворять ограничениям.
Можетбыть выбрано два варианта: 4 = +2, 4 = − −1 или 4 = +1, 4 =1. Сравним ожидаемые полезности в этих случаях:1−−1 24 ( + 2, − − 1) = ( + 2 +) +414 ( + 1, ) = ( + 2)2 +23( + 1)241( + 1)22(A.3)(A.4)Функция (12) является убывающей от y. Выбор абитуриента будет зависеть от конкретных y, n, i, однако будет "переключаться от первоговарианта ко второму при одном значении y.162Решив соответствующее неравенство, получим, что при ≥ ( +√1)( 12 + 32 + 21 2 + 6 + 7) следует выбирать 4 = + 1. Иначе говоря,если нет очень привлекательного ВУЗа из категории +2 , разумнеевыбрать наилучший ВУЗ из категории +1 . Нижняя граница добавочной привлекательности 4 растет с увеличением i. Таким образом,чем выше качество подготовки абитуриента, тем меньше он склоненрисковать и подавать документы в более сильный ВУЗ.Шаг 3На шаге 3 необходимо будет рассматривать два случая каждый раз,в зависимости от решения, которое последует на шаге 4. В общемслучае задача отыскания оптимального решения будет выглядеть следующим образом(2−3 (3 +2 +2≥ 3 +3)3+ (1 − 2−3 )(2−4 * (4 +4)+ (1 − 2−4 ) * ( + 1)2 )),+ 1 ,2 ≥ 3 ,3 ≥ 4 ,1 ≤ 3 ≤ ,3 , 3 .(A.5)В этой задаче переменными являются 3 , 3 .
Величины 2 , 2 , , являются параметрами задачи, а величины 4 , 4 определяются в соответстии с выявленным выше правилом.Заметим, что поскольку всего в выборе 5 шагов и на первом шагенецелесообразно выбирать ВУЗ из какой-либо категории с < , то∀2 2 = − 1 или 2 = .163Рассмотрим последовательно все возможные ситуации.2 = + 1, 2 = − В этом случае единственно возможным решением является 3 = + 1, 3 = − − 1 при > 2 = + 2Сначала рассмотрим такие значения n, при которых на четвертомшаге будет выбран ВУЗ из категории +2 .
Рассмотрим случай 2 =√ − 1, ≥ 23 + 92 + 32 2 + 6 + 7. При таком n, если будет выбрано3 = + 2, 3 = − 2, то на четвертом шаге будет принято решение4 = + 2, 4 = − 3. Возможные стратегии на третьем шаге: выбрать3 = + 2 или 3 = + 1. Сравним ожидаемые полезности в обоихслучаях1−2 23−3 2923 ( + 2, − 2) = ( + 2 +) + ( + 2 +) + ( + 1)(A.6)41616211−1123 ( + 1, ) = ( + 2)2 + ( + 1 +) + ( + 1)(A.7)244Найдем n, при которых выполняется неравенство 3 (+2, −2 ) ≥ 3 (+1, ).
Оказывается, что при соблюдении ограничения на значение n(15) всегда больше (16), поэтому выбор при заданных условиях выборабитуриента однозначный,а именно такой что 3 = + 2, 3 = − 2.√Теперь рассмотрим ситуацию, когда 2 = , ≥ + 3 + 2 + 6 * + 7.Опять сравним ожидаемые полезности в двух вариантах развития со-164бытий1−1 23−2 2923 ( + 2, − 1) = ( + 2 +) + ( + 2 +) + ( + 1)(A.8),4161611−1 2 1223 ( + 1, ) = ( + 2) + ( + 1 +) + ( + 1)(A.9).244В данном случае также при выполнении ограничения на n всегда будетвыбрано решение 3 = + 2, 3 = − 1.Теперь рассмотрим ситуации, когда n достаточно мало, чтобы абитуриент выбирал 4 = + 1, 4 = при 3 = + 2.
Здесь опять нужноучесть два возможных предыдущих состояния: 2 = − 1 и 2 = .√Рассмотрим случай 2 = − 1, < 23 + 29 + 32 2 + 6 + 7. При такомn при выборе 3 = + 2, 3 = − 2 на четвертом шаге будет приняторешение 4 = + 1, 4 = 1.Возможные стратегии на третьем шаге: выбрать 3 = + 2 или 3 = + 1.
Сравним ожидаемые полезности в обоих случаях:−2 2 331) + ( + 2)2 + ( + 1)2 , (A.10)3 ( + 2, − 2) = ( + 2 +488211−113 ( + 1, ) = ( + 2)2 + ( + 1 +) + ( + 1)2 . (A.11)244Полезность (18) выше при всех ≥√2+8+ 42 +20+22.2+7Правая частьэтого неравенства меньше 2 при всех i. В то же время, для выбора3 = + 2, 3 = − 2 значение n должно быть больше или равно 3,так как выбирается три ВУЗа из одной категории. Таким образом, привсех допустимых n выбор абитуриента будет 3 = + 2, 3 = − 2.√Теперь рассмотрим ситуацию, когда 2 = , а < + 3 + 2 + 6 + 7.При данных n, абитуриент, выбравший 3 = + 2, 3 = − 1, начетвертом шаге сделает выбор 4 = + 1, 4 = 1.В данном случае165можно воспользоваться выводом предыдущего абзаца, так как 3 ( +2, − 1) > 3 ( + 2, − 2) при одинаковом выборе на 4-ом шаге.Следовательно, выбор абитуриента в этом случае 3 = + 2, 3 = − 2.2 = + 3Сначала рассмотрим ситуацию, когда 2 = 1.
В результате предшествующего анализа было получено, что 3 ( + 2, − 1) > 3 ( + 1, 1).Следовательно, верно и следующее: 3 ( + 2, 1) > 3 ( + 1, 1). Поэтому остается сравнить два возможных решения абитуриента - 3 = + 3, 3 = − 2 или 3 = + 2, 3 = 1.√Рассмотрим случай ≥ 21 + 32 + 12 2 + 6 + 7 при котором после3 = + 2 на 4-ом шаге будет сделан выбор 4 = + 2, 4 = − 1.Ожидаемые полезности от возможных решений абитуриента в этомслучае равны:−1 27241) + ( + 3)2 + ( + 1)2 , (A.12)3 ( + 3, − 1) = ( + 3 +83232213−1123 ( + 2, ) = ( + 3)2 + ( + 2 +) + ( + 1)2 .(A.13)41616√1 +1+ 2 +3При всех ≥ 2 и ≥ 2 −1вторая ожидаемая полезность√√2первой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
