Lectures_all

ГЛАВА 5. ДИЗАЙН КРУГОВЫХ ТУРНИРОВ. АКСИОМАТИЧЕСКИЙ ПОДХОД. 19.02.20

1)Анонимность. Правило ранжирования называется анонимным, если для любой перестановки на множестве участников турнира выполняется следующее свойство: для любых двух команд и ,

( ) ( ) ( ( )) ( ).

2)Положительная отзывчивость (Positive reponsiveness). Правило ранжирования обладает свойством положительно отзывчи- вости, если ( , ) и , : и : ( , ) = 0 в турнире выполняется условие: в турнире с характеристической функцией ′( , ), которая совпадает с всюду кроме наборов ( , ), ( , ) и для них ′( , ) = 1, ′( , ) = 0, выполняется соотношение

( ′ ) (каждой команде в каждом индивидуальном матче нет стимулов проиграть).

3)Независимость от посторонних альтернатив (Independence of irrelevant alternatives). Правило ранжирования обладает

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

Âрассматриваемых турнирах аксиомам удовлетворяет лишь метод определения победителя по числу максимальных побед.

Теорема 5.0.1 (Рубинштейн (1980)). Правило ранжирования удовлетворяет свойствам анонимности, положительной отзывчивости и независимости от посторонних альтернатив тогда и только тогда, когда — правило ранжирования по максимальному числу побед.

Доказательство. Легко видеть, что правило ранжирования по мак-

симальному числу побед удовлетворяет этим свойствам.

. 1( ) число побед команды , а 0( ) число побед команды

.

Лемма. Пусть обладает свойствами анонимности и независимости от посторонних альтернатив. Тогда если команды и таковы, что 1( ) = 0( ), то .

Доказательство. Пусть без ограничения общности, → . Разделим все команды на 4 группы:

= { | → , → }

ГЛАВА 5. ДИЗАЙН КРУГОВЫХ ТУРНИРОВ. АКСИОМАТИЧЕСКИЙ ПОДХОД. 19.02.20

= { | → , → }

= { | → , → }

= { | → , → }

Âсилу аксиомы независимости от посторонних альтернатив, будем считать, что команды множества обыграла все команды из , , , и

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

База индукции. | | = 0, тогда так как по условию побед у команд и одинаково и одинаковое место, и → , то | | = 1. Обозначим эту команду за . Так как , то → . Но тогда по свойству анонимности команды , , занимают одинаковое место. База доказана.

Индуктивный переход. Пусть для всех таких, что | | 6 −1 утверждение верно. Докажем лемму для случая | | = . Выберем некоторую команду и . Доопределим результаты матчей (это не скажется на расстановке и по аксиоме о независимости от посторонних альтернатив) так что { }, → и { }, → .

Предположим, что команды из { } все обыграли команду .

Êкомандам и можно применить предположение индукции. Тогда

. Команды , , показали одинаковый результат и попарно по кругу друг друга обыграли, а с остальными сыграли одинаково. В силу

свойства анонимности . Тогда .

Продолжаем доказательство теоремы. Рассмотрим две произвольные команды и .

1)åñëè 1( ) = 1( ), то утверждение следует из леммы.

2)åñëè 1( ) > 1( ) > 0 (не меняя общности). Рассмотрим новую характеристическую функцию ′, которая получена из функции заменой 1( ) − 1( ) − 1 победных результатов команды на поражения и заменой одного поражения на победу.

Тогда в этом турнире с характеристической функцией ′ количе- ство побед команды равно количеству побед команды . Но тогда

( ′ ) , но по положительной отзывчивости в новом турнире уже

( ′ ) значит, в старом турнире (при большем количестве побед) должно быть ( ) . Противоречие.

4)те, кто не купил информацию, выбывают из игры

5)информированные агенты делают ставки ставка 'го агента на первое событие

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

√

= − +

(1 − )

1 −

Посмотрим, когда ставка больше 0.

√

(1 − ) > 1 −

>

условие того, что информированный игрок делает положительную ставку.

Чем выше пот , тем выше ставки. Чем выше доля от пирога, которую получают информированные игроки, размер ставки раст¼т.

С ростом числа неинформированных агентов наша ставка должен падать.

ГЛАВА 8. ЗАДАЧА СОСТАВЛЕНИЯ РАСПИСАНИЯ ТУРНИРА 12.03.2015 27

å¼ êàê 2 +1 . . . 2 + . Антиподов попросим играть так же, как и в первой половине.

Удалим р¼бра игр, которые играют с бесконечность. Теперь этим команды будут играть друг против друга. Мы таким образом убиваем все оставшиеся матчи команд из одной половины с командами из другой. И сделаем такое расписание для 2 + 1 тура.

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

И так будем продолжать делать делать до 2 + −1-го тура. В 2 + - ом туре сделаем ещ¼ несколько переопределений. Так как ч¼тное, то мы отменяем матчи команд отменим матчи команд + 1 и так далее до 2 . И мы можем предположить, что команды играли ( + 1) ( + 2) с ( + 2) ( + 3). Теперь ставим играть эти команды со своими анти-

подами. Таким образом мы израсходовали все матчи одной половины с другой, кроме одного. Предположим, что остались несыгранными ещ¼ два тура, а матч 2 + 1 со своим антиподом, тогда в одном из двух ту-

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

6 2 −1, и ч¼тное, и 6 2 −2, но тогда 6 4 −2, а = 2 + 1, поэтому 2 = 4 + 2, и оста¼тся ровно разность = 2 − 4

Случай ч¼тного рассмотрен в статье.