Leximin order

Last updated

In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division. [1] [2] [3]

Contents

Definition

A vector x = (x1, ..., xn) is leximin-larger than a vector y = (y1, ..., yn) if one of the following holds:

Examples

The vector (3,5,3) is leximin-larger than (4,2,4), since the smallest element in the former is 3 and in the latter is 2. The vector (4,2,4) is leximin-larger than (5,3,2), since the smallest elements in both are 2, but the second-smallest element in the former is 4 and in the latter is 3.

Vectors with the same multiset of elements are equivalent w.r.t. the leximin preorder, since they have the same smallest element, the same second-smallest element, etc. For example, the vectors (4,2,4) and (2,4,4) are leximin-equivalent (but both are leximin-larger than (2,4,2)).

In the lexicographic order , the first comparison is between x1 and y1, regardless of whether they are smallest in their vectors. The second comparison is between x2 and y2, and so on.

For example, the vector (3,5,3) is lexicographically smaller than (4,2,4), since the first element in the former is 3 and in the latter it is 4. Similarly, (4,2,4) is lexicographically larger than (2,4,4).

The following algorithm can be used to compute whether x is leximin-larger than y:

The leximax order is similar to the leximin order except that the first comparison is between the largest elements; the second comparison is between the second-largest elements; and so on.

Applications

In social choice

In social choice theory, [4] particularly in fair division, [1] the leximin order is one of the orders used to choose between alternatives. In a typical social choice problem, society has to choose among several alternatives (for example: several ways to allocate a set of resources). Each alternative induces a utility profile - a vector in which element i is the utility of agent i in the allocation. An alternative is called leximin-optimal if its utility-profile is (weakly) leximin-larger than the utility profile of all other alternatives.

For example, suppose there are three alternatives: x gives a utility of 2 to Alice and 4 to George; y gives a utility of 9 to Alice and 1 to George; and z gives a utility of 1 to Alice and 8 to George. Then alternative x is leximin-optimal, since its utility profile is (2,4) which is leximin-larger than that of y (9,1) and z (1,8). The leximin-optimal solution is always Pareto-efficient.

The leximin rule selects, from among all possible allocations, the leximin-optimal ones. It is often called the egalitarian rule ; see that page for more information on its computation and applications. For particular applications of the leximin rule in fair division, see:

In multicriteria decision

In Multiple-criteria decision analysis a decision has to be made, and there are several criteria on which the decision should be based (for example: cost, quality, speed, etc.). One way to decide is to assign, to each alternative, a vector of numbers representing its value in each of the criteria, and chooses the alternative whose vector is leximin-optimal. [5]

The leximin-order is also used for Multi-objective optimization, [6] for example, in optimal resource allocation, [7] location problems, [8] and matrix games. [9]

It is also studied in the context of fuzzy constraint solving problems. [10] [11]

In flow networks

The leximin order can be used as a rule for solving network flow problems. Given a flow network, a source s, a sink t, and a specified subset E of edges, a flow is called leximin-optimal (or decreasingly minimal) on E if it minimizes the largest flow on an edge of E, subject to this minimizes the second-largest flow, and so on. There is a polynomial-time algorithm for computing a cheapest leximin-optimal integer-valued flow of a given flow amount. It is a possible way to define a fair flow. [12]

In game theory

One kind of a solution to a cooperative game is the payoff-vector that minimizes the leximin vector of excess-values of coalitions, among all payoff-vectors that are efficient and individually-rational. This solution is called the nucleolus.

Representation

A representation of an ordering on a set of vectors is a function f that assigns a single number to each vector, such that the ordering between the numbers is identical to the ordering between the vectors. That is, f(x) ≥ f(y) iff x is larger than y by that ordering. When the number of possible vectors is countable (e.g. when all vectors are integral and bounded), the leximin order can be represented by various functions, for example:

However, when the set of possible vectors is uncountable (e.g. real vectors), no function (whether contiuous or not) can represent the leximin order. [14] : 34  The same is true for the lexicographic order.

See also

Related Research Articles

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.

<span class="mw-page-title-main">Loss function</span> Mathematical relation assigning a probability event to a cost

