Pareto efficiency

From WFM Labs


Pareto efficiency, also called Pareto optimality, is a state of allocation or decision in which it is impossible to improve any one objective (or the welfare of any one party) without making at least one other objective (or party) worse off.[1] The concept is named after the Italian economist and engineer Vilfredo Pareto, who introduced it in his study of economic welfare and the distribution of resources.[2] A closely related idea, Pareto dominance, orders candidate solutions: one solution dominates another when it is no worse on every objective and strictly better on at least one. The set of non-dominated solutions forms the Pareto set in the space of decisions, whose image in objective space is the Pareto front.[3] Pareto efficiency is central to multi-objective optimization, welfare economics, engineering design, and any setting involving conflicting goals.

Formal definition

Consider a minimization problem with a feasible set X and a vector-valued objective f(x) = (f1(x), …, fk(x)) mapping each decision x to k real-valued criteria. A point x* ∈ X is said to Pareto-dominate a point x if fi(x*) ≤ fi(x) for all objectives i and fj(x*) < fj(x) for at least one objective j.[1] A feasible point is Pareto-efficient (equivalently Pareto-optimal, non-dominated, or non-inferior) if no other feasible point dominates it.[3] Because the dominance relation is only a partial order, a multi-objective problem generally has not one optimum but a whole set of mutually non-dominated solutions, each representing a different trade-off among the objectives.[1]

Several refinements are standard. Weak Pareto efficiency requires only that no feasible point be strictly better on every objective simultaneously, and therefore admits more points than the strict notion.[3] Proper Pareto efficiency (in the sense of Geoffrion) additionally bounds the trade-off ratios, excluding solutions in which an unbounded gain in one objective would be traded for an arbitrarily small loss in another.[4]

Pareto set and Pareto front

The collection of all Pareto-efficient decisions is the Pareto set (or efficient set); its image under the objective map is the Pareto front (or non-dominated frontier).[3] For two conflicting objectives the front is typically a curve; for k objectives it is a surface of dimension up to k − 1. Characterizing, approximating, or enumerating this front is the core computational task of multi-objective optimization, because the front summarizes every rational compromise available to a decision maker.[1] Fronts are commonly described by their shape: a convex front admits solutions recoverable by weighted-sum methods, whereas non-convex (concave) regions of a front cannot be reached by any positive weighted sum of the objectives and require other techniques.[5]

Computing Pareto-efficient solutions

A range of methods produce Pareto-efficient points. In scalarization, the vector objective is collapsed into a single parameterized scalar objective; sweeping the parameters traces out points on the front.[3] The best-known instance is the weighted-sum method, which minimizes a convex combination ∑ wi fi(x) with non-negative weights; every solution it returns is Pareto-efficient, but it can only recover points on the convex hull of the front and so misses solutions in non-convex regions.[5] The ε-constraint method instead optimizes one objective while bounding the others by constants ε, and can in principle recover any Pareto-efficient point, including those in non-convex regions.[3]

Population-based evolutionary and metaheuristic algorithms approximate the whole front in a single run by evolving a diverse set of non-dominated candidates. Elitist algorithms such as NSGA-II combine fast non-dominated sorting with a crowding-distance measure to spread solutions across the front,[6] and the broader family of multi-objective evolutionary algorithms treats front approximation and diversity maintenance as joint goals.[7] These ideas connect to quality-diversity search, where algorithms such as MAP-Elites deliberately retain a spread of high-performing but behaviorally distinct solutions rather than a single optimum.[8]

In welfare economics

In economics, an allocation of goods is Pareto-efficient when no reallocation can make one individual better off without making another worse off; Pareto used this criterion to reason about welfare without requiring interpersonal comparisons of utility.[2] The first fundamental theorem of welfare economics states that, under idealized competitive conditions, any market equilibrium is Pareto-efficient, while the second theorem states that any Pareto-efficient allocation can be supported as a competitive equilibrium given a suitable initial redistribution of endowments.[9] Pareto efficiency is a criterion of allocative efficiency only and is silent about equity: an allocation in which one party holds everything can still be Pareto-efficient, which is why the concept is usually paired with distributional judgments in policy analysis.[9]

Applications in workforce management

Contact-center and workforce management decisions are naturally multi-objective, trading off competing goals such as service level, labor cost, occupancy, and schedule fairness. Because improving one of these objectives typically degrades another, staffing and scheduling problems can be framed as searches for Pareto-efficient roster configurations rather than for a single optimum.[10] Presenting planners with the Pareto front, for example a curve of achievable service level against staffing cost, makes the trade-off explicit and lets managers choose an operating point that reflects business priorities, rather than committing to weights chosen in advance.[1] The same reasoning underlies multi-criteria formulations of shift design, skill-based routing, and break placement, where diverse near-optimal plans are often more useful to operations than one nominally best schedule.[7]

See also

References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 Ehrgott, M. (2005). Multicriteria Optimization, 2nd ed. Springer, Berlin/Heidelberg. ISBN 978-3-540-21398-7.
  2. ↑ 2.0 2.1 Pareto, V. (1906/2014). Manual of Political Economy: A Critical and Variorum Edition (Montesano, A. et al., eds.). Oxford University Press, Oxford. ISBN 978-0-19-960757-4.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston. ISBN 978-0-7923-8278-2.
  4. ↑ Geoffrion, A. M. (1968). "Proper efficiency and the theory of vector maximization". Journal of Mathematical Analysis and Applications 22 (3), 618–630. doi:10.1016/0022-247X(68)90201-1.
  5. ↑ 5.0 5.1 Das, I., Dennis, J. E. (1997). "A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems". Structural Optimization 14 (1), 63–69. doi:10.1007/BF01197559.
  6. ↑ Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II". IEEE Transactions on Evolutionary Computation 6 (2), 182–197. doi:10.1109/4235.996017.
  7. ↑ 7.0 7.1 Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester. ISBN 978-0-471-87339-6.
  8. ↑ Mouret, J.-B., Clune, J. (2015). "Illuminating search spaces by mapping elites". arXiv:1504.04909 [cs.NE].
  9. ↑ 9.0 9.1 Mas-Colell, A., Whinston, M. D., Green, J. R. (1995). Microeconomic Theory. Oxford University Press, New York. ISBN 978-0-19-507340-9.
  10. ↑ Ernst, A. T., Jiang, H., Krishnamoorthy, M., Sier, D. (2004). "Staff scheduling and rostering: A review of applications, methods and models". European Journal of Operational Research 153 (1), 3–27. doi:10.1016/S0377-2217(03)00095-X.
Retrieved from "https://wiki.wfmlabs.org/w/index.php?title=Pareto_efficiency&oldid=3582"