порядок лексимин

Понятие в математике

В математике лексиминный порядок — это полный предварительный порядок конечномерных векторов. Более точный, но менее распространенный термин — лексиминный предварительный порядок . Лексиминный порядок особенно важен в теории общественного выбора и справедливого дележа . ^{[1] [2] [3]}

Определение

Вектор x = ( x ₁ , ..., x _n ) лексиминно больше вектора y = ( y ₁ , ..., y _n ), если выполняется одно из следующих условий:

• Наименьший элемент x больше наименьшего элемента y ;
• Наименьшие элементы обоих векторов равны, а второй по величине элемент x больше второго по величине элемента y ;
• ...
• Наименьшие k элементов обоих векторов равны, а наименьший ( k +1) элемент x больше наименьшего ( k +1) элемента y .

Примеры

Вектор (3,5,3) лексимин-больше, чем (4,2,4), так как наименьший элемент в первом равен 3, а во втором равен 2. Вектор (4,2,4) лексимин-больше, чем (5,3,2), так как наименьшие элементы в обоих равны 2, но второй по величине элемент в первом равен 4, а во втором равен 3.

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

Связанные отношения порядка

В лексикографическом порядке первое сравнение — между x ₁ и y ₁ , независимо от того, являются ли они наименьшими по своим векторам. Второе сравнение — между x ₂ и y ₂ , и так далее.

Например, вектор (3,5,3) лексикографически меньше , чем (4,2,4), поскольку первый элемент в первом равен 3, а во втором — 4. Аналогично, (4,2,4) лексикографически больше, чем (2,4,4).

Следующий алгоритм можно использовать для вычисления того, является ли x лексиминно больше, чем y :

• Пусть x' — вектор, содержащий те же элементы x , но в порядке возрастания;
• Пусть y' — вектор, содержащий те же элементы y, но в порядке возрастания;
• Возвращает «истина», если x ' лексикографически больше, чем y ' .

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

Приложения

В социальном выборе

В теории общественного выбора ^[4] , в частности , в справедливом разделении ^[1], порядок лексимина является одним из порядков, используемых для выбора между альтернативами. В типичной задаче общественного выбора общество должно выбирать среди нескольких альтернатив (например, нескольких способов распределения набора ресурсов). Каждая альтернатива индуцирует профиль полезности — вектор, в котором элемент i является полезностью агента i в распределении. Альтернатива называется лексимин-оптимальной, если ее профиль полезности (слабо) лексимин-больше, чем профиль полезности всех других альтернатив.

Например, предположим, что есть три альтернативы: x дает полезность 2 для Алисы и 4 для Джорджа; y дает полезность 9 для Алисы и 1 для Джорджа; и z дает полезность 1 для Алисы и 8 для Джорджа. Тогда альтернатива x является лексимин-оптимальной, поскольку ее профиль полезности равен (2,4), что лексимин-больше, чем у y (9,1) и z (1,8). Лексимин-оптимальное решение всегда является Парето-эффективным .

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

• Лексимин разрезание торта
• Распределение элементов Leximin

В многокритериальном решении

В многокритериальном анализе решений необходимо принять решение, и есть несколько критериев, на которых должно основываться решение (например: стоимость, качество, скорость и т. д.). Один из способов принятия решения — назначить каждой альтернативе вектор чисел, представляющих ее значение в каждом из критериев, и выбрать альтернативу, вектор которой является лексиминно-оптимальным. ^[5]

Лексиминовый порядок также используется для многокритериальной оптимизации , ^[6] например, в оптимальном распределении ресурсов, ^[7] задачах размещения, ^[8] и матричных играх. ^[9]

Он также изучается в контексте решения задач с нечеткими ограничениями. ^{[10] [11]}

В сетях потоков

Порядок лексимина может использоваться как правило для решения задач сетевого потока . При наличии сети потока, источника s , стока t и заданного подмножества E ребер поток называется лексимин-оптимальным (или убывающе минимальным ) на E , если он минимизирует наибольший поток на ребре E , при условии, что это минимизирует второй по величине поток и т. д. Существует полиномиальный алгоритм для вычисления самого дешевого лексимин-оптимального целочисленного потока заданного объема потока. Это возможный способ определения справедливого потока . ^[12]

В теории игр

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

Представление

Представление порядка на множестве векторов — это функция f , которая присваивает каждому вектору один номер, так что порядок между номерами идентичен порядку между векторами. То есть, f ( x ) ≥ f ( y ) тогда и только тогда, когда x больше y на этот порядок. Когда число возможных векторов счетно (например, когда все векторы целые и ограниченные), порядок лексимина может быть представлен различными функциями, например:

• ${\displaystyle f(\mathbf {x} )=-\sum _{i=1}^{n}n^{-x_{i}}}$; ^[13]
• ${\displaystyle f(\mathbf {x} )=-\sum _{i=1}^{n}x_{i}^{-q}}$, где q — достаточно большая константа; ^[14]
• ${\displaystyle f(\mathbf {x} )=\sum _{i=1}^{n}w_{i}\cdot (x^{\uparrow })_{i}}$, где вектор x отсортирован в порядке возрастания, и . ^{[15] [16]} ${\displaystyle \mathbf {x^{\uparrow }} }$ ${\displaystyle w_{1}\gg w_{2}\gg \cdots \gg w_{n}}$

