Везде
Scarf’s Lemma and Brauer's Theorem
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
Scarf’s Lemma and Brauer's Theorem
Annotation
PII
S042473880005771-7-1
DOI
10.31857/S042473880005771-7
Publication type
Article
Status
Published
Authors
Vladimir Danilov 
Occupation: Principal Scientific Researcher
Affiliation: Central Economics and Matthematics Institute, Russian Academy of Sciences
Address: Moscow, Russian Federation
Edition
Volume 55 Issue 3
Pages
141-146
Abstract

In the paper (Petri, Voorneveld, 2018) it was proposed an elementary proof of Brouwer’s fixed point theorem. It was founded on some combinatirial statenet called the no-bullying lemma. In this short note we show that this lemma is a reformulation of the famous Scarf Lemma from classical article (Scarf, 1967). We discuss also a relation of no-bullying to the notion of equilibrated states  from paper (Danilov, Sotskov, 1987).

Keywords
KKM-theorem, equilibrated state, no-bullying lemma
Received
13.08.2019
Date of publication
22.08.2019
Number of purchasers
92
Views
2122
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 Известно много утверждений, близких по духу к теореие Брауэра о неподвижной точке, например, лемма Шпернера, теорема Кнастера–Куратовского–Мазуркевича (ККМ), теорема Какутани, лемма Гейла–Никайдо, лемма и теорема Скарфа. Интуитивно понятно, что все они эквивалентны между собой. Используя некотороые элементарные соображения и конструкции, можно вывести одно утверждение из любого другого. К примеру, сведение теоремы Скарфа к теореме Какутани можно найти в работе (Данилов, 1999), к теореме Какутани в контексте уравновешенных состояний приводится в работе (Данилов, Сотсков, 1987) лемма Скарфа. Скарф (Scarf, 1967) выводил свою теорему из некоторой комбинаторной леммы, которую доказывал прямым алгоритмом, хотя, как мы говорили выше, в принципе ее можно вывести из теоремы Брауэра. Оставался открытым вопрос, а можно ли теорему Брауэра вывести из леммы Скарфа. В настоящей работе мы рассказываем, как это сделать.
2 Толчок в этом направлении был спровоцирован работой (Petri, Voorneveld, 2018), где авторы получают теорему Брауэра (а также теоремы ККМ и Шпернера) из придуманной ими леммы о нетретировании (no-bullying lemma). Мы покажем, что эта лемма представляет измененный вариант леммы Скарфа. Так что фактически теорема Брауэра вытекает из упрощенного варианта леммы Скарфа. Для полноты картины мы приводим схему доказательства этого вырианта, близкую к оригинальному рассуждению Скарфа и более прозрачную, чем рассуждение (Petri, Voorneveld, 2018). Что подтверждает неоднократно высказанную мудрость, что новое — это хорошо забытое (или незамеченное) старое1.
1. В работе (Petri, Voorneveld, 2018) авторы выражают благодарность многим людям за полезные комментарии, среди них Kim Border и Jean-Jacques Herings. Поразительно, что даже эти специалисты по ядрам сбалансированных игр не увидели, что основной результат статьи (Petri, Voorneveld, 2018) установлен Скарфом в его знаменитой работе. Этого не увидел и Н. Иванов, который в своей статье (Ivanov, 2019)).
3 ЛЕММА О НЕТРЕТИРОВАНИИ
4 Сформулируем лемму, придерживаясь терминологии (Petri, Voorneveld, 2018). Имеется несколько агентов, множество которых обозначим как . Для удобства восприятия агентов удобно понимать как детей, у каждого из которых имеется некоторое непустое конечное множество его игрушек . Множество всех игрушек обозначим как . Отображение однозначно указывает владельца игрушки. Каждый ребенок упорядочивает игрушки по привлекательности некоторым способом. Иначе говоря, предполагается, что для каждого i задан линейный порядок на множестве T. Будем считать, что этот порядок задается функцией полезности . Тем самым можно понимать игрушку t как точку в n-мерном пространстве .
5 Пусть — некоторое подмножество игрушек, — группа владельцев этих игрушек. Предполагается, что дети внутри этой группы могут перераспределять игрушки из набора X некоторым спососбом. Обозначим через наилучшую игрушку для i в наборе X. Желательно, чтобы каждый ребенок i внутри группы C получил игрушку . В этой связи вводится следующее определение.
6 Определение. Набор игрушек X называется нетретирующим (no bullying), если нет такой игрушки , которая была бы хуже для каждого ребенка i из . Иными словами, для любой игрушки t найдется , такой что .
7 Некоторое оправдание терминологии состоит в том, что если это условие нетретируемости нарушается (т.е. набор — третирующий и имеется игрушка t, которая всем членам группы C кажется хуже ), то дети единодушно могут третировать (или жалеть) владельца этой игрушки: “Твоя игрушка хуже моей” или “Твоя игрушка нам не интересна”. Однако такое оправдание не слишком убедительно. В самом деле, каждый член группы C мог бы воспринимать владельца игрушки t как неудачника. Но хозяин этой игрушки t вполне может быть доволен игрушкой. Почему ему должно быть важно, чтобы ему кто-то завидовал?
8 Тем не менее в требовании нетретируемости есть и разумное соображение. Например, все игрушки [[[image13]]][[[image13]]] (для ) оказываются разными и могут быть безконфликтно перераспределены между членами группы C. В самом деле, допустим, что какая-то игрушка из X оказалась наилучшей для двух (или более) членов группы C. Но тогда внутри X имеется игрушка x, которая не является наилучшей ни для кого из группы C, что противоречит требованию нетретируемости.
9 Пример. Рассмотрим простой пример с тремя участниками А, В и С, которые владеют игрушками a, b и c соответственно. Предпочтения заданы в табличной форме (более желательная игрушка располагается выше):
10 A= {b, a, c}, B={c, b, a}, C={b, a, c}
11 Предпочтения показывают, что игрушка b лучше, чем игрушка a, для всех участников. Отсюда следует, что она не может входить в нетретирующий набор (третируется ребенок A). Поэтому можно удалить ребенка В и перейти ко второму набору:
12 A= {b, a, c}, C={b, a, c}
13 Теперь мы видим, что a лучше c для всех членов уменьшенной группы . Поэтому игрушка a тоже не может входить в состав нетретирующего набора. Остается ребенок С, который со своей игрушкой c образует (единственный) нетретирующий набор.
14 В этом примере нетретирующий набор существует (хотя его и трудно назвать удачным), и это не случайно, как показывает следующий общий факт, установленный в работе (Petri, Voorneveld, 2018).
15 Теорема 1. Всегда существует непустой нетретирующий набор игрушек.
16 Точнее, авторы этой работы доказывают теорему 1 в частном случае, когда каждый ребенок владеет единственной игрушкой. Однако они же показывают, что общий случай сводится к этому частному с помощью нехитрого приема репликации агентов. О доказательстве теоремы мы еще поговорим, а пока займемся другим вопросом, как эта теорема связана с теоремой Брауэра, а точнее, с теоремой ККМ.
17 СВЯЗЬ С ТЕОРЕМОЙ ККМ
18 Вместо теоремы Брауэра о неподвижных точках мы будем работать с эквивалентной ей (Aubin, 1984) теоремой ККМ. Для ее формулировки надо напомнить некоторые определения.
19 Символом мы обозначаем стандартный симплекс в пространстве , т.е. множество точек , таких что для всех и . Это будет выпуклый многогранник, грани которого индексируются непустыми подмножествами множества . Если , соответствующая грань совпадает с множество , состоящим из точек , у которых для . Например, , а для грань — вершина симплекса, состоящая их базисного вектора пространства .
20 Теорема ККМ. Пусть в симплексе заданы замкнутых подмножеств . Предположим, что выполнено краевое условие, для любого грань покрывается множествами , где . Тогда существует точка , принадлежащая всем , .
21 Покажем, что теорему 1 можно рассматривать как дискретный вариант ККМ при некоторой простой модификации теоремы 1, связанной с краевым условием в теореме ККМ. В работе (Petri, Voorneveld, 2018) авторы такую модификацию не проводят, чем только усложняют доказательство.
22 Нужная нам модификация предложена Скарфом и она состоит в следующем. Без ущерба для общности можно считать, что полезности всех игрушек находятся строго между 0 и 1. Давайте расширим множество игрушек , добавив для каждого ребенка фиктивную игрушку , принадлежащую ему. Полезность такой игрушки для его владельца положим равной 1, а полезность для всех остальных членов группы, равной 0. Как точка в пространстве полезностей, такая фиктивная игрушка представляется базисным вектором . Расширенное (за счет добавления фиктивных игрушек) множество игрушек обозначим как . Мы утверждаем, что с точки зрения существования нетретирующего набора добавление фиктивных игрушек ничего принципиально не меняет. Более точно, имеет место следующее простое утверждение, проверка которого предоставляется читателю.
23 Лемма. Пусть набор нетретирующий (в исходной постановке с игрушками T). Тогда набор , полученный добавлением к X фиктивных игрушек игроков, не входящих в группу , нетретирующий (в постановке с игрушками ). Обратно, если набор нетретирующий (в постановке ), то набор , полученный удалением фиктивных игрушек из , является нетретирующим в постановке T.
24 Заметим, что добавление фиктивных игрушек приводит к тому, что любой нетретирующий набор X состоит в точности из n игрушек, принадлежащих разным игрокам. В самом деле, если какой-то игрок i не участвует в коалиции , его фиктивная игрушка кажется плохой остальным игрокам. Покажем как теорема ККМ выводится из теоремы 1.
25 Пусть, как в теореме 1, дан набор замкнутых подмножеств , удовлетворяющий краевому условию. В качестве множества игрушек T возьмем любое достаточно плотное конечное подмножество (-сеть) в симплексе , содержащее вершины этого симплекса. Полезность игрушки t из T для ребенка i положим равной координате i точки t в . Каждая игрушка t принадлежит некоторому ; такое i будем считать хозяином этой игрушки. Таким образом, . Согласно теореме 1, существует набор игрушек из n игрушек, который нетретирующий. Последнее влечет, что эти точки расположены близко друг к другу, на расстоянии порядка (точнее, на расстоянии, не большем ). При уменьшении такие наборы стремятся к некоторой точке x. Эта предельная точка x принадлежит уже всем множествами в силу их замкнутости.
26 Обратно, теорема 1 (в постановке с фиктивными игрушками) следует из ККМ. Наметим такой вывод в общих чертах, не углубляясь в детали. Пусть T — множество игрушек, представленное как множество точек в пространстве полезностей . С каждой такой точкой t свяжем верхний конус , и положим и . Нас будт интересовать нижняя граница множества , состояшая из точкек Y, которые видны из начала координат 0. Лучи, выходящие из 0, задают биекцию (гомеоморфизм) этой границы на симплекс . Подмножества в задаются как образы множеств (см. рисунок).
27

