Главная страница

теориия игр. Лекции по теории игр вводный уровень


Скачать 1.71 Mb.
НазваниеЛекции по теории игр вводный уровень
Анкортеориия игр
Дата29.03.2023
Размер1.71 Mb.
Формат файлаpdf
Имя файлаgamestheory0_230130_141053.pdf
ТипЛекции
#1022531
страница2 из 10
1   2   3   4   5   6   7   8   9   10
Заметим, что выбор индикатора неоднозначен: с точностью до строго монотонного преобразования. (?)Докажите это в общем виде?
Примеры 7. Демонстрируя неоднозначность, постройте по два индикатора пред- почтения а)для гиперболы со степенью: y = 1/x
2
(?), б)для круговых линий уровня расхо- дящихся (возрастающих) наружу или возрастающих внутрь, в)для прямых уголков,
у которых точка излома возрастает от начала координат по биссектрисе или не по биссектрисе, (см. также такие задачи ниже).
Утверждение. Любое строго монотонное преобразование индикатора есть инди- катор того же предпочтения.
Доказательство - элементарно. . . . . .
Оказывается, подобрать индикатор не всегда возможно, даже если предпочтение полно, транзитивно (ниже пример — разрывное “Лексикографическое” предпочте- ние).
Для непрерывных же рациональных предпочтений в лекциях приведена –
Теорема Дебре (G.Debreu) о представимости непрерывных предпочтений целевыми функциями: Th.:
Если предпочтение рационально (полно, транзи- тивно) и непрерывно, то найдется представляющая его функция – инди- катор, причем непрерывная
(?) Док-во – частично было на лекции (а более общее - см. в кн. Алипрантис).
Идея доказательства для монотонных предпочтений на R
n
+
Непредставимость: Контрпример непредставимости предпочтений в отстут- ствии непрерывности – это предпочтение Lexgraph. Это такое предпочтение: Если у вектора x первая компонента больше, чем у y, то x лучше. Если они равны, то сравниваются вторые компоненты аналогично. Если и вторые равны, то третьи, и т.д.
Утверждение: предпочтение Lexgraph не может быть представлено никакой функцией. Причина - то, что оно не непрерывно.
Определение. Максимальный элемент в множестве – тот, для которого в этом множестве нельзя найти более хорошего элемента. А наилучший элемент - тот, что строго лучше всех других.
Утверждение. Все максимальные элементы лежат в одном множестве безраз- личия. (Очевидно)

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

º рационально
u(.) монотонна (возрастает)

º монотонно
u(.) строго монотонна (стр. возрастает)
º строго монотонно
u(.) непрерывна

º непрерывно
u(.) вогнута или квазивогнута

º выпукло
(Лекция 2)
1.2
Многоцелевой оптимум: сильный и слабый оп- тимум Парето
Когда целевых функций много, обычное понятие оптимальности приходится обоб- щить. Рассмотрим любую ситуацию, где есть множество участников N = {1, ..., n} и общее множество доступных им альтернатив X.
Сильное и слабое доминирование среди векторов: знаки (2, 3) (2, 3), (2, 3) >
(2, 2), (2, 3) À (1, 2).
Сильное и слабое доминирование среди профиля предпочтений коллектива Ann,
Bob:
V ine º
AB
V ine ⇔ (u
A
(V ine), u
B
(V ine)) (u
A
(V ine), u
B
(V ine));
V ine Â
AB
T ea ⇔ (u
A
(V ine), u
B
(V ine)) > (u
A
(T ea), u
B
(T ea)) (u
A
(V ine), u
B
(V ine)) ≥6=
(u
A
(T ea), u
B
(T ea));
V ine ÂÂ
AB
W hisky ⇔ (u
A
(V ine), u
B
(V ine)) À (u
A
(W hisky), u
B
(W hisky)).
Слабо Парето-оптимальные ( ˜
P или wP ) –
это доступные альтернативы,
для которых нет сильного Парето-улучшения среди доступных альтер- натив, то есть которые нельзя улучшить для всех участников сразу (нет доступного сильного Парето-доминирующего варианта)
Сильно Парето-оптимальные ( ˜
P ) –
это доступные альтернативы, для ко- торых нет слабого Парето-улучшения среди доступных альтернатив, то есть которые нельзя улучшить для кого-то не ухудшив для кого-то (нет доступного слабого Парето-доминирующего варианта)
Пример “Круглый остров”. Есть в теплом море круглый остров радиуса 5 км,
центр имеет координаты (0,0), то есть допустимое множество X = {(x
1
, x
2
)| x
2 1
+ x
2 2

5}. Для полноты рая, Анна и Боб собираются построить общий шалаш, но Анна хоте- ла бы по-восточнее, чтобы романтично встречать рассветы, а ленивый Боб поближе к любимой точке (-3,4) – банановой пальме. Эти предпочтения можно описать, на- пример, функциями u
A
(x
1
, x
2
) = x
1
, u
B
(x
1
, x
2
) = (x
1
3)
2
(x
2
4)
2
, (можно и другими, с точностью до строго монотонного преобразования).

1.3. Индивидуальные и коалиционные возможности: “переговорное множество”и ядро 13
Легко проверить, что сильный и слабый Парето-оптимумы этого сообщества в этой задаче поиска компромиссов совпадут: P = wP, и окажутся некой кривой со- единяющей наилучшую для Анны точку x

A
= (5, 0) с наилучшей для Боба точкой
x

B
= (3, 4). При этом, часть этого множества идет горизонтально по внутренности острова - от точки x

B
до береговой точки (3, 4), а остальная часть по восточному берегу до x

A
= (5, 0).
Можно предложить два геометрических критерия проверки любой точки ˆ
x на
Парето-оптимальность. (1) Провести через нее все линии уровня. Если множество
L
++
N

x) лучших для всего сообщества N = {A, B} точек (сильно-доминирующих)
пусто, то она слабо-Паретовская. Если к тому же множество L
+
N

x) не-худших для всего сообщества точек состоит только из этой точки ˆ
x, то она и Паретовская (а если не только из нее, то нужно исследовать подробнее).
(2) Можно в проверяемой точке построить градиенты всех целевых функций, то есть нормали к линиям уровня. Если для внутренней точки не существует неотри- цательных весов с которыми эти градиенты суммировались бы к нулю, то точка никакая, ни слабо и ни сильно-Паретовская. Для краевой точки в качестве допол- нительного градиента можно брать "реакцию опоры", сдерживающую рост полез- ности, то есть нормаль к активному в точке ограничению. В другую сторону (что точка Паретовская) этот критерий в невыпуклой задаче может подвести, поскольку бывают и локальные оптимумы не являющиеся глобальными.
1.3
Индивидуальные и коалиционные возможности:
“переговорное множество”и ядро
Пусть, к уже рассмотренным задачам добавляется новое условие. Теперь, кроме сов- местных действий, каждый участник может что-то и в одиночку. Это накладывает дополнительное ограничение на множество возможных компромиссов, или ”исходов соглашения”, которое мы пытаемся предсказать. Участник отвергает соглашение, ес- ли оно хуже некоторого ”статус-кво”, случившегося точкой отсчета в переговорах. В
играх обмена это точка начального запаса.
В приведенной задаче об острове, пускай, точка отсчета – это условие, выдвинутое каждым, что он уступит не более 2/3 своей полезности, от наилучшей для него до наихудшей на острове точки. Где тогда могут лежать исходы переговоров?
Есть соответствие между допустимым множеством в физическом пространстве выбора – например, точки на рассмотренном острове – и допустимым множеством результирующих полезностей. Пространство достижимых уровней полезности назы- вают критериальным пространством, оно имеет такую размерность как число участ- ников игры (в отличие от физического пространства выбора). Каждую точку физи- ческого пространства x ∈ X можно отобразить вектор-функцией u
N
= (u
1
, ..., u
n
) в точку критериального пространства (u
1
(x), ..., u
n
(x)) ∈ R
n
. Но точке Парето здесь может соответствовать несколько прообразов в исходном физическом пространстве,
доставляющих ту же полезность. Так или иначе, все допустимое множество x ∈ X
имеет некоторый образ u
N
(X) в критериальном пространстве. Обычно считают, что вместе с любой полезностью участнику игры доступна и меньшая (вред себе все уме- ют приносить), поэтому допустимым множеством полезностей считают не сам образ
u
N
(X) физического множества, а его расширение ˜
U вниз до бесконечности по всем

