Orden de Leximin

En matemáticas, el orden leximin es un preorden total en vectores de dimensión finita. Un término más preciso, pero menos común, es preorden leximin . El orden leximin es particularmente importante en la teoría de la elección social y la división justa . ^{[1] [2] [3]}

Un vector x = ( x ₁ , ..., x _n ) es leximin-mayor que un vector y = ( y ₁ , ..., y _n ) si se cumple una de las siguientes condiciones:

• El elemento más pequeño de x es mayor que el elemento más pequeño de y ;
• Los elementos más pequeños de ambos vectores son iguales, y el segundo elemento más pequeño de x es mayor que el segundo elemento más pequeño de y ;
• ...
• Los k elementos más pequeños de ambos vectores son iguales, y el elemento ( k + 1) más pequeño de x es mayor que el elemento ( k + 1) más pequeño de y .

El vector (3,5,3) es leximin-mayor que (4,2,4), ya que el elemento más pequeño en el primero es 3 y en el segundo es 2. El vector (4,2,4) es leximin-mayor que (5,3,2), ya que los elementos más pequeños en ambos son 2, pero el segundo elemento más pequeño en el primero es 4 y en el segundo es 3.

Los vectores con el mismo multiconjunto de elementos son equivalentes con respecto al preorden leximin, ya que tienen el mismo elemento más pequeño, el mismo segundo elemento más pequeño, etc. Por ejemplo, los vectores (4,2,4) y (2,4,4) son equivalentes a leximin (pero ambos son leximin más grandes que (2,4,2)).

En el orden lexicográfico , la primera comparación es entre x ₁ e y ₁ , independientemente de si son los más pequeños en sus vectores. La segunda comparación es entre x ₂ e y ₂ , y así sucesivamente.

Por ejemplo, el vector (3,5,3) es lexicográficamente más pequeño que (4,2,4), ya que el primer elemento en el primero es 3 y en el último es 4. De manera similar, (4,2,4) es lexicográficamente más grande que (2,4,4).

El siguiente algoritmo se puede utilizar para calcular si x es leximin-mayor que y :

• Sea x' un vector que contiene los mismos elementos de x pero en orden ascendente;
• Sea y' un vector que contiene los mismos elementos de y pero en orden ascendente;
• Devuelve "verdadero" solo si x' es lexicográficamente más grande que y ' .

El orden leximax es similar al orden leximin excepto que la primera comparación es entre los elementos más grandes ; la segunda comparación es entre los segundos elementos más grandes; y así sucesivamente.

En la teoría de la elección social , ^[4] particularmente en la división justa , ^[1] el orden leximin es uno de los órdenes utilizados para elegir entre alternativas. En un problema típico de elección social, la sociedad tiene que elegir entre varias alternativas (por ejemplo: varias formas de asignar un conjunto de recursos). Cada alternativa induce un perfil de utilidad - un vector en el que el elemento i es la utilidad del agente i en la asignación. Una alternativa se llama leximin-óptima si su perfil de utilidad es (débilmente) leximin-mayor que el perfil de utilidad de todas las demás alternativas.

Por ejemplo, supongamos que hay tres alternativas: x da una utilidad de 2 a Alice y 4 a George; y da una utilidad de 9 a Alice y 1 a George; y z da una utilidad de 1 a Alice y 8 a George. Entonces la alternativa x es leximin-óptima, ya que su perfil de utilidad es (2,4) que es leximin-mayor que el de y (9,1) y z (1,8). La solución leximin-óptima siempre es Pareto-eficiente .

La regla leximin selecciona, de entre todas las asignaciones posibles, las óptimas para el leximin. A menudo se la denomina regla igualitaria ; consulte esa página para obtener más información sobre su cálculo y aplicaciones. Para aplicaciones particulares de la regla leximin en la división justa, consulte:

• Corte de pastel de Leximin
• Asignación de elementos de Leximin

En el análisis de decisiones multicriterio se debe tomar una decisión, y existen varios criterios en los que se debe basar la decisión (por ejemplo: coste, calidad, rapidez, etc.). Una forma de decidir es asignar a cada alternativa un vector de números que representan su valor en cada uno de los criterios, y elegir la alternativa cuyo vector sea leximin-óptimo. ^[5]

El orden leximin también se utiliza para la optimización multiobjetivo , ^[6] por ejemplo, en la asignación óptima de recursos, ^[7] problemas de ubicación, ^[8] y juegos de matrices. ^[9]

También se estudia en el contexto de problemas de resolución de restricciones difusas. ^{[10] [11]}

El orden leximin se puede utilizar como regla para resolver problemas de flujo de red . Dada una red de flujo, una fuente s , un sumidero t y un subconjunto especificado E de aristas, un flujo se denomina leximin-óptimo (o decrecientemente mínimo ) en E si minimiza el flujo más grande en una arista de E , sujeto a que este minimice el segundo flujo más grande, y así sucesivamente. Existe un algoritmo de tiempo polinomial para calcular un flujo de valor entero leximin-óptimo más barato de una cantidad de flujo dada. Es una forma posible de definir un flujo justo . ^[12]

Un tipo de solución para un juego cooperativo es el vector de pagos que minimiza el vector leximin de valores excedentes de las coaliciones, entre todos los vectores de pagos que son eficientes y racionales individualmente. Esta solución se llama nucléolo .

Una representación de un ordenamiento en un conjunto de vectores es una función f que asigna un único número a cada vector, de modo que el ordenamiento entre los números sea idéntico al ordenamiento entre los vectores. Es decir, f ( x ) ≥ f ( y ) si y solo si x es mayor que y por ese ordenamiento. Cuando el número de vectores posibles es contable (por ejemplo, cuando todos los vectores son enteros y acotados), el orden leximin puede representarse mediante varias funciones, por ejemplo:

• ${\displaystyle f(\mathbf {x} )=-\sum _{i=1}^{n}n^{-x_{i}}}$; ^[13]
• ${\displaystyle f(\mathbf {x} )=-\sum _{i=1}^{n}x_{i}^{-q}}$, donde q es una constante suficientemente grande; ^[14]
• ${\displaystyle f(\mathbf {x} )=\sum _{i=1}^{n}w_{i}\cdot (x^{\uparrow })_{i}}$, donde el vector x está ordenado en orden ascendente, y . ^{[15] [16]}${\displaystyle \mathbf {x^{\flecha arriba}}}$${\displaystyle w_{1}\gg w_{2}\gg \cdots \gg w_{n}}$

Sin embargo, cuando el conjunto de vectores posibles es incontable (por ejemplo, vectores reales), ninguna función (ya sea continua o no) puede representar el orden leximin. ^{[14] : 34} Lo mismo ocurre con el orden lexicográfico .

• La optimización máxima-mínima lexicográfica es el problema computacional de encontrar un elemento máximo del orden leximin en un conjunto dado.