Сбалансированные и двойственно сбалансированные дискретные кооперативные игры

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

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

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

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

01

учтена в них недостаточно. ¡5

ü

ЛИТЕРАТУРА. 7

1. Агапцов С.А и др. Мотивация труда как фактор повышения эффективности производственно-хо- Г зяйственной деятельности предприятия // http://www.smartcat.ru/books/book_61/intro.shtml ^

2. Бовыкин В. И. Новый менеджмент: (управление предприятиями на уровне высших стандартов; q теория и практика эффективного управления). М.: Экономика, 1997.

3. Воробьев Е., Шедякова Т. Мотивации современных инноваций: основания и механизмы // Биз- ^ нес-информ. 1996. № 3. ^

4. Завлин П.Н. Основы инновационного менеджмента: Теория и практика: Учебное пособие для ву- ö зов. М.: Экономика, 2000.

5. Пригожин А.И. Управленческие нововведения: неопознанные ресурсы // Управление персона- о лом. 2000. № 1(43).

6. Рогов А.В. Мотивация инновационной деятельности в промышленности: Дис.. .. канд. экон. наук: I 08.00.05. Саратов, 2000. 0

_ са

Ö

Конфликты, возникающие в окружающем нас мире (в живой и неживой природе, социальные, о экономические, политические, семейно-бытовые и т.д.), условно делятся на антагонистические и g неантагонистические. Некоторые типы неантагонистических конфликтных ситуаций можно разре- i шить, используя кооперативные игры, впервые введенные Нейманом и Моргенштерном [7].

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

ЗИНЧЕНКО А.Б., МЕРМЕЛЬШТЕЙН Г.Г.

СБАЛАНСИРОВАННЫЕ И ДВОЙСТВЕННО СБАЛАНСИРОВАННЫЕ ДИСКРЕТНЫЕ КООПЕРАТИВНЫЕ

ИГРЫ

а

(Б ^

О

а.

ф

о

X

О

о

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

В работах [5, 2, 1] было дано определение дискретной кооперативной игры, ее ядра и решения (аналогичного решению Неймана-Моргенштерна), предложены алгоритмы нахождения дележей ядра игр малой размерности. Насколько известно авторам, дальнейшего развития это направление не получило.

В данной статье приводятся примеры игр, ядра которых, найденные согласно [5, 2, 1], не удовлетворяют аксиомам ядра и содержат дискриминирующие дележи, рассматривается другая концепция ядра, а также обобщаются на дискретный случай некоторые связанные с ядром понятия кооперативной теории.

Классическая кооперативная игра 0Е=<Ы,п> определяется множеством игроков Ы={1,...,п}, п>2,

и характеристической функцией V . 2N  Я , п(0)=О, которая каждой коалиции 3сЫ ставит в соответствие ее (числовую) прибыль п(3). Игру часто отождествляют с характеристической функцией. В играх, возникающих в экономике, функция п обычно неотрицательна и удовлетворяет условию супераддитивности

у

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

и Исходом игры является неотрицательный вектор х е Я" выигрышей ее участников. Дележом

о

называется исход, удовлетворяющий условию индивидуальной рациональности xi >п(г), ¡еЫ, и эффективности XемХ ) .

В дискретной кооперативной игре побочные платежи между игроками разрешены, но предел полагается, что значения характеристической функция и компоненты дележей — целые неотрицательные числа V . 2N  Z+, хе . Дележами 0-редуцированной формы у(\)=0, ¡еЫ, у(3)>0, БсЫ, дискретной игры являются целочисленные точки симплекса, определенного условиями

X iеNXi =п(Ы), Х> 0, ¡еЫ.

Приведем примеры дискретных игр, которые будем использовать для содержательной интер-

претации результатов.

о о

Пример 1 (Игра «Распределение неделимой продукции»).

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

о предприятия заинтересованы производить взаимные расчеты путем перераспределения конечного

о

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

о ров может служить множество альтернатив, полученных с помощью кооперативной игры с характе £2 ристической функцией п(3)=а(3), 3сЫ. о Пример 2 (Игра «Упаковка в контейнеры»).

I Каждый игрок имеет некоторое количество груза и владеет контейнерами (вагонами, рефрижераторами и т.п.), в которых этот груз перевозится. Предполагается, что игроки могут перевести гру зы, пользуясь только собственными контейнерами. Если при оптимальной упаковке груза, все контей->| неры какого-либо игрока будут заполнены полностью, то он в игре не участвует. Остальным игрокам

0 выгодно кооперироваться, то есть заполнять контейнеры грузами разных владельцев. Проблема соф

1 стоит в определении количества контейнеров, которые должен выделить каждый игрок для перевозки грузов кооперативного объединения. Характеристическая функция этой игры имеет вид п(3)=к(3), 3сЫ, где к(3) — количество контейнеров, необходимых для перевозки грузов коалиции 3.

Пример 3 (Игра «Мусор» [8]).

Каждый из п игроков имеет мешок с мусором, который он должен выбросить во дворе у кого-то другого. Если создается коалиция 5 (|й| < п ), то игроки из 5 могут договориться не оставлять мусор

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

