Unanimity

Unanimity is principle from Voting Theory that is the same as Dominance:

If a candidate $a$ is always preferred by the majority to $b$, then we can say that $b$ is dominated by $a$ and never consider $b$ again


Pareto-Optimal Solutions

In Multi-Objective Optimization and Multi-Criteria Decision Aid there could be many "best" solutions - these solutions are called the Pareto-Optimal solutions


Consider this example:

  • knapsack.png
    • the two alternatives along the blue line form the pareto-optimal set
  • moo-illustration.png
    • the solutions in blue circles also form the pareto-optimal set

Dominance

  • for the second examples we can say that $b$ dominates $c$:
  • $b$ has the same level of quality, but it is cheaper
  • we can remove all dominated solutions from the solution space and this will give us the Pareto-optimal set of solutions
  • in MOO this is also called the set of efficient solutions
dominance
$a$ dominates $b$ $\iff \forall i: f_i(a) \geqslant f_i(b)$ and $\exists i: f_j(a) > f_j(b)$
i.e. for all criteria $a$ is at least as good as $b$, but there's at least one criteria at which $a$ is strictly better than $b$


This is not always good. Consider this example

  • you're looking for an apartment to rent
  • you consider price and distance to work (want to minimize both)
  • dominance-bad-case.png
  • in this case $c$ is dominated by $a$ and $b$:
    • $b$ is very cheap, $a$ is very close
    • $c$ is a good compromise, but it's dominated


Another example

  • suppose we're choosing a car
  • there are 4 criteria: price, power, consumption, comfort
  • there are 6 alternatives
Price Power Consumption Comfort
Avg A. 18 75 8 3
Sport 18.5 110 9 2
Avg B. 17.5 85 7 3
Lux 1 24 90 8.5 5
Exonomic 12.5 50 7.5 1
Lux 2 22.5 85 9 4

We see that Avg B is always better than Avg. A

  • then nobody will ever choose Avg A: A is dominated by B

No other alternative can be eliminated this way


Game Theory

This principle is as well applied in the Game Theory

Notation:

  • $A_i$ - set of strategies for player $i$
  • $u_i$ - the utility function of $i$
  • $a, b \in A_i$ - two strategies in $A_i$
  • denote $A_{-i}$ as the set of all strategies for other players
Strict dominance
$a$ strictly dominates $b$ if $\forall c \in A_{-1}: u_i(a, c) > u_i(b, c)$
in other words: $a$ strictly dominates $b$ is for every action that other players can take, the action $a$ gives $i$ better payoff than $b$
Weak dominance
$a$ (weakly) dominates $b$ if $\forall c \in A_{-1}: u_i(a, c) \geqslant u_i(b, c)$


If $a$ dominates all other strategies $b$ of the player $i$ then it's dominant


Pareto Optimality

In Game Theory there's also a notion of Pareto Optimality

Suppose you see a game as an outside observer, not a player

  • Can we say that one outcome $O$ is better than some other outcome $O'$?

Pareto-Dominance

  • suppose there's one outcome $O$ that is as good as some other outcome $O'$ for all players
  • but there's one agent $i$ who strictly prefers $O$ to $O'$
  • then $O$ is considered better than $O'$
  • and $O$ pareto-dominates $O'$

Pareto-Optimality

  • outcome $O^*$ is pareto-optimal if there is no other outcome that pareto-dominates it
  • a game can have more than one pareto-optimal outcome
  • for Zero-Sum Games every outcome is pareto-optimal


Problems

Close Contenders

$b$ is a close contender if

  • it's dominated by some alternative $a$
  • but $b$ is still a good choice

Consider this example:

  • $A = \{a, b, c, d\}$
  • $A^* = \{a, c, d\}$ - efficient (pareto-optimal) set of solutions
$c$ $e_1$ $e_2$ $e_3$ $...$ $e_{100}$
$a$ 100 100 100 ... 100
$b$ 99 99 99 ... 99
$c$ 101 0 0 ... 0
$d$ 0 101 0 ... 0

But we see that $c$ and $d$ aren't that good, but both are in $A^*$

  • i.e. we should have taken $b$ instead them


Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion