Правдивая резка торта - Truthful cake-cutting

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

Классический разделяй и выбирай Процедура разрезания торта не соответствует действительности: если резчик знает предпочтения выбирающего, он может получить гораздо больше, чем 1/2, действуя стратегически. Например, предположим, что резак оценивает кусок по его размеру, а выборщик оценивает кусок по количеству шоколада в нем. Таким образом, резак может разрезать торт на две части с почти одинаковым количеством шоколада, чтобы в меньшем кусочке было немного больше шоколада. Затем выборщик возьмет меньший кусок, а резак получит больший кусок, который может стоить намного больше, чем 1/2 (в зависимости от того, как распределен шоколад).

Рандомизированные механизмы

Существует тривиальный рандомизированный правдивый механизм для ярмарка разрезания торта: выберите одного агента наугад и отдайте ему / ей весь торт. Этот механизм тривиально правдив, потому что не задает вопросов. Более того, ожидание справедливо: ожидаемая стоимость каждого партнера составляет ровно 1 /п. Однако такое распределение несправедливо. Задача состоит в том, чтобы разработать правдивые механизмы, справедливые постфактум, а не только заранее. Было разработано несколько таких механизмов.

Механизм точного деления

An точное деление (он же разделение консенсуса) представляет собой разбиение торта на п штук так, что каждый агент оценивает каждую часть точно в 1 /п. Существование такого разделения следствие из теоремы Дубинса – Спаниера о выпуклости. Более того, существует такое деление с не более чем порезы; это следствие Теорема Стромквиста – Вудалла и теорема о расщеплении ожерелья.

В общем, точное деление не может быть найдено с помощью конечного алгоритма. Однако его можно найти в некоторых частных случаях, например, когда все агенты имеют кусочно-линейные оценки. Предположим, у нас есть неправдивый алгоритм (или оракул) для нахождения точного деления. Его можно использовать для построения рандомизированный механизм, правдивый в ожидании.[1][2] Рандомизированный механизм - это механизм прямого раскрытия - он начинается с того, что всех агентов просят раскрыть все свои ценности:

  1. Попросите агентов сообщить о своих оценках стоимости.
  2. Используйте существующий алгоритм / оракул, чтобы произвести точное деление.
  3. Произведите случайную перестановку на консенсусном разделе и дайте каждому партнеру одну из частей.

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

Сверхпропорциональный механизм

А сверхпропорциональное деление торт-деление, в котором каждый агент получает строго больше 1 /п по их собственным оценкам. Известно, что такое разделение существует тогда и только тогда, когда есть по крайней мере два агента, которые имеют разные оценки по крайней мере по одному куску пирога. Любые детерминированный Механизм, который всегда возвращает пропорциональное деление и всегда возвращает сверхпропорциональное деление, когда он существует, не может быть правдивым.

Моссель и Тамуз представить суперпропорциональный рандомизированный механизм, правдивый в ожидании:[1]

  1. Выберите подразделение из определенного распределения D над подразделениями.
  2. Попросите каждого агента оценить его / ее работу.
  3. Я упал п оценок больше 1 /п, затем выполните выделение и закончите.
  4. В противном случае используйте механизм точного разделения.

Распространение D на шаге 1 следует выбирать так, чтобы независимо от оценок агентов существовала положительная вероятность того, что будет выбрано сверхпропорциональное деление, если оно существует. Затем на шаге 2 для каждого агента оптимально сообщать истинное значение: сообщение о более низком значении либо не имеет эффекта, либо может привести к падению значения агента с суперпропорционального до просто пропорционального (на шаге 4); сообщение о более высоком значении либо не имеет эффекта, либо может привести к падению значения агента с пропорционального до менее 1 /п (на шаге 3).

Примерное точное деление с помощью запросов

Предположим, что вместо того, чтобы прямо раскрывать свои оценки, агенты раскрывают свои ценности косвенно, отвечая отметка и оценка запросы (как в модели Робертсона-Уэбба).

Бранзей и Мильтерсен[3] показывают, что механизм точного деления может быть «дискретизирован» и выполнен в модели запроса. Это дает для любого , а рандомизированный протокол на основе запросов, который запрашивает не более запросов, правдив в ожидании и выделяет каждому агенту часть ценности между и , по оценкам всех агентов.

С другой стороны, они доказывают, что в любом детерминированный Правдивый протокол, основанный на запросах: если все агенты положительно оценивают все части торта, есть по крайней мере один агент, который получает пустой кусок. Это означает, что если агентов только два, то по крайней мере один агент является «диктатором» и получает весь торт. Очевидно, что ни один такой механизм не может быть беззаветным.

Рандомизированный механизм кусочно-постоянных оценок

Предположим, что у всех агентов есть кусочно-постоянные оценки. Это означает, что для каждого агента торт делится на конечное число подмножеств, и плотность ценности агента в каждом подмножестве постоянна. В этом случае Азиз и Е представить рандомизированный алгоритм, который является более экономически эффективным: Ограниченная серийная диктатура истинен в ожидании, надежен и пропорционален и удовлетворяет свойству, называемому единодушие: если наиболее предпочтительный для каждого агента 1 /п длина торта не пересекается с другими агентами, тогда каждый агент получает свой наиболее предпочтительный 1 /п длина торта. Это слабая форма эффективности, которой не удовлетворяют механизмы, основанные на точном разделении. Когда есть только два агента, это также полиномиальное время и надежность без зависти.[4]

Детерминированные механизмы: кусочно-постоянные оценки

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

Курокава, Лай и Прокачча доказать, что не существует детерминированного, правдивого и свободного от зависти механизма, который требует ограниченного числа запросов Робертсона-Уэбба.[5]

Азиз и Е доказать, что не существует детерминированного истинного механизма, который удовлетворяет одному из следующих свойств:[4]

  • Пропорциональный и Парето-оптимальный;
  • Надежно-пропорциональный и не расточительный («не расточительный» означает, что никакая часть не выделяется агенту, который не хочет этого; это слабее, чем оптимальность по Парето).

Менон и Ларсон ввести понятие ε-правдивость, что означает, что ни один агент не получает больше, чем часть ε из-за неправильной отчетности, где ε - положительная постоянная, не зависящая от оценок агентов. Они доказывают, что никакой детерминированный механизм не удовлетворяет ни одному из следующих свойств:[6]

  • ε-правдивый, приблизительно пропорциональный и не расточительный (для констант аппроксимации не более 1 /п);
  • Правдивые, приблизительно пропорциональные и связанные (для константы приближения не более 1 /п).

Они представляют собой незначительную модификацию Протокол Even – Paz и докажи, что это ε- правдивый с ε = 1 - 3/(2п) когда п четный, и ε = 1 - 3/(2п) + 1/п2 когда п странно.

Бэй, Чен, Хучжан, Тао и У доказать, что не существует детерминированного, правдивого и свободного от зависти механизма даже в модели прямого откровения, который удовлетворял бы одному из следующих дополнительных свойств:[7]

  • Связанные кусочки;
  • Не расточительно;
  • Позиция без внимания - распределение части торта основывается только на оценке этой части агентами, а не на ее относительном положении на торте.

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

С положительной стороны, в реплицируемой экономике, где реплицируется каждый агент. k время от времени существуют свободные от зависти механизмы, в которых правдивость равновесие по Нэшу:[7]

  • С требованием подключения в любом свободном от зависти механизме правдивость сводится к равновесию по Нэшу, когда k приближается к бесконечности;
  • Без требования связности в механизме, который распределяет каждый однородный подинтервал поровну между всеми агентами, установление истины является равновесием Нэша уже тогда, когда k ≥ 2.

Кусочно-равномерные оценки

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

Чен, Лай, Паркс и Прокачча представить механизм прямого откровения, который детерминированный, пропорциональный, без зависти, Парето-оптимальный, и полиномиальное время.[2] Работает для любого количества агентов. Вот иллюстрация механизма CLPP для двух агентов (где торт - это интервал).

  1. Попросите каждого агента сообщить свои желаемые интервалы.
  2. Каждый подинтервал, который не требуется ни одному агенту, отбрасывается.
  3. Каждый подинтервал, который требуется ровно одному агенту, назначается этому агенту.
  4. Подинтервалы, которые требуются обоим агентам, распределяются таким образом, чтобы оба агента получали одинаковую сумму. длина.

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

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

Заметка: Азиз и Е[4] представили два механизма, которые расширяют механизм CLPP до кусочно-постоянных оценок - алгоритм ограниченного употребления пирожных и алгоритм рыночного равновесия. Однако оба этих расширения перестают быть истинными, если оценки не кусочно-однородны.

Майя и Нисан показывают, что механизм CLPP уникален в следующем смысле.[8] Рассмотрим частный случай два агентов с кусочно-равномерными оценками, где торт [0,1], Алисе нужен только подынтервал [0,а] для некоторых а<1, и Бобу нужен только подынтервал [1-б, 1] для некоторых б<1. Считайте только не расточительный механизмы - механизмы, которые распределяют каждую деталь, желаемую хотя бы одним игроком, игроку, которому она нужна. Каждый такой механизм должен давать Алисе подмножество [0,c] для некоторых c<1, а Боб - подмножество [1-d, 1] для некоторых d<1. В этой модели:

  • Безотходный детерминистический механизм правдив тогда и только тогда, когда для некоторого параметра т в [0,1] он дает Алисе интервал [0, min (а, макс (1-б,т))] и Боб интервал [1-min (б, макс (1-а,1-т)),1]
  • Такому механизму не позавидуешь iff т= 1/2; в этом случае он эквивалентен механизму CLPP

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

Ли, Чжан и Чжан показать, что механизм CLPP работает хорошо, даже если есть внешние эффекты (т. е. некоторые агенты получают некоторую выгоду из ценности, данной другим), пока внешние эффекты достаточно малы. С другой стороны, если внешние эффекты (положительные или отрицательные) велики, не существует правдивого, не расточительного и независимого от позиции механизма.[9]

Алиджани, Фархади, Годси, Седдигин и Таджик представим несколько механизмов для частных случаев кусочно-равномерных оценок:[10]

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

Бэй, Хучжан и Суксомпонг представляют механизм для двух агентов с кусочно-равномерными оценками, который имеет те же свойства CLPP (истинный, детерминированный, пропорциональный, свободный от зависти, оптимален по Парето и работает за полиномиальное время), но гарантирует, что весь торт выделяется:[11]

  1. Найдите самый маленький Икс в [0,1] такая, что желаемая длина Алисы в [0,Икс] равняется желаемой длине Боба в [Икс,1].
  2. Дайте Алисе интервалы в [0,Икс], оцененные Алисой, и интервалы в [Икс,1] не оценен Бобом; оставшуюся часть отдайте Бобу.

Механизм BHS работает как для нарезки торта, так и для деление по дому (где оценки агентов отрицательные). Обратите внимание, что BHS не удовлетворяет некоторым естественным желаемым свойствам:

  • Это не гарантирует соединенные части, например, когда Алиса хочет [0,1], а Боб хочет [0,0.5], тогда Икс= 0,25, Алиса получает [0,0,25] и [0,5,1], а Боб - [0,25,0,5].
  • Это не так анонимный (увидеть симметричная резка торта ): если Алиса хочет [0,1], а Боб хочет [0,0,5], то Алиса получает желаемую длину 0,75, а Боб - 0,25, но если оценки поменялись местами (Алиса хочет [0,0,5], а Боб хочет [0 , 1]), то Икс= 0,5, и оба агента получат желаемую длину 0,5.
  • Это не так позиция не обращая внимания: если Алиса хочет [0,0.5], а Боб хочет [0,1], то оба агента получают значение 0,5, но если желаемый интервал Алисы переместится на [0,5,1], тогда Икс= 0,75, и Алиса получает 0,25, а Боб - 0,75.

Это не проблема конкретного механизма: доказуемо невозможно иметь правдивый и свободный от зависти механизм, который распределяет весь торт и гарантирует любое из этих трех свойств, даже для двух агентов с кусочно-однородными оценками.[11]

Механизм BHS был распространен на любое количество агентов, но только для частного случая кусочно-однородных оценок, в котором каждому агенту нужен только один интервал вида [0, Икся].

Яновский[12] доказывает, что никакой правдивый механизм не может утилитарно-оптимальная резка торта, даже когда все агенты имеют кусочно-равномерные оценки. Более того, никакой правдивый механизм не может обеспечить распределение с утилитарным благосостоянием, по крайней мере, таким же большим, как любой другой механизм. Однако существует простой правдивый механизм (обозначенный Lex Order), который не расточительный: отдайте агенту 1 все, что ему нравится; затем передайте агенту 2 все части, которые ему нравятся и которые еще не были переданы агенту 1; и т. д. Вариантом этого механизма является игра на длину, в которой агенты переименовываются по общей длине их желаемых интервалов, так что агент с наименьшим интервалом называется 1, агент со следующим наименьшим интервалом называется 2 и т. д. Однако это неверный механизм:

  • Если все агенты правдивы, это дает утилитарно оптимальное распределение.
  • Если агенты являются стратегическими, то все его хорошо развитые равновесия по Нэшу эффективны по Парето и свободны от зависти и дают те же выгоды, что и механизм CLPP.



Резюме правдивых механизмов и результатов невозможности

имяТипДетерминированный?# агенты (п)Оценки[13]Работы?[14]Время выполненияВсе?[15]ПО?[16]EF?[17]Аноним?[18]Конн?[19]Поз. Об.?[20]Нет отходов?[21]
Точное деление[1][2]непосредственныйНетМногоОбщеедаНеограниченный[22]даНетдадаНет??
Сверхпропорциональный[1]непосредственныйНетМногоОбщеедаНеограниченныйдаНетНетдаНет??
Дискретное точное деление[3]ЗапросыНетМногоОбщеедадаНет-EFдаНет??
Ограниченная серийная диктатура[4]непосредственныйНетМногоPWC??НетЕдинодушиеРеквизит.?Нет??
CLPP[2]непосредственныйдаМногоPWUНетПолиномиальныйНетдададаНет?да
BHS 1, 2непосредственныйда2PWUдаПолиномиальныйдададаНетНетНетда
BHS 3, 4непосредственныйдаМногоPWU1даПолиномиальныйдадада (для тортов)???да
Расширение[10]непосредственныйдаМногоPWU1 + заказать?Полиномиальный??да?да??
Расширение + РазблокировканепосредственныйдаМногоPWU1?Полиномиальный??да?2п-2 разреза??
НЕВОЗМОЖНЫЕ КОМБИНАЦИИ:
[BM][3]Запросыда2+Любые
[BHS][11]непосредственныйда2+PWUдадада
[BHS]непосредственныйда2+PWUдадада
[BHS]непосредственныйда2+PWUдадада
[BCHTW][7]непосредственныйда2+PWCдада
[BCHTW]непосредственныйда2+PWCдада
[BCHTW]непосредственныйда2+PWCдада
[BCHTW]Последовательныйда2+PWCда


Смотрите также

использованная литература

  1. ^ а б c d Моссель, Эльханан; Тамуз, Омер (2010). «Правдивая честная дивизия». Алгоритмическая теория игр. Конспект лекций по информатике. Springer Berlin Heidelberg. 6386: 288–299. arXiv:1003.5480. Bibcode:2010LNCS.6386..288M. Дои:10.1007/978-3-642-16170-4_25. ISBN  9783642161704.
  2. ^ а б c d Чен, Илин; Лай, Джон К .; Паркс, Дэвид С .; Прокачча, Ариэль Д. (01.01.2013). «Правда, справедливость и разрезание торта». Игры и экономическое поведение. 77 (1): 284–297. Дои:10.1016 / j.geb.2012.10.009. ISSN  0899-8256.
  3. ^ а б c Brânzei, Simina; Милтерсен, Питер Бро (2015-06-22). "Теорема диктатуры для разрезания торта". Двадцать четвертая международная совместная конференция по искусственному интеллекту.
  4. ^ а б c d Азиз, Харис; Е, Чун (2014). Лю, Те-Янь; Ци, Ци; Е Инью (ред.). «Алгоритмы вырезания торта для кусочно-постоянных и кусочно-однородных оценок». Интернет и Интернет-экономика. Конспект лекций по информатике. Издательство Springer International. 8877: 1–14. Дои:10.1007/978-3-319-13129-0_1. ISBN  9783319131290.
  5. ^ Курокава, Дэвид; Лай, Джон К .; Прокачча, Ариэль Д. (30.06.2013). «Как разрезать торт до окончания вечеринки». Двадцать седьмая конференция AAAI по искусственному интеллекту.
  6. ^ Менон, Виджай; Ларсон, Кейт (17 мая 2017 г.). «Детерминированный, устойчивый к стратегии и честный разрезание торта». arXiv:1705.06306 [cs.GT ].
  7. ^ а б c Бэй, Сяохуэй; Чен, Нин; Хучжан, Гуанда; Тао, Бяошуай; У, Цзяцзюнь (2017). «Резка торта: зависть и правда». Материалы 26-й Международной совместной конференции по искусственному интеллекту. IJCAI'17. AAAI Press: 3625–3631. ISBN  9780999241103.
  8. ^ Майя, Авишай; Нисан, Ноам (2012). Голдберг, Пол В. (ред.). «Совместимость по стимулированию резки торта для двух игроков». Интернет и сетевая экономика. Конспект лекций по информатике. Springer Berlin Heidelberg. 7695: 170–183. arXiv:1210.0155. Bibcode:2012arXiv1210.0155M. Дои:10.1007/978-3-642-35311-6_13. ISBN  9783642353116.
  9. ^ Ли, Минмин; Чжан, Цзялинь; Чжан, Цян (2015-06-22). "Правдивые механизмы для резки торта с внешними факторами: не заставляйте их слишком заботиться о других!". Двадцать четвертая международная совместная конференция по искусственному интеллекту.
  10. ^ а б Алиджани, Реза; Фархади, Маджид; Годси, Мохаммад; Седдигин, Масуд; Таджик, Ахмад С. (2017-02-10). «Механизмы без зависти с минимальным количеством разрезов». Тридцать первая конференция AAAI по искусственному интеллекту.
  11. ^ а б c Бэй, Сяохуэй; Хучжан, Гуанда; Суксомпонг, Варут (18.04.2018). «Правдивый справедливый раздел без свободного распоряжения». arXiv:1804.06923 [cs.GT ].
  12. ^ Яновский, Егор (2012-03-01). «Механизмы нарезки торта». arXiv:1203.0100 [cs.GT ].
  13. ^ PWC = кусочно-постоянная, PWU = кусочно-однородная, PWU1 = кусочно-однородная с одним желаемым интервалом.
  14. ^ Может ли алгоритм обрабатывать также торты с отрицательными утилитами.
  15. ^ Делится ли весь торт, без удаления.
  16. ^ Всегда ли результирующее распределение Оптимальный по Парето.
  17. ^ Всегда ли результирующее распределение без зависти.
  18. ^ Является ли механизм анонимный.
  19. ^ Всегда ли соединены получившиеся кусочки.
  20. ^ Является ли механизм позиция не обращая внимания.
  21. ^ Гарантирует ли алгоритм не расточительность.
  22. ^ Во время выполнения преобладает расчет точное деление. Обычно он неограничен, но в особых случаях может быть полиномиальным.