Обмен подарками белого слона: механизмы справедливого разделения

Популярная игра на праздничных вечеринках в Северной Америке - обмен подарками белых слонов . Вкратце (без учета вариаций) это работает следующим образом:

Есть людей и упакованных подарков. Игроки заказаны произвольно. В раунде , игрок либо$n$$n$$i^{\text{th}}$$i$

• выбирает завернутый подарок и разворачивает его как подарок
• «крадет» один из уже открытых подарков (у какого-то игрока ).$k < i$

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

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

Это подпадает под класс методов справедливого разделения, относящихся к неделимым товарам (в отличие от разрезания тортов).

Мои вопросы:

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

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

Это не полный ответ, но он неполный.

Некоторые фоны и связанные с ними освещены для тех, кто не знаком -

$1/n$

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

[2] применять критерий «максимальная справедливость». Идея состоит в том, чтобы рассмотреть функцию оценки каждого игрока по подмножествам предметов, нормализовав ее до одной на всем множестве, и найти распределение, которое максимизирует минимальную полезность любого агента. Опять же, тем не менее, они не рассматривают нашу настройку здесь со спросом на единицу. Другие изучают алгоритмы приближения для этой проблемы, но я не знаю, рассматривал ли кто-нибудь это ограничение.

-

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

Из-за этого сложно попытаться ослабить эти понятия естественным образом, если использовать этот философский подход к справедливому разделению. Может быть заманчиво определить такой критерий, как «ex-ante-зависть-свобода», в котором мы надеемся быть свободными от зависти в ожидании (что бы это ни значило). Тем не менее, я думаю, что это было бы действительно на новом треке из нынешней философии. Если бы кто-то сделал это, я думаю, что мы должны были бы вообще отказаться от понятия зависти или пропорциональности и начать думать о том, как ожидаемые максимизаторы полезности будут играть в эти игры с справедливым разделением.

$n$$\frac{1}{n}$

Чтобы обойти это, я думаю, что мы должны рассмотреть порядковые критерии вместо этого. В качестве «естественного» расслабления я предлагаю следующее:

$(\varepsilon,\delta)$$1-\varepsilon$$\delta n$

$(\varepsilon,\varepsilon)$$\varepsilon$$\varepsilon n$$\varepsilon n$

$(\varepsilon,\varepsilon)$$\varepsilon$

$(\varepsilon,\varepsilon)$

-

[1] Липтон, Маркакис, Моссель, Сабери. «О приблизительно справедливом распределении неделимых товаров». EC 2004.

[2] Безакова, Дани. «Распределение неделимых товаров». SIGECOM 2005.

[3] Ну, как и случайный серийный диктатор, но случайный серийный диктатор часто обладает хорошими теоретическими свойствами. Я также предполагаю, что каждый предмет может быть украден только один раз за раунд.

Большая часть опыта обмена подарками белого слона также контролируется случайным выбором. Популярный вариант включает в себя правило, что первый выбирает последний, но это не всегда входит в правило. Это использует несправедливое преимущество случайного выбора первым из уравнения. Другое правило требует, чтобы в игре не было прямых «перехватов». Кроме того, в большинство игр играют по правилу «три касания», которое гласит, что если его открыть, затем украсть один раз, а затем украсть дважды, то он замерзнет в результате кражи в будущем. Это правило создает еще один уровень несправедливого преимущества для тех, кто выбирает подарок, который был затронут дважды.

Наш специалист по отдыху как AlbinoPhant изучает эти игры по обмену подарками в течение всего года. Если вы хотите добавить дополнительное случайное измерение в игру, используйте лево-правую историю в игре. В качестве примера предлагается история Левши Белого Слона .

Фактическая выгода обмена подарками в рамках этой деятельности заключается в социальной активности, которую производит этот процесс - подарки обычно являются вторичными по отношению к веселью великого подшучивания. Тем не менее, все игроки уходят с некоторым уровнем подарочной награды.

$n$$G$$G$$n$$n$

$\Omega(\log n)$

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