Монотонность ресурса

Монотонность ресурсов ( RM ; также известная как совокупная монотонность ) — это принцип справедливого деления . Он говорит, что если есть больше ресурсов, которыми можно поделиться, то благосостояние всех агентов должно быть немного лучше; ни один агент не должен проиграть от увеличения ресурсов. Принцип RM изучался в различных задачах деления. ^[1]^: 46–51^[2]

Распределение делимых ресурсов

Единый однородный ресурс, общие коммунальные услуги

Предположим, что общество имеет $m$ единицы некоторого однородного делимого ресурса, например воды или муки. Ресурс следует разделить между $n$ агенты с различными утилитами. Полезность агента $i$ представлена функцией $u_{i}$ ; когда агент $i$ получает $y_{i}$ единиц ресурса, он извлекает из него полезность в размере $u_{i}(y_{i})$ . Общество должно решить, как разделить ресурс между агентами, т. е. найти вектор $y_{1},\dots ,y_{n}$ такой, что: $y_{1}+\cdots +y_{n}=m$ .

Двумя классическими правилами распределения являются эгалитарное правило , стремящееся уравнять полезности всех агентов (что эквивалентно: максимизировать минимальную полезность), и утилитарное правило , стремящееся максимизировать сумму полезностей.

Эгалитарное правило всегда RM: ^[1]^: 47 когда появляется больше ресурсов, которыми можно поделиться, минимальная полезность, которая может быть гарантирована всем агентам, увеличивается, и все агенты поровну делят этот прирост. Напротив, утилитарное правило может быть не РМ.

Например, предположим, что есть два агента, Алиса и Боб, со следующими утилитами:

$u_{A}(y_{A})=y_{A}^{2}$
$u_{B}(y_{B})=y_{B}$

Эгалитарное распределение находится путем решения уравнения: $y_{A}^{2}=(m-y_{A})$ , что эквивалентно $m=y_{A}^{2}+y_{A}$ , так $y_{A}$ монотонно возрастает с $m$ . Эквивалентное уравнение: $y_{B}=(m-y_{B})^{2}$ , что эквивалентно $m={\sqrt {y_{B}}}+y_{B}$ , так $y_{B}$ тоже монотонно возрастает с $m$ . Итак, в этом примере (как всегда) эгалитарным правилом является RM.

Напротив, утилитарное правило — это не РМ. Это происходит потому, что Алиса имеет возрастающую отдачу : ее предельная полезность мала, когда у нее мало ресурсов, но быстро растет, когда у нее много ресурсов. Следовательно, когда общий объем ресурса невелик (в частности, $m<1$ ), утилитарная сумма максимальна, когда все ресурсы переданы Бобу; но когда ресурсов много( $m>1$ ), максимум достигается, когда все ресурсы отданы Алисе. Математически, если $y$ — сумма, данная Алисе, то утилитарная сумма равна $y^{2}+(m-y)$ . Эта функция имеет только внутреннюю точку минимума, но не внутреннюю точку максимума; его максимальная точка в диапазоне $[0,m]$ достигается в одной из конечных точек. Это левая конечная точка, когда $m<1$ и правильная конечная точка, когда $m>1$ . В общем, правилом утилитарного распределения является RM, когда все агенты имеют убывающую отдачу , но оно может и не быть RM, когда некоторые агенты имеют возрастающую отдачу (как в примере). ^[1]^: 46–47

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

Два взаимодополняющих ресурса, Леонтьевские утилиты

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

Для задач Алисы требуется 1 единица ОЗУ и 2 единицы ЦП;
Для задач Боба требуется 2 единицы оперативной памяти и 1 единица процессора.

Таким образом, служебные функции (=количество задач), обозначающие ОЗУ через r и ЦП через c, являются утилитами Леонтьева :

$u_{A}(r,c)=\min(r,c/2)$
$u_{B}(r,c)=\min(r/2,c)$

Если сервер имеет 12 ОЗУ и 12 ЦП, то как утилитарное, так и эгалитарное распределение (а также оптимальное по Нэшу распределение максимального продукта):

$r_{A}=4,c_{A}=8\implies u_{A}=4$
$r_{B}=8,c_{B}=4\implies u_{B}=4$

