4.12.2.2. Вектор Шепли

Суть подхода Шепли состоит в том, что он строится на основании аксиом, отражающих справедливость дележей.

Носителем игры с характеристической функцией v называется такая коалиция T, что v(T) = v(ST) для любой коалиции S.

Смысл носителя T состоит в том, что любой игрок, не принадлежащий T, является нейтральным, он не может ничего внести в коалицию и ему ничего не следует выделять из общих средств.

Пусть v – характеристическая функция кооперативной игры n игроков,  – любая перестановка множества N игроков. Через v обозначим характеристическую функцию такой игры, что для коалиции S = {i₁, i₂, ..., i_S} будет верно

v({( i₁), ( i₂), ..., ( i_S)}) = v(S).

Содержательный смысл функции v состоит в том, что если в игре с характеристической функцией v поменять местами игроков согласно перестановке , то получим игру с характеристической функцией v.

Вектором цен (вектором Шепли) игры с характеристической функцией v называется n-мерный вектор Ф(v) = (Ф₁(v), Ф₂(v), ..., Ф_n(v)), удовлетворяющий аксиомам Шепли:

1.  Аксиома эффективности. Если S – любой носитель игры с характеристической функцией v, то

= v (S).

2.  Аксиома симметрии. Для любой перестановки  и iN должно выполняться = Ф_i(v).

3.  Аксиома агрегации. Если есть две игры с характеристическими функциями v и v, то Ф_i (v + v) = Ф_i(v) + Ф_i(v).

Существование вектора Шепли вытекает из следующей теоремы

Теорема. Существует единственная функция Ф, определённая для всех игр и удовлетворяющая аксиомам Шепли.

Характеристическая функция _S(T), определённая для любой коалиции S, называется простейшей, если

_S(T) =

Содержательно простейшая характеристическая функция описывает такое положение дел, при котором множество игроков Т выигрывает единицу тогда и только тогда, когда оно содержит некоторую основную минимальную выигрывающую коалицию S.

Можно доказать, что компоненты вектора Шепли в явном виде запишутся следующим образом

где t – число элементов в T, .

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

Тогда, очевидно, объем хранилищ, который удовлетворяет n потребителей, равен .

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

Требуется определить число хранилищ и коалиции, которые их будут строить, а также распределить расходы на постройку хранилищ между членами коалиции.

Решение. Эту задачу можно интерпретировать как кооперативную игру n лиц, характеристическая функция которой задана следующим образом:

.

Для распределения расходов между игроками воспользуемся вектором Шепли. После вычисления компонент для каждой коалиции необходимо проверить выполнение неравенства

, (1)

где – компонента вектора Шепли игры лиц, характеристическая функция которой является сужением функции на множество .

Коалиция , для которой выполняется неравенство (1), должна строить свое хранилище, а игроки, не входящие в коалицию , – свое хранилище. Если такой коалиции нет, то все игроки строят общее хранилище, а расходы распределяются согласно вектору Шепли.

Пусть теперь затраты на строительство хранилищ заданы такой возрастающей функцией, что характеристическая функция принимает следующие значения:

Коалиция
Характеристическая функция	2	3	2,5	4	3,9	5	6

Для коалиций , , , найдем

,

,

.

Аналогично для коалиций , и получим

, , ,

, , .

Из сравнения , и видно, что неравенство (1) не выполняется. Следовательно, игрокам, целесообразно строить одно хранилище, а расходы распределить следующим образом: игрок 1 – 7/5 усл. ед., игрок 2 – 49/20 усл. ед. и игрок 3 – 43/20 усл. ед.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.

1.Исследовать игры, заданные следующими матрицами:

1. 2. 3.

4. 5.

2. Два предприятия, производящие шкафы-купе, конкурируют между собой за рынок сбыта. Стратегии, которыми могут воспользоваться оба предприятия, заданы следующей матрицей: .

Необходимо определить, какие стратегии являются наиболее выгодными для предприятий.

3. Генеральные директора компаний Motorola и Samsung, на корпоративной вечеринке, поспорили о том, чья компания останется в выигрыше при продаже новой серии сотовых телефонов. Стратегии, среди которых компании должны выбрать свою, представлены в матрице Y. Необходимо определить наиболее выгодную из стратегий для каждого предприятия, а также цену игры. .

4. Фермер решает засеять участок земли пшеницей. Исходя из опыта других фермеров региона, при благоприятных условиях с 1 кг зерна в период сбора урожая собирается 10 кг, при удовлетворительных - 5 кг, а при плохих климатических условиях фермер получает тоже количество пшеницы, которое было посеяно. Перед фермером стоит задача определить, сколько надо купить и засеять тонн зерна - 1, 2 или же 3 тонны, в расчете на какую погоду.

