Процессы управления и устойчивость

Лежнина Е.А.

Санкт-Петербургский государственный университет

Нормированное наименьшее с-ядро

в кооперативных играх

1. Введение. Теория игр занимается анализом конфликтов ме-

тодами математического моделирования. Математические модели

конфликтных ситуаций называются играми. Анализ игр направлен

на поиск справедливого разрешения конфликта. Целью исследова-

ния кооперативных игр является нахождение правил распределения

выигрышей между игроками.

Эксцесс представляет собой отрицательную полезность выигры-

ша x(S) для коалиции S, нормированную таким образом, чтобы по-

лезность выигрыша v(S) для любой коалиции S равнялась нулю.

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

рышами, доставляемыми вектором x, для разных коалиций. Вместо

указанных эксцессов можно рассматривать и другие функции. Од-

ной из таких функций является «нормированный» (per capita) экс-

цесс, определяемый для каждой коалиции как дробь

v(S)−x(S)

|S|

. Дей-

ствительно, при сравнении значений эксцессов различных коалиций

между собой такая нормировка естественна.

Настоящая работа посвящена аксиоматизации наименьшего

c-ядра, определенного с помощью нормированного эксцесса.

Правила, по которым формируется выбор множества σ(N, v),

формализуют естественные понятия оптимальности и справедли-

вости: индивидуальная рациональность, коллективная рациональ-

ность, анонимность (равноправие игроков), симметричность, ковари-

антность, ковариантность относительно сдвига, положительная од-

нородность, инвариантность относительно сдвига, макс-инвариант-

ность, согласованность, свойство подтверждения («flexibility») [1].

2. Нормированное наименьшее с-ядро. Рассмотрим задачу

минимизации (по векторам выигрышей) максимального (по коали-

циям) эксцесса:

max

S

(v(S) − x(S)) →

min

x∈X(N,v)

.

(1)

578

Решение этой задачи существует для всех игр c трансферабель-

ными полезностями (ТП игр) и является подмножеством c-ядра (ес-

ли оно непусто). Оно называется наименьшим c-ядром (LC). Дей-

ствительно, если c-ядро непусто, то оптимальное значение задачи

(1) не положительно, т. е. достигается на векторах из с-ядра.

Известна характеризация наименьшего с-ядра (см., например, [1]):

Теорема 1. Для того чтобы x ∈ LC(N, v), необходимо и доста-

точно, чтобы набор S

1

(x) был слабо сбалансирован.

Рассмотрим теперь задачу минимизации (по векторам выигры-

шей) максимального (по коалициям) нормированного эксцесса:

max

S

(v(S) − x(S))

|S|

→

min

x∈X(N,v)

.

(2)

Аналогично тому, как это показывается для классического экс-

цесса, легко можно показать, что решение этой задачи существует

для всех ТП игр и является подмножеством c-ядра (если оно непу-

сто). Оно называется нормированным наименьшим c-ядром (LC

n

).

Пусть x – произвольный вектор выигрышей игры (N, v). Обо-

значим через S

n

1

(x) набор коалиций, на которых достигается макси-

мальное значение нормированного эксцесса:

S

n

1

(x) = {S ⊂ N :

v(S) − x(S)

|S|

= max

S ⊂N

v(S ) − x(S )

|S|

} = µ

n

(x).

Теорема 2. Для того чтобы x ∈ LC

n

(N, v), необходимо и до-

статочно, чтобы набор S

n

1

(x) был слабо сбалансирован .

Доказательство теоремы 2 аналогично доказательству теоремы 1

о наименьшем с-ядре.

3. Свойства нормированного наименьшего с-ядра. Укажем

теперь свойства, которым удовлетворяет нормированное наименьшее

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

ными полезностями, эффективно, ковариантно, анонимно, ограниче-

но. Покажем, что оно удовлетворяет еще следующим свойствам:

Макс-инвариантность. Решение Φ для класса ТП игр G обладает

