Методические указания и задание на проектирование по курсу «Теория игр» Кафедра "Экономическая кибернетика"



страница1/7
Дата30.12.2012
Размер0.49 Mb.
ТипМетодические указания
  1   2   3   4   5   6   7


Хабаровский государственный технический университет

Методические указания

и задание на проектирование


по курсу «Теория игр»

Кафедра "Экономическая кибернетика"




Хабаровск 2000



  1. Классификация и описание игр. Понятийный аппарат теории игр (терминоло­гия).

  2. Способы описания и анализа игр. Игры в развернутой и нормальной форме.

  3. Игры двух лиц с 0-ой суммой. Игра с постоянной суммой.

  4. Игра с седловой точкой.

  5. Игра со смешанными стратегиями. Сведение матричной игры к ЗЛП.

  6. Кооперативные игры. Арбитражные схемы. Природа и структура арбитражных схем.

  7. Принципы оптимальности Нэша для общих арбитражных схем.

  8. Классические кооперативные игры. Природа и структура игр. Условия индиви­дуальной и коллективной рациональности.

  9. Доминирование дележей в кооперативной игре.

  10. Эквивалентность кооперативных игр.

  11. Нормализация кооперативных игр (0-1 редуцированная форма).

  12. Кооперативные игры. Решение по Нейману-Моргенштейну.

  13. Кооперативные игры. Применение с-ядра.

  14. Кооперативные игры. Вектор Шепли. Аксиомы Шепли.

  15. Кооперативные игры. Принцип оптимальности п-ядра.

  16. Модели торгов. Закрытые и аукционные торги.

  17. Аукционные торги с целью максимизации разности доходов.

  18. Аукционные торги с целью максимизации ожидаемого дохода.

  19. Закрытые торги: 2 лица и 2 объекта.

  20. Закрытые торги: п ® ¥ да лиц участников. Цель торгов - тах дохода.

  21. Закрытые торги. Вероятность получения контракта.

  22. Закрытые торги. Определение оптимального предложения цен.

  23. Закрытые торги. Моделирование торгов за несколько контрактов.

  24. Игры п лиц с 0-й суммой. Коалиции.

  25. Многошаговые игры. Природа и структура конечных позиционных игр.

  26. Позиционные игры с полной и неполной информацией.

  27. Детерминированные позиционные игры.

  28. Стохастические позиционные игры.

  29. Общая постановка многокритериальной детерминированной статической за­дачи принятия решения.

  30. Классификация многокритериальных задач принятия решений.

  31. Проблемы решения задач векторной оптимизации.

  32. Классификация возможных схем компромисса в векторных ЗПР. Принцип равномерности (равенства, максимина, квазиравенства).

  33. Схемы компромисса в векторных ЗПР. Принципы справедливой уступки.

  34. Схемы компромисса в векторных ЗПР. Принцип выделения главного крите­рия. Принцип последовательной уступки.

  35. Способы нормализации критериев в многокритериальных ЗПР.

  36. Способы задания приоритета локальных критериев в многокритериальных ЗПР.


  37. Методы учета критериев в многокритериальных ЗПР.



Задание (теоретико-игровая модель системы водоснабжения).

Пусть предполагается строительство плотин для накопления воды в районе, в котором имеется т промышленных и п-т сельскохозяйственных объединений. Будем считать, что промышленное объединение iA = {1, 2, ..., m} нуждается в годовом объеме воды i , а не одно из сельскохозяйственных объединений jB = {m + 1, m + 2, ..., n} недостатка в воде не испытывает. Каждая коалиция предприятий S I A B может удовлетворить потребности в воде своих членов двумя путями: либо построить дамбу, либо тем или другим способом транспортировать воду из источников, которые находятся на территории функционирования сельскохозяйственных предприятий, входящих в коалицию S. Возможно также сочетание этих двух способов.

Пусть v(S) - затраты коалиции S на удовлетворение потребности в воде своих членов. Примем, что эти затраты складываются из затрат на строительство плотин, если она строится, затрат на транспортировку воды (например, строительство водопровода) и затрат на возмещение убытка сельскохозяйственных предприятий, если им не будет хватать воды для своих нужд. Для простоты мы не будем включать в модель убытки сельскохозяйственных предприятий от порчи их угодий, хотя это сделать нетрудно. Нахождение функции v(S) - довольно трудоемкая задача. Упрощая модель, будем считать, что затраты на строительство плотины пропорциональны объему водохранилища, затраты на транспортировку пропорциональны объему транспортируемой воды, убытки от недостатка воды пропорциональны недостатку.