Теперь предположим, что станут доступны еще 12 единиц ЦП. Эгалитарное распределение не меняется, но утилитарное распределение теперь отдает все ресурсы Алисе:

$r_{A}=12,c_{A}=24\implies u_{A}=12$
$r_{B}=0,c_{B}=0\implies u_{B}=0$

поэтому Боб теряет ценность из-за увеличения ресурсов.

Оптимальное по Нэшу (максимальное произведение) распределение становится следующим:

$r_{A}=6,c_{A}=12\implies u_{A}=6$
$r_{B}=6,c_{B}=3\implies u_{B}=3$

поэтому Боб здесь тоже теряет ценность, но потеря менее серьезна. ^[1]^: 83–84

Резка торта, дополнительные утилиты

В задаче о справедливом разрезании торта классические правила распределения, такие как «разделяй и выбирай», не являются RM. Известно несколько правил РМ:

Когда части могут быть разъединены , любое правило распределения, максимизирующее вогнутую функцию благосостояния абсолютных ( не нормализованных) полезностей, является RM. В частности, оптимальное по Нэшу правило, абсолютно- лексиминовое правило и абсолютно- утилитарное правило — все они являются RM. Однако если при максимизации используются относительные полезности (полезности, деленные на общую стоимость торта), то большинство этих правил не являются RM; единственное, что остается RM, — это правило оптимальности по Нэшу. ^[3]
Когда части должны быть соединены , RM не является оптимальным по Парето правилом пропорционального деления. Правило абсолютной справедливости является слабо Парето-оптимальным и RM, но не пропорциональным. Правило относительной справедливости является слабо Парето-оптимальным и пропорциональным, но не RM. Так называемое правило крайней правой отметки , являющееся вариантом правила «разделяй и выбирай» , является пропорциональным, слабо Парето-оптимальным и RM — но оно работает только для двух агентов. Вопрос о том, существуют ли процедуры разделения, одновременно пропорциональные и RM для трех и более агентов, остается открытым. ^[4]

Однопиковые предпочтения

Ресурсно-монотонность изучалась в задачах справедливого дележа с однопиковыми предпочтениями . ^[5]^[6]

Распределение дискретных элементов

Идентичные предметы, общие коммунальные услуги

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

Например, ^[1]^: 82 предположим, есть $m$ теннисные ракетки. Алиса получает полезность 1 всякий раз, когда у нее есть ракетка, поскольку ей нравится играть у стены. Но Боб и Карл получают полезность 1 только тогда, когда у них две ракетки, поскольку им нравится играть только друг против друга или против Алисы. Следовательно, если есть только одна ракетка, правило эгалитаризма полностью отдает ее Алисе. Но если ракеток две, они делятся между агентами поровну (каждому агенту достается ракетка на 2/3 времени). Следовательно, Алиса теряет полезность, когда общее количество ракеток увеличивается. У Алисы есть стимул противостоять росту.

Различные предметы, дополнительные утилиты

В задаче справедливого распределения предметов классические процедуры распределения, такие как скорректированный победитель и граф зависти, не являются RM. Более того, даже оптимальное по Нэшу правило, которое представляет собой RM при разрезании торта, не является RM при распределении предметов. Напротив, при циклическом распределении элементов используется RM. Более того, циклический алгоритм можно адаптировать для получения последовательностей выбора , подходящих для агентов с различными правами; все эти последовательности выбора тоже являются RM. ^[7]

Идентичные предметы, дополнительные утилиты

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

Расположение объекта

Местоположение объекта – это вопрос социального выбора, заключающийся в том, где должно быть расположено определенное учреждение. Рассмотрим следующую сеть дорог, где буквы обозначают перекрестки, а цифры обозначают расстояния:

А ---6--- Б --5-- С --5-- Д ---6--- Е

Население распределено равномерно вдоль дорог. Люди хотят быть как можно ближе к объекту, поэтому их «бесполезность» (отрицательная полезность) измеряется расстоянием до объекта.

В исходной ситуации эгалитарное правило размещает объект в C, поскольку оно минимизирует максимальное расстояние до объекта, равное 11 (утилитарное правило и правила Нэша также размещают объект в C).

Теперь появился новый перекресток X и несколько новых дорог (предыдущие дороги не меняются):

Б --3-- Х --3-- Д

..........|.........

..........4.........

..........|.........