In mathematical optimization and decision theory, a loss function or cost function is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost" associated with the event. An optimization problem seeks to minimize a loss function. An objective function is either a loss function or its opposite, in which case it is to be maximized. The loss function could include terms from several levels of the hierarchy.

In mathematics, the lexicographic or lexicographical order is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set.

Multi-objective optimization or Pareto optimization is an area of multiple-criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously. Multi-objective is a type of vector optimization that has been applied in many fields of science, including engineering, economics and logistics where optimal decisions need to be taken in the presence of trade-offs between two or more conflicting objectives. Minimizing cost while maximizing comfort while buying a car, and maximizing performance whilst minimizing fuel consumption and emission of pollutants of a vehicle are examples of multi-objective optimization problems involving two and three objectives, respectively. In practical problems, there can be more than three objectives.

<span class="mw-page-title-main">José Encarnación Jr.</span>

José Encarnación Jr. was a Filipino professor of economics at the University of the Philippines Diliman, where he served as dean of the School of Economics from 1974 until his retirement in 1994.

Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule. In the specific variant known as job-shop scheduling, each job consists of a set of operationsO1, O2, ..., On which need to be processed in a specific order. Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set.

In economics, and in other social sciences, preference refers to an order by which an agent, while in search of an "optimal choice", ranks alternatives based on their respective utility. Preferences are evaluations that concern matters of value, in relation to practical reasoning. Individual preferences are determined by taste, need, ..., as opposed to price, availability or personal income. Classical economics assumes that people act in their best (rational) interest. In this context, rationality would dictate that, when given a choice, an individual will select an option that maximizes their self-interest. But preferences are not always transitive, both because real humans are far from always being rational and because in some situations preferences can form cycles, in which case there exists no well-defined optimal choice. An example of this is Efron dice.

The Coffman–Graham algorithm is an algorithm for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

Resource monotonicity is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Multi-objective linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objective linear programming is also a subarea of Multi-objective optimization.

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on. Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

In social choice and operations research, the egalitarian rule is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the minimum utility of all individuals in society. It is a formal mathematical representation of the egalitarian philosophy. It also corresponds to John Rawls' principle of maximizing the welfare of the worst-off individual.

In operations research and social choice, the proportional-fair (PF) rule is a rule saying that, among all possible alternatives, one should pick an alternative that cannot be improved, where "improvement" is measured by the sum of relative improvements possible for each individual agent. It aims to provide a compromise between the utilitarian rule - which emphasizes overall system efficiency, and the egalitarian rule - which emphasizes individual fairness.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

Egalitarian cake-cutting is a kind of fair cake-cutting in which the fairness criterion is the egalitarian rule. The cake represents a continuous resource, that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is also called leximin cake-cutting, since the optimization is done using the leximin order on the vectors of utilities.

Lexicographic optimization is a kind of Multi-objective optimization. In general, multi-objective optimization deals with optimization problems with two or more objective functions to be optimized simultaneously. Often, the different objectives can be ranked in order of importance to the decision-maker, so that objective is the most important, objective is the next most important, and so on. Lexicographic optimization presumes that the decision-maker prefers even a very small increase in , to even a very large increase in etc. Similarly, the decision-maker prefers even a very small increase in , to even a very large increase in etc. In other words, the decision-maker has lexicographic preferences, ranking the possible solutions according to a lexicographic order of their objective function values. Lexicographic optimization is sometimes called preemptive optimization, since a small increase in one objective value preempts a much larger increase in less important objective values.

Lexicographic max-min optimization is a kind of multi-objective optimization. In general, multi-objective optimization deals with optimization problems with two or more objective functions to be optimized simultaneously. Lexmaxmin optimization presumes that the decision-maker would like the smallest objective value to be as high as possible; subject to this, the second-smallest objective should be as high as possible; and so on. In other words, the decision-maker ranks the possible solutions according to a leximin order of their objective function values.

In cooperative game theory, the nucleolus of a cooperative game is the solution that maximizes the smallest excess of a coalition. Subject to that, the nucleolus satisfies the second-smallest excess; and so on, in the leximin order. The nucleolus was introduced by David Schmeidler.

