7.2. Оглядові питання

1. Які ви знаєте основні критерії в теорії ігор? Які їхні призначення?

2. У чому полягає зміст критерію Вальда?

3. Зміст критерію Гурвича?

4. Зміст критерію Севіджа?

5. Що таке позиційні ігри? Яка ділянка їхнього застосування?

3. Практичні завдання

1. На промисловому підприємстві готуються до переходу на випуск нових видів продукції товарів народного споживання. При цьому можливі чотири рішення - Р₁, Р₂, Р₃, і Р₄, кожному з яких відповідає певний вид випуску продукції чи їхнє сполучення. Результати прийнятих рішень істотно залежать від обстановки (ступеня забезпеченості виробництва матеріальними ресурсами), яка заздалегідь точно не відома і може бути трьох видів: О₁, О₂, О₃. Кожному сполученню рішень Р і обстановки О відповідає певний виграш а, що поміщається в клітинки таблиці ефективності на перетинанні Р і О (табл. 8). Цей виграш характеризує відносну ймовірність різних варіантів обстановки:

О₁ = 0,50; О₂ = 0,30; О₃ = 0,20.

Яке рішення є оптимальним?

2. Ймовірність різних варіантів обстановки (табл. 8) не відома, і немає підстави віддавати перевагу якому-небудь її варіанту. Яке рішення є оптимальним?

Таблиця 2

Таблиця ефективності

Варіанти рішень	Варіанти обстановки (ефективність)
	О1	О2	О3
Р1	0,25	0,35	0,40
Р2	0,70	0,20	0,30
Р3	0,35	0,85	0,20
Р4	0,80	0.10	0.35

3. Ймовірність різних варіантів обстановки (табл. 8) не відома, але відомо, що найбільш ймовірна з них О₁, менш ймовірна О₂ і найменш ймовірна О₃.

Яке рішення є оптимальним?

4. Ймовірність різних варіантів обстановки (табл. 8) не відома, але потрібна гарантія, щоб виграш у будь-яких умовах виявився не меншим, ніж найбільш можливий у гірших умовах (принцип "розраховуй на гірше").

5. Ймовірність різних варіантів обстановки (табл. 8) не відома, але потрібно у будь-яких умовах уникати великого ризику.

6. Ймовірність різних варіантів обстановки (табл. 8) не відома, але потрібно зупинитися між лінією поводження "розраховуй на гірше" і лінією поводження "розраховуй на краще" (к=0; 0,25; 0,5; 0,75; 1).

Тема 8. Методи розподілу ресурсів

8.1. Коротке теоретичне викладення

Організаційна система - це система, що включає техніку і колективи людей, інтереси яких істотно зв'язані з її функціонуванням. Прикладами тут можуть служити родина, фірма, університет, місто, країна. Кожна оргсистема складається з елементів (які у свою чергу теж можуть являти собою системи).

Для нас істотними є наступні дві обставини. З одного боку, система існує для досягнення яких-небудь визначених цілей, тобто можна говорити про інтереси системи в цілому. З іншого боку, елементи системи найчастіше переслідують власні інтереси, узагалі говорячи не співпадаючі з інтересами системи в цілому. Усе це дає підставу формалізувати деякі аспекти функціонування оргсистем у термінах теорії ігор.

У даному розділі ми будемо розглядати найпростішу дворівневу модельну оргсистему, що складається з Центра і деякого числа однотипних Елементів. Управління такою системою ми розглянемо на прикладі задачі розподілу ресурсів. Суть цієї задачі полягає в наступному. Елементи (надалі ми будемо називати їх Споживачами) представляють Центру заявки на одержання деякого ресурсу (для простоти розглядається один вид ресурсу). Центр на підставі цих заявок розподіляє наявний у його розпорядженні ресурс. Якщо всі заявки можуть бути цілком задоволені, то Центру, очевидно, так і варто поступити - виділити кожному Споживачу стільки, скільки він просить.

Істотно складніше ситуація дефіциту, коли сумарний об’єм заявок перевершує наявний у розпорядженні Центра ресурс. У тому випадку задача розподілу ресурсу стає нетривіальною. Універсальних рекомендацій тут не існує. Нижче будуть розглянуті деякі способи, чи механізми, розподілу ресурсів, кожний з який має визначені достоїнства і недоліки.