.......... С .......

Эгалитарное правило теперь размещает объект в X, поскольку оно позволяет уменьшить максимальное расстояние с 11 до 9 (утилитарные правила и правила Нэша также размещают объект в X).

Увеличение ресурсов помогло большинству людей, но снизило полезность тех, кто живет в C или рядом с ним. ^[1]^: 84–85

торг

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

«Если для каждого уровня полезности, который может потребовать игрок 1, максимально возможный уровень полезности, которого может одновременно достичь игрок 2, увеличивается, то уровень полезности, назначенный игроку 2 в соответствии с решением, также должен быть увеличен». Эта аксиома приводит к характеристике решения переговоров Калая–Смородинского .
«Пусть T и S — игры торга; если T содержит S, то для всех агентов полезность в T незначительно превышает полезность в S». Другими словами, если набор альтернатив растет, выбранное решение должно быть как минимум таким же хорошим для всех агентов, как и предыдущее решение. Эта аксиома, в дополнение к Парето-оптимальности и симметрии, а также независимости нерелевантных альтернатив , приводит к характеристике эгалитарного переговорного решения. ^[8]

См. также

Отбросьте парадокс

^[9]^[10]^[11]^[12]^[13]^[14]^[15]^[16]

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231 .
^ Томсон, Уильям (2011). Правила справедливого распределения . Справочник по социальному выбору и благосостоянию. Том. 2. С. 393–506. дои : 10.1016/s0169-7218(10)00021-3 . ISBN 9780444508942 .
^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .
^ Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсно-монотонность и популяционно-монотонность в связанном разрезании торта» . Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .
^ Томсон, Уильям (1994). «Ресурсно-монотонные решения проблемы справедливого дележа при однопиковости предпочтений». Социальный выбор и благосостояние . 11 (3). дои : 10.1007/bf00193807 . S2CID 122306487 .
^ Томсон, Уильям (1997). «Принцип замещения в экономике с однопиковыми предпочтениями» . Журнал экономической теории . 76 : 145–168. дои : 10.1006/jeth.1997.2294 .
^ Чакраборти, Митхун; Шмидт-Крепелин, Ульрике; Суксомпонг, Варут (29 апреля 2021 г.). «Последовательность выбора и монотонность в взвешенном справедливом дележе». Искусственный интеллект . 301 : 103578. arXiv : 2104.14347 . дои : 10.1016/j.artint.2021.103578 . S2CID 233443832 .
^ Калаи, Эхуд (1977). «Пропорциональные решения в переговорных ситуациях: межвременные сравнения полезности» (PDF) . Эконометрика . 45 (7): 1623–1630. дои : 10.2307/1913954 . JSTOR 1913954 .
^ Мантел, Рольф Р. (1984). «Взаимозаменяемость и влияние увеличения благосостояния на благосостояние». Журнал международной экономики . 17 (3–4): 325–334. дои : 10.1016/0022-1996(84)90027-8 .
^ Мулен, Эрве (1992). «Границы благосостояния в проблеме кооперативного производства». Игры и экономическое поведение . 4 (3): 373–401. дои : 10.1016/0899-8256(92)90045-т .
^ Полтерович, В.М.; Спивак, В.А. (1983). «Грубая заменяемость соответствий точка-множество». Журнал математической экономики . 11 (2): 117. дои : 10.1016/0304-4068(83)90032-0 .
^ Собел, Джоэл (1979). «Справедливое распределение возобновляемых ресурсов». Журнал экономической теории . 21 (2): 235–248. CiteSeerX 10.1.1.394.9698 . дои : 10.1016/0022-0531(79)90029-2 .
^ Мулен, Эрве; Томсон, Уильям (1988). «Может ли каждый получить выгоду от экономического роста?». Журнал математической экономики . 17 (4): 339. doi : 10.1016/0304-4068(88)90016-x .
^ Мулен, Эрве (1992). «Применение стоимости Шепли к справедливому разделу денег». Эконометрика . 60 (6): 1331–1349. дои : 10.2307/2951524 . JSTOR 2951524 .
^ Мулен, Х. (1990). «Справедливое разделение в совместной собственности: последние итоги и открытые проблемы». Социальный выбор и благосостояние . 7 (2): 149–170. дои : 10.1007/bf01560582 . S2CID 154300207 .
^ Мулен, Эрве (1991). «Границы благосостояния в проблеме справедливого дележа». Журнал экономической теории . 54 (2): 321–337. дои : 10.1016/0022-0531(91)90125-н .

