VCG and GSP auctions

[Neytrall]

Здравствуйте.
Мне нужна ваша помощь, что бы понять как решить 2 задачи.

Задача 1. На аукционе выставлено два лота $a$ и $b$.
Есть два игрока со следующими предпочтениями:
Первый игрок: $v_1(ab)=201, v_1(a)=1 , v_1(b)=3$
Второй игрок: $v_2(ab)=202, v_2(a)=200 , v_2(b)=200$
а) Просят найти оптимальное распределение лотов между игроками.
б) Найти распределение лотов между игроками по правилам VCG аукциона и определить выплаты игроков.

Если к аукциону присоединяется ещё один игрок с такими же предпочтениями как и у второго:
$v_3(ab)=202, v_3(a)=200 , v_3(b)=200$
Найти распределение лотов между игроками по правилам VCG аукциона и определить выплаты игроков.

Задача 2.
Проводят GSP аукцион на котором продают рекламные места на сайте.
Есть всего два места.
Вероятность клика по ссылке на первом месте $0.14$.
Вероятность клика по ссылке на втором месте $0.08$.
Участвуют 3 игрока:
Первый игрок готов заплатить $18$$ за клик.
Второй игрок готов заплатить $13$$ за клик.
Третий игрок готов заплатить $9$$ за клик.
Просят найти равновесие в аукционе.

[Neytrall]

Я понимаю, что первая задача показывает слабые места VCG механизма, а вторая показывает, что GSP это не часный случай VCG. Но проблема в том, что нам на курсе не показывали слабые места VCG и не рассказывали как найти равновесие в GSP.

-- Сб янв 15, 2011 22:10:06 --

Похоже в этой теме сижу только я, а остальные просто прохожие.
Ну да ладно. Вроде бы я смог разобраться и решить вторую задачу. Вот решение:
Если первый игрок решит взять первый слот, то его выгода будет равна:
$U=0.14(18-13)=0.7$
Но если он возьмёт второй слот,то $U=0.08(18-9)=0.72$.
Поэтому ему выгодно взять именно второй. Но для этого нужно, что бы второй игрок согласился взять первый слот. Выгода второго игрока от второго слота: $U=0.08(13-9)=0.32$
Поэтому первый игрок должен назначить ставку, при которой оба слота для второго игрока будут равноценны.
То есть, если $X$ это ставка первого игрока то:
$0.14(13-X)=0.32$
$X=\frac{75}{7}$

Выходит, что в состояние равновесия первый игрок получит второй слот и заплатит $9$, второй получит первый слот и заплатит $X=\frac{75}{7}$, а третий в пролёте. Так?

[Shtirlic]

Рассуждения близки, но в начале была сделана ошибка. Сразу ясно, что третий игрок в пролете, т.к. ниже его цены ставить не выгодно ни первому ни второму. Следовательно минимальная цена 9. У каждого из игроков 2 варианта: либо взять сразу второе место, либо бороться за первое. Я модифицирую предложенную вами функцию полезности, разделю ее на 0,08. Тогда $U_{12}=18-9=9$ - максимальная полезность первого игрока, если он возьмет второй слот, аналогично для второго $U_{22}=13-9=4$. А при какой цене игрок 1 получит такую же полезность если возьмет 1 место? $U_{11}=1,75(18-X)=9\rightarrow X=12,857$, аналогично для второго $U_{21}=1,75(13-X)=4\rightarrow Y=\frac{75}{7}=10,714$, при меньших ценах оба игрока будут получать большую полезность от первого места. Отсюда вывод. Первый игрок покупает лот 1 по цене $\frac{75}{7}$, а второй игрок 2-е по цене 9. Третий в пролете.И нужно понимать что заявленные цены должны быть на малую величину больше, чтобы не было ситуации ничьей (но это так присказка).
Но сразу предупреждая, я не совсем в курсе, что такое GSP аукцион.

[Neytrall]

GSP аукцион изобрёл Google, сказав что это обобщённый аукцион VCG, но как вы видите он ошибся, так как GSP не всегда имеет рановесие при "честной" стратегии. Это аукцион в котором игрок платит цену установленную следующим игроком (second price auction).
Спасибо вам, я совсем забыл, что нужно ещё и для первого игрока проверить равноценность.
Но меня смущает, что равновесие это одна точка. Ведь по идее оно должно быть отрезком (хотя бы для одного из игроков).

-- Пн янв 17, 2011 12:22:17 --

Кстати, вот моё решение первой задачи:
а)Оптимальное распределение лотов: первый игрок получает $b$, а второй $a$.
б)VCG: первый игрок получает $b$ и платит 1$.
Второй $a$ и платит 198$.

После прихода ещё одного игрока:
VCG: Первый игрок в пролёте. Второй и третий делят между собой $a$ и $b$, не важно как. Допустим, что $a$ достаётся второму игроку, а $b$ третьему. Каждый платит по 2$.

Из этого примера можно увидить, что аукцион не revenue-monotone, так как увеличение числв игроков не увеличило прибыль продавца, а наоборот сильно сократило.

От сюда следует, что если третий игрок это "подсадная утка" второго игрока, то в этом случае второй игрок заберёт оба лота, заплатив всего 4$.
В то время как в первом случае он получал всего один лот за 198$.

-- Пн янв 17, 2011 12:25:14 --

Shtirlic
А каковы будут ставки игроков?

[Shtirlic]

Neytrall
Я вообще эти темы не знаю. Во второй задаче я нашел просто равновесие по Нэшу, а это обычно точка (по определение, стратегии игроков, когда каждому не выгодно отклоняться от своей, если второй оставит свою стратегию без изменений) предположив, что 1 рубль одинаково полезен всем игрокам.