На закінчення цього розділу проведемо формалізацію задачі. Мається п Споживачів, кожний з який заявляє Центру число s_i (i = 1,2,.....п) – заявку, а також ще деяку інформацію. Далі Центр на підставі заявок Споживачів, що мається в його розпорядженні ресурсу R и додаткової інформації про Споживачів обчислює за деяким правилом числа x_i (i = 1,2.....п) - обсяг ресурсу, що виділяється і-му Споживачу.

У випадку

(відсутність дефіциту) природним рішенням Центра є наступне:

х_і=s_i

(кожен Споживач одержує стільки, скільки просив). Надалі ми будемо вважати виконаним нерівність

(сумарна заявка Споживачів перевершує ресурс Центра).

Відзначимо наступне важливу обставину. Споживачі формують свої заявки на підставі власних реальних потреб r_i що їм відомі, але невідомі Центру. Можна сказати. що числа s_i є стратегіями Споживачів як учасників ієрархічної гри. У свою чергу, стратегією Центра є числа х_i.

Метод прямих пріоритетів. Метод прямих пріоритетів відноситься до числа так званих пріоритетних механізмів, відмітною рисою яких є приписування кожному Споживачу деякого пріоритету. Отже, поряд з розмірами заявок s_i (і = 1, 2, … п) Центр враховує пріоритет кожного Споживача, що визначається числом A_i, (і = 1, 2, … п).

Відповідно до механізму прямих пріоритетів розподіл ресурсу здійснюється за правилом

x_i = min{s_i, yA_is_i}, i= 1,2, ...,п, (1)

де y - загальний для всіх Споживачів параметр - визначається з умови

(2)

(весь ресурс розподіляється без залишку).

Особливо простий вигляд формула (1) здобуває у випадку "рівності" Споживачів з погляду Центра, тобто при

А₁ = А₂ = … = А_п = 1

Тоді

x_i = min{s_i, ys_i}=ys_і, i= 1,2, ...,п,

(випадок х_і=s_i неможливий, оскільки при цьому кожен Споживач одержує стільки, скільки просив, а це суперечить умові про наявність дефіциту). З умови (2) одержуємо

звідки

Описаний механізм розподілу ресурсів є, мабуть, найпростішим . Зміст його полягає в тому, що всі заявки пропорційно зменшуються шляхом множення на число у.

Переваги механізму прямих пріоритетів очевидні. Відзначимо два недоліки. По-перше, кожен Споживач одержує менше, ніж просить. Тим часом неважко уявити собі ситуацію, коли Споживачу потрібно на здійснення якого-небудь проекту саме s_i одиниць ресурсу, а ys_i вже не вистачає. По-друге, даний механізм "штовхає" Споживачів до завищення заявок в умовах дефіциту. Дійсно, оскільки чим більше Споживач просить, тим більше одержує, він може, завищуючи свої потреби, спробувати наблизити підсумкове рішення Центра х_i, до своїх реальних потреб r_i,. Тим самим дефіцит ще більш зростає, причому Центр навіть не має можливості довідатися реальні запити Споживачів r_i оскільки вони повідомляють заявки s_i > r_i..

Метод зворотних пріоритетів. Механізм зворотних пріоритетів ґрунтується на припущенні, що, чим менше потрібно Споживачу ресурсу, тим більше ефективність його використання. Відповідно до цього розподіл ресурсу здійснюється за правилом

x_i = min{s_i, yA_i /s_i}, i= 1,2, ...,п, (3)

де число у визначається, як і в механізмі прямих пріоритетів, з умови

З формули (3) видно, що подаючи дуже малу або дуже велику заявку s_i,. Споживач одержує малий ресурс х_і.

Знайдемо, яку ж заявку s_i, повинний подавати і-й Споживач, щоб одержати максимальний ресурс х_і (в умовах дефіциту така ціль Споживача представляється цілком зрозумілою).

Максимальне значення s*_i розраховується так

Таким чином, рівноважним є набір стратегій Споживачів

…

при цьому

х_і= s*_i

Вибираючи замість s*_i будь-яку іншу стратегію s_i і-й Споживач лише зменшує виділюваний йому ресурс х_і,.

Залишилося обчислити константу у. Маємо:

звідки

.