свойством

макс-инвариантности,

если

для

любых

игр

N, v , N, w ∈ G

x ∈ Φ(N, v) ∩ Φ(N, w) =⇒ x ∈ Φ(N, v ∨ w),

579

где (v ∨ w)(S) = max{v(S), w(S)}, S ⊂ N.

Нормированная независимость от сдвига. Φ(N, v) = Φ(N, v

β

), где

(v

β

)(S) =

v(S) + β|S|,

если S = N,

v(N ),

если S = N .

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

зациях решений, является свойство согласованности, связывающее

между собой решение исходной игры, и «редуцированной», получа-

ющейся, когда один или несколько игроков покидают игру с некото-

рыми выигрышами. Пусть N, v – произвольная игра. Редуцирован-

ная игра S, v

x

определяется для любой коалиции S ⊂ N и вектора

выигрышей x.

Решение Φ на классе G называется согласованным, если для лю-

бой игры N, v ∈ G, любых векторов выигрышей x и коалиции S

редуцированная игра S, v

x

∈ G и x

S

∈ Φ(S, v

x

).

При этом само определение редуцированной игры может быть

неоднозначным. Для характеризации решений, определяемых клас-

сическими эксцессами v(S)−x(S), обычно используется определение

редуцированной игры в смысле Дэвиса – Машлера:

v

x

(T ) =

max

Q⊂N \S

(v(T ∪ Q) − x(Q)),

если T

S,

v(N ) − x(N \ S),

если T = S.

Для решений с нормированными эксцессами определим редуци-

рованную игру следующим образом:

v

x

S

(T ) − x(T )

|T |

=

max

Q⊂N \S

v(T ∪Q)−x(T ∪Q)

|T ∪Q|

, если T = S,

0,

если T = S.

(3)

Из формулы (3) значения характеристической функции редуци-

рованной игры для коалиций T

S определяются следующим обра-

зом:

v

x

S

(T ) =

q

t + q

x(T ) + max

Q⊂N \S

t

t + q

v(T ∪ Q) − x(Q) .

(4)

Другим свойством, в некотором смысле обратным согласованно-

сти, является свойство подтверждения.

580

Решение Φ на классе G обладает свойством подтверждения, если

из x ∈ Φ(N, v), y

S

∈ Φ(S, v

x

) следует x

N \S,y

S

∈ Φ(N, v).

Далее будем говорить, что решение обладает свойством нормиро-

ванного подтверждения, если оно обладает свойством подтвержде-

ния в смысле определения (4) редуцированной игры.

Наименьшие с-ядра (относительно различных эксцессов) не обла-

дают свойствами согласованности, однако они обладают свойствами

подтверждения в различных определениях редуцированной игры.

Утверждение 1. Нормированное наименьшее с-ядро обладает

свойством нормированногог подтверждения в классе G .

Доказательство. Пусть N, v ∈ G – произвольная игра, x ∈

LC

n

(N, v), S ⊂ N – произвольная коалиция, (S, v

x

S

) – редуцирован-

ная игра на множество игроков S относительно вектора x в опре-

делении (4) редуцированной игры, и пусть y

S

∈ LC

n

(S, v

x

S

). Нужно

доказать, что (y

S

, x

N \S

) ∈ LC

n

(N, v).

Обозначим через e

n

1

(v, x) = max

T ⊂N

e

n

(v, x, T ) максимальный

нормированный эксцесс игры с характеристической функцией v для

вектора x. Соответственно, для редуцированной игры

e

n

1

(v

x

S

, y

S

) max

T ⊂S

e

n

1

(v

x

S

, T ).

По определению наименьшего с-ядра (нормированного в том числе)

величина e

n

1

(v, x) = e

n

1

(v) одна и та же для всех x ∈ p.c.LC(N, v) и

равна

e

n

1

(v) =

min

x ∈X(N,v)

e

n

1

(v, T, x ).

