Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Аукцион первой цены: поиск функции реакции
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория игр
32 個評分
從本節課中
Секвенциальные равновесия и равновесия Байеса-Нэша
Мы изучим концепцию равновесия Байеса-Нэша и секвенциального равновесия.
與講師見面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Итак, будем писать условия о максимизации,
помня о том, что, в принципе, условия второго порядка можно не проверять.
Всё равно здесь есть максимум, и в нём должна быть производная равна нулю,
поэтому мы можем просто взять и приравнять производную нулю.
Давайте возьмём производную от этого выражения по по b с волной.
Итак, чтобы найти Argmax, нужно продифференцировать вот это по b с волной.
Поехали.
Все, наверное, помнят, как дифференцируются обратные функции,
придётся дифференцировать здесь.
Получается, −b в −1 от (b
с волной) + (v
− b с волной) * производную обратной функции,
то есть 1 / b' от (b в − 1 от (b с волной)).
И вот это вот = 0.
Давайте я перепишу, перекидаю, вот это я направо скину и умножу на вот это.
Тогда я получу: v − b с волной останется слева,
а справа b в −1 от (b с волной) * b'(b
в −1 от (b с волной)).
И это есть условие на b с волной в
зависимости от v, как функция от v, то есть при
каждом v b с волной должно быть выбрано так, чтобы максимизировать это выражение,
то есть так, чтобы удовлетворять вот этому вот уравнению.
А теперь внимание!
Теперь самый главный момент, ключевой момент.
Если b
— равновесие, симметричное равновесие в нашем аукционе,
то есть равновесная стратегия поведения, стратегия ставок,
то для любого v
решением этого
уравнения должно
служить в точности b
с волной = b (v).
То есть вот у нас есть условие, по нему можно вывести b с волной как функцию от V.
Но если мы ищем равновесие, предположим, что b — действительно, равновесная функция
поведения, тогда ответная функция поведения — тоже b, а значит,
b с волной при любом v должен быть вот таким, то есть вот такая вот функция.
Мы должны теперь подставить сюда,
и вместо равенства написать равенство из трёх чёрточек, как функций.
Получается следующее уравнение,
получим v − b(v) — это я заменил b с волной на b(v),
≡ по v равно
b в −1(b(v))
* (b'(b в −1(b(v))),
закрываю три скобки.
[БЕЗ СЛОВ] Вот это и есть уравнение, полученное на функцию.
Функция реакции, оптимальная функция должна удовлетворять вот этому уравнению,
то есть оптимальная функция ставок в зависимости от v,
но здесь очень много сокращается, правда?
Потому что обратная функция берётся от прямой, поэтому получается уравнение
такое, уравнение на функцию получается дифференциальным.
Оно выглядит так: v − b(v) =
v * b'(v), здесь всё сокращается.
Значит, мы ищем функцию,
которая удовлетворяет такому уравнению функцию, стартующую из 0.
Перепишем это здесь, получим v,
это вот перебросим направо, должно быть ≡
b(v) + v * b'(v).
Замечательно.
Я думаю, что прилежные слушатели уже угадали здесь полные производные
от следующих двух функций: d по dv от v² / 2
≡ d по dv от выражения (v * b(v)) просто.
Но тогда,
как все знают из уроков математического анализа,
функция v² / 2 должна быть равна Const + v * b(v).
В силу наложенного условия, что b стартует из 0, на самом деле, это можно доказать,
константа должна быть равна 0, поэтому я её убираю и пишу вот так.
Это функциональное равенство, поэтому его можно сократить и получить.
Ответ: равновесное поведение в аукционе первой цены в случае равномерных,
равномерно распределённых ценностей — это v/2,
назвать — половина своей собственной ценности.
Если картина стоит для вас 3000 рублей, говорите — полторы,
если 100 рублей, говорите — 50 и т.д.
Это один из тоже знаменитых результатов,
но всё-таки Нобелевскую премию за него не дали.
Что можно сказать в связи с этим результатом?
Можно сказать следующее.
Во-первых, если игроков много и все
они априори обладают независимыми
реализациями ценностей из одного и того же распределения,
но необязательно равномерного, то тоже можно выписать универсальную формулу,
в которой будут интегралы.
То есть задача, как говорят, решается в квадратурах, задача — аукцион первой цены
с одинаковыми покупателями — решается в квадратурах — первое.
Второе: если аккуратно взять
все требуемые интегралы и посчитать средний выигрыш человека,
продающего картину нерпы или любой другой объект с использованием правила
аукциона первой цены и правила аукциона второй цены, то результаты совпадут.
Это неслучайно.
В 1981 году Роджер Майерсон доказал,
что если аукцион обладает некоторыми тремя,
то есть, если аукцион устроен, вот правила проведения аукциона совершенно произвольны
и только обладают некоторыми тремя необходимыми свойствами такими,
как человек, у которого оценка 0, ничего не платит, это понятно,
собственно говоря, странно было бы с него что-то брать, хотя всякое бывает по жизни,
бывают аукционы с входной платой какой-то, которые уже не удовлетворяют
этому условию, то есть 1) чтобы человек с нулевой оценкой, у которого реализовалась
нулевая оценка, ничего не платит, его нельзя заставить что-то заплатить.
2) предмет
всегда отходит тому, у кого максимальная оценка.
То есть правила устроены таким образом, что в равновесии всегда реализуется то,
что предмет уходит тому, у кого самая большая оценка.
И третье условие состоит в том,
что найдено именно симметричное равновесие в игре.
Тогда независимо от правил проведения аукционов в
этом симметричном равновесии средний выигрыш продавца будет такой же,
как в аукционе первой и в аукционе второй цены.
Это было названо revenue equivalence
theorem, то есть «теорема об эквивалентности дохода» во всех
аукционах при любых правилах при некоторых небольших ограничениях.
И за это тоже была дана Нобелевская премия, это Нобелевская премия 2007 года.
На самом деле, то,
что сейчас было некоторое приглашение в теорию аукционов,
там очень много интересного, это совершенно отдельная область теории игр,
которой я рекомендую заниматься, это область, может быть,
даже я бы сказал так: это наиболее практически значимая область теории игр.