Зауваження. Ще раз відзначимо, що набір стратегій s*_i (i = 1,2,.....п) є рівноважним, тобто , подаючи будь-яку заявку і-й Споживач лише зменшує виділюваний йому ресурс х_і. Можна довести, що кожна зі стратегій s*_i є також гарантуючої, тобто у випадку застосування і-м Споживачем цієї стратегії він у будь-якому випадку (тобто при будь-яких заявках інших Споживачів) одержує не менше, ніж х_і = s*_i.

Зауваження 1. Через помилки округлення сума заявок небагато відрізняється від R=60.

Зауваження 2. Насправді ми розглянули випадок, коли s*_i < r_i, для всіх i, тобто коли кожний iз Споживачів змушений, подаючи заявку, занижувати свою реальну потребу. Може бути і так. що для деяких Споживачів s*_i ≥ r_i,. тоді ці Споживачі подають заявку на ресурс s_i = r_i, і стільки ж одержують.

Механізм зворотних пріоритетів володіє рядом переваг. Зокрема , не відбувається невиправданого завищення заявок, крім того, за умови розумного поводження Споживачів вони одержують стільки, скільки просять.

Метод конкурсного механізму. Конкурсний механізм застосовується в тих випадках, коли недоцільно "урізати” заявки, оскільки Споживачам ресурс потрібний на реалізацію яких-небудь конкретних проектів, на які меншого ресурсу не вистачить. У цих умовах Центр проводить конкурс заявок. Ті, хто перемагають у конкурсі, цілком одержують необхідний ресурс, а програвши не одержують нічого.

Реалізація цього відбувається в такий спосіб. Споживачі повідомляють Центру свої заявки s_i, а також величини w_i, що характеризують ефект, що вони мають намір одержати. На підставі цих даних Центр обчислює для кожного Споживача показник ефективності (e_i):

Після цей ресурс розподіляється в такий спосіб. Спочатку розглядається Споживач з найбільшою ефективністю. Йому виділяється стільки, скільки він просить (якщо в Центра вистачає ресурсу). Потім береться другий по ефективності і т.д.. У якийсь момент виявляється, що на задоволення чергової заявки ресурсу, що залишився в Центра, не вистачає. Тоді цей споживач, так само як і всі що залишилися, нічого не одержує.

Зауваження. В ефективності описаного механізму можуть виникнути сумніву. Адже Споживачі можуть пообіцяти великий ефект, одержати ресурс, а потім не виконати обіцяного. Тому при реальному застосуванні конкурсного механізму необхідна діюча система контролю (можливо, поетапний контроль для проектів із тривалим часом реалізації).

Метод відкритого управління. В усіх розглянутих вище методах розподілу ресурсів Споживачі можуть домогтися кращого для себе рішення Центра шляхом перекручування інформації. У такий спосіб, Центр не одержує достовірних даних про запити Споживачів.

Можливість ефективно керувати на підставі недостовірної інформації представляється, узагалі говорячи, сумнівною. Тому цікаві методи відкритого управління, ідея яких полягає в створенні для Споживачів стимулів до повідомлення в заявці своїх реальних потреб.

Опишемо один з можливих методів відкритого управління. Розподіл ресурсів проводиться в кілька етапів. На першому етапі ресурс розділяється нарівно між усіма Споживачами, тобто по R/n кожному. Якщо заявки яких-небудь Споживачів виявилися не більше чим R/n, то вони цілком задовольняються. Тим самим число Споживачів зменшується до, зменшується і ресурс Центра. На другому етапі ресурс розділяється нарівно між тими що залишилися Споживачами і т.д..

На якомусь етапі виявляється, що, розділивши ресурс нарівно між Споживачами, що залишилися, не вдається задовольнити ні однієї заявки. Тоді всі ці Споживачі одержують нарівно.

Дійсно, у кінцевому рахунку всі Споживачі поділяються на пріоритетних (який одержали стільки, скільки просили) і непріоритетних (до останнього в приведеному прикладі відносяться перший і восьмий Споживачі). Пріоритетні одержують стільки, скільки просять, тому їм не має змісту спотворювати свої реальні потреби. Непріоритетні ж, як неважко бачити, не можуть збільшити виділений їм ресурс ні підвищуючи, ні знижуючи свою заявку.

Таким чином, при розподілі ресурсів відповідно до описаного механізму Центр одержує достовірну інформацію про реальні запити Споживачів.