14
Глава 1. Предпочтения, кооперативные игры, общее равновесие
направлениям:
˜
U = u
N
(X) + R
n

.
На этом множестве Парето-оптимум выглядит как его верхняя правая граница,
поэтому его часто так и называют. Мы увидим, что когда ц. функции вогнуты, то множество . выпукло и его Парето-граница непрерывна в некотором смысле.
Забегая вперед, в дополнение к Контрактному множеству введем понятие ядра,
оно нам понадобится для анализа равновесий.
Определение.
Ядром игры называется множество альтернатив, не блокируемое никакой коалицией. Коалиция S блокирует (отверга- ет) какую-либо альтернативу x, если имеет в своем распоряжении (что бы ни делали остальные участники) другую альтернативу y, строго луч- шую, чем x для всех участников из S.
Это определение имеет ясный смысл только в тех играх, где возможности ко- алиций ясно описаны. Например, они описаны в терминах пространства выигры- шей, которое мы здесь преимущественно и обсуждаем, то есть следует понимать,
что x, y ∈ R
n
– это вектора выигрышей. Или, в экономике обмена, x, y ∈ R
n
– это распределения товаров.
Из определения очевидно, что слабая Парето-граница есть просто множество альтернатив, не блокиру- емых большой (полной) коалицией
1.3.1
Теоремы, характеризующие сильный и слабый Парето- оптимумы
(Характеризация Парето-оптимума варьированием ограничений.)
Утверждение 1.3.1.1 Пусть предпочтения заданы функциями u
i
(.) на допу-
стимом множестве X. Допустимая точка x ∈ X является Паретовской (x ∈ P )
тогда и только тогда, когда она есть решение n оптимизационных задач по макси-
мизации полезности каждого при неубывании полезности остальных по сравнению
с этой точкой:
¯
x ∈ P ⇔ [∀i
¯
x ∈ arg max
x∈X
u
i
(x) : u
j
(x) ≥ u
0j
= u
j

x)∀j].
Доказательство очевидно, ведь это и есть определение Парето-оптимума: неулуч- шаемость предпочтений любого из участников при неубывании полезности осталь- ных.
Соответственно, варьируя запрашиваемые уровни u
0j
полезности каждого, можно получать разные точки Парето-оптимума, и перебрать их все.
Варьирование весов целей для характеризации Парето-оптимума и его существование.
Есть и другой способ вычислить все точки Парето-оптимума варьируя парамет- ры. Введем вектор весов α ∈ R
n
+
, α 6= 0 и соответствующую Функцию Суммарного
Благосостояния в виде
U
α
(x) =
X
i
α
i
u
i
(x).