й) =

предложенном Шепли и Шубиком, одному мешку с мусором присваивалась «полезность» равная 1, однако, более естественно считать игру дискретной.

Классическую кооперативную игру вв, соответствующую дискретной игре (то есть игру с тем же множеством игроков и характеристической функцией, допускающую нецелочисленные дележи), назовем релаксированной. Множества дележей дискретной и релаксированной игр обозначим через О (у) и 0(у) соответственно.

Понятие ядра (с-ядра,соге) является центральным для кооперативной теории. Принцип «справедливости», положенный в основу ядра, предохраняет любую коалицию от получения доли прибыли ниже ее собственных кооперативных возможностей (принцип коллективной рациональности). I-Концепция ядра успешно применялась для анализа экономики обмена, экономики производства, со экономики общественных продуктов и других проблем микроэкономики [6]. Теория ядра интенсивно развивается ([9]-[11, 12, 13]). ^

Ядро классической кооперативной игры определяется [7], [6] как множество решений системы

V

хеВД, хгейх > У

или как множество всех недоминируемых дележей (дележ х'= (х^...,х\) доминирует дележ

V 1 °

х2= (х12,...,х2п), если существует такая коалиция всЫ, что х) >х2, гев, и ^¡е$х. <у(5)). Неодноз-

' о

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

В работах [5, 2, 1] ядром дискретной кооперативной игры названо множество С*(п) недо-

х

О О

0-редуцированной форме п ) =У(й) — ^, всЫ:

минируемых целочисленных дележей и доказано, что С*(у) определяется условиями ф

<3

хеВ2(у), > У(в)-\3\+1, всЫ. (3) §

Проиллюстрируем на примерах недостатки такого подхода. о

В игре «Распределение неделимой продукции» (пример 1) положим п=3; у(1)=2, у(2)=1, у(3)=3, о у(1,2)=4, у(1,3)=8, у(2,3)=6, у(1,2,3)=10. Для упрощения геометрической иллюстрации переходим к 9

гей'4' ^ <3

О

у'(1)=у'(2) = у'(3) =0, V'(1,2) =1, V(1,3) =3, V'(2,3) =2, у'(2,3) =4. (4) *

X

Из (3) получаем систему

3 т

хг+х3> 2, х2+х>1, хг+х2+х3=4, х е > |

определяющую множество недоминируемых целочисленных дележей о

С'Цп') = {(0,0,4), (1,0,3), (2,0,2), (3,0,1), (0,1,3), (1,1,2),(2,1,1), (3,1,0), (0,2,2),(1,2,1), (2,2,0)}. |

X

Ol

л

н ü ш

7

Рисунок 1. Графическая иллюстрация множества C*z(v') игры (4).

Ol

^

о ф s

О

о.

ф

х

<3

<5

о

.

а

<

о о

о о

Q-

О Ф

О Ф

О

Точки заштрихованной области рисунка 1 являются проекциями дележей из Cz(v') на плоскость XjX.,. Используя (2) получаем систему

x+x>1, x1+x3>3, x2+x3>2, x1+x2+x3=4, x e Z+,

определяющую множество целочисленных дележей релаксированной игры CZ(v')={(1,0,3),(2,0,2),(0,1,3),(1,1,2),(2,1,1)}. На рисунке 2 изображены проекции дележей из Cz(v') на плоскость X1X2. Для исходной игры

C *(v) ={(2,1,7),(3,1,6),(4,1,5),(5,1,4),(2,2,6),(3,2,5),(4,2,4),(5,2,3),(2,3,5),(3,3,4),(4,3,3)}, Cz(v)={ (3,1,6), (4,1,5), (2,2,6), (3,2,5), (4,2,4)}.

Рисунок 2. Гоафическая иллюстрация множества С

Дележи х1=(2,1,7), х2=(5,1,4), х3=(5,2,3), х4=(2,3,5), х5=(3,3,4), х6=(4,3,3), принадлежащие разности найденных множеств С*(у) \С/м), не доминируются другими целочисленными дележами, но

дискриминируют, по крайней мере, одну коалицию игры (4), то есть не является устойчивыми (справедливыми, разумными). Например, при распределении х1 коалиция первого и второго игроков получит 3 единицы конечной продукции, что меньше ее собственных возможностей у(1,2)=4. Для дележа х2 имеем ^ге{2 3} =5 < у(2,3)=6 и т. д. Дискриминируемые коалиции будут возражать против исходов х^х6, так как существуют пять дележей множества Сг(у), удовлетворяющих минимальным требованиям всех коалиций.

В игре «Упаковка в контейнеры» (пример 2) положим п=3: п(1)=3, п(2)=2, п(3)=3, п(1,2)=4, п(1,3)=5, п(2,3)=5, п(1,2,3)=6. Игра распределяет затраты, а не прибыль, как в предыдущем примере, поэтому умножаем характеристическую функцию п на (-1) и переходим к 0-редуцированной форме

у'

Определив множества С* У) ={(2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)},