Тогда затраты на строительство дамбы коалицией S будут равны , где yi - годовое количество воды, используемое предприятием i из водохранилища, S - стоимость единицы воды, потребляемой за год из водохранилища, если плотину строит коалиция S. Затраты коалиции S на транспортировку воды будут равны

где хi j - годовое количество воды, потребляемое предприятием i из сельскохозяйственного района j, li j - годовая стоимость транспортировки воды из j в i. Наконец, потери предприятия j от транспортировки единицы объема воды в год будут равны

где j - необходимое количество воды для предприятия j, cj - цена потерянной сельскохозяйственной продукции в результате нехватки воды. Если считать, что все предприятия имеют возможность удовлетворить свои потребности в воде и имеют такую цель, то, очевидно, они будут минимизировать затраты. Следовательно, в этом случае нахождение v(S) сведется к задаче математического программирования:

найти минимум величины

при ограничениях



Таким образом, v(S) равно минимуму целевой функции данной задачи математического программирования.

Полагая v(S) = -v(S), мы придем к кооперативной игре п лиц, допускающий подобные платежи. Эта игра моделирует рассматриваемый конфликт предприятий. И задача состоит в том, чтобы определить, сколько средств каждое предприятие должно вложить на удовлетворение их общих нужд, т.е. надо найти такой дележ х*, что

х*i v ({i}) ,

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

Из этого неравенства следует, что расходы v(S) любой коалиции S согласно дележу х* будут не больше, чем при ее обособлении. В качестве х* можно взять вектор Шепли, если он содержится в с-ядре, или использовать п-ядро. Это зависит от принципов, которыми руководствуется арбитр или игроки, принимающие решение совместно.

Если же неравенства (1.1) для некоторого S нарушаются, то ситуация становится сложной. В этом случае коалиция S, для которой нарушаются неравенства (1.1), несомненно захочет отделиться. Ей это обойдется дешевле. Если это возможно, то она так и поступит. Однако возможно, что одна из коалиций не имеет права отделиться. Такая ситуация возникает тогда, когда арбитр (например, государство) хочет поддержать одни предприятия за счет других. Тогда естественно это делать с наименьшей «обидой» (потерями), т.е. таким образом, что максимальный из эксцессов v(S) - x(S) (SI) был минимальным.
Т а б л и ц а 1.1. Параметры j, I





j м3/год

i м3/год

Игрок 1

Игрок 2

Игрок 3

Игрок 4

Игрок 5

1,67108

1,28108

0

0

0

0

0

1,48108

2,28108

1,94108


1. Природа и структура кооперативных игр п лиц

Пусть условия неантагонистического конфликта таковы, что допускается заключение взаимообязывающих соглашений о стратегиях, а выигрыши могут перераспределяться между игроками. Тогда достаточно рассматривать только суммарный выигрыш игроков, образующих коалицию, причем масштабы функций полезностей игроков могут быть выбраны так, что полезности для любых двух игроков передаются без их численного изменения. В этом случае силу коалиции S полностью характеризует число v(S), которое определим следующим образом.

Объединение игроков из S означает превращение их в единого игрока I , стратегией которого являются всевозможные совместные действия составляющих его игроков на S, а выигрышем - сумма выигрышей игроков S. В худшем для объединенного игрока I случае игроки из I \ S могут также объединиться в некоторого коллективного игрока II с интересами, диаметрально противоположными интересам игрока I. В результате коалиция S (как игрок I) может себе гарантировать выигрыш v(S), равный значению возникающей антагонистической игры. Иными словами v(S) - гарантированное математическое ожидание выигрыша игроков коалиции S, действующих совместно против объединенных игроков коалиции I \ S. Мы будем предполагать, что значение v(S) существует для любой коалиции SI .

О п р е д е л е н и е 1.1. Кооперативной игрой п лиц называется пара (I, v), где I={1,2,...,n}, а v(v()=0) - функция, определенная на всех подмножествах SI . Функция v называется характеристической функцией.

Таким образом, кооперативную игру п лиц можно анализировать с помощью характеристической функции, область определения которой состоит из 2п возможных подмножеств множества I. Если для всех непересекающихся подмножеств S и T (S, TI и ST=) выполняется неравенство
v(S)+ v(T) v(ST), (1.1)
то характеристическая функция называется супераддитивной. Это свойство содержательно выражает то обстоятельство, что объединение игроков в коалиции является целесообразным с точки зрения увеличения выигрыша, т.е. условие (1.1) отражает разумность коллективистской точки зрения. Далее будем рассматривать игры, для которых выполняется условие (1.1).