5. На рынке Ставропольского края функционируют два хладокомбината «Иней» и «Холод». Их стратегии заданы платежной матрицей:

Необходимо определить оптимальную стратегию каждого из предприятий, хладокомбинат «Иней» принять за первого игрока, а «Холод», соответственно, за второго.

6. Невинномысская швейная фабрика изготовляет плащи и пальто. Сбыт верхней одежды зависит от состояния погоды осенью. По наблюдениям прошлых лет, предприятие реализует в условиях сухой осени 300 пальто и 150 плащей, а в условиях дождливой осени – 200 пальто и 500 плащей. Известно, что затраты на пошив одного плаща и пальто соответственно составляют 110 и 150 рублей, а цена реализации 170 и 200 рублей.

Определить оптимальную стратегию предприятия, обеспечивающую гарантированную среднюю прибыль при любой погоде.

7. Совет директоров строительной фирмы «Аспект» принял решение об инвестировании свободных средств в ценные бумаги с целью получения прибыли. Вложения производят в ценные бумаги трех видов (А₁, А₂, А₃). В условиях нестабильности экономики была проанализирована ситуация и получен прогноз доходности в зависимости от трех рыночных ситуаций (С₁, С₂, С₃).

Стратег. Стратегии рынка Фирмы	С1	С2	С3
Вложения в А1	2	3	1
Вложения в А2	4	5	6
Вложения в А3	7	10	8

Найти оптимальную стратегию, которая обеспечит фирме наибольшую прибыль.

8. (Планирование выпуска новых моделей одежды на швейном предприятии). Швейное предприятие планирует к массовому выпуску новую модель одежды. Спрос на эту модель не может быть точно определен, однако можно предположить, что его величина характеризуется тремя возможными состояниями (I, II, III). С учетом этих состо­яний анализируется три возможных варианта выпуска данной модели (A, Б, В). Каждый из этих вариантов требует своих затрат и обеспечивает в конечном счете различный эффект.

Прибыль (тыс. руб.) которую получает предприятие при данном объеме выпуска модели и соответствующем состоянии спроса, определяется матрицей

I II III

Требуется найти объем выпуска модели одежды, обеспечивающий среднюю величину прибыли при любом состоянии спроса.

9. (Планирование выпуска обуви). Обувная фабрика планирует выпуск двух моделей А и В. Спрос на эти модели не определен, однако можно предположить, что он может принимать одно из двух состояний I и II. В зависимости от этих состояний прибыль предприятия различна и определяется матрицей .

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

10. (Планирование посева). Сельскохозяйственное предприятие может посеять одну из трех культур, которые обозначим через , , . Необходимо определить, какую из культур сеять, если при прочих равных условиях урожаи этих культур зависят главным образом от погоды, а план должен обеспечить наибольший доход. Рассмотрим лишь три состояния природы: год может быть засушливым, нормальным и дождливым.

Решить численный пример для исходных данных, приведенных в таблице.

Исходные условия	Урожайность культуры (центнеры)
Нормальная погода	5	12,5	7,5
Дождливая погода	15	5	10
Сухая погода	20	7,5	0
Цена за один центнер в ед. стоимости	2	4	8

Замечание. Рассмотренный конфликт можно обобщить на случай, когда высевается одна из культур, а состояния природы более тонко отдифференцированы. Аналогичные модели легко построить для случая, когда предприятие имеет возможность варьировать не только культуры, которые оно сеет, но и способы обработки поля.

11. (Распределение конкурсных работ). Пусть имеется два конструкторских бюро (КБ), причем одно из КБ имеет 4 отдела, а другое – 3 отдела. Объявлен конкурс на создание проектов двух агрегатов. Эти проекты должны будут оцениваться некоторой комиссией, которая выбирает лучший проект каждого агрегата. То конструкторское бюро, чей проект первого агрегата лучше, получит «а» рублей премии; аналогично, за принятый второй проект выплачивают «b» рублей. Предполагается, что если в одном КБ над проектом одного агрегата работало больше отделов, чем в другом, то, наверное, будет принят проект первого КБ, если же в каждом КБ число отделов, работающих над аналогичным проектом, одинаково, то вероятность принятия данного проекта равна 1/2.

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

Решить эту задачу при условии, что а = b, т. е. премии за каждую из двух работ равны.

Указание. В качестве выигрыша первого игрока принять разницу между математическим ожиданием фактически получаемой премии и величиной (а + b)/2, равной половине величины премии за оба проекта.