References

  1. 1 2 Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN   9780262134231.
  2. ↑ Barbarà, Salvador; Jackson, Matthew (1988-10-01). "Maximin, leximin, and the protective criterion: Characterizations and comparisons". Journal of Economic Theory. 46 (1): 34–44. doi:10.1016/0022-0531(88)90148-2. ISSN   0022-0531.
  3. ↑ Yager, Ronald R. (1997-10-01). "On the analytic representation of the Leximin ordering and its application to flexible constraint propagation". European Journal of Operational Research. 102 (1): 176–192. doi:10.1016/S0377-2217(96)00217-2. ISSN   0377-2217.
  4. ↑ Sen, Amartya (2017-02-20). Collective Choice and Social Welfare. Harvard University Press. doi:10.4159/9780674974616. ISBN   978-0-674-97461-6.
  5. ↑ Dubois, Didier; Fargier, Hélène; Prade, Henri (1997), Yager, Ronald R.; Kacprzyk, Janusz (eds.), "Beyond Min Aggregation in Multicriteria Decision: (Ordered) Weighted Min, Discri-Min, Leximin", The Ordered Weighted Averaging Operators: Theory and Applications, Boston, MA: Springer US, pp. 181–192, doi:10.1007/978-1-4615-6123-1_15, ISBN   978-1-4615-6123-1 , retrieved 2021-06-11
  6. ↑ Ehrgott, Matthias (2005-05-18). Multicriteria Optimization. Springer Science & Business Media. ISBN   978-3-540-21398-7.
  7. ↑ Luss, Hanan (1999-06-01). "On Equitable Resource Allocation Problems: A Lexicographic Minimax Approach". Operations Research. 47 (3): 361–378. doi: 10.1287/opre.47.3.361 . ISSN   0030-364X.
  8. ↑ Ogryczak, Włodzimierz (1997-08-01). "On the lexicographic minimax approach to location problems". European Journal of Operational Research. 100 (3): 566–585. doi:10.1016/S0377-2217(96)00154-3. ISSN   0377-2217.
  9. ↑ Potters, Jos A. M.; Tijs, Stef H. (1992-02-01). "The Nucleolus of a Matrix Game and Other Nucleoli". Mathematics of Operations Research . 17 (1): 164–174. doi:10.1287/moor.17.1.164. hdl: 2066/223732 . ISSN   0364-765X. S2CID   40275405.
  10. ↑ Dubois, Didier; Fortemps, Philippe (1999-10-01). "Computing improved optimal solutions to max–min flexible constraint satisfaction problems". European Journal of Operational Research. 118 (1): 95–126. doi:10.1016/S0377-2217(98)00307-5. ISSN   0377-2217.
  11. ↑ Pires, J.M.; Prade, H. (1998-05-01). "Logical analysis of fuzzy constraint satisfaction problems". 1998 IEEE International Conference on Fuzzy Systems Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98CH36228) (PDF). Vol. 1. pp. 857–862 vol.1. doi:10.1109/FUZZY.1998.687603. ISBN   0-7803-4863-X. S2CID   123126673.
  12. ↑ Frank, András; Murota, Kazuo (2020-09-18). "Fair integral network flows". Mathematics of Operations Research . 48 (3): 1393–1422. arXiv: 1907.02673 . doi:10.1287/moor.2022.1303. S2CID   246411731.
  13. ↑ Frisch, Alan M.; Hnich, Brahim; Kiziltan, Zeynep; Miguel, Ian; Walsh, Toby (2009-02-01). "Filtering algorithms for the multiset ordering constraint". Artificial Intelligence. 173 (2): 299–328. arXiv: 0903.0460 . doi:10.1016/j.artint.2008.11.001. ISSN   0004-3702. S2CID   7869870.
  14. 1 2 Moulin, Herve (1991-07-26). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN   978-0-521-42458-5.
  15. ↑ Yager, R.R. (1988-01-01). "On ordered weighted averaging aggregation operators in multicriteria decisionmaking". IEEE Transactions on Systems, Man, and Cybernetics. 18 (1): 183–190. doi:10.1109/21.87068. ISSN   2168-2909.
  16. ↑ Yager, Ronald R. (1997-10-01). "On the analytic representation of the Leximin ordering and its application to flexible constraint propagation". European Journal of Operational Research. 102 (1): 176–192. doi:10.1016/S0377-2217(96)00217-2. ISSN   0377-2217.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.