レキシミン注文

数学において、レキシミン順序とは有限次元ベクトル上の全順序である。より正確だがあまり一般的ではない用語はレキシミン順序である。レキシミン順序は社会的選択理論と公平な分割において特に重要である。^{[1] [2] [3]}

次のいずれかが成り立つ場合、 ベクトルx = ( x ₁ , ..., x _n ) はベクトルy = ( y ₁ , ..., y _n ) よりもleximin 大きいです。

• xの最小要素はyの最小要素よりも大きい。
• 両方のベクトルの最小要素は等しく、xの 2 番目に小さい要素はyの 2 番目に小さい要素よりも大きい。
• ...
• 両方のベクトルのk 個の最小要素は等しく、xの ( k +1) 最小要素はyの ( k +1) 最小要素よりも大きい。

ベクトル (3,5,3) は (4,2,4) よりも leximin 大きい。これは前者の最小要素が 3 で、後者の最小要素が 2 であるためである。ベクトル (4,2,4) は (5,3,2) よりも leximin 大きい。これは両方の最小要素が 2 であるが、前者の 2 番目に小さい要素が 4 で、後者の 3 であるためである。

同じ要素の多重集合を持つベクトルは、最小の要素、2 番目に小さい要素などが同じであるため、レキシミン順序に関して同等です。たとえば、ベクトル (4,2,4) と (2,4,4) はレキシミン同等です (ただし、どちらも (2,4,2) よりもレキシミン大きくなります)。

辞書式順序では、ベクトルが最小であるかどうかに関係なく、最初の比較はx ₁とy ₁の間で行われます。2 番目の比較はx ₂とy ₂の間で行われ、以下同様に続きます。

たとえば、ベクトル (3,5,3) は、前者の最初の要素が 3 で後者の最初の要素が 4 であるため、辞書式では (4,2,4) よりも小さくなります。同様に、(4,2,4) は辞書式では (2,4,4) よりも大きくなります。

次のアルゴリズムを使用して、xがyよりもleximin 大きいかどうかを計算できます。

• x' をxと同じ要素を昇順で含むベクトルとします。
• y' をyと同じ要素を昇順で含むベクトルとします。
• x'がy 'より辞書式に大きい場合は「true」を返します。

レキシマックス順序は、最初の比較が最大の要素間で行われ、2 番目の比較が2 番目に大きい要素間で行われるという点を除いて、 レキシミン順序に似ています。

社会的選択理論^[4]、特に公平な分割^[1]において、レキシミン順序は選択肢を選択するために使用される順序の1つです。典型的な社会的選択問題では、社会はいくつかの選択肢（たとえば、一連のリソースを割り当てるいくつかの方法）の中から選択する必要があります。各選択肢は、効用プロファイル、つまり要素iが割り当てにおけるエージェントiの効用であるベクトルを誘導します。代替案の効用プロファイルが他のすべての代替案の効用プロファイルよりも（弱く）レキシミン大きい場合、 その代替案はレキシミン最適と呼ばれます。

たとえば、3 つの選択肢があるとします。x はアリスに 2、ジョージに 4 の効用を与えます。yはアリスに 9、ジョージに 1 の効用を与えます。zはアリスに 1、ジョージに 8 の効用を与えます。この場合、選択肢x は、その効用プロファイルが (2,4) であり、y ( 9,1 ) およびz (1,8)よりもレキシミン大きいため、レキシミン最適です。レキシミン最適ソリューションは常にパレート効率的です。

レキシミンルールは、すべての可能な割り当ての中から、レキシミンに最適な割り当てを選択します。これは、平等主義ルールと呼ばれることもあります。計算と適用の詳細については、そのページを参照してください。公平な分割におけるレキシミンルールの特定の適用については、以下を参照してください。

• レキシミンケーキカット
• Leximinアイテム割り当て

多基準意思決定分析では、意思決定を行う必要があり、意思決定の根拠となる基準がいくつかあります（例：コスト、品質、スピードなど）。意思決定方法の1つは、各選択肢に各基準における値を表す数値のベクトルを割り当て、そのベクトルがレキシミン最適である選択肢を選択することです。^[5]

レキシミン順序は、多目的最適化にも使用されます。 ^[6]例えば、最適資源割り当て^[7] 、配置問題^[8] 、行列ゲーム^{[9]などです。}

ファジィ制約解決問題の文脈でも研究されている。^{[10] [11]}

レキシミン順序は、ネットワークフロー問題を解くための規則として使用できます。フローネットワーク、ソースs、シンクt、および指定されたエッジのサブセットEが与えられた場合、フローがE上のレキシミン最適（または減少最小）であるとは、 Eのエッジ上の最大フローを最小化し、2番目に大きいフローを最小化するという条件を満たす場合です。与えられたフロー量に対して最も安価なレキシミン最適整数値フローを計算する多項式時間アルゴリズムがあります。これは、公平なフローを定義するための可能な方法です。^[12]

協力ゲームの解法の 1 つは、効率的かつ個々に合理的なすべての報酬ベクトルの中で、連合の超過値のレキシミン ベクトルを最小化する報酬ベクトルです。この解法は核小体と呼ばれます。

ベクトルの集合上の順序の表現は、各ベクトルに単一の数値を割り当てる関数 f であり、数値間の順序はベクトル間の順序と同じになります。つまり、f ( x ) ≥ f ( y ) は、x がその順序でyよりも大きい場合に限ります。可能なベクトルの数が可算である場合 (たとえば、すべてのベクトルが整数で有界である場合)、leximin 順序はさまざまな関数で表すことができます。たとえば、次のようになります。

• ${\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}辞書式順序についても同様である。

• 辞書式最大最小最適化は、与えられた集合内の辞書式順序の最大要素を見つける計算問題です。