Сг(у')={(2,0,0),(1,1,0),(1,0,1),(0,1,1)} и вернувшись к исходной игре, получаем

С** (У ) ={ (1,2,3), (3,0,3), (3,2,1), (2,1,3), (2,2,2), (3,1,2) },

2.

Сг(у)={ (1,2,3), (2,1,3), (2,2,2), (3,1,2)}. Н

При распределении (3,0,3) е С*(у) \Сг(у), коалиция {1,3} должна выделить 6 контейнеров, хотя I объединенный груз первого и третьего игроков можно упаковать в 5 контейнеров. Против дележа Г

(3,2,1)е С*(у) \Сг(у) будет возражать коалиция {1,2}. |\

Классическая игра «Мусор» (пример 3) не имеет ядра, следовательно, Сг(у)=0. Недоминиру- О емым является только один целочисленный дележ (1,1,:,1) — равномерное распределение величины у (Я). Скорее всего, этот дележ будет одобрен всеми коалициями.

Примеры показывают, что С*(у) может не удовлетворять условию коллективной рациональ- §

ности, поэтому ядром дискретной кооперативной игры назовем множество Сг(у) целочисленных о дележей ядра релаксированной игры [4], то есть множество, удовлетворяющее условиям

хеБ(у), * у(Я С. (6) |

о

Сравнивая (3) и (6) получаем вложение Сг(у)сС*(у) .

со

После введения понятия ядра дискретной игры возникает вопрос о его существовании и свой- о ствах. Необходимым условием сбалансированности дискретной игры является непустота ядра Св(у) а релаксированной игры. Если Св(у) ф0, то проблема сводится к отысканию критерия существова- о ния целочисленного решения совместной системы линейных ограничений. В теории многогранни- д ков [3] эта задача является одной из основных и для систем общего вида до сих пор не решена. о Учитывая специальную структуру множества Св(у) (пересечение симплекса с неограниченным мно- т гогранным множеством, заданным полиматроидными ограничениями), можно попытаться решить эту £ проблему, по крайней мере, для частных классов игр. Такими, например, будут дискретные игры, у £ которых ядро релаксированной игры — целочисленный многогранник, то есть все его крайние точки 1

п О

принадлежат 2+ . ф

+ со

Важным для экономических приложений семейством классических супераддитивных игр (1), являются выпуклые игры о

У(ЯМ/})-у(¿1) <У(Я и {/}) —У(Я2), Я с Я, ¡еМ, ЭсЯШ (7) |

о

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

01

л h G CD 7

ru

a ф s

О

a.

ф

X

О

.

D

<

О О

о о

Q-

О Ф

О

рестановок ж = (i,..., in ) игроков. Как известно, каждая выпуклая классическая кооперативная игра имеет ядро, крайние точки которого х(ж) = (х^,...,x ), вычисляются по формуле

\ =n

Количество крайних точек х(ж) не всегда равно v!, так как возможно равенство х(жк) = х(ж'), k ф l. Игра называется вогнутой, если выполняются обратные (7) неравенства.

Для целочисленной характеристической функции v векторы х(ж) целочисленных, следовательно, любая выпуклая дискретная игра сбалансирована, а х(ж) — крайние точки выпуклой оболочки дележей ее ядра. Зная только их, можно получить границы изменения выигрышей игроков

хеС (v) ^ minxi (ж) < xi < тах xi (ж) {еn

z> ' жеР жеР '

Игра (4) примера 1 супераддитивна, но не выпукла. Игра (5) примера 2 является выпуклой. Используя предыдущие результаты и (8), получаем, что ядро CZ(v) игры (5) состоит только из дележей х(ж) (таблица 1).

Таблица 1. Дележи ядра игры

Выпуклая оболочка всех недоминируемых целочисленных дележей C*(v) игры (5) имеет три крайние точки (0,0,2), (0,2,0), (2,0,0), только одна из которых удовлетворяет (8). Заметим, что в этой игре C*(v) =D(v).

Относительно недавно в теории кооперативных игр появилось направление, связанное с аксиоматизацией ядра [14], [15]. Ядро Cz(v) дискретной игры, как подмножество ядра CR(v) соответствующей классической игры, также удовлетворяет этим аксиомам. Для множества C*(v) недоминируемых целочисленных дележей, аксиомы ядра могут не выполняться. Рассмотрим, например, аксиому ограниченности: если x принадлежит ядру, то для любого ieN справедливо соотношение

xi < max {v

' SeN\{i}

то есть выигрыш каждого игрока не может быть больше его максимального маргинального вклада. В игре

х3= 4 > max{v(l,2,3)-v(l,2), v(l,3)-n(l), v(2,3)-v(2)}=3.

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

CR(v) = {xe rn: jieSxt <v(sx s £ N}

/ 1 ¿—Ней

классической игры совпадает с ядром двойственной игры 0е=(ы,у), где V (й) = ) — \ й), всЫ. Игра, имеющая непустое двойственное ядро, называется двойственно сбалансированной.