[moulin-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж Эрве Мулен (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231 .

[thomson-2] Томсон, Уильям (2011). Правила справедливого распределения . Справочник по социальному выбору и благосостоянию. Том. 2. С. 393–506. дои : 10.1016/s0169-7218(10)00021-3 . ISBN 9780444508942 .

[3] Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2019 г.). «Монотонность и конкурентное равновесие в разрезании тортов» . Экономическая теория . 68 (2): 363–401. arXiv : 1510.05229 . дои : 10.1007/s00199-018-1128-6 . ISSN 1432-0479 . S2CID 179618 .

[4] Сегал-Халеви, Эрель; Шиклай, Балаж Р. (01 сентября 2018 г.). «Ресурсно-монотонность и популяционно-монотонность в связанном разрезании торта» . Математические социальные науки . 95 : 19–30. arXiv : 1703.08928 . doi : 10.1016/j.mathsocsci.2018.07.001 . ISSN 0165-4896 . S2CID 16282641 .

[thomson94-5] Томсон, Уильям (1994). «Ресурсно-монотонные решения проблемы справедливого дележа при однопиковости предпочтений». Социальный выбор и благосостояние . 11 (3). дои : 10.1007/bf00193807 . S2CID 122306487 .

[thomson97-6] Томсон, Уильям (1997). «Принцип замещения в экономике с однопиковыми предпочтениями» . Журнал экономической теории . 76 : 145–168. дои : 10.1006/jeth.1997.2294 .

[7] Чакраборти, Митхун; Шмидт-Крепелин, Ульрике; Суксомпонг, Варут (29 апреля 2021 г.). «Последовательность выбора и монотонность в взвешенном справедливом дележе». Искусственный интеллект . 301 : 103578. arXiv : 2104.14347 . дои : 10.1016/j.artint.2021.103578 . S2CID 233443832 .

[8] Калаи, Эхуд (1977). «Пропорциональные решения в переговорных ситуациях: межвременные сравнения полезности» (PDF) . Эконометрика . 45 (7): 1623–1630. дои : 10.2307/1913954 . JSTOR 1913954 .

[mantel84-9] Мантел, Рольф Р. (1984). «Взаимозаменяемость и влияние увеличения благосостояния на благосостояние». Журнал международной экономики . 17 (3–4): 325–334. дои : 10.1016/0022-1996(84)90027-8 .

[moulin92welfare-10] Мулен, Эрве (1992). «Границы благосостояния в проблеме кооперативного производства». Игры и экономическое поведение . 4 (3): 373–401. дои : 10.1016/0899-8256(92)90045-т .

[ps83-11] Полтерович, В.М.; Спивак, В.А. (1983). «Грубая заменяемость соответствий точка-множество». Журнал математической экономики . 11 (2): 117. дои : 10.1016/0304-4068(83)90032-0 .

[sobel79-12] Собел, Джоэл (1979). «Справедливое распределение возобновляемых ресурсов». Журнал экономической теории . 21 (2): 235–248. CiteSeerX 10.1.1.394.9698 . дои : 10.1016/0022-0531(79)90029-2 .

[mt88-13] Мулен, Эрве; Томсон, Уильям (1988). «Может ли каждый получить выгоду от экономического роста?». Журнал математической экономики . 17 (4): 339. doi : 10.1016/0304-4068(88)90016-x .

[moulin92shapley-14] Мулен, Эрве (1992). «Применение стоимости Шепли к справедливому разделу денег». Эконометрика . 60 (6): 1331–1349. дои : 10.2307/2951524 . JSTOR 2951524 .

[moulin90-15] Мулен, Х. (1990). «Справедливое разделение в совместной собственности: последние итоги и открытые проблемы». Социальный выбор и благосостояние . 7 (2): 149–170. дои : 10.1007/bf01560582 . S2CID 154300207 .

[moulin91-16] Мулен, Эрве (1991). «Границы благосостояния в проблеме справедливого дележа». Журнал экономической теории . 54 (2): 321–337. дои : 10.1016/0022-0531(91)90125-н .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]