Рисунок
28 Легко проверить, что все условия теоремы ККМ выполнены. Поэтому существует точка , которая принадлежит всем . Ее прообраз z в принадлежит всем , а принадлежность означает, что для некоторой игрушки . Остается взять набор игрушек в качестве нетретирующего. Это показывает, что теорема 1 — дискретный двойник теоремы ККМ.
29 УРАВНОВЕШЕННЫЕ СОСТОЯНИЯ
30 Понятие нетретирующего набора X (и соответствующей группы владельцев напоминает понятие уравновешенного состояния, рассмотренное в статьях (Полтерович, 1984, Данилов, Сотсков, 1987). Для этого нужно заменить отношения на противоположные. После этого нетретирующий набор игрушек превращается в набор, удовлетворяющий следующему условию.
31 Условие недоминируемости (ND). Для любой игрушки найдется ребенок (владелец некоторой игрушки из X), для которого .
32 Такую пару мы называли уравновешенным состоянием. ND-условие выглядит уже более осмысленно. Оно состоит в том, что набор игрушек X в некотором смысле оптимален для коалиции C. Точнее, нет игрушки t, которая была бы лучше для каждого по сравнению с его наихудшей игрушкой в X. То есть член i группы не знает, какая игрушка достанется ему при перераспределении игрушек из X и ориентируется на самый плохой исход. А то что какая-то игрушка ему достанется обязательно, устанавливается как и раньше, в разд. 1. Более того, пусть обозначает самую плохую игрушку для в наборе X. Как и раньще, все игрушки (I пробегает C) в совокупности образуют все X. В самом деле, пусть какая-то игрушка не попала в этот список и отлична от всех . Но тогда она лучше для каждого , что противоречит ND-условию. В частности, множества C и B имеют одинаковый размер, .
33 Если — владелец игрушки t, отображение осуществляет биекцию X и C для уравновешенного состояния . Кроме того, набор X Парето-оптимален для коалиции C, если полезность набора X участник i понимает как .
34 В работе (Данилов, Сотсков, 1987) было доказано существование уравновешенных состояний путем сведения к теореме Брауэра–Какутани. Понятно, что этот результат также нельзя использовать для доказательства самой теоремы Брауэра. Нужно прямое доказательство теоремы 1. Его дает лемма и алгоритм Скарфа, о чем буде сказано в следующем разделе.
35 ЛЕММА СКАРФА
36 Обсуждая понятие уравновешенного состояния в (Данилов, Сотсков, 1987), мы отмечали, что оно тесно связано с результатами из (Scarf, 1967). В этой работе доказывается непустота ядра сбалансированной кооперативной игры. Для этого Скарф использовал вспомогательный факт про конечные множества, который принято называть леммой Скарфа (Scarf, 1967, Theorem 2). В частном случае эта лемма превращается в точности в утверждение о существовании уравновешенного состояния (или теорему 1, если угодно). Так что дальше будем обсуждать именно такой упрощенный вариант леммы Скарфа. Заметим, что Скарф прекрасно понимал, что из упрощенного варианта его леммы следует лемма Шпернера, а значит и теорема Брауэра2.
2. «Взятие повторяющихся единичных матриц в теореме 2 — это и есть упрощенный вариант леммы Скарфа» (Scarf, 1967).
37 Упрощенный вариант леммы Скарфа — это в точности теорема 1 с фиктивными игрушками, но для порядков, замененных на противоположные. Для ясности, напомним формулировку. Имеется конечное непустое множества игрушек T, которые распределены между участниками с помощью отображения . Для каждого участника задана функция полезности . Набор игрушек называется недоминируемым для коалиции , если для любой игрушки найдется участник для которого . Наконец, выполняется предположение о фиктивных игрушках.
38 Лемма Скарфа (упрощенный вариант). В этих условиях существует непустой набор игрушек X, который допустим (в том смысле, что ) и недоминируем коалицией всех участников.
39 Слегка изменив функции полезности, можно дополнительно считать, что полезности разных игрушек различны. Это позволяет немного сузить круг поисков недоминируемого набора игрушек. А именно, можно ограничиться наборами размера n. Таким образом, нам нужно найти набор X из n игрушек, который обладает двумя свойствами:
40
  1. он допустим, т.е. (или, что то же самое, что игрушки из X принадлежат разным участникам),
  2. он недоминируем коалицией : для любой игрушки найдется участник i, такой что t для него хуже всех игрушек из X.
41

Чтобы найти такой набор, Скарф предлагает переходить от одного набора к другому так, чтобы поочередно выполнялось либо условие 1, либо условие 2. При этом каждый следующий набор отличается от предыдущего заменой одной игрушки. Через конечное число шагов алгоритм приходит к состоянию, когда выполнены условия 1 и 2. Этот алгоритм во многом напоминает алгоритм поиска пестрого симплекса при доказательстве леммы Шпернера (см. например, (Данилов, 1998, с. 38–39)). Эта аналогия наводит на мысль в таком же стиле реорганизовать алгоритм Скарфа. Наиболее изящно эта идея была реализована Г.У. Куном (Kuhn, 1968) (Я благодарен Николаю Иванову, который указал мне на эту статью.) Назовем примитивным n-элементное подмножество в T, которое удовлетворяет свойству 2. Можно показать, что семейство примитивных множеств образует псевдо-многообразие с границей, являющейся границей симплекса (см. детали у (Scarf, 1967) или в работах (Aharoni, Holzman, 1998, Lemma 3.2; Васильев, 1984, лемма 1.2, глава 2). А тогда стандартный подсчет в стиле Шпернера показывает, что имеется нечетное число пестрых (т.е. удовлетворяющих свойству 1) примитивных множеств, а алгоритм Скарфа превращается в привычный путь по полупестрым симплексам. Это показывает, что имеется общая основа при доказательстве леммы Скарфа и леммы Шпернера.

References

1. Vasiliev V.A. (1984). Models of Economacal Exchange and Cooperative Games. Novosibirsk: NGU (in Russian).

2. Danilov V.I., Sotskov A.I. (1987). Equilibrated States and Theorems on the Core. Optimizatsija, 41, 36–49 (in Russian). [Trans. in: Danilov V.I., Sotskov A.I. (2006). Equilibrated states and theorems on the core. In: “Russian Contributions to Game Theory and Equilibrium theoty” Driessen T., Laan G. van der, Vasil’ev V., Yanovskaya E. (eds). Berlin: Springer, 237–250.]

3. Danilov V.I. (1998). Lectures on fixed points. Moscow: NES (in Russian).

4. Danilov V.I. (1999). On Scarf Theorem. Economics and Mathematical Methods, 35, 3, 137–139 (in Russian).

5. Aubin J.-P. (1984). L’analise non lineare et ses motivations economiques. Paris: Mason.

6. Aharoni R., Holzman R. (1998). Fractional Kernels in Digraphs. Journal of Comb. Theory, Series B, 73, 1–6.

7. Ivanov N.V. (2019). Beyond Sperner’s Lemma. arXiv:1902.00827[math.AT].

8. Kuhn H.W. (1968). Simplicial Approximation of Fixed Points. Proceedings of the National Academy of Sciences, 61, 1238–1242.

9. Petri H., Voorneveld M. (2018). No Bullying! A Playful Proof of Brouwer’s Fixed-Point Theorem. Journal of Mathematical Economics, 78, 1–5.

10. Scarf H. (1967). The Core of N-Person Game. Econometrica, 35, 50–69.

Comments

No posts found

Write a review
Translate