12. (Планирование выпуска продукции). В некотором городе имеется два предприятия, которые могут выпускать для населения продукцию одного и того же назначения. Эту продукции они предполагают продавать в том же городе, никуда ее не вывозя. Хотя назначение этой продукции одно, она отличается по оформлению, по удобству пользования и т. д. – другими словами, типы продукции разные. Первое предприятие может выпускать продукции типа . Второе – продукции типа . Себестоимость и продажная цена всех видов продукции одинакова. Путем прогнозирования спроса установлено, что в городе найдет сбыт N единиц товара всех видов, причем, если первое предприятие будет выпускать продукцию типа , а второе – продукцию типа , то в городе найдет сбыт товаров типа и товаров типа , . Мощности предприятий таковы, что каждое из них может обеспечить город. Пусть доход от продажи единицы товара равен единице. Определить, какие типы продукции следует выпускать обоим предприятиям, чтобы прибыль от реализации продукции была наибольшей.

Показать решение игры на конкретном числовом примере. Предприятие А выпускает детские игрушки типа , а предприятие В – игрушки типа . Для простоты будем считать, что затраты на производство каждого типа игрушек одинаковы и что эти игрушки реализуются по одной и той же цене. Прогнозируемая доля сбыта игрушек предпри­ятия А задана таблицей 1.1. Ожидается, что всего будет реализовано 1000 игрушек. Требуется определить типы игрушек, выпускаемых каждым предприятием.

Предприятие А	Предприятие В
	0,5	0,5	0,4	0,5	0,2
	0,5	0,4	0,7	0,1	0,6
	0,3	0,6	0,7	0,3	0,2
	0,4	0,4	0,3	0,0	0,2

13. Найдите седловые точки и значение игры:

14. Найти оптимальные стратегии и значения игр с матрицами

15. Преобразуя матрицу выигрышей, найти решение игр с матрицами:

16. Используя геометрический метод, найти решения игр с матрицами:

17. Найдите решение игр, определяемых следующими матрицами:

18. Решите следующие игры методом линейного программирования:

а) б)

19. Два экономических партнера договариваются о совместном проведении одного из двух действий: Д₁ или Д₂, каждое из которых требует необходимого совместного участия обоих партнеров.

В случае совместного осуществления действия Д₁ партнер 1 получит одну единицу полезности, а партнер 2 – две единицы. Наоборот, в случае совместного осуществления Д₂ партнер 1 получает две единицы, а партнер 2 – лишь одну. Наконец, если игроки выполняют различные действия, то выигрыш каждого из них равен нулю.

Определить ситуации, приемлемые для партнеров 1 и 2 соответственно, найти ситуации равновесия.

20. «Два бандита». Два бандита (игроки 1 и 2), подозреваемые в совершении тяжкого преступления, находятся изолированно друг от друга в предварительном заключении. Ввиду отсутствия прямых улик успех или неуспех обвинения зависит от признания или непризнания самих бандитов. Если оба бандита признаются, то они будут признаны виновными при смягчающих обстоятельствах и будут приговорены к 5 годам тюрьмы. Если ни один из них не признается, то обвинитель все-таки докажет их виновность в сопутствующем менее тяжком преступлении, и они будут приговорены к 1 году тюрьмы. Если признается только один из них, то признавшийся будет освобожден (таково законодательство в условиях задачи), а непризнавшийся будет приговорен к 10 годам (максимальный срок).

21. Два человека, работая вместе, могут произвести 100 фунтов продукта, который игрок 1 оценивает в 1 долл. за фунт, а игрок 2 – в 0,25 долл. за фунт. У игроков 1 и 2 совсем нет денег, а у игрока 3 деньги есть, и он оценивает товар по 1 долл. за фунт. Найти c-ядро для данной игры.

22. Имеется трое рабочих (игроки А, Б, В). Пусть за смену А может заработать 10 ед., Б – 9 ед., В – 3 ед. Разрешено образование любой бригады из двух или трех человек. Пусть заработки бригад таковы: АБ – 22, БВ – 15, АВ – 17, АБВ – 28.

Как должны действовать рабочие, чтобы получить наибольшие заработки, и каковы размеры этих заработков? Составить модель игры, найти c-ядро.

23. Пусть три игрока поставлены перед необходимостью раздела дохода, равного 1. Пусть при этом , , . Показать, что c-ядро пусто. Найти вектор Шепли.

24. Рассматривается корпорация из четырёх акционеров, имеющих акции соответственно в следующих размерах a₁ = 10, a₂ = 20, a₃ = 30, a₄ = 40. Любое решение утверждается акционерами, имеющими в сумме большинство акций. Это решение считается выигрышем, равным 1. Рассмотрите данную ситуацию как игру четырёх игроков и найдите вектор Шепли для этой игры.

144