Покажем, что при редуцировании числа e

n

1

(v) не возрастают. Имеем

неравенства

e

n

1

(v) = e

n

1

(v, x) = max

T ⊂N

e

n

(v, T, x) ≥

≥

max

T ∪Q

T ⊂S, Q⊂N \S

e

n

(v, T ∪ Q, x) =

(5)

= max

T ⊂S

e(v

x

S

, T , x

S

) = e

n

1

(v

x

S

, x

S

) ≥ e

1

(v

x

S

).

Рассмотрим набор S

1

(x

N \S

, y

S

). Могут иметь место следующие

случаи:

1. Существует K ∈ S

1

(x

N \S

, y

S

), такая что K∩S = ∅, KN \ S = ∅.

В этом случае e

n

1

(v, (x

N \S

, y

S

)) = e

n

1

(v

x

S

, y) = e

n

1

(v

x

S

). Но из нера-

венств (5) следует, что

581

e

n

1

(v

x

S

) ≤ e

n

1

(v) ≤ e

n

1

(v, x) ≤ e

n

1

(v, (x

N \S,y

S

).

(6)

Из неравенств (5) и (6) следуют равенства

e

n

1

(v, (x

N \S

, y

S

)) = e

n

1

(v, x) = e

n

1

(v),

доказывающие, что (x

N \S

, y

S

) ∈ p.c.LC(N, v).

2. Если K ∈ S

1

(x), то K ⊂ S или K ⊂ N \ S. Если к тому

же e

n

1

(v) = e

n

1

(v

x

S

), то доказательство аналогично случаю 1. Пусть

теперь e

n

1

(v

x

S

) < e

n

1

(v). Это может быть только в случае, если

K ∈ S

1

(x), K ⊂ S =⇒ K = S.

Но y(S) = x(S) = v −x(N \S) по определению редуцированной игры,

следовательно,

e

n

1

(v) = e

n

1

(v, x) = e

n

(v, x, S) = e

n

(v, x, y) = e

n

1

(v, (x

N \S

, y

S

)),

откуда опять следует (x

N \S

, y

S

) ∈ LC

n

(N, v).

Покажем, что нормированное наименьшее с-ядро не обладает

свойством болвана.

Пример. Рассмотрим игру трех лиц с пустым с-ядром:

N = {1, 2, 3}, v({i}) = 0, i = 1, 2, 3,

v(1, 3) = v(2, 3) = 0, v(1, 2) = v(1, 2, 3) = −1.

В этой игре игрок 3 – болван. Нормированное наименьшее с-ядро

состоит из единственного вектора p.c.LC(N, v) = (−1/2, −1/3, −1/3).

Соответствующий упорядоченный вектор нормированных эксцессов

равен x = (1/3, 1/3, 1/3, 1/3, 0, 0). Набор S

n

1

(x) = {1, 2, (1, 3), (2, 3)}.

Болван получает −1/3 < v({3}) = 0.

Еще одно свойство – индивидуальная рациональность для су-

пераддитивных игр – также не выполняется для нормированного

наименьшего с-ядра.

4. Аксиоматическая характеризация нормированного наи-

меньшего с-ядра. Перечисленных свойств достаточно для харак-

теризации нормированного наименьшего с-ядра.

582

Пусть N, v ∈ G – произвольная игра, x – произвольный вектор

выигрышей. Рассмотрим характеристическую функцию w

x

на мно-

жестве N, определяемую следующим образом: для любой коалиции

S ⊂ N

w

x

(S) − x(S) =

v(S) − x(S)

s

.

(7)

Утверждение 2.

Пусть N, v

– произвольная игра, x ∈

LC

n

(N, v). Тогда x ∈ LC(N, w), где характеристическая функция

w

x

определена в (7) .

Доказательство. Из равенств (7) следует, что

e

n

(v(S), x(S)) = e(w(S), x(S)) для всех S ⊂ N,

и тогда S

n

1

(v, x) = S

1

(w, x). Так как x ∈ LC

n

(n, v), по теореме 2

набор S

n

1

(v, x) слабо сбалансирован. Следовательно, по теореме 1

x ∈ LC(N, w).

Теорема 3. Пусть Φ

n

– решение на классе G, обладающее свой-

ствами непустоты, ограниченности, ковариантности, нормиро-

ванным свойством подтверждения, нормированной независимости

от сдвига и макс-инвариантности. Тогда для любой игры N, v ∈ G

Φ(N, v) ⊂ LC

n

(N, v) .

Доказательство. По данному решению Φ

n

определим другое

решение Φ на классе G соотношениями

x ∈ Φ

n

(N, v) ⇐⇒ x ∈ Φ(N, w

x

),

(8)

где w

x

(S) = x(S) +

v(S)−x(S)

s

, ∀S ⊂ N .

По ковариантности Φ

n

решение Φ определено на всем классе G,

непусто, ограничено, ковариантно, обладает (обычным) свойством

инвариантности относительно сдвига и макс-инвариантности.

Доказательство теоремы будем проводить индукцией по числу

игроков. По лемме из [1] для игр двух лиц Φ является стандартным

решением, которое совпадает как с обычным, так и с нормированным

наименьшим с-ядром. Предположим, что теорема доказана для всех

игр с числом игроков, меньших n, и рассмотрим игру N, v , |N | = n.

Пусть x ∈ Φ(N, v) – произвольный вектор выигрышей, S

N –

произвольная коалиция. Рассмотрим редуцированную игру S, v

x

в

583

смысле определения (4), и пусть y

S

∈ Φ

n

(S, v

x

). Тогда по индукци-

онному предположению y

S

∈ LC

n

(S, v

x

). По теореме 2 набор

S

1

(y, v

x

) = arg max

T ⊂S

v

x

(T ) − y(T )

|T |

=

= arg max

T ⊂S

Q⊂N \S

v(T ∪ Q) − x(Q) − y(T )

|T | + |Q|

(9)

слабо сбалансирован на S, что эквивалентно тому факту, что на век-

торе y

S

достигается минимум

min

z:z(S)=v(N )−x(N \S)

max

T S,Q⊂N \S

v(Q ∪ T ) − x(Q) − z(T )

|T | + |Q|

.

Рассмотрим теперь редуцированную игру S, w

x

x

в смысле Дэви-

са – Машлера игры N, w

x

на множество S относительно вектора x.

Покажем, что вектор y

S

минимизирует максимальный по коалициям

T ⊂ S эксцесс w

x

x

(T ) − z(T ).

По определению редуцированной игры имеем

w

x

x

(T ) − y

S

(T ) = max

Q⊂N \S

w

x

(T ∪ Q) − x(Q) − y

S

(T ) =

= max

Q⊂N \S

v(T ∪ Q) − x(T ∪ Q)

|T | + |Q|

+ x(T ) − y(T ).

(10)

Легко заметить (см. (9)), что

v

x

(T ) − y

S

(T )

|T |

= max

Q⊂N \S

v(T ∪ Q) − x(T ∪ Q)

|T | + |Q|

+

x(T ) − y(T )

|T | + |Q|

.

Так как y

S

∈ LC

n

(S, v

x

), то на векторе y

S

достигается минимум

по всем векторам z ∈ X(S, v

x

) максимальных эксцессов

max

T ⊂S

v

x

(T ) − z(T )

|T |

=

max

T ⊂S,Q⊂N \S

v(T ∪ Q) − x(T ∪ Q)

|T | + |Q|

+

x(T ) − z(T )

|T | + |Q|

.

Поэтому, если положить z = y

S

, то для всех T ∈ S

n

1

(y

S

, v

x

) вы-

полняются неравенства

584

v(T ∪ Q) − x(T ∪ Q)

|T | + |Q|

+

x(T ) − y

S

(T )

|T | + |Q|

≤

v(T ∪ Q) − x(T ∪ Q)

|T | + |Q|

,

откуда следует, что

y

S

(T ) ≥ x(T ) для всех T ∈ S

n

1

(y, v

x

).

(11)

Так как набор S

n

1

(y

S

, v

x

) слабо сбалансирован по индукционному

предположению, неравенства (11) возможны только, если y

S

(T ) =

x(T ) для всех T ∈ S

n

1

(y

S

, v

x

).

А тогда из (10) следует, что вектор y

S

доставляет также минимум

максимальных эксцессов max

T ⊂S

(w

x

x

(T ) − z(T )) по всем векторам

выигрышей z редуцированной игры S, w

x

x

, т.е. по теореме 1 y

S

∈

LC(S, w

x

x

).

Итак, проекции наборов S

n

1

((x

N \S

, y

S

), v), S

1

((x

N \S

, y

S

), w

x

) на

множество S совпадают. Кроме того, они совпадают на коалициях

из множества N \ S, так как на коалициях из этого множества выиг-

рыши для вектора x и (x

N \S

, y

S

) равны. Поэтому из допустимости

(для решения Φ

n

) набора S

n

1

((x

N \S

, y

S

), v), которая следует из свой-

ства нормированного подтверждения решения Φ

n

, следует допусти-

мость (для решения Φ) набора S

1

((x

N \S

, y

S

), w

x

). А это означает, что

(x

N \S

, y

S

) ∈ Φ(N, w

x

), т.е. решение Φ обладает свойством (обычного)

подтверждения.

Таким образом, доказано, что решение Φ, определенное в (8), об-

ладает всеми свойствами, требуемыми в теореме 1. Следовательно,

для любой игры N, v Φ(N, v) ⊂ LC(N, v). Возвращаясь к решению

Φ

n

, по (8) получаем, что Φ

n

(N, v) ⊂ LC

n

(N, v).

Литература

1. Печерский С.Л., Яновская Е.Б. Кооперативные игры: решения и

аксиомы. СПб.: Изд-во Европ. ун-та в С.-Петербурге, 2004. 459 с.

2. Мулен Э. Кооперативное принятие решений: аксиомы и модели.

М.: Мир, 1991.

585

Малафеев О.А., Радченко А.Ю.

Санкт-Петербургский государственный университет

Конкурентная задача синхронизации работы

серверов и идемпотентный анализ

1. Постановка задачи. Рассматривается система массового об-

служивания [1], состоящая из четырех последовательных серверов

S

i

, i = 1, . . . , 4, и буфера, ассоциированного с первым сервером. Каж-

дый клиент k, (k = 1, . . . , N ) должен быть обслужен всеми четырьмя

серверами в определенной последовательности: S

1

, S

2

, S

3

и S

4

. Огра-

ниченное количество клиентов прибывает в буфер системы массово-

го обслуживания одновременно, и каждый ожидает своей очереди

на обслуживание l

k

.

Будем обозначать k[l

k

] клиента, который занимает в очереди ме-

сто [l

k

]. Для того, чтобы обслужить клиента k, серверу S

i

необходи-

мо τ

i

(k[l

k

]) тактов времени. Между серверами буфера отсутствуют.

Следовательно, если сервер S

i

, i = 1, 2, 3, уже закончил обслужива-

ние клиента k[l

k

], а S

i+1

все еще занят с клиентом k[l

k

− 1], то S

i

не

может начать работу с клиентом k[l

k

+ 1] и должен ждать. Время

перехода от сервера к серверу положим нулевым.

Обозначим через x

i

(k[l

k

]) момент начала работы сервера S

i

с

клиентом k. Прежде чем S

i

сможет начать обслуживание клиента

k[l

k

+ 1], должны быть выполнены следующие условия:

• S

i

закончил обслуживание клиента k[l

k

];

• S

i+1

свободен (для i = 4 это условие не применяется);

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: