Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Рандомизированные механизмы [ править ]

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

Механизм точного деления [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бэй, Чен, Хучжан, Тао и Ву доказывают, что не существует детерминированного, правдивого и свободного от зависти механизма, даже в модели прямого откровения, который удовлетворял бы одному из следующих дополнительных свойств: [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, a ] для некоторого a <1, а Бобу нужен только подинтервал [1] - b , 1] для некоторого b <1. Рассматривайте только не расточительные механизмы - механизмы, которые распределяют каждую деталь, желаемую хотя бы одним игроком, игроку, которому она нужна. Каждый такой механизм должен давать Алисе подмножество [0, c ] для некоторого c <1, а Бобу - подмножество [1- d , 1] для некоторого d <1. В этой модели:

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

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

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

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

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

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

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

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

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

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

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

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

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



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

ИмяТипДетерминированный?# агенты ( n )Оценки [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. ^ a b c d Моссель, Эльханан; Тамуз, Омер (2010). «Правдивая честная дивизия». Алгоритмическая теория игр . Конспект лекций по информатике. Springer Berlin Heidelberg. 6386 : 288–299. arXiv : 1003,5480 . Bibcode : 2010LNCS.6386..288M . DOI : 10.1007 / 978-3-642-16170-4_25 . ISBN 9783642161704.
  2. ^ a b c d Чен, Илин; Лай, Джон К .; Паркс, Дэвид С .; Прокачча, Ариэль Д. (01.01.2013). «Правда, справедливость и разрезание торта». Игры и экономическое поведение . 77 (1): 284–297. DOI : 10.1016 / j.geb.2012.10.009 . ISSN 0899-8256 . 
  3. ^ a b c Brânzei, Simina; Милтерсен, Питер Бро (2015-06-22). «Теорема диктатуры для разрезания торта» . Двадцать четвертая международная совместная конференция по искусственному интеллекту .
  4. ^ a b c d Азиз, Харис; Е, Чун (2014). Лю, Те-Янь; Ци, Ци; Е Инью (ред.). «Алгоритмы вырезания торта для кусочно-постоянных и кусочно-однородных оценок». Интернет и экономика Интернета . Конспект лекций по информатике. Издательство Springer International. 8877 : 1–14. DOI : 10.1007 / 978-3-319-13129-0_1 . ISBN 9783319131290.
  5. ↑ Курокава, Дэвид; Лай, Джон К .; Прокачча, Ариэль Д. (30.06.2013). «Как разрезать торт до окончания вечеринки» . Двадцать седьмая конференция AAAI по искусственному интеллекту .
  6. ^ Менон, Виджай; Ларсон, Кейт (17 мая 2017 г.). «Детерминированный, устойчивый к стратегии и честный разрезание торта» arXiv : 1705.06306 [ cs.GT ].
  7. ^ a b 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 . DOI : 10.1007 / 978-3-642-35311-6_13 . ISBN 9783642353116.
  9. ^ Ли, Минмин; Чжан, Цзялинь; Чжан, Цян (2015-06-22). "Правдивые механизмы для резки торта с внешними факторами: не заставляйте их слишком заботиться о других!" . Двадцать четвертая международная совместная конференция по искусственному интеллекту .
  10. ^ а б Алиджани, Реза; Фархади, Маджид; Годси, Мохаммад; Седдигин, Масуд; Таджик, Ахмад С. (2017-02-10). «Механизмы без зависти с минимальным количеством разрезов» . Тридцать первая конференция AAAI по искусственному интеллекту .
  11. ^ a b 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. ^ Время выполнения определяется вычислением точного деления . Обычно он неограничен, но в особых случаях может быть полиномиальным.