Однако, когда множество возможных векторов несчетно (например, действительные векторы), никакая функция (непрерывная или нет) не может представлять лексиминный порядок. ^{[14] : 34} То же самое верно и для лексикографического порядка .

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

• Лексикографическая оптимизация по максимуму и минимуму — это вычислительная задача нахождения максимального элемента порядка лексимина в заданном множестве.

Ссылки

1. Herve Moulin (2004). Справедливое разделение и коллективное благосостояние . Кембридж, Массачусетс: MIT Press. ISBN 9780262134231.
2. Барбара, Сальвадор; Джексон, Мэтью (1988-10-01). «Максимин, лексимин и защитный критерий: характеристики и сравнения». Журнал экономической теории . 46 (1): 34–44. doi :10.1016/0022-0531(88)90148-2. ISSN  0022-0531.
3. Ягер, Рональд Р. (1997-10-01). «Об аналитическом представлении порядка Leximin и его применении к распространению гибких ограничений». Европейский журнал операционных исследований . 102 (1): 176–192. doi :10.1016/S0377-2217(96)00217-2. ISSN  0377-2217.
4. Сен, Амартия (2017-02-20). Коллективный выбор и социальное благосостояние. Издательство Гарвардского университета. doi :10.4159/9780674974616. ISBN 978-0-674-97461-6.
5. Дюбуа, Дидье; Фаржье, Элен ; Прад, Анри (1997), Ягер, Рональд Р.; Кацпржик, Януш (ред.), «За пределами минимальной агрегации в многокритериальном решении: (упорядоченный) взвешенный минимум, дискримин, лексимин», Операторы упорядоченного взвешенного усреднения: теория и приложения , Бостон, Массачусетс: Springer US, стр. 181–192, doi : 10.1007/978-1-4615-6123-1_15, ISBN 978-1-4615-6123-1, получено 2021-06-11
6. Эрготт, Маттиас (2005-05-18). Многокритериальная оптимизация. Springer Science & Business Media. ISBN 978-3-540-21398-7.
7. Лусс, Ханан (1999-06-01). «О проблемах справедливого распределения ресурсов: лексикографический минимаксный подход». Исследование операций . 47 (3): 361–378. doi : 10.1287/opre.47.3.361 . ISSN  0030-364X.
8. Огрычак, Влодзимеж (1997-08-01). «О лексикографическом минимаксном подходе к проблемам местоположения». Европейский журнал операционных исследований . 100 (3): 566–585. doi :10.1016/S0377-2217(96)00154-3. ISSN  0377-2217.
9. Поттерс, Джос AM; Тийс, Стеф Х. (1992-02-01). «Ядрышко матричной игры и другие ядрышки». Математика исследования операций . 17 (1): 164–174. doi :10.1287/moor.17.1.164. hdl : 2066/223732 . ISSN  0364-765X. S2CID  40275405.
10. Дюбуа, Дидье; Фортемпс, Филипп (1999-10-01). «Вычисление улучшенных оптимальных решений для задач удовлетворения гибких ограничений по максимуму–мину». Европейский журнал исследований операций . 118 (1): 95–126. doi :10.1016/S0377-2217(98)00307-5. ISSN  0377-2217.
11. Пирес, Дж. М.; Праде, Х. (1998-05-01). "Логический анализ проблем удовлетворения нечетких ограничений". Труды Международной конференции IEEE по нечетким системам 1998 г. Всемирный конгресс IEEE по вычислительному интеллекту (Кат. № 98CH36228) (PDF) . Том 1. стр. 857–862 том 1. doi :10.1109/FUZZY.1998.687603. ISBN 0-7803-4863-X. S2CID  123126673.
12. Франк, Андраш ; Мурота, Казуо (2020-09-18). «Справедливые интегральные сетевые потоки». Математика исследования операций . 48 (3): 1393–1422. arXiv : 1907.02673 . doi : 10.1287/moor.2022.1303. S2CID  246411731.
13. Фриш, Алан М.; Хнич, Брахим; Кизилтан, Зейнеп; Мигель, Ян; Уолш, Тоби (2009-02-01). «Алгоритмы фильтрации для ограничения упорядочения мультимножеств». Искусственный интеллект . 173 (2): 299–328. arXiv : 0903.0460 . doi :10.1016/j.artint.2008.11.001. ISSN  0004-3702. S2CID  7869870.
14. Moulin, Herve (1991-07-26). Аксиомы кооперативного принятия решений. Cambridge University Press. ISBN 978-0-521-42458-5.
15. Ягер, Р. Р. (1988-01-01). «О операторах агрегации с упорядоченным взвешенным усреднением в многокритериальном принятии решений». Труды IEEE по системам, человеку и кибернетике . 18 (1): 183–190. doi :10.1109/21.87068. ISSN  2168-2909.
16. Ягер, Рональд Р. (1997-10-01). «Об аналитическом представлении порядка Leximin и его применении к распространению гибких ограничений». Европейский журнал операционных исследований . 102 (1): 176–192. doi :10.1016/S0377-2217(96)00217-2. ISSN  0377-2217.