Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Многие учебные заведения позволяют студентам регистрироваться в порядке очереди . Однако это может привести к несправедливым результатам: студент, который оказывается рядом со своим компьютером, когда начинается регистрация, может успеть зарегистрироваться на все наиболее востребованные курсы, в то время как студент, который приходит слишком поздно, может обнаружить, что все желаемые курсы уже заполнены. и сможете записаться только на менее востребованные курсы. Чтобы смягчить эту несправедливость, многие учреждения используют более сложные механизмы распределения. [1]

Тяговые механизмы [ править ]

В механизме драфта (также называемом циклическим ) студенты по очереди выбирают курсы из набора курсов с доступными местами. Порядок выбора является случайным в первом раунде, а затем меняется на противоположный в последующих раундах. На практике студентам не нужно выбирать по раундам: они могут просто сообщить о своих предпочтениях по отдельным курсам на компьютер, и компьютер выберет для них курсы по одному. Эта процедура использовалась, например, в Гарвардской школе бизнеса с середины 1990-х годов. [2]

Одна из проблем с черновиком процедуры состоит в том, что она не защищена от стратегии : студенты потенциально могут получить лучшие курсы, манипулируя своими заявленными предпочтениями. Более того, черновиком легко манипулировать: студенты должны завышать отчет о том, насколько им нравятся более востребованные курсы, и занижать, насколько им нравятся менее востребованные курсы. Результаты полевого исследования в Гарварде показывают, что студенты действительно манипулируют своими предпочтениями, и это манипулирование приводит к распределению, неэффективному по Парето и имеющему низкое социальное обеспечение . [2]

Вариантом черновика, который потенциально может снизить неэффективность из-за манипуляций, является прокси-черновик . В этом механизме учащиеся по-прежнему сообщают о своих предпочтениях компьютеру, но на этот раз компьютер оптимальным образом управляет их предпочтениями, а затем воспроизводит исходный черновик. Эта процедура снижает потери благосостояния из-за ошибок в манипуляциях и незнания позиции в последовательности выбора. [3] : 5

Другие варианты - это проект квеста [4] и проект, улучшающий Парето . [5]

Случайная серийная диктатура [ править ]

Экономические теоретики доказали, что случайная последовательная диктатура (RSD) является единственным стратегически защищенным механизмом, который постфактум эффективен по Парето и удовлетворяет некоторым другим естественным свойствам. Исходя из этого теоретического факта, они предложили использовать его на практике для распределения курсов. [6] [7] [8]

Однако полевые эксперименты показали, что RSD работает хуже, чем управляемый механизм проекта по естественным показателям, таким как количество студентов, которые выбирают первый вариант, средний рейтинг курсов на одного студента. [3] : 5

Механизмы торгов [ править ]

В механизме торгов каждому студенту дается фиксированная сумма нереальных денег, и он может распределить эти «деньги» между курсами, которые он / она желает пройти. Заявки всех студентов на все курсы упорядочиваются в порядке убывания и обрабатываются по очереди. Каждая ставка, в свою очередь, считается удовлетворенной, если и только если студент не заполнил свое расписание и на курсе есть свободные места. Аналогичные механизмы используются в Росс школы бизнеса , Columbia Business School , Хаас Школа Бизнеса , Kellogg School управления , Принстонский университет , Йельской школы менеджмента [9] и Тель-Авивском университете .[10]

Механизмы равновесия [ править ]

В механизме равновесия каждому студенту разрешается ранжировать все возможные расписания курсов (т. Е. Все подмножества курсов, в которых никакие два курса не перекрываются во времени, никакие два курса не преподают один и тот же материал в разное время и т. Д.) компьютер находит конкурентное равновесие из равных доходов на этом рынке. Поскольку точное конкурентное равновесие может не существовать, на практике часто используется механизм приблизительного конкурентного равновесия на основе равных доходов (A-CEEI). Эрик Будиш разработал теорию; [11] Осман и Сандхольм [12] предоставили эффективные компьютерные реализации. Механизм реализован в Wharton Business School., заменяя предыдущий механизм на основе торгов. [13]

Необходимость сообщать о ранжировании по расписаниям является серьезной проблемой при реализации таких алгоритмов, поскольку количество возможных расписаний может быть очень большим. [14] [15] Для решения этой проблемы необходимо разработать простой язык, позволяющий учащимся описывать свои предпочтения в разумные сроки. Язык, разработанный в Wharton, позволяет студентам указывать полезность для каждого отдельного курса и «значение корректировки» для каждой пары курсов. Полезность каждой пары - это сумма полезностей отдельных курсов плюс значение корректировки. Нулевые / положительные / отрицательные значения корректировки соответствуют курсам, которые являются независимыми товарами / дополнительными товарами / заменяющими товарами.соответственно. Кроме того, запрещены некоторые конкретные комбинации курсов (например, курсы, которые проводятся одновременно или имеют одинаковое содержание). Хотя этот язык не позволяет выразить все возможные рейтинги в расписаниях, на практике этого достаточно. [13]

Другие механизмы [ править ]

Другие механизмы для распределения курсов включают справедливое случайное назначение , [16] стабильное соответствие , [17] [18] [19] и механизмы, основанные на оптимизации . [20]