Расскажите, что такое VCG аукционы, что понимается под оптимальном распределением и что такое $u(ab),u(a),u(b)$, полагаю какие-то полезности, но как они связанны с деньгами?

[Neytrall]

Shtirlic
$v_1(ab), v_1(a) , v_1(b)$- это ставки игроков. Например, только за $a$ первый игрок готов поставить 1, только за $b$ это максимум 3, но если ему предложат оба лота, то он готов заплатить 201.

VCG auction - Механизм Викри-Кларка-Гровса

Обобщение аукциона Викри, сохраняющее стимулы к правдивому назначению ставок, известно как механизм Викри-Кларка-Гровса (Vickrey-Clarke-Groves, VCG). Идея VCG состоит в том, что каждый участник аукциона платит цену исходя из того, как его участие воздействует на всех остальных участников.

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

* Участник A желает одно яблоко и делает ставку $5.
* Участник B также хочет одно яблоко и готов заплатить $2.
* Участник C претендует на два яблока и намерен заплатить $6 за оба, но не желает приобретать одно яблоко без другого.

Во-первых, мы определяем победителей путем максимизации ставок: яблоки отходят к участникам A и B (поскольку проиграв одно яблоко участнику A, С не претендует на второе). Во-вторых, чтобы определить платежи, мы рассматриваем что произойдет, если бы победитель не участвовал в аукционе.

* Платеж победителя A: B получает яблоко, сделав ставку $2. Если бы участника A не было, C выиграл бы оба яблока и заплатил бы за них $6. Так что A платит разницу между ценой C за оба яблока и ценой B за одно из них: $6-$2 = $4.
* Платеж победителя B: A получает яблоко, сделав ставку $5, а C не получает ничего. Не будь B, C получил бы оба яблока за $6 (поскольку $6 за два яблока превышает ставку A $5 в отсутствие других участников). Поэтому B платит разницу $6-$5 = $1.

[Shtirlic]

Neytrall в сообщении #401079 писал(а):

* Платеж победителя A: B получает яблоко, сделав ставку $2. Если бы участника A не было, C выиграл бы оба яблока и заплатил бы за них $6. Так что A платит разницу между ценой C за оба яблока и ценой B за одно из них: $6-$2 = $4.
* Платеж победителя B: A получает яблоко, сделав ставку $5, а C не получает ничего. Не будь B, C получил бы оба яблока за $6 (поскольку $6 за два яблока превышает ставку A $5 в отсутствие других участников). Поэтому B платит разницу $6-$5 = $1.

Не знаю определения платежей, но мне кажется что тут просто имеется ввиду определить кто-сколько заплатит. (например для второго игрока 198). А этот текст я так и не понял.
Пока буду исходить из своего предположения.
Я так понимаю каждый делает ставки, потом они вскрываются и лоты распределяются исходя из максимума, и по VCG каждый определяет свой максимальный гарантированный выигрышь. Тогда:
а) все тут понятно, я согласен.
б) со вторым игроком (198) согласен, а вот первый за b предложит 2 (иначе второй заберет все по ставке $u(ab)=202$)
появился третий игрок) При вашем раскладе, первый заберет все по ставке $u(ab)=201$. Ставки у 2 и 3 игроков понятно будут одинаковые, $u(a)+u(b)=201$, $u(a)=198,u(b)=3$, первый в пролете, аукционер получает те же 201.
И опять же ставки не 198 и 3, а чуть больше, чтобы не было ничьей.

[Neytrall]

Shtirlic в сообщении #401132 писал(а):

б) со вторым игроком (198) согласен, а вот первый за b предложит 2 (иначе второй заберет все по ставке $u(ab)=202$)

да, вы правы.

Но когда приходит третий, то:
если он находится то он и второй забирают оба лота. И он платит "ущерб" присутствия, который равен 2. Со вторым получается то же самое. Так что каждый заплатит по 2.

[Shtirlic]

Neytrall в сообщении #401141 писал(а):

Но когда приходит третий, то:
если он находится то он и второй забирают оба лота. И он платит "ущерб" присутствия, который равен 2. Со вторым получается то же самое. Так что каждый заплатит по 2.

Я вас не пойму, оба заберут оба лота за 4? Но у первого ставка $u(ab)=201$, по идеи он должен выиграть.

[Neytrall]

первый проиграет бой за $a$ и поэтому он не будет готов заплатить за $a+b$.

-- Пн янв 17, 2011 16:26:08 --

201 это не ставка, а то сколько он максимум готов заплатить.

[Shtirlic]

Neytrall в сообщении #401154 писал(а):

201 это не ставка, а то сколько он максимум готов заплатить.

Тогда объясните мне как проходит аукцион, начиная от того как делаются (на какие лоты, комбинации) ставки и заканчивая розыгрышем, видать я что-то не понял.
И в любом случае первый за лот b предлагает 3, что больше двух.

[Neytrall]

впринципе это аукцион Викри, но VCG механизм помогает определить, кто сколько заплатит.
Игрок платит величину ущерба от своего присутствия, то есть
его плата=
Optimal welfare (for the other players) if player i was not participating минус Welfare of the other players from the chosen outcome.

Полное объяснение в сообщение выше.

-- Пн янв 17, 2011 16:52:56 --

вот здесь нормальное объяснение
http://en.wikipedia.org/wiki/Vickrey%E2 ... es_auction

[Neytrall]

Shtirlic
Я сверился со знакомыми, и у них такие же ответы, как и у меня.
Ответьте мне, пожалуйста, на один вопрос по второй задаче.
Какие ставки будут у игроков?
Первый игрок поставит $b_1=12.857$
Второй $b_2=10.714$
Третий $b_3=9$
Так?

[Shtirlic]

Первый - 10,714 на лот 1;
Второй - чуть более 9 на лот 2;
Третий - 9, в пролете;