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



жүктеу 30.48 Mb.
Pdf просмотр
бет53/57
Дата27.12.2016
өлшемі30.48 Mb.
1   ...   49   50   51   52   53   54   55   56   57

= 30000, Y

2

1

= 45000, Y



3

1

= 9000, Y



1

2

= Y



2

2

= Y



3

2

= Y



1

3

= Y



2

3

=



Y

3

3



= 0.

Литература

1. Габасова О.Р. Об оптимальной политике фирмы, использующей

в производстве два технологических способа. VIII Белорусская

математическая конференция: Тез. докл., Минск, 19 – 24 июня

2000. Институт маетматики НАНБ, 2000. Ч. 4. С. 60–61.

2. Интрилигатор М. Математические методы оптимизации и эконо-

мическая теория. М.: Прогресс, 1975. 607с.

3. Малафеев О.А., Муравьев А.И. Математические модели кон-

фликтных ситуаций и их разрешение. СПб.: Изд-во СПбГУЭФ,

2000.

4. Петросян Л.А., Зенкевич Н.А., С¨емина Е.А. Теория игр: Учебное



пособие для университетов. М.: Высшая школа, Книжный дом

"Университет", 1998. 304 c.

5. Ramsey F. Mathematical Theory of Saving // Econ. J., 1928. Vol. 38,

№ 12. P. 534–559.

577


Лежнина Е.А.

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

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

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

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 это условие не применяется);


Каталог: bitstream
bitstream -> С. торайғыровтың публицистикасы
bitstream -> Қ атыстық сын есімдердің лексикалық тіркесімділігі
bitstream -> «Қазақ» газетіндегі ұлт-азаттық көтеріліс туралы мақалалардың маңызы
bitstream -> Бегімбай К. М. Дизайн және бейнелеу өнері салаларына
bitstream -> Грам м атические форм ы вы раж ения ком паративны Х отнош ений в научно-популярной лингвистической литературе
bitstream -> СҮттің Қоректік сапасы және сүттегі микроорганизмдер
bitstream -> Қазақ халқының ою-өрнектерінің Қолданылуы
bitstream -> Л. Н. Гумилев атындағы ЕҰу хабаршысы


Поделитесь с Вашими друзьями:
1   ...   49   50   51   52   53   54   55   56   57


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет