Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет Бизнес-информатики
Отделение прикладной математики и информатики
Программа дисциплины
Модели согласования интересов
для направления 010400.62 «Прикладная математика и информатика»
подготовки бакалавра
Автор программы: *****@***ru
Одобрена на заседании кафедры высшей математики на факультете экономики
25 февраля 2013 г.
Зав. кафедрой
Рекомендована секцией УМС «___»____________ 20 г.
Председатель
Утверждена УС факультета «___»_____________20 г.
Ученый секретарь ________________________ [подпись]
Москва, 2012
Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.
2 Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400.62 «Прикладная математика и информатика» подготовки бакалавра, изучающих дисциплину «Дискретная математика».
Программа разработана в соответствии с:
· Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»;
· Образовательной программой 010400.62, направление «Прикладная математика и информатика» подготовки бакалавра;
· Рабочим учебным планом университета по направлению 010400.62 «Прикладная математика и информатика», утвержденным в 2012г.
3 Цели освоения дисциплины
Целями освоения дисциплины «Модели согласования интересов» являются
- формирование представлений у студентов о современных моделях кооперативной теории игр и теории принятия решений дискретных их практическом применени;
- формирование умения демонстрировать знание и понимание основных определений, теорем, алгоритмов и методов решения задач по курсу;
- привить студентам понимание как общности разнообразных моделей согласования интересов, так и представление об отличиях между ними;
- дать студентам знания и умения для освоения на 4-м курсе следующих спецкурсов этого блока.
- развитие творческого, научного потенциала студентов, их познавательных интересов в области теории принятия решений и теории игр, стимулирование к дальнейшему занятию научной деятельностью.
4 Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
Знать: основные факты кооперативной теории игр, модели дележа, влияния, основы теории принятия решений в объеме курса.
Уметь: строго доказывать все утверждения, сделанные при изложении материала курса;
Владеть: терминологией и методами кооперативной теории игр и теории принятия решений.
Компетенция | Код по ФГОС / НИУ | Дескрипторы – основные признаки освоения (показатели достижения результата) | Формы и методы обучения, способствующие формированию и развитию компетенции |
Общенаучные | ОНК-1 | Способность к анализу и синтезу на основе системного подхода | Стандартные (лекционно-семинарские) |
Общенаучные | ОНК-2 | Способность порождать новые идеи (креативность) | Стандартные (лекционно-семинарские) |
Профессиональные | ПК-1 | Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат | Стандартные (лекционно-семинарские) |
Профессиональные | ПК-2 | Способность решать задачи прикладные задачи принятия решений на профессиональном уровне, включая разработку математических моделей, алгоритмических и программных решений | Стандартные (лекционно-семинарские) |
5 Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к циклу дисциплин вариативной части цикла дисциплин профиля подготовки по теме «игровые модели и общественный выбор».
Изучение данной дисциплины базируется на следующих дисциплинах:
· Математический анализ
· Дискретная математика
· Геометрия и алгебра
· Теория вероятностей и математическая статистика
· Теория игр и исследование операций
Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:
· Уметь дифференцировать, интегрировать, анализировать функции одной и нескольких переменной.
· Уметь решать задачи на условный и безусловный экстремум.
· Владеть начальными понятиями теории графов.
· Уметь решать комбинаторные задачи.
· Обладать стандартными знаниями по линейной алгебре в объеме семестрового курса.
· Уметь решать простейшие задачи аналитической геометрии.
· Обладать элементарными знаниями и навыками в теории вероятности.
· Понимать определение равновестия Нэша и уметь находить их в несложных играх.
Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:
· Механизмы принятия решений в экономических системах;
· Теория индивидуального и коллективного выбора;
· Анализ и поддержка решений.
6 Тематический план учебной дисциплины
№ | Название раздела | Всего часов | Аудиторные часы | Самостоятельная работа | ||
Лекции | Семинары | Практические занятия | ||||
1 | Обобщенные паросчетания | 3 | 2 | 6 | ||
2 | Справедливый дележ | 3 | 4 | 9 | ||
3 | Кооперативные игры. Ядро. | 4 | 4 | 8 | ||
4 | Существование ядра и решение Фон Неймана – Моргенштерна. | 6 | 4 | 6 | ||
5 | Вектор Шепли. | 4 | 3 | 8 | ||
6 | Задача голосования. | 4 | 5 | 9 | ||
7 | Принятие коллективных решений. Влияние групп в парламенте. | 6 | 6 | 12 | ||
Итого | 162 | 30 | 28 | 104 |
7 Формы контроля знаний студентов
Тип контроля | Форма контроля | 1 год | Параметры | |
3 модуль | 4 модуль | |||
Текущий | Контрольная работа | 9 неделя | Письменная работа, 120 минут | |
Текущий | Домашнее задание | 6-7 неделя | Письменная работа (решение типовых задач из д/з), 120 минут | |
Итоговый | Экзамен | в конце 4 модуля | Письменная зачетная работа, 160 мин. |
7.1 Критерии оценки знаний, навыков
Для прохождения контроля студент должен, как минимум, продемонстрировать знания основных определений и формулировок теорем; умение решать типовые задачи, разобранные на семинарских занятиях.
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.
7.2 Порядок формирования оценок по дисциплине
Аудиторная и самостоятельная работа не входят в итоговую оценку, т. е. накопленная итоговая оценка вычисляется, как
Онакопл итоговая=(Онакопл 3 модуль+ Онакопл 4 модуль):2,
где Онакопл 3 модуль =Отекущ 3 модуль=Ок/р, Онакопл 4 модуль =Отекущ 4 модуль=Од. з.
Оценка за текущий контроль (и накопленная оценка) не округляется.
Результирующая оценка за дисциплину рассчитывается следующим образом:
Орезульт = 0,6· Онакопл итоговая. + 0,4·Оэкз
Способ округления результирующей оценки – арифметический, за исключением границы 3 / 4, где округление строгое (т. е. для положительной оценки необходиомо набрать 4,00, а не 3,99).
В случае спорной оценки (между 3 и 4) на проставлении студент может получить дополнительную практическую задачу, правильное решение которой оценивается в 1 балл.
8 Содержание дисциплины
Тема I Обобщенные паросочетания.
Предпочтения участников и паросочетания. Задача о свадьбах при линейных предпочтениях участников. Распределение комнат в общежитии. Устойчивые паросочетания. Теорема Гейла – Шепли. Наем персонала.
Литература:
1. Базовый учебник: [1] (гл.2).
2. Дополнительная литература: [12], [15], [16] .
Тема II Справедливый дележ.
Библейский пример дележа. Формализация понятия справедливости. Процедуры справедливого дележа: "дели и выбирай", "подстраивающийся победитель". Решение трудовых споров. Разрешение территориальных конфликтов. Слияние фирм. Поиск справедливого дележа в случае, когда один из пунктов не делим. Справедливый дележ при числе участников большем 2.
Литература:
1. Основная литература: [1] (гл.8).
2. Дополнительная литература: [4], [7], [8], [14] .
Тема III Кооперативные игры. Ядро.
Кооперативные игры. Определения и примеры: задача торга, очистка сбросов, потоки в сетях. Понятие решения кооперативной игры и требования к нему: Парето-оптимальность, индивидуальная рациональность. Ядро.
Литература:
1. Основная литература: [2] (гл.4).
2. Дополнительная литература: [9], [10], [17] .
Тема IV Существование ядра и решение Фон Неймана – Моргенштерна.
Стабильные системы коалиций: вето-игрок, задача о свадьбах. Выпуклые игры: определения, примеры и теорема Шепли. Решение Фон Неймана – Моргенштерна.
Литература:
1. Основная литература: [2] (гл.5-6).
2. Дополнительная литература: [9], [11] .
Тема V Вектор Шепли.
Определение, интерпретация. Свойства решения Шепли: эффективность, анонимность, линейность, отсутствие выплат несущественным игрокам. Аксиоматический подход: теорема единственности. Примеры вычисления вектора Шепли.
Литература:
1. Основная литература: [2] (гл.8).
2. Дополнительная литература: [9] .
Тема VI. Принятие коллективных решений. Влияние групп в парламенте.
Простые игры и голосования с квотой: необходимые и достаточные условия.
Коалиции, число коалиций. Индексы Банцафа и Шепли-Шубика. Влияние групп в российском парламенте и Евросоюзе. Аксиоматический подход к индексам влияния Банцафа и Шепли-Шубика. Другие индексы влияния.
Литература:
1. Основная литература: [1] (гл.6).
2. Дополнительная литература: [5], [6].
Тема VII. Задача голосования.
Правило простого большинства. Парадокс Кондорсе. Правило Борда. Парадокс Эрроу. Ядро и манипулирование предпочтениями. Теорема Гиббарда - Саттертуэйта.
Унимодальные предпочтения и победители по Кондорсе.
Литература:
1. Основная литература: [1] (гл.4-5).
2. Дополнительная литература: [3], [9], [13].
9 Образовательные технологии
На лекцях и семинарах проводится разбор практических ситуаций из экономической, социальной и общественно-политической сфер жизни современного общества.
10 Оценочные средства для текущего контроля и аттестации студента
10.1 Тематика заданий текущего контроля
Вариант контрольной работы по аналогичному курсу прошлых лет.
1.а) Найдите какое-нибудь устойчивое паросочетание при данных предпочтениях
участников.
P(m_1)=w_4,w_2,w_3,w_1; P(w_1)=m_1,m_3,m_2,m_5,m_4;\\
P(m_2)=w_3,w_1,w_4,w_2; P(w_2)=m_2,m_4,m_1,m_5,m_3;\\
P(m_3)=w_2,w_4,w_1,w_3; P(w_3)=m_3,m_1,m_2,m_2,m_5;\\
P(m_4)=w_1,w_3,w_2,w_4; P(w_4)=m_4,m_2,m_3,m_1,m_5.\\
P(m_5)=w_4,w_2,w_3,w_1;\\
б) Найдите все устойчивые паросочетания.
2. Найдите индексы Банцафа для всех участников в следующем голосовании
с квотой
а) (51;35,30,20,15);
б) (11;3,3,3,3,1,1,1,1).
3 а) Найдите все Парето-оптимальные дележи и справедливый дележ при следующих
оценках участников.
A
B
б) Покажите пример манипулирования со стороны B.
4. Рассмотрим "квадратичное правило Борда". Оно аналогично правилу Борда, но последнее место дается нуль очков, за предпоследнее - одно, за предпредпоследнее - 4, за первое (при n+1 кандидате - n^2 очков). Вычислите, каковы будут результаты голосования на профиле
P_1 P_2 P_3 P_4 P_5 P_6 P_7
b b b d a d d
c a c c c c c
d c a b d a b
a d d a b b a
Будет ли это правило удовлетворять аксиоме единогласия? Локальности? Приведите пример манипулирования при использовании этого правила.
5. Найдите ядро и вектор Шепли в кооперативной игре 4 лиц, заданной выигрышами коалиций:
v(i)=1, v(1,2)=4, v(1,3)=3, v(2,3)=2, v(1,4)=2, v(2,4)=3, v(3,4)=4, v(1,4)=3, v(2,4)=2, v(3,4)=4, v(i, j,k)=5, v(1,2,3,4)=8.
10.2 Вопросы для оценки качества освоения дисциплины
Базовые учебники [1] и [2] содержат более 150 задач, которые могут быть использованы для проверки качества усвоения курса студентами
11 Учебно-методическое и информационное обеспечение дисциплины
11.1 Основная литература
, , Шварц отношения, графы и коллективные решения. – М.: ФИЗМАТЛИТ, 2012. «Кооперативное принятие решений: аксиомы и модели», М., Мир, 199111.2 Дополнительная литература
3. , «Выбор вариантов (основы теории)», М., Наука, 1990
«Слияние фирм: анализ трех ключевых проблем», Финансовый бизнес, №6, 2002, 3-7 , «Выборы. Голосование. Партии», М., Академия, 1995 , , "Оценка влияния групп и фракций в российском парламенте (1гг.)", препринт ГУ Высшая Школа Экономики, WP7/2003/01, Москва, 2003 , «Применение теории справедливых решений ктрудовым спорам», Управление персоналом, №1, 2003, 59-61
Делим по справедливости. М., СИНТЕГ, 2003 Данилов по теории игр. М. 2002. , Адельсон-Вельский математика для инженера, М.: Энергия, 1980 Миркин группового выбора. М., Наука, 1974 Дискретные математические модели. М., Наука, 1986 Aleskerov F., Monjardet B. Utility Maximization, Choice and Preference, Springer-Verlag, Berlin, 2002 Brams S., Taylor A. Fair Division Cambridge University Press, New York, 1996 Gale, David, and Lloyd Shapley. 1962. College admissions and the stability of marriage. American Mathematical Monthly, 69, 9-Roth A., Sotomayor M. O. Two-sided matching, Cambridge University Press, 1990, Cambridge Taylor A. D., Zwicker W. S. Simple Games. Prineston University Press, 2008/12 Материально-техническое обеспечение дисциплины
Некоторые лекции по курсу читаются с использованием мультимедийного проектора для демонстрации слайдов и презентационных материалов.
На семинарских занятиях используется электронный задачник, включающий задачи для текущего семинара и текущей домашней работы. Студентам рекомендуется иметь распечатку части задачника, относящейся к текущей теме. Задачник обновляется после каждого семинара.