1.4. Вальрасовское равновесие и ядро в игре обмена
15
Теорема. (1) При неотрицательных весах α ∈ R
n
+
, любой аргмаксимум суммар- ного Благосостояния является слабым оптимумом Парето, при положительных весах являющийся и оптимумом Парето:
¯
x ∈ arg max
X
i
α
i
u
i
(x) => ¯
x ∈ wP.
(2) Если целевые функции вогнуты, а допустимое множество выпукло, то любой эле- мент оптимума Парето можно найти как аргмаксимум суммарного Благосостояния взятого с неотрицательными весами:
¯
x ∈ P => ∃α > 0 : ¯
x ∈ arg max
X
i
α
i
u
i
(x).
Следствие. Пусть допустимое множество – непустой компакт и целевые функции непрерывны. Тогда Парето-оптимум непуст, и более того, содержит точки не-худшие по сравнению с любой допустимой точкой.
Доказательство теоремы в прямую сторону – несложно (от противного). Доказа- тельство теоремы в обратную сторону – по теореме отделимости выпуклых множеств,
используя выясненную выпуклость множества достижимых полезностей.
Доказательство Следствия – по теореме Вейерштрасса, применяя предыдущую теорему с любыми ненулевыми весами.
Утверждения о форме Парето-оптимума . . . . .
Утверждение 1.3.1.2 Если допустимое множество компактно, а предпочте-
ния рациональны и непрерывны (например, заданы непрерывными функциями) то
на каждой линии или поверхности безразличия каждого участника в допустимом
множестве есть точка Парето. Если к тому же участников двое и их предпо-
чтения выпуклы (на выпуклом д.м.), то подмножество Паретовских точек при-
надлежащее любой поверхности безразличия любого из участников выпукло. Если
предпочтения при этом строго выпуклы и строго монотонны (например, заданы
строго вогнутыми строго монотонными функциями), то это единственная точка.
Утверждение 1.3.1.3 Если допустимое множество выпукло и компактно, а
предпочтения заданы непрерывными вогнутыми функциями, то Парето-оптимум
связное множество, включающее наилучшие точки каждого из участников.
1 1.4
Вальрасовское равновесие и ядро в игре обмена
(Лекция 4)
В этой лекции рассмотрим частный случай игр – игры обмена товарами. Будем интересоваться тоже Парето-оптимумом, ядром, и новым понятием – равновесием
Вальраса. Вообще, это основная классическая модель совершенного (неискаженного)
рынка. Она предложена в идее Адамом Смитом, развита в виде примеров Давидом
1
Связность множества означает существование пути (непрерывной кривой) из любой точки в любую. Вполне строго сформулировать и доказать это в рамках этого курса не получится, нужны понятия топологии.

16
Глава 1. Предпочтения, кооперативные игры, общее равновесие
Рикардо, записана в уравнениях Вальрасом и Джевонсом в 19-м веке. В 1950-е годы
Эрроу и Дебре теоретически “зачистили” эту модель, доказав существование равно- весий, их Парето-эффективность и другие свойства, и получили за это Нобелевскую премию. Модель стала "неоклассической”. Мы повторим вариант без производства,
известный вам из курса микроэкономики, но с деталями и доказательствами (кото- рые понадобятся вам на 3-м курсе).
Неоклассическая модель для рынка обмена l товарами включает исходные данные:
1)предпочтения или целевые функции u
i
(.) для n потребителей, 2)исходное рас- пределение собственности: для каждого i начальные запасы ω
i
и долю θ
ij
1 в прибыли j предприятия.
По этим исходным данным предсказывается “состояние” экономики (x, y, p), ко- торое включает: план общего потребления x ∈ R
ml
, цены p ∈ R
l
. В сущности, найти равновесие – значит решить задачу аукциониста: подобрать цены, при кото- рых спрос участников совпал бы с предложением по всем товарам.
В аналитических задачах этот подбор сводится к системе уравнений, вытекающих из определения равновесия. В графических задачах это делается перебором наклонов ценовой линии.
Определение. Состояние экономики обмена (¯
p, ¯
x) ∈ R
l∗ml∗nl
назовем равновесие
Вальраса (W E), если:
1) (¯
x, ¯
y) – оптимальный выбор потребителей при ценах ¯
p, т.е., ¯
x ∈ X

i

p), ¯
y ∈
Y

j
(p), где спрос и предложение есть
X

i
(p, y) = arg max
x
i
∈B
i
(p,y)
u(x
i
),
(p, y) ∈ R
l+nl
,
Y

j
(p) = arg max
y
j
∈Y j
(py
j
),
∀p ∈ R
l
2) выполнены материальные балансы спроса по всем товарам, то есть равенство нулю "избыточного спроса” ζ: ζ :=
P
m
i=1

x
i
− ω
i
)
P
n
j=1
¯
y
j
= 0 ∈ R
l
.
Когда производства нет, равновесие Вальраса для двух участников и двух то- варов можно найти графически на "ящике Эджворта”. Как показано в лекциях (в конце этого текста), равновесие в ядре. Следовательно, задакча аукциониста сводит- ся к предложению ценовой линии, соединяющей точку начальных запасов с одной из точек ядра. Причем такой, чтобы спрос совпал с предложением, то есть выбор пер- вого участника x
1
и выбор второго
1   2   3   4   5   6   7   8   9   10


написать администратору сайта