Ссылки [ править ]

  1. ^ Коминерс, Скотт Дьюк; Рубери, Майк; Ульман, Джонатан (2010). Сабери, Амин (ред.). «Распределение курса через аукцион по доверенности» . Интернет и сетевая экономика . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 551–558. DOI : 10.1007 / 978-3-642-17572-5_49 . ISBN 978-3-642-17572-5.
  2. ^ a b Будиш, Эрик; Кантильон, Эстель (2007). Крэмтон, Питер; Мюллер, Рудольф; Тардос, Ева; Тенненхольц, Моше (ред.). «Стратегическое поведение в задачах с несколькими единицами назначения: теория и доказательства из распределения курсов» . Вычислительные социальные системы и Интернет . Дагштульский семинар. Дагштуль, Германия: Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Германия.
  3. ^ a b Будиш, Эрик; Кантильон, Эстель (01.08.2012). «Проблема распределения нескольких единиц: теория и доказательства из распределения курсов в Гарварде» . Американский экономический обзор . 102 (5): 2237–2271. DOI : 10,1257 / aer.102.5.2237 . ISSN 0002-8282 . 
  4. ^ Хошино, Ричард; Райбл-Кларк, Калеб (27.07.2014). «Черновик квеста: алгоритм автоматического распределения курсов» . Труды Двадцать восьмой конференции AAAI по искусственному интеллекту . AAAI'14. Квебек, Квебек, Канада: AAAI Press: 2906–2913.
  5. ^ Ли, Менглинг (2020-10-01). «Связи имеют значение: повышение эффективности распределения курсов за счет разрешения связей» . Журнал экономического поведения и организации . 178 : 354–384. DOI : 10.1016 / j.jebo.2020.07.030 . ISSN 0167-2681 . 
  6. ^ Папай, Szilvia (2001). «Стратегически стойкие и небезупречные множественные назначения» . Журнал общественной экономической теории . 3 (3): 257–271. DOI : 10.1111 / 1097-3923.00066 . ISSN 1467-9779 . 
  7. ^ Элерс, Ларс; Клаус, Беттина (2003). «Коалиционные стратегически обоснованные и ресурсо-монотонные решения для множественных задач назначения» . Социальный выбор и благосостояние . 21 (2): 265–280. ISSN 0176-1714 . 
  8. ^ Хэтфилд, Джон Уильям (2009-09-01). «Стратегическое, эффективное и небезопасное распределение квот» . Социальный выбор и благосостояние . 33 (3): 505–515. DOI : 10.1007 / s00355-009-0376-6 . ISSN 1432-217X . 
  9. ^ Сёнмез, Тайфун; Юнвер, М. Утку (2010). «Предложение курсов в бизнес-школах *» . Международное экономическое обозрение . 51 (1): 99–123. DOI : 10.1111 / j.1468-2354.2009.00572.x . ISSN 1468-2354 . 
  10. ^ "Инструкции по регистрации в Тель-Авивском университете (на иврите)" . 2020-06-15.
  11. ^ Будит, Эрик (2011-12-01). «Комбинаторная проблема распределения: приблизительное конкурентное равновесие от равных доходов» . Журнал политической экономии . 119 (6): 1061–1103. DOI : 10.1086 / 664613 . ISSN 0022-3808 . 
  12. ↑ Осман, Авраам; Сандхольм, Туомас; Будиш, Эрик (10.05.2010). «Нахождение приблизительного конкурентного равновесия: эффективное и справедливое распределение курса» . Материалы 9-й Международной конференции по автономным агентам и многоагентным системам: том 1 - Том 1 . AAMAS '10. Торонто, Канада: Международный фонд автономных агентов и многоагентных систем: 873–880. ISBN 978-0-9826571-1-9.
  13. ^ a b Будиш, Эрик; Cachon, Gérard P .; Кесслер, Джадд Б .; Осман, Авраам (28 октября 2016 г.). «Соответствие курсов: крупномасштабная реализация приблизительного конкурентного равновесия на основе равных доходов для комбинаторного распределения» . Исследование операций . 65 (2): 314–336. DOI : 10.1287 / opre.2016.1544 . ISSN 0030-364X . 
  14. ^ Будиш, Эрик; Кесслер, Джадд Б. (25 июля 2016 г.). «Могут ли участники рынка точно (достаточно) сообщать о своих предпочтениях?» . Цитировать журнал требует |journal=( помощь )
  15. ^ Будиш, Эрик Б .; Кесслер, Джадд Б. (12 ноября 2017 г.). «Могут ли агенты сообщать о своих типах? Эксперимент, изменивший механизм распределения курсов в Wharton» . Рочестер, штат Нью-Йорк. Цитировать журнал требует |journal=( помощь )
  16. ^ Будиш, Эрик; Че, Ён-Ку; Кодзима, Фухито; Милгром, Пол (2013-04-01). «Разработка механизмов случайного распределения: теория и приложения» . Американский экономический обзор . 103 (2): 585–623. DOI : 10,1257 / aer.103.2.585 . ISSN 0002-8282 . 
  17. ^ Дибольд, Франц; Азиз, Харис; Бихлер, Мартин; Маттес, Флориан; Шнайдер, Александр (2014-04-01). «Распределение курса через стабильное соответствие» . Бизнес и информационные системы . 6 (2): 97–110. DOI : 10.1007 / s12599-014-0316-6 . ISSN 1867-0202 . 
  18. ^ Budish, Эрик (2012-12-01). «Соответствие» и «конструкция механизма» . Биржи ACM SIGecom . 11 (2): 4–15. DOI : 10.1145 / 2509002.2509005 .
  19. ^ Дибольд, Франц; Бихлер, Мартин (2017-07-01). «Сопоставление с безразличием: сравнение алгоритмов в контексте распределения курсов» . Европейский журнал операционных исследований . 260 (1): 268–282. DOI : 10.1016 / j.ejor.2016.12.011 . ISSN 0377-2217 . 
  20. ^ Atef Yekta, Ход; День, Роберт (13.01.2020). «Оптимизационные механизмы для задачи распределения курсов» . ИНФОРМС Журнал по вычислительной технике . 32 (3): 641–660. DOI : 10.1287 / ijoc.2018.0849 . ISSN 1091-9856 .