Методом математической индукции из неравенства (1.1) нетрудно получить следующее неравенство:

,
где Si - непересекающиеся коалиции. Следовательно,
(1.2)
В дальнейшем величина v({i}) будет обозначаться через v(i).
О п р е д е л е н и е 1.2. Игра (I,v) называется существенной, если
< v(I). (1.3)
В противном случае игра (I, v) называется несущественной.

Обозначим через хi сумму, которую получит игрок i при распределении полезности, имеющейся в распоряжении множества игроков I, и дадим следующее определение.
О п р е д е л е н и е 1.3. Дележом называется вектор х = (х1, х2,..., хп), удовлетворяющий условиям
хi v(i) для всех i


Условие (1.4) называется условием индивидуальной рациональности и характеризует предположение, что, участвуя в коалиции, каждый игрок получает по меньшей мере столько, сколько он мог бы получить, действуя самостоятельно и не заботясь о согласии каких-либо других игроков. В противном случае он в распределении х будет получать меньше, чем v(i), и тем самым это распределение не будет реализовано. Вполне обосновано также условие (1.5), так как в случае
< v(I)

существует распределение х', при котором каждый игрок iполучит больше, чем его доля хi. Если же

> v(I),
то игроки из I делят между собой нереализуемую полезность, и поэтому вектор х неосуществим. Следовательно, вектор х может считаться допустимым только при выполнении условия (1.5), которое называется условием коллективной (или групповой) рациональности.

На основании условий (1.4) и (1.5) для того, чтобы вектор х = (х1, х2,..., хп) был дележом в кооперативной игре (I, v), необходимо и достаточно выполнение равенства
хi = v(i) + i, i

причем

i0, i
В дальнейшем для любого дележа х через х (S) мы будем обозначать величину

а множество всех дележей через Н.

Таким образом, исходом кооперативной игры является дележ, который возникает в результате соглашений игроков. Поэтому в кооперативных играх сравниваются по предпочтительности не ситуации, а дележи и это сравнение, имея сложный характер, исходят из различных представлений об оптимальности для этих классов игр. В результате принципы оптимальности для кооперативных игр оказываются весьма разнообразными.
  1   2   3   4   5   6   7

Похожие:

Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМетодические указания и контрольные работы №1, 2 по курсу «Теория математической обработки геодезических измерений»
Методические указания и контрольные работы №1, 2 по курсу «Теория математической обработки геодезических измерений. Раздел II. Теория...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconКафедра прикладной информатики и информационных систем Нейронные сети Методические указания к выполнению лабораторных работ по курсу «Интеллектуальные информационные системы»
Методические указания к выполнению лабораторных работ по курсу «Интеллектуальные информационные системы» для студентов 4-го курса...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconСистемное проектирование в дипломной работе
Системное проектирование в дипломной работе. Методические указания./Лебедев А. А. – М.: Маи, кафедра 604, 2010
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМетодические указания к лабораторным работам для студентов Казань 2004 Составители: М. Г. Габидуллин, Д. С. Смирнов удк 691: 620
Проектирование составов и испытания тяжелых бетонов и строительных растворов. Методические указания к лабораторным работам по курсу...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМосковский государственный
Методические указания к проведению практических работ по дисциплине «Экономическая теория» для студентов специальности «Менеджмент...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМетодические указания и контрольные задания по курсу «Высшая математика (спецглавы)»
Методические указания содержат варианты контрольных работ по курсу «Высшая математика (спецглавы)», для студентов факультета визо,...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМетодические указания к лабораторной работе по курсу
Расчет радиоэлектронных схем методом узловых потенциалов: Методические указания к лабораторной работе по курсу "Основы компьютерного...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМосковский государственный
Методические указания к проведению практических работ по дисциплине «Экономическая теория» для студентов специальности «Менеджмент...
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМетодические указания к выполнению контрольной работы по курсу Криминалистика
Методические указания к выполнению контрольных работ по курсу «Криминалистика». – М.: Импэ им. А. С. Грибоедова, 2005. – 8 с
Методические указания и задание на проектирование по курсу «Теория игр» Кафедра \"Экономическая кибернетика\" iconМетодические указания к лабораторной работе по курсу
Параметрическая оптимизация радиоэлектронных схем: методические указания к лабораторной работе по курсу Компьютерный анализ электронных...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org