Порядок чтения

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

Определение

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

Наименьший элемент x больше наименьшего элемента y ;
Наименьшие элементы обоих векторов равны, а второй наименьший элемент x больше второго наименьшего элемента y ;
...
k k наименьших элементов обоих векторов равны, а ( k +1)-наименьший элемент x больше, чем ( +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). Оптимальное для лексимина решение всегда является эффективным по Парето .

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

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

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

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

Это также изучается в контексте задач решения нечетких ограничений . ^[10]^[11]

В проточных сетях

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

В теории игр

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

Представительство

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

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

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

См. также

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

Ссылки

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

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

[2] Барбара, Сальвадор; Джексон, Мэтью (1 октября 1988 г.). «Максимин, лексимин и защитный критерий: характеристики и сравнения» . Журнал экономической теории . 46 (1): 34–44. дои : 10.1016/0022-0531(88)90148-2 . ISSN 0022-0531 .

[3] Ягер, Рональд Р. (1 октября 1997 г.). «Об аналитическом представлении упорядочения Лексимина и его применении к гибкому распространению ограничений» . Европейский журнал операционных исследований . 102 (1): 176–192. дои : 10.1016/S0377-2217(96)00217-2 . ISSN 0377-2217 .

[:02-4] Сен, Амартия (20 февраля 2017 г.). Коллективный выбор и социальное благосостояние . Издательство Гарвардского университета. дои : 10.4159/9780674974616 . ISBN 978-0-674-97461-6 .

[5] Дюбуа, Дидье; Фаржье, Элен ; Прад, Анри (1997), Ягер, Рональд Р.; Кацпршик, Януш (ред.), «За пределами минимальной агрегации в многокритериальном решении: (упорядоченный) взвешенный минимум, дискри-мин, лексимин» , Упорядоченные операторы взвешенного усреднения: теория и приложения , Бостон, Массачусетс: Springer US, стр. 181– 192, номер домена : 10.1007/978-1-4615-6123-1_15 , ISBN 978-1-4615-6123-1 , получено 11 июня 2021 г.

[:2-6] Эрготт, Матиас (18 мая 2005 г.). Многокритериальная оптимизация . Springer Science & Business Media. ISBN 978-3-540-21398-7 .

[:3-7] Лусс, Ханан (1 июня 1999 г.). «О проблемах справедливого распределения ресурсов: лексикографический минимаксный подход» . Исследование операций . 47 (3): 361–378. дои : 10.1287/opre.47.3.361 . ISSN 0030-364X .

[:4-8] Огрычак, Влодзимеж (1 августа 1997 г.). «О лексикографическом минимаксном подходе к задачам размещения» . Европейский журнал операционных исследований . 100 (3): 566–585. дои : 10.1016/S0377-2217(96)00154-3 . ISSN 0377-2217 .

[:5-9] Поттерс, Джос AM; Тийс, Стеф Х. (1 февраля 1992 г.). «Ядрышко матричной игры и другие ядрышки» . Математика исследования операций . 17 (1): 164–174. дои : 10.1287/moor.17.1.164 . hdl : 2066/223732 . ISSN 0364-765X . S2CID 40275405 .

[:6-10] Дюбуа, Дидье; Фортемпс, Филипп (1 октября 1999 г.). «Вычисление улучшенных оптимальных решений задач удовлетворения максимальных и минимальных гибких ограничений» . Европейский журнал операционных исследований . 118 (1): 95–126. дои : 10.1016/S0377-2217(98)00307-5 . ISSN 0377-2217 .

[11] Пирес, Ж.М.; Прад, Х. (1 мая 1998 г.). «Логический анализ задач удовлетворения нечетких ограничений» . 1998 г. Международная конференция IEEE по материалам нечетких систем. Всемирный конгресс IEEE по вычислительному интеллекту (кат. № 98CH36228) (PDF) . Том. 1. С. 857–862, т. 1. дои : 10.1109/FUZZY.1998.687603 . ISBN 0-7803-4863-Х . S2CID 123126673 .

[12] Франк, Андраш ; Мурота, Кадзуо (18 сентября 2020 г.). «Справедливые интегральные сетевые потоки». Математика исследования операций . 48 (3): 1393–1422. arXiv : 1907.02673 . дои : 10.1287/moor.2022.1303 . S2CID 246411731 .

[13] Фриш, Алан М.; Хнич, Брахим; Кизилтан, Зейнеп; Мигель, Ян; Уолш, Тоби (01 февраля 2009 г.). «Алгоритмы фильтрации для ограничения порядка мультимножества» . Искусственный интеллект . 173 (2): 299–328. arXiv : 0903.0460 . дои : 10.1016/j.artint.2008.11.001 . ISSN 0004-3702 . S2CID 7869870 .

[:1-14] Jump up to: ^а ^б Мулен, Эрве (26 июля 1991 г.). Аксиомы совместного принятия решений . Издательство Кембриджского университета. ISBN 978-0-521-42458-5 .

[15] Ягер, Р.Р. (1 января 1988 г.). «Об упорядоченных операторах взвешенного усреднения при многокритериальном принятии решений» . Транзакции IEEE по системам, человеку и кибернетике . 18 (1): 183–190. дои : 10.1109/21.87068 . ISSN 2168-2909 .

[16] Ягер, Рональд Р. (1 октября 1997 г.). «Об аналитическом представлении упорядочения Лексимина и его применении к гибкому распространению ограничений» . Европейский журнал операционных исследований . 102 (1): 176–192. дои : 10.1016/S0377-2217(96)00217-2 . ISSN 0377-2217 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]