\chapter{ Conflict Situations}
\index{Conflict situations|(}

In all areas of everyday life there are situations when conflicting aspects have to be taken into account simultaneously.  
A problem becomes even more difficult when several decision makers' or interest groups' mutual agreement is needed to
find a solution.

Conflict situations are divided in three categories in terms of mathematics:
 
\begin{enumerate}
\item One decision maker has to make a decision by taking several conflicting aspects into account
\item Several decision makers have to find a common solution, when every decision maker takes only one criterion into account
\item Several decision makers look for a common solution, but every decision maker takes several criteria into account 
\end{enumerate}

In the first case the problem is a multi-objective optimization problem, where the objective functions make up the various aspects.
The second case is a typical problem of the game theory, when the decision makers are the players and the criteria mean the 
payoff functions.  The third case appears as Pareto games
\index{Pareto games}\nevindex{Pareto, Vilfredo Federico Damaso (1848--1923)} 
in the literature, when the different players only strive to
find Pareto optimal solutions\index{Pareto optimal solution} instead of optimal ones.

In this chapter we will discuss the basics of this very important and complex topic.

\section{The basics of multi-objective programming}\label{sec1}
\index{multi-objective programming|(}

Suppose, that one decision maker wants to find the best decision alternative on the basis of several, usually 
conflicting criteria. The criteria usually represent decision objectives. At first these are usually 
defined verbally, such as clean air, cheap maintenance, etc. Before the mathematical model is given,
firstly, these objectives have to be described by quantifiable indices.
It often occurs that one criterion is described by more than one indices, such as the quality of the air,
since the simultaneous presence of many types of pollution have an effect on it.
In mathematics it is usually assumed that the bigger value of the certain indices (they will be called \ki{objective functions})
\inddef{objective function} means favorable value, hence we want to maximize
all of the objective functions simultaneously. If we want to minimize one of the objective functions,
we can safely multiply its value by $(-1)$, and maximize the resulting new objective function.
If in the case of one of the objective functions, the goal is to attain some kind of optimal value,
we can maximize the deviation from it by multiplying it by $(-1)$.

If $X$ denotes the set of possible decision alternatives, and $f_i:X\rightarrow\R$ denotes the $i$th
objective function $(i=1,2,\ldots,I)$, the problem can be described mathematically as follows:

\begin{equation}\label{eq1}
\hspace{-5mm} f_i(x)\rightarrow max \mspace{40mu}  (i=1,2,\ldots,I)\koz ,
\end{equation}
supposing that $x \in X$.

In the case of a single objective function we look for an \ki{optimal solution.}\inddef{optimal solution} Optimal
solutions satisfy the following requirements: 

\begin{enumerate}[(i)]
\item An optimal solution is always better than any non-optimal solution.
\item There is no such possible solution that provides better objective functions than an optimal solution.
\item If more than one optimal solution exist simultaneously, they are equivalent in the meaning that
they have the same objective functions.
\end{enumerate}

These properties come from the simple fact that the \ki{consequential space,}\inddef{consequential space}
\begin{equation}\label{eq2}
H = \{  u | u = f(x)\mspace{10mu}\mbox{for some}\mspace{10mu} x \in X\}
\end{equation}
is a subset of the real number line, which is totally ordered. In the case of multiple objective functions, the
\begin{equation}\label{eq3}
H = \{  \mathbf{u}=(u_1,\ldots,u_I) | u_i = f_i(x), i=1,2,\ldots,I\mspace{10mu}\mbox{for some}\mspace{10mu} x \in X\}
\end{equation}
consequential space is a subset of the  $I$-dimensional Euclidean space, which is only partially ordered.
Another complication results from the fact that a decision alternative that could maximize all of the objective functions simultaneously
doesn't usually exist.

Let's denote
\begin{equation}\label{eq4}
f_i^{\star} = \max\{  f_i(x) |  x \in X\}
\end{equation}
the maximum of the $i$th objective function, then the $$\mathbf{f}^{\star} = (f_1^{\star},\ldots,f_I^{\star})$$
point is called \ki{ideal point.}\inddef{ideal point} If  $\mathbf{f}^{\star} \in H$, then there
exits an $x^{\star}$ decision for which $f_i(x^{\star})=f_i^{\star}, i=1,2,\ldots,I$.
In such special cases $x^{\star}$ satisfies the previously defined (i)-(iii) conditions. However, if 
$\mathbf{f}^{\star} \notin H$, the situation is much more complicated. In that case we look for Pareto optimal solutions
instead of optimal ones.

\begin{defi}
An alternative $x \in X$ is said to be \ki{Pareto optimal,}\inddef{Pareto optimal} if there is no $\overline{x} \in X$ such that
$f_i(\overline{x}) \geq f_i(x)$ for all $ i=1,2,\ldots,I$, with at least one strict inequality.
\end{defi}

It is not necessary that a multi-purpose optimization problem has Pareto optimal solution, as the case of the
$$H = \{  (f_1, f_2) | f_1 + f_2 < 1\}$$
set shows it. Since $H$ is open set, $(f_1 + \epsilon_1, f_2 + \epsilon_2) \in H$ for arbitrary $(f_1,f_2) \in H$ and 
for a small enough positive $\epsilon_1$ and $\epsilon_2$.

\begin{tetel}
If $X$ bounded, closed in a finite dimensional Euclidean space and all of the objective functions are continuous, there is
Pareto optimal solution.
\end{tetel}

The following two examples present a discrete and a continuous problem.

\begin{pelda}
Assume that during the planning of a sewage plant one out of two options must be chosen. The expenditure of the first option 
is two billion Ft, and its daily capacity is 1500 $m^3$. The second option is more expensive, three billion Ft with 
2000 $m^3$ daily capacity. In this case $X = \{1,2\}$, $f_1 = -$expenditure, $f_2 = $ capacity. The following table
summarizes the data:

\begin{figure}[!h]
$$
\begin{tabular}{|r|cc|}
\hline
Options
& $f_1$ & $f_2$ \\
\hline $\begin{array}{r}
\textup{1} \\
\textup{2}
\end{array}$ &
$\begin{array}{c}
-2 \\
-3
\end{array}$ &
$\begin{array}{c}
1500 \\
2000
\end{array}$ \\
\hline
\end{tabular}
$$
\caption{Planning of a sewage plant.}
\end{figure}

Both options are Pareto optimal,\index{Pareto optimal} since $-2>-3$ and $2000>1500$.The $H$ consequential space consists of two points:
$(-2, 1500)$ and $(-3,2000)$.
\end{pelda}

\begin{pelda}\label{ex2}
The optimal combination of three technology variants is used in a sewage station. The first variant removes 3,2,1 $mg/m^3$
from one kind of pollution, and 1,3,2 $mg/m^3$ quantity from the another kind of pollution. Let 
$x_1$, $x_2$ and $1-x_1-x_2$ denote the percentage composition of the three technology variants.

The restrictive conditions:
\begin{eqnarray*}
x_1, x_2 & \geq & 0 \\
x_1+x_2 & \leq & 1 \koz ,
\end{eqnarray*}
the quantity of the removed pollution: 
\begin{eqnarray*}
3x_1+2x_2+(1-x_1-x_2) & = & 2x_1+x_2+1 \\
x_1+3x_2+2(1-x_1-x_2) & = & -x_1+x_2+2 \koz .
\end{eqnarray*}
Since the third term is constant, we get the following two objective-function optimum problem:

$$2x_1+x_2, -x_1+x_2  \longrightarrow  max$$ provided that
\begin{eqnarray*}
x_1, x_2 & \geq & 0 \\
x_1+x_2 & \leq & 1 \koz .
\end{eqnarray*}
A $H$ consequential space can be determined as follows. From the 
\begin{eqnarray*}
f_1 & = & 2x_1 + x_2 \\
f_2 & = & -x_1 + x_2
\end{eqnarray*}
equations 
$$x_1  =  \frac{f_1 - f_2}{3} \mspace{10mu} \mbox{and} \mspace{10mu} x_2 = \frac{f_1 - 2f_2}{3} \koz ,$$ 
and from the restrictive conditions the following conditions arises for the $f_1$ and $f_2$ objective functions:
\begin{eqnarray*}
x_1 \geq 0 & \Longleftrightarrow & f_1 - f_2 \geq 0 \\
x_2 \geq 0 & \Longleftrightarrow & f_1 + 2f_2 \geq 0 \\
x_1 + x_2 \leq 1 & \Longleftrightarrow & 2f_1 + f_2 \leq 3 \koz .
\end{eqnarray*}

Figures \ref{fig8:abra1} and \ref{fig8:abra2} display the $X$ and $H$ sets.

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.5]{5.1.eps}
\caption{The image of set $X$.\label{fig:abra1}}
\end{center}
\end{figure}

%\epskep{5.2}{Távolság minimalizálás.\label{fig:abra3a}}

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.5]{5.2.eps}
\caption{The image of set $H$.\label{fig:abra2}}
\end{center}
\end{figure}

On the basis of the image of the $H$ set, it is clear that the points of the straight section joining $(1,1)$ to $(2,-1)$ are Pareto 
optimal. Point $(2,-1)$ isn't better than any possible point of  $H$, because in the first objective function it results the
worst possible planes. The points of the section are not equivalent to each other, either, going down from the point  $(1,1)$
towards point $(2,1)$, the first objective function is increasing, but the second one is continually decreasing. 
Thus the (ii) and (iii) properties of the optimal solution doesn't remain valid in the case of multi-objection.
\end{pelda}

As we saw in the previous example, the different Pareto optimal solutions result in different objective function values, so
it is primary importance to decide which one should be selected in a particular case. This question is answered by the
methodology of the multi-objective programming. Most methods' basis is to substitute some real-valued 
\idez{value-function} for the objective functions, that is the preference generated by the objective functions is
replaced by a single real-valued function.  In this chapter the most frequently used methods of multi-objective programming 
are discussed.

\subsection{Applications of utility functions}\label{subsec11}
\index{utility function|(}

A natural method is the following. We assign one utility function to every objective function.
Let $u_i(f_i(x))$ denote the utility function of the $i$th objective function. The construction of
the $u_i$ function can be done by the usual manner of the theory of utility functions, for example
the decision maker can subjectively define the $u_i$ values for the given $f_i$ values, then
a continuous function can be interpolated on the resulting point.
In the case of additive independent utility function additive, whereas in the case of  
independent of usefulness utility function additive or multiplicative aggregate utility function can be obtained.
That is, the form of the aggregate utility function is either
\begin{equation}\label{eq5}
u(\mathbf{f}) = \sum_{i=1}^I k_i u_i(f_i)
\end{equation}
or
\begin{equation}\label{eq6}
k u(\mathbf{f})+1 = \prod_{i=1}^I k k_i u_i(f_i)+1 \koz.
\end{equation}
In such cases the multi-objective optimization problem can be rewrite to one objective-function form:
\begin{equation}\label{eq7}
u(\mathbf{f}) \longrightarrow max
\end{equation}
provided that $x \in X$,
and thus $u(\mathbf{f})$ means the "value-function".

\begin{pelda}
Consider again the decision making problem of the previous example. The range of the first objective function
is $[0,2]$, while the range of the second one is $[-1,1]$. Assuming linear utility functions
$$u_1(f_1) =\frac{1}{2}(f_1)  \mspace{10mu}\mbox{and}\mspace{10mu} u_2(f_2) =\frac{1}{2}(f_2)+1 \koz .$$
In addition, suppose that the decision maker gave the
$$u(0,-1)=0, u(2,1)=1, \mspace{10mu}\mbox{and the}\mspace{10mu} u(0,1)=\frac{1}{4}$$ values.
Assuming linear utility functions $$u(f_1,f_2)=k_1 u_1(f_1)+k_2 u_2(f_2) \koz ,$$
and in accordance with the given values

\begin{eqnarray*}
0 & = & k_1 0 + k_2 0 \\
1 & = & k_1 1 + k_2 1 \\
\frac{1}{4} & = & k_1 0 + k_2 1 \koz . 
\end{eqnarray*}
By the third equation $k_2=\frac{1}{4}$, and by the second one we obtain $k_1=\frac{3}{4}$, so that
$$u(f_1,f_2)=\frac{3}{4}u_1(f_1)+\frac{1}{4}u_2(f_2)=\frac{3}{4}\frac{1}{2}(2x_1+x_2)+\frac{1}{4}\frac{1}{2}(-x_1+x_2+1)=
\frac{5}{8}x_1+\frac{4}{8}x_2+\frac{1}{8} \koz .$$
Thus we solve the following one objective-function problem:
$$\frac{5}{8}x_1 + \frac{4}{8}x_2 \longrightarrow max$$ provided that
\begin{eqnarray*}
x_1,x_2 & \geq & 0 \\
x_1 + x_2 & \leq & 1 \koz .
\end{eqnarray*}
Apparently, the optimal solution is: $x_1=1$, $x_2=0$, that is the first technology must be chosen.
\end{pelda}

Assume that the number of objective functions is $n$ and the decision maker gives $N$ vectors: $(f_1^{(l)},\dots,f_n^{(l)})$ and the related $u^{(l)}$ aggregated utility function values. Then the $k_1,\dots,k_n$ coefficients can be given by the solution of the
$$k_1 u_1(f_1^{(l)})+\dots+k_n u_n(f_n^{(l)})=u^{(l)} \mspace{40mu}  (l=1,2,\ldots,N)$$
equation system. We always suppose that $N \geq n$, so that we have at least as many equations as the number of
unknown quantities. If the equation system is contradictory, we determine the best fitting solution by the method of least squares\index{method of least squares}. Suppose that

$$
\mathbf{U} = \left(
\begin{array}{ccc}
u_{11} & \cdots & u_{1n} \\
u_{21} & \cdots & u_{2n} \\
\vdots & & \vdots \\
u_{N1} & \cdots & u_{Nn}
\end{array}\right)
\mspace{10mu} \mbox{és} \mspace{10mu}
\mathbf{u} = \left(
\begin{array}{c}
u^{(1)} \\
u^{(2)} \\
\vdots \\
u^{(N)}
\end{array}\right) \koz .
$$

The formal algorithm is as follows: 

\begin{algN}{Utility-Function-Method$(\mathbf{u})$}\inddef{\textsc{Utility-Function-Method}}
1 \' \key{for} \= $i \leftarrow 1$ \key{to} $N$ \\
2 \'           \> \key{do} \key{for} \= $j \leftarrow 1$ \key{to} $n$\\
3 \'   \>     \>     \key{do} $u_{ij} \leftarrow u_j(f_j^{(i)})$\\
4 \'  $\mathbf{k} \leftarrow (\mathbf{U}^T \mathbf{U})^{-1} \mathbf{U}^T \mathbf{u}$ the vector of solutions \\
5 \' \key{return} $\mathbf{k}$
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. Konstruáljuk meg az
%$$
%\mathbf{U} = \left(
%\begin{array}{ccc}
%u_1(f_1^{(1)}) & \cdots & u_n(f_n^{(1)}) \\
%u_1(f_1^{(2)}) & \cdots & u_n(f_n^{(2)}) \\
%\vdots & & \vdots \\
%u_1(f_1^{(N)}) & \cdots & u_n(f_n^{(N)})
%\end{array}\right)
%\mspace{10mu} \mbox{és az} \mspace{10mu}
%\mathbf{u} = \left(
%\begin{array}{c}
%u^{(1)} \\
%u^{(2)} \\
%\vdots \\
%u^{(N)}
%\end{array}\right)
%$$
%mátrixot és vektort.

%\vspace{4 mm}
%\underline{2.Lépés}. A $\mathbf{k}=(k_1,\dots,k_n)^T$ megoldásvektor a 
%$$\mathbf{k}=(\mathbf{U}^T \mathbf{U})^{-1} \mathbf{U}^T \mathbf{u}$$
%képlettel adódik.

\index{utility function|)}

\subsection{Weighting method}
\index{weighting method|(}

Using this method the value-function is chosen as the linear combination of the original 
object functions, that is we solve the
\begin{equation}\label{eq8}
\sum_{i=1}^I \alpha_i f_i(x) \longrightarrow max  \mspace{40mu} (x \in X)
\end{equation}
problem. If we measure the certain objective functions in different dimensions, the aggregate 
utility function can't be interpreted, since we add up terms in different units.
In this case we generally normalize the objective functions. Let $m_i$ and $M_i$ the minimum and maximum
of the $f_i$ objective function on the set $X$. Then the normalized $i$th objective function is given by the
$$\overline{f_i}(x) = \frac{f_i(x) - m_i}{M_i - m_i}$$
formula, and in the  (\ref{eq8}) problem $f_i$ is replaced by $\overline{f_i}$:

\begin{equation}\label{eq9}
\sum_{i=1}^I \alpha_i \overline{f_i}(x) \longrightarrow max \koz .  \mspace{40mu} (x \in X)
\end{equation}
It can be shown, that if all of the $\alpha_i$ weights are positive, the optimal solutions of (\ref{eq9}) are 
Pareto optimal\index{Pareto optimal} with regard to the original problem. 

\begin{pelda}
Consider again the case of Example \ref{ex2}. From Figure \ref{fig:abra2}, we can see that $m_1=0$, $M_1=2$,
$m_2=-1$, and $M_2=1$. Thus the normalized objective functions are: 
$$\overline{f_1}(x_1,x_2) = \frac{2x_1+x_2-0}{2-0}=x_1+\frac{1}{2}x_2$$
and
$$\overline{f_2}(x_1,x_2) = \frac{-x_1+x_2+1}{1+1}=-\frac{1}{2}x_1+\frac{1}{2}x_2+\frac{1}{2} \koz .$$
Assume that the objective functions are equally important, so we choose equivalent weights: 
$\alpha_1=\alpha_2=\frac{1}{2}$, in this way the aggregate objective function is:
$$\frac{1}{2}(x_1+\frac{1}{2}x_2)+\frac{1}{2}(-\frac{1}{2}x_1+\frac{1}{2}x_2+\frac{1}{2})=\frac{1}{4}x_1+\frac{1}{2}x_2+\frac{1}{4} \koz .$$
It is easy to see that the optimal solution on set $X$: $$x_1=0, x_2=1 \koz ,$$
that is, only the second technology variant can be chosen.
\end{pelda}

Suppose that
$\mathbf{\alpha} =(\alpha_{1}, \alpha_{2}, \dots, \alpha_{I})$.
The formal algorithm is as follows: 

\begin{algN}{Weighting-Method$(\mathbf{\alpha})$}\inddef{\textsc{Weighting-Method}}
1 \' \key{for} \= $i \leftarrow 1$ \key{to} $I$ \\
2 \'        \>     \key{do} $m_i \leftarrow (f_i(x) \longrightarrow min)$\\
3 \'        \>      \> $M_i \leftarrow (f_i(x) \longrightarrow max)$\\
4 \'  $k \leftarrow (\sum_{i=1}^I \alpha_i \overline{f_i} \longrightarrow max$) \\
5 \' \key{return} $k$
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. $i=1,2,\dots,I$ esetére oldjuk meg az $$f_i(x) \longrightarrow min \mspace{40mu} (x \in X)$$
%és az
% $$f_i(x) \longrightarrow max \mspace{40mu} (x \in X)$$
%feladatokat. Jelölje $m_i$ és $M_i$ az optimális célfüggvényértékeket.

%\vspace{4 mm}
%\underline{2.Lépés}. Oldjuk meg az
%$$\sum_{i=1}^I \alpha_i \overline{f_i} \longrightarrow max  \mspace{40mu} (x \in X)$$
%optimum problémát.

\index{weighting method|)}

\subsection{Distance-dependent methods}
\index{distance-dependent methods|(}

If we normalize the objective functions, the certain normalized objective functions most favorable value is 1 and  
the most unfavourable is 0. So that $\mathbf{1}=(1,1,\dots,1)$ is the ideal point \index{ideal point} and
$\mathbf{0}=(0,0,\dots,0)$ is the worst yield vector.

In the case of distance-dependent methods we either want to get nearest to the vector $\mathbf{1}$ or get farthest from
the point $\mathbf{0}$, so that we solve either the 
\begin{equation}\label{eq10}
\varrho(\mathbf{f}(x),\mathbf{1}) \longrightarrow min  \mspace{40mu} (x \in X)
\end{equation}
or the
\begin{equation}\label{eq11}
\varrho(\mathbf{f}(x),\mathbf{0}) \longrightarrow max  \mspace{40mu} (x \in X)
\end{equation}
problem, where $\varrho$ denotes some distance function in $\R^I$.

In practical applications the following distance functions are used most frequently:
\begin{equation}\label{eq12}
\varrho_1(\mathbf{a},\mathbf{b})=\sum_{i=1}^I \alpha_i |a_i-b_i|
\end{equation}
\begin{equation}\label{eq13}
\varrho_2(\mathbf{a},\mathbf{b})=\left( \sum_{i=1}^I \alpha_i |a_i-b_i|^2 \right)^\frac{1}{2}
\end{equation}
\begin{equation}\label{eq14}
\varrho_\infty(\mathbf{a},\mathbf{b})=\max_i \{ \alpha_i |a_i-b_i| \}
\end{equation}
\begin{equation}\label{eq15}
\varrho_g(\mathbf{a},\mathbf{b})=\prod_{i=1}^I |a_i-b_i|^{\alpha_i} \koz .
\end{equation}
The $\varrho_1, \varrho_1, \varrho_\infty$ distance functions the commonly known Minkowski 
\nevindex{Minkowski, Hermann (1864--1909)} 
distance for $p = 1,2,\infty$. The $\varrho_g$ geometric distance doesn't satisfy the usual requirements of distance functions however, it is frequently used in practice. As we will see it later, Nash's 
\nevindex{Nash, John Forbes} 
classical conflict resolution algorithm uses the geometric distance as well.
It is easy to prove that the methods using the $\varrho_1$ distance are equivalent of the weighting method.
Notice firstly that
\begin{equation}\label{eq16}
\varrho_1(\mathbf{f}(x),\mathbf{1})=\sum_{i=1}^I \alpha_i |f_i(x)-1|=\sum_{i=1}^I \alpha_i |1-f_i(x)|=\sum_{i=1}^I \alpha_i-\sum_{i=1}^I \alpha_i f_i(x) \koz ,
\end{equation}
where the first term is constant, while the second term is the objective function of the weighting method.
Similarly,
\begin{equation}\label{eq17}
\varrho_1(\mathbf{f}(x),\mathbf{0})=\sum_{i=1}^I \alpha_i |f_i(x)-0|=\sum_{i=1}^I \alpha_i (f_i(x)-0)=\sum_{i=1}^I \alpha_i f_i(x)
\end{equation}
which is the objective function of the weighting method.

The method is illustrated in Figures \ref{fig:abra3a}. and \ref{fig:abra3b}.

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.40]{5.3-a.eps}
\caption{Minimizing distance.\label{fig:abra3a}}
\end{center}
\end{figure}

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.40]{5.3-b.eps}
\caption{Maximizing distance.\label{fig:abra3b}}
\end{center}
\end{figure}

%\epskep{5.3-a}{Távolság minimalizálás.\label{fig:abra3a}}
%\epskep{5.3-b}{Távolság maximalizálás.\label{fig:abra3b}}

\begin{pelda}
Consider again the problem of the previous example. The normalized consequences are shown by Figure \ref{fig:abra4}.
The two coordinates are:
$$\overline{f_1}=\frac{f_1}{2} \mspace{10mu} \mbox{and} \mspace{10mu} \overline{f_2}=\frac{f_2+1}{2} \koz .$$

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.4.eps}
\caption{The image of the normalized set $H$.\label{fig:abra4}}
\end{center}
\end{figure}

%\epskep{5.4}{A normált $H$ halmaz képe.\label{fig:abra4}}

Choosing the $\alpha_1=\alpha_2=\frac{1}{2}$ and the $\varrho_2$ distances, the nearest point of  $\overline{H}$ to the ideal point is $$\overline{f_1}=\frac{3}{5}, \overline{f_2}=\frac{4}{5} \koz .$$
Hence
$$f_1=2\overline{f_1}=2x_1+x_2=\frac{6}{5}  \mspace{10mu} \mbox{and} \mspace{10mu} f_2=2\overline{f_1}-1=-x_1+x_2=\frac{3}{5} \koz ,$$
that is the optimal decision is:
$$x_1=\frac{1}{5}, x_2=\frac{4}{5}, 1-x_1-x_2=0 \koz .$$

Therefore only the first two technology must be chosen in 20\% and 80\% proportion.

Let's choose again equivalent weights ($\alpha_1=\alpha_2=\frac{1}{2}$) and the $\varrho_2$ distance, but look for
the farthest point  of $\overline{H}$ from the ideal worst point. We can see from Figure \ref{fig:abra3b}, that the solution is
$$\overline{f_1}=\frac{f_1}{2}, \overline{f_2}=1 \koz ,$$
so
$$f_1=2\overline{f_1}=1, f_2=2\overline{f_2}-1=1 \koz .$$
Thus the optimal decision is: $x_1=0$ and $x_2=1$
\end{pelda}

The formal algorithm is as follows: 

\begin{algN}{Distance-Dependent-Method$(\mathbf{\varrho}, \mathbf{f})$}\inddef{\textsc{Distance-Dependent-Method}}
1 \' \key{for} \= $i \leftarrow 1$ \key{to} $I$ \\
2 \'        \>     \key{do} $m_i \leftarrow (f_i(x) \longrightarrow min)$\\
3 \'        \>    \> $M_i \leftarrow (f_i(x) \longrightarrow max)$\\
4 \'        \>     \> $\overline{f_i}(x) \leftarrow (f_i(x)-m_i)/(M_i-m_i)$\\
5 \'  $k \leftarrow (\varrho(\overline{\mathbf{f}}(x),\mathbf{1}) \longrightarrow min)$ or 
$k \leftarrow (\varrho(\overline{\mathbf{f}}(x),\mathbf{0}) \longrightarrow max)$\\
6 \' \key{return} $k$
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. $i=1,2,\dots,I$ esetére oldjuk meg az $$f_i(x) \longrightarrow min \mspace{40mu} (x \in X)$$
%és az
% $$f_i(x) \longrightarrow max \mspace{40mu} (x \in X)$$
%feladatokat. Jelölje $m_i$ és $M_i$ az optimális célfüggvényértékeket.
%
%\vspace{4 mm}
%\underline{2.Lépés}. $i=1,2,\dots,I$ esetére oldjuk meg az $$\overline{f_i}(x)=\frac{f_i(x)-m_i}{M_i-m_i}$$
%normált célfüggvényeket.
%
%\vspace{4 mm}
%\underline{3.Lépés}. Oldjuk meg az
%$$\varrho(\overline{\mathbf{f}}(x),\mathbf{1}) \longrightarrow min 
%\mspace{10mu} \mbox{vagy} \mspace{10mu}
%\varrho(\overline{\mathbf{f}}(x),\mathbf{0}) \longrightarrow max
% \mspace{40mu} (x \in X)$$
%optimumfeladatot.

\index{Distance-dependent methods|)}

\subsection{Direction-dependent methods}
\index{direction-dependent methods|(}

Assume that we have a $\mathbf{f_*}$ point in set $H$, on which we'd like to improve.
$\mathbf{f_*}$ denotes the present position, on which the decision maker wants to improve, or at design level
we can choose the worst point for the starting one. Furthermore, we assume that the decision maker gives an
improvement direction vector, which is denoted by $\mathbf{v}$. 
After that, the task is to reach the farthest possible point in set $H$ starting from $\mathbf{f_*}$ along the $\mathbf{v}$ direction vector. Thus, mathematically we solve the
\begin{equation}\label{eq18}
t \longrightarrow max \mspace{40mu} (\mathbf{f_*} + t \mathbf{v} \in H)
\end{equation}
optimum task, and the related decision is given by the solution of the
\begin{equation}\label{eq19}
\mathbf{f}(x) = \mathbf{f_*}+ t \mathbf{v}
\end{equation}
equation under the optimal $t$ value. The method is illustrated in Figure \ref{fig:abra5}.

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.5.eps}
\caption{Direction-dependent methods.\label{fig:abra5}}
\end{center}
\end{figure}

%\epskep{5.5}{Irányfüggõ módszerek.\label{fig:abra5}}

\begin{pelda}\label{ex6}
Let's consider again the problem of Example \ref{ex2}, and assume that $\mathbf{f_*}=(0,-1)$, which contains the worst
possible objective function values in its components. If we want to improve the objective functions equally, we have to
choose  $\mathbf{v}=(1,1)$. The graphical solution is illustrated in Figure \ref{fig:abra6}, that 
$$f_1=\frac{4}{3} \mspace{10mu} \mbox{and} \mspace{10mu} f_2=\frac{1}{3} \koz ,$$
so the appropriate values of the decision variables are the following:  
$$x_1=\frac{1}{3} \mspace{10mu} \mbox{és} \mspace{10mu} x_2=\frac{2}{3} \koz .$$
\end{pelda}

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.6.eps}
\caption{The graphical solution of Example \ref{ex6}\label{fig:abra6}}
\end{center}
\end{figure}

%\epskep{5.6}{A \ref{ex6} példa grafikus megoldása.\label{fig:abra6}}

A very rarely used variant of the method is when we diminishes the object function values systematically starting from an unreachable ideal point until a possible solution is given. If  $\mathbf{f^*}$ denotes this ideal point, the  (\ref{eq18})
optimum task is modified as follows:
\begin{equation}\label{eq20}
t \longrightarrow min \mspace{40mu} (\mathbf{f^*} - t \mathbf{v} \in H)
\end{equation}
and the appropriate decision is given by the solution of the   
\begin{equation}\label{eq21}
\mathbf{f} = \mathbf{f^*} - t \mathbf{v}
\end{equation}
equation.

\begin{pelda}\label{ex7}
To return to the previous example, consider again that $\mathbf{f^*} =(2,1)$ and $\mathbf{v}=(1,1)$, that is we want to
diminish the object functions equally. Figure \ref{fig:abra7} shows the graphical solution of the problem, in which we can see 
that the given solution is the same as the solution of the previous example. 
\end{pelda}

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.7.eps}
\caption{The graphical solution of Example \ref{ex7}\label{fig:abra7}}
\end{center}
\end{figure}

%\epskep{5.7}{A \ref{ex7} példa grafikus megoldása.\label{fig:abra7}}

Applying the method is to solve the (\ref{eq18}) or the (\ref{eq20}) optimum tasks, and the optimal decision is given by
the solution of the (\ref{eq19}) or the (\ref{eq21}) equations.

\begin{gyak}
\ujgyak \label{jat1.1}
Determine the consequence space $H$ for the following exercise:
$$x_1+x_2 \longrightarrow max \mspace{40mu} x_1-x_2 \longrightarrow max$$
provided that
\begin{eqnarray*}
x_1, x_2 & \geq & 0  \\
3x_1+ x_2 & \leq & 3 \\
x_1+ 3x_2 & \leq & 3 \koz .
\end{eqnarray*}
\ujgyak \label{jat1.2}
Consider the utility functions of the decision maker: $u_1(f_1)=f_1$ és $u_2(f_2)=\frac{1}{2}f_2$.
Furthermore, assume that the decision maker gave the $u(0,0)=0, u(1,0)=u(0,1)=\frac{1}{2}$ values.
Determine the form of the aggregate utility function.
\ujgyak \label{jat1.3}
Solve Exercise \ref{jat1.1} using the weighting-method without normalizing the objective functions.
Choose the $\alpha_1=\alpha_2=\frac{1}{2}$ weights.
\ujgyak \label{jat1.4}
Repeat the previous exercise, but do normalize the objective functions.
\ujgyak \label{jat1.5}
Solve Exercise \ref{jat1.1} with normalized objective functions, $\alpha_1=\alpha_2=\frac{1}{2}$ weights and
minimizing the 
\begin{enumerate}[(i)]
\item $\varrho_1$ distance
\item $\varrho_2$ distance
\item $\varrho_{\infty}$distance.
\end{enumerate}
\ujgyak \label{jat1.6}
Repeat the previous exercise, but maximize the distance from the $\mathbf{0}$ vector instead of minimizing it.
\ujgyak \label{jat1.7}
Solve Exercise \ref{jat1.1} using the direction-dependent method, choosing  $\mathbf{f}_*=(0,-1)$ and $\mathbf{v}=(1,1)$.
\ujgyak \label{jat1.8}
Repeat the previous exercise, but this time choose $\mathbf{f}_*=(\frac{3}{2},1)$ and $\mathbf{v}=(1,1)$.
\end{gyak}

\index{direction-dependent methods|)}

\section{Method of equilibrium}\label{sec2}
\index{method of equilibrium|(}

In this chapter we assume that $I$ decision makers interested in the selection of a mutual decision alternative.
Let $f_i:X \mapsto \R$ denote the objective function of the $i$th decision maker, which is also called payoff function in
the game theory literature. Depending on the decision makers relationship to each other we can speak about
cooperative and non-cooperative games. In the first case the decision makers care about only their own benefits,
while in the second case they strive for an agreement when every one of them are better off than in the non-cooperative case.
In this chapter we will discuss the non-cooperative case, while the cooperative case will be topic of the next chapter.

Let's denote $H_i(x)$ for $i=1,2,\dots,I$ and $x \in X$, the set of the decision alternatives into which the 
$i$th decision maker can move over without the others' support. Evidently $H_i(x) \subseteq X$.

\begin{defi}
An $x^* \in X$ alternative is equilibrium\inddef{equilibrium} if for all $i$ and $x \in H_i(x^*)$,
\begin{equation}\label{eq22}
f_i(x) \leq f_i(x^*) \koz .
\end{equation}
\end{defi}

This definition can also be formulated that $x^*$  is stable in the sense that none of the decision makers can change 
the decision alternative from $x^*$ alone to change any objective function value for the better.
In the case of non-cooperative games, the equilibrium are the solutions of the game.

For any $x \in X$ and $i$ decision maker, the set
\begin{equation}\label{eq23}
L_i(x) = \{z | z \in H_i(x) \mspace{10mu} \mbox{and for all} \mspace{10mu} y \in H_i(x)
\mbox{,} \mspace{10mu} f_i(z) \geq f_i(y) \}
\end{equation}
is called the set of the best answers of the $i$th decision maker to alternative $x$.
It is clear that the elements of $L_i(x)$ are those alternatives which the $i$th decision maker can move over from $x$,
and which ensure the best objective functions out of all the possible alternatives.
According to inequality (\ref{eq22}) it is also clear that $x^*$ is an equilibrium if and only if for all $i=1,2,\dots,I$,
$x^* \in L_i(x^*)$, that is $x^*$ is mutual fixed point of the $L_i$ point-to-set maps.
Thus, the existence of equilibrium can be traced to the existence of mutual fixed point of point-to-set maps, so
the problem can be solved by the usual methods.

It is a very common case when the collective decision is made up by the personal decisions of the certain decision makers.
Let $X_i$ denote the set of the $i$th decision maker's alternatives, let $x_i \in X_i$ be the concrete alternatives, and let
$f_i(x_1,\dots,x_I)$ be the objective function of the $i$th decision maker.
That is the collective decision is $x=(x_1,\dots,x_I)\in X_1 \times X_2 \times \dots \times X_I = X$.
In this case 
$$H_i(x_1,\dots,x_I)=\{(x_1,\dots,x_{i-1},z_i,x_{i+1},\dots,x_I)|z_i \in X_i \}$$
and the (\ref{eq22}) definition of equilibrium is modified as follows:
\begin{equation}\label{eq24}
f_i(x_1^*,\dots,x_{i-1}^*,x_i,x_{i+1}^*,\dots,x_I^*) \leq f_i(x_i^*,\dots,x_I^*) \koz .
\end{equation}
In the game theory literature the equilibrium is also called \ki{Nash-equilibrium.}\inddef{Nash-equilibrium}

The existence of an equilibrium is not guaranteed in general. To illustrate this let's consider the $I=2$ case,
when both decision makers can choose between to alternatives: $X_1=\{1,2\}$ and $X_2=\{1,2\}$. 
The objective function values are shown in Figure \ref{fig:tbl2}, where the the first number in the
parentheses shows the first, the second number shows the second decision maker's objective function value.
If equilibrium exists, it might not be unique, what can be proved by the case of constant
objective functions, when every decision alternative is an equilibrium.

\begin{figure}[!t]
$$
\begin{tabular}{|r|cc|}
\hline
& \multicolumn{2}{|c|}{$i=2$} \\
& 1 & 2 \\
\hline $i=1$ $\begin{array}{r}
\textup{1} \\
\textup{2}
\end{array}$ &
$\begin{array}{c}
(1,2) \\
(2,4)
\end{array}$ &
$\begin{array}{c}
(2,1) \\
(0,5)
\end{array}$ \\
\hline
\end{tabular}
$$
\caption{\label{fig:tbl2} Game with no equilibrium.}
\end{figure}

If the $X_1,\dots,X_I$ sets are finite, the equilibrium can be found easily by the method of reckoning,
when we check for all of the $\mathbf{x}=(x_1,\dots,x_I)$ decision vectors whether the component 
$x_i$ can be changed for the better of the $f_i$ objective function.
If the answer is yes, $\mathbf{x}$ is not equilibrium. If none of the components can be changed 
in such manner,  $\mathbf{x}$ is equilibrium. For the formal algorithm, let's assume that $X_1=\{1,2,\dots,n_i\}$.

\begin{algN}{Equilibrium-Search}\inddef{\textsc{Equilibrium-Search}}
1 \' \key{for} \= $i_1 \leftarrow 1$ \key{to} $n_1$ \\
2 \'           \> \key{do} \key{for} \= $i_2 \leftarrow 1$ \key{to} $n_2$\\
3 \'   \>   \>  $\ddots$ \\
4 \'          \>          \>                             \>  \key{do} \=  \key{for} $i_I \leftarrow 1$ \key{to} $n_I$ \\
5 \'   \>     \>      \>          \> \key{do} \textit{key} $\leftarrow 0$\\
6 \'   \>   \>  \>   \>   \key{for} \= $k \leftarrow 1$ \key{to} $n$\\
7 \'   \>   \>  \>   \>             \> \key{do} \key{for} \= $j \leftarrow 1$ \key{to} $n_k$ \\
8 \'   \>   \>  \>   \>             \>                    \>  \key{do} \key{if} \= $f_k(i_1,\dots,i_{k-1},j,i_{k+1},\dots,i_I) > f(i_1,\dots,i_I)$ \\
9 \'   \>   \>  \>   \>             \>                    \>                    \> \key{then}
\textit{key} $\leftarrow 1$ and go to 10 \\
10 \'   \>   \>  \>   \>   \key{if} \> $key=0$ \\
11 \'   \>   \>  \>   \>            \>  \key{then} \= $(i_1,\dots,i_I)$  is equilibrium
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. 
%\begin{eqnarray*}
%i_1&=&1,2,\dots,n_1 \\
%i_2&=&1,2,\dots,n_2 \\
%\vdots & & \\
%i_I&=&1,2,\dots,n_I
%\end{eqnarray*}
%
%\vspace{4 mm}
%\underline{2.Lépés}. 
%\begin{eqnarray*}
%k&=&1,2,\dots,n \\
%j&=&1,2,\dots,n_k 
%\end{eqnarray*}
%Ha $f_k(i_1,\dots,i_{k-1},j,i_{k+1},\dots,i_I) > f(i_1,\dots,i_I)$, akkor $(i_1,\dots,i_I)$ nem egyensúlypont és menjünk
%vissza az 1.Lépés ciklusába. Különben folytassuk a ciklust $k$ és $j$ szerint. Ha ez befejezõdött, menjünk a 
%1.Lépésre.
%
%\vspace{4 mm}
%\underline{3.Lépés}.  $(i_1,\dots,i_I)$ egyensúlypont, írassuk ki. Menjünk vissza az 1.Lépés ciklusába. Ha ez is befejezõdött, az %eljárás véget ér.
%
%\vspace{4 mm}

The existence of equilibrium is guaranteed by the following theorem.

\begin{tetel}\label{theorem2}
Assume that for all $i=1,2,\dots,I$
\begin{enumerate}
\item[(i)] $X_i$ is convex, bounded and closed in a final dimensional Euclidean space;
\item[(ii)] $f_i$ is continuous on the set $X$;
\item[(iii)] for any fixed $x_1,\dots,x_{i-1},x_{i+1},\dots,x_I$, $f_i$ is concave in $x_i$.
\end{enumerate}
Then there is at least one equilibrium.
\end{tetel}

Determination of the equilibrium is usually based on the observation that for all $i$, $x_i^*$ is the solution of the
\begin{equation}\label{eq25}
f_i(x_1^*,\dots,x_{i-1}^*,x_i,x_{i+1}^*,\dots,x_I^*) \longrightarrow max \mspace{40mu} (x_i \in X_i)
\end{equation}
optimum task. Writing the necessary conditions of the optimal solution (for example the Kuhn-Tucker conditions)
\nevindex{Kuhn, Harold William}\nevindex{Tucker, Albert William (1905--1995)} 
we can get an equality-inequality system which solutions include the equilibrium.
To illustrate this method let's assume that $$X_i=\{x_i | g_i(x_i) \geq 0\}$$ where $x_i$ is a finite dimensional 
vector and $g_i$ is a vector-valued function.
In this way (\ref{eq25}) can be rewritten as follows:
\begin{equation}\label{eq26}
f_i(x_1^*,\dots,x_{i-1}^*,x_i,x_{i+1}^*,\dots,x_I^*) \longrightarrow max \mspace{40mu} (g_i(x_i) \geq 0) \koz .
\end{equation}
In this case the Kuhn-Tucker necessary conditions are: 
\begin{equation}\label{eq27}
\begin{array}{rcl}
u_i  & \geq & 0 \\
g_i(x_i)  & \geq &  0 \\
\nabla_i f_i(x)+u_i^T \nabla_i g_i(x_i)&=&0^T \\
u_i^T g_i(x_i)&=&0 \koz ,
\end{array}
\end{equation}
where $\nabla_i$ denotes the gradient at $x_i$, and $u_i$ is a vector which has the same length as $g_i$.
If we formulate the (\ref{eq27}) conditions for $i=1,2,\dots,I$, we get an equality-inequality system which can be 
solved by computer methods. It is easy to see that (\ref{eq27}) can also be rewritten to an nonlinear optimization task:

\begin{equation}\label{eq28}
\begin{array}{rcl}
\sum_{i=1}^I u_i^T g_i(x_i) & \longrightarrow & min \\
u_i  & \geq & 0  \\
g_i(x_i) & \geq  & 0  \\
\nabla_i f_i(x)+u_i^T \nabla_i g_i(x_i)&=&0^T \koz .
\end{array}
\end{equation}
If the optimal objective function value is positive, the (\ref{eq27}) system doesn't have a solution, and if the optimal objective
function value is zero, any optimal solution is also a solution of the (\ref{eq27}) system, so the equilibrium are among the
optimal solutions. We know about the sufficiency of the Kuhn-Tucker conditions that if $f_i$ is concave in $x_i$ with all $i$,
the Kuhn-Tucker conditions are also sufficient, thus every solution of (\ref{eq27}) gives an equilibrium. 

The formal algorithm is as follows: 

\begin{algN}{Kuhn--Tucker-Equilibrium}\inddef{\textsc{Kuhn--Tucker-Equilibrium}}
1 \' \key{for} \= $i \leftarrow 1$ \key{to} $I$ \\
2 \'        \>     \key{do} $\mathbf{g_i} \leftarrow \nabla_i f_i$\\
3 \'        \>    \> $\mathbf{J_i} \leftarrow \nabla_i g_i(x_i)$\\
4 \'   $(x_1,\dots,x_I) \leftarrow $ the solution of the (\ref{eq28}) optimum task\\
5 \'   \key{if} \= $\sum_{i=1}^I u_i^T g_i(x_i) > 0$ \\
6 \'   \>   \key{then} \> \> \key{return} "there is no equilibrium"\\
7 \' \> \key{else} \> \> \key{return} ($x_1,\dots,x_I$)
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. Határozzuk meg a $\nabla_i f_i$ gradiensvektorokat és a $\nabla_i g_i(x_i)$ Jacobi mátrixokat
%$i=1,2,\dots,I$ esetén.
%
%\vspace{4 mm}
%\underline{2.Lépés}. Oldjuk meg a (\ref{eq28}) optimumfeladatot. 
%
%\vspace{4 mm}
%\underline{3.Lépés}. Ha az optimális célfüggvényérték pozitív, akkor a játéknak nincs egyensúlypontja, különben az 
%egyensúlypontokat az $(x_1,\dots,x_I)$ megoldások adják.

\begin{pelda}
Assume that $I$ production plant produce some water purification device sold into households.
Let $x_i$ denote the quantity produced by the $i$th production plant, let $c_i(x_i)$ be the cost function of it,
and let $p(\sum_{j=1}^I x_j)$ be the sale price, which depends on the total quantity to be put on the market.
Furthermore, be $L_i$ is the capacity of the $i$th production plant.
Thus, the possible $X_i$ decision set is the $[0,L_i]$ closed interval, which can be defined by the 
\begin{equation}\label{eq29}
\begin{array}{rcl}
x_i  & \geq & 0  \\
L_i-x_i & \geq  & 0
\end{array}
\end{equation}
conditions, so $$g_i(x_i)=\binom{x_i}{L_i - x_i} \koz .$$ The objective function of the $i$th production plant is the profit of that:
\begin{equation}\label{eq30}
f_i(x_1,\dots,x_n) = x_i p(x_1+\dots+x_n)-c_i(x_i) \koz .
\end{equation}

Since $g_i(x_i)$ is two-dimensional, $u_i$ is a two-element vector as well, and the (\ref{eq28}) optimum task has the
following form:
\begin{equation}\label{eq31}
\begin{array}{rcl}
\sum_{i=1}^I (u_i^{(1)}x_i + u_i^{(2)}(L_i-x_i)) & \longrightarrow & min \\
u_i^{(1)}, u_i^{(2)} & \geq & 0 \\
x_i  & \geq &  0 \\
L_i-x_i  & \geq &  0 \\
p (\sum_{j=1}^I x_j ) + x_i p'(\sum_{j=1}^I x_j)-c'_i(x_i)+(u_i^{(1)}, u_i^{(2)})\binom{1}{-1}&=&0 \koz .
\end{array}
\end{equation}
Let's introduce the $\alpha_i=u_i^{(1)}-u_i^{(2)}$ new variables, and for the sake of notational convenience be
$\beta_i=u_i^{(2)}$, then taking account of the last condition, we get the following problem:
\begin{equation}\label{eq32}
\begin{array}{rcl}
\sum_{i=1}^I(-x_i(p(\sum_{j=1}^I x_j)+x_i p'(\sum_{j=1}^I x_j) -c'_i(x_i))+\beta_i L_i) & \longrightarrow & min \\
\beta_i & \geq & 0 \\
x_i & \geq & 0 \\
x_i & \leq & L_i \koz .
\end{array}
\end{equation}
Let's notice that in case of optimum $\beta_i=0$, so the last term of the objective function can be neglected.

Consider the special case of $I=3$, $c_i(x_i)=i x_i^3+x_i$, $L_i=1$, $p(s)=2-2s-s^3$. The (\ref{eq32}) problem 
is now simplified as follows:
\begin{equation}\label{eq33}
\begin{array}{rcl}
\sum_{i=1}^3 x_i(2-2s-s^2-2x_i-2x_i s-3i x_i^2-1) & \longrightarrow & max \\
x_i & \geq & 0 \\
x_i & \leq & 1 \\
x_1+x_2+x_3 & = & s \koz .
\end{array}
\end{equation}
Using a simple computer program we can get the optimal solution:
$$ x_1^*=0.1077, x_2^*=0.0986, x_3^*=0.0919 \koz ,$$
which is the equilibrium as well.
\end{pelda}

\begin{gyak}
\ujgyak \label{jat2.1}
Let $I=2$, $X_1=X_2=[0,1]$, $f_1(x_1,x_2)=x_1+x_2-x_1^2$, $f_2(x_1,x_2)=x_1+x_2-x_2^2$. Formulate the (\ref{eq27})
conditions and solve them as well.
\ujgyak \label{jat2.2}
Formulate and solve the optimum problem (\ref{eq28}) for the previous exercise.
\ujgyak \label{jat2.3}
Let again $I=2$. $X_1=X_2=[-1,1]$, $f_1(x_1,x_2)=-(x_1+x_2)^2+x_1+2x_2$, $f_2(x_1,x_2)=-(x_1+x_2)^2+2x_1+x_2$. 
Repeat Exercise \ref{jat2.1}.
\ujgyak \label{jat2.4}
Repeat Exercise \ref{jat2.2} for the problem given in the previous exercise.
\end{gyak}

\index{method of equilibrium|)}

\section{Methods of cooperative games}\label{sec3}
\index{methods of cooperative games|(}

Similarly to the previous chapter let $X_i$ denote again the decision set of the $i$th decision maker and let 
$x_i \in X_i$ be the concrete decision alternatives. Furthermore, let $f_i(x_1,\dots,x_I)$ denote the objective
function of the $i$th decision maker. Let $S$ be some subset of the decision makers, which  is 
usually called \ki{coalition}\inddef{coalition} in the game theory.
For arbitrary $S\subseteq \{1,2,\dots,I\}$, let's introduce the
\begin{equation}\label{eq34}
v(S)=\max_{x_i \in X_i} \min_{x_j \in X_j} \sum_{k\in S} f_k(x_1,\dots,x_I) \mspace{40mu} (i\in S, j \notin S)
\end{equation}
function, which is also called the characteristic function defined on all of the subsets of the set $\{1,2,\dots,I\}$, if we
add the $v(\emptyset  )=0$ and
$$v(\{1,2,\dots,I\}) = \max_{x_i \in X_i} \sum_{k=1}^I f_k(x_1,\dots,x_I) \mspace{40mu} (1 \leq i \leq I)$$
special cases to definition (\ref{eq34}).

Consider again that all of the $X_i$ sets are finite for $X_i=\{1,2,\dots,n_i\}  \koz , \koz  i=1,2,\dots,I$.
Be $S$ a coalition. The value of $v(S)$ is given by the following algorithm, where $|S|$ denotes the number of 
elements of $S$, $k_1,k_2,\dots,k_{|S|}$ denotes the elements and $l_1,l_2,\dots,l_{I-|S|}$ the elements	
which are not in $S$.

\begin{algN}{Characteristic-Function($S$)}\inddef{\textsc{Characteristic-Function}}
1 \' $v(S) \leftarrow -M$,  where $M$ a very big positive number \\
2 \' \key{for} \= $i_1 \leftarrow 1$ \key{to} $n_{k_1}$ \\
3 \'  \>  $\ddots$ \\
4 \'                               \>  \key{do} \=  \key{for} $i_{|S|} \leftarrow 1$ \key{to} $n_{k_{|S|}}$ \\
5 \'                                  \>  \>  \> \key{do} \key{for} \= $j_1\leftarrow 1$ \key{to} $n_{l_1}$ \\
6 \'  \> \> \>  \>  $\ddots$ \\
7 \'  \> \>  \> \>  \> \key{do} \=  \key{for} $j_{I-|S|} \leftarrow 1$ \key{to} $n_{l_{I-|S|}}$ \\
8 \' \> \>  \> \>  \> \> \> \key{do} $Z \leftarrow M$,  where $M$ a very big positive number \\
9 \' \> \>  \> \>  \> \> \>\> $V \leftarrow\sum_{t=1}^{|S|} f_{i_t}(i_1,\dots,i_{|S|},j_1,\dots,j_{I-|S|})$ \\
10 \' \> \>  \> \>  \> \> \>\> \key{if} \> $V< Z$ \\
11 \' \> \>  \> \>  \> \> \>\> \>  \key{then}  $Z \leftarrow V$ \\
12 \'  \> \>\> \key{if} \> $Z > v(S)$ \\
13 \' \> \>\> \> \key{then}  $v(S) \leftarrow Z$ \\
14 \'  \key{return} $v(S)$
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. $v(S)=-M$, ahol $M$ egy nagyon nagy pozitív szám.
%
%\vspace{4 mm}
%\underline{2.Lépés}. 
%\begin{eqnarray*}
%i_1&=&1,2,\dots,n_{k_1} \\
%i_2&=&1,2,\dots,n_{k_2} \\
%\vdots & & \\
%i_{|S|}&=&1,2,\dots,n_{k_{|S|}}
%\end{eqnarray*}
%
%\vspace{4 mm}
%\underline{3.Lépés}. 
%\begin{eqnarray*}
%j_1&=&1,2,\dots,n_{l_1} \\
%j_2&=&1,2,\dots,n_{l_2} \\
%\vdots & & \\
%j_{I-|S|}&=&1,2,\dots,n_{l_{I-|S|}}
%\end{eqnarray*}
%
%\vspace{4 mm}
%\underline{4.Lépés}. $Z=M$, ahol $M$ egy nagyon nagy pozitív szám. Számítsuk ki a
%$$V=\sum_{t=1}^{|S|} f_{i_t}(i_1,\dots,i_{|S|},j_1,\dots,j_{I-|S|})$$
%értékét.
%Ha $V<Z$, legyen $Z=V$, különben $Z$ értéke változatlan marad. A $j_1,\dots,j_{I-|S|}$ ciklusok befejeztével
%menj a következõ lépésre.
%
%\vspace{4 mm}
%\underline{5.Lépés}. Ha $Z>v(S)$, akkor legyen $v(S)=Z$, különben $v(S)$ értéke változatlan marad. A $i_1,\dots,i_{|S|}$
%ciklusok befejeztével $v(S)$ értéke adja a karakterisztikus függvény értékét az $S$ koalíción.

\begin{pelda}
Let's return to the problem discussed in the previous example, and assume that $I=3$, $L_i=3$,
$p(\sum_{i=1}^I x_i)= 10-\sum_{i=1}^I x_i$ és $c_i(x_i)=x_i+1$ for $ i=1,2,3$.
Since the cost functions are identical, the objective functions are identical as well:
$$f_i(x_1,x_2,x_3)=x_i(10-x_1-x_2-x_3)-(x_i+1) \koz .$$
In the following we determine the characteristic function. At first be $S=\{i\}$, then
$$v(S)=\max_{x_i} \min_{x_j} \{x_i(10-x_1-x_2-x_3)-(x_i+1)\} \mspace{40mu} (j\neq i) \koz .$$
Since the function strictly decreases in the $x_j (i\neq j)$ variables, the minimal value of it is given at $x_j=3$, so
$$v(S)=\max_{i} x_i(4-x_i)-(x_i+1)=\max_{0\leq x_i \leq 3} (-x_i^2+3x_i-1)=\frac{5}{4} \koz ,$$
what is easy to see by plain differentiation. Similarly for  $S=\{i,j\}$
$$v(S)=\max_{i,j} \min_{k\neq i,j} \{(x_i+x_j)(10-x_1-x_2-x_3)-(x_i+1)-(x_j+1)\} \koz .$$
Similarly to the previous case the minimal value is given at $x_k=3$, so
$$v(S)=\max_{0\leq x_i,x_j \leq 3} \{(x_i+x_j)(7-x_i-x_j)-(x_i+x_j+2)\}\\=\max_{0\leq x \leq 6}\{x(7-x)-(x+2)\}=$$
$$=\max_{0\leq x \leq 6}\{-x^2+6x-2\}=7$$
where we introduced the new $x=x_i+x_j$ variable. In the case of $S=\{1,2,3\}$
$$v(S)=\max_{0\leq x_1,x_2,x_3 \leq 3} \{ (x_1+x_2+x_3)(10-x_1-x_2-x_3)-(x_1+1)-(x_2+1)-(x_3+1)\}= $$
$$=\max_{0\leq x \leq 9} \{x(10-x)-(x+3)\}=\max_{0\leq x \leq 9} \{-x^2+9x-3)\}=17.25 \koz ,$$
where this time we introduced the $x=x_1+x_2+x_3$ variable.
\end{pelda}

Definition (\ref{eq34}) can be interpreted in a way that the $v(S)$ characteristic function value gives the
\ki{guaranteed} aggregate objective function value\inddef{guaranteed aggregate objective function value}
of the $S$ coalition regardless of the behavior of the others. The central issue of the theory and practice of
the cooperative games is how should the certain decision makers share in the maximal aggregate profit 
$v(\{1,2,\dots,I\})$ attainable together. An $(\phi_1, \phi_2, \dots, \phi_I)$ division is usually called \ki{imputation},
\inddef{imputation} if
\begin{equation}\label{eq35}
\phi_i \geq v(\{i\})
\end{equation}
for $i=1,2,\dots,I$ and
\begin{equation}\label{eq36}
\sum_{i=1}^I \phi_i=v(\{1,2,\dots,I\}) \koz .
\end{equation}

The inequality system (\ref{eq35})--(\ref{eq36}) is usually satisfied by infinite number of imputations, so we have to
specify additional conditions in order to select one special element of the imputation set.
We can run into a similar situation while discussing the multi-objective programming, when we looks for a special
Pareto optimal solution using the concrete methods.

\begin{pelda}
In the previous case a $(\phi_1,\phi_2,\phi_3)$ vector is imputation if
\begin{eqnarray*}
\phi_1,\phi_2,\phi_3 &\geq& 1.25 \\
\phi_1+\phi_2,\phi_1+\phi_3,\phi_2+\phi_3  &\geq& 7 \\
\phi_1+\phi_2+\phi_3 & = & 17.2 \koz .
\end{eqnarray*}
\end{pelda}

The most popular solving approach is the \ki{Shapley value,}\inddef{Shapley value}\index{Shapley value}
\nevindex{Shapley, Lloyd Stowell} 
which can be defined as follows:
\begin{equation}\label{eq37}
\phi_i=\sum_{S\subseteq \{1,2,\dots,I\}} \frac{(s-1)!(I-s)!}{I!}(v(S)-v(S-\{i\})) \koz ,
\end{equation}
where $s$ denotes the number of elements of the $S$ coalition.

Let's assume again that the decision makers are fully cooperating, that is they formulate the coalition \{1,2,\dots,I\}, and
the certain decision makers join to the coalition in random order. The difference $v(S)-v(S-\{i\})$ indicates the contribution to the $S$
coalition by the $i$th decision maker, while expression (\ref{eq37}) indicates the average contribution of the same decision maker.
It can be shown that $(\phi_1, \phi_2, \dots, \phi_I)$ is an imputation.

The Shapley value can be computed by following algorithm:

\begin{algN}{Shapley-Value}\inddef{\textsc{Shapley-Value}}
1 \' \key{for} \= $\forall S \subseteq \{1,\dots,I\}$ \\
2 \'  \>   \key{do} $v(S) \leftarrow $ \textsc{Characteristic-Function}($S$) \\
3 \' \key{for} \= $i \leftarrow 1$ \key{to} $I$ \\
4 \'                               \>  \key{do} \=  use (\ref{eq37}) for calculating $\phi_i$ \\
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. Határozzuk meg $v(S)$ értékét valamilyen lehetséges koalíció esetére.
%
%\vspace{4 mm}
%\underline{2.Lépés}. Alkalmazzuk a (\ref{eq37}) képletet $i=1,2,\dots,I$ esetére.

\begin{pelda}
In the previous example we calculated the value of the characteristic function. Because of the symmetry, $\phi_1=\phi_2=\phi_3$
must be true for the case of Shapley value. Since $\phi_1+\phi_2+\phi_3=v(\{1,2,3\})=17.25, \phi1=\phi_2=\phi_3=5.75$.
We get the same value by formula (\ref{eq37}) too. Let's consider the $\phi_1$ value. If $i\notin S$,
$v(S)=v(S-\{i\})$, so the appropriate terms of the sum are zero-valued. The non-zero terms are given for coalitions
$S=\{1\}, S=\{1,2\}, S=\{1,3\}$ and $S=\{1,2,3\}$, so 
$$\phi_1=\frac{0!2!}{3!}(\frac{5}{4}-0)+\frac{1!1!}{3!}(7-\frac{5}{4})+\frac{1!1!}{3!}(7-\frac{5}{4})+
\frac{2!0!}{3!}(\frac{69}{4}-7)=$$
$$\frac{1}{6}(\frac{10}{4}+\frac{23}{4}+\frac{23}{3}+\frac{82}{4})=\frac{138}{24}=5.75 \koz .$$
\end{pelda}

An alternative solution approach requires the stability of the solution. It is said that the vector 
$\mathbf{\phi}=(\phi_1,\dots,\phi_I)$ majorizes the vector $\mathbf{\psi}=(\psi_1,\dots,\psi_I)$ in coalition $S$, if
$$\sum_{i\in S} \phi_i > \sum_{i\in S} \psi_i \koz ,$$
that is the $S$ coalition has an in interest to switch from payoff vector $\mathbf{\phi}$ to payoff vector $\mathbf{\psi}$,
or $\mathbf{\psi}$ is instabil for coalition $S$. The \ki{Neumann--Morgenstern solution}\inddef{Neumann--Morgenstern solution}\nevindex{Neumann, János (1903--1957)}\nevindex{Morgenstern, Oskar  (1902--1977)}
is a $V$ set of imputations for which 
\begin{enumerate}[(i)]
\item There is no $\mathbf{\phi}, \mathbf{\psi} \in V$, that $\mathbf{\phi}$ majorizes $\mathbf{\psi}$ in some coalition (inner stability)
\item If $\mathbf{\psi} \notin V$, there is $\mathbf{\phi} \in V$, that $\mathbf{\phi}$ majorizes $\mathbf{\psi}$-t
in at least one coalition (outer stability).
\end{enumerate}

The main difficulty of this conception is that there is no general existence theorem for the existence of a non-empty $V$ set,
and there is no general method for constructing the set $V$. 

\begin{gyak}
\ujgyak \label{jat3.1}
Let $I=3$, $X_1=X_2=X_3=[0,1]$, $f_i(x_1,x_2,x_3)=x_1+x_2+x_3-x_i^2 \koz (i=1,2,3)$. Determine the $v(S)$
characteristic function.
\ujgyak \label{jat3.2}
Formulate the (\ref{eq35}), (\ref{eq36}) condition system for the game of the previous exercise.
\ujgyak \label{jat3.3}
Determine the $\psi_i$ Shapley values for the game of Exercise \ref{jat3.1}.
\end{gyak}

\index{methods of cooperative games|)}

\section{Collective decision-making}\label{sec4}\index{collective decision-making|(}

In the previous chapter we assumed that the objective functions are given by numerical values. These numerical values
also mean preferences, since the $i$th decision maker prefers alternative $x$  to $z$, if $f_i(x) > f_i(z)$.
In this chapter we will discuss such methods which don't require the knowledge of the objective functions, but
the preferences of the certain decision makers. 

Let $I$ denote again the number of decision makers, and $X$ the set of decision alternatives. If the $i$th decision maker
prefers alternative $x$ to $y$, this is denoted by $x \succ_i y$, if prefers alternative $x$ to $y$ or thinks to be equal,
it is denoted by $x \succeq_i y$. Assume that
\begin{enumerate}[(i)]
\item For all $x,y\in X$, $x \succeq_i y$ or $y \succeq_i x$ (or both)
\item For $x \succeq_i y$ and $y \succeq_i z$, $x \succeq_i z$.
\end{enumerate}
Condition (i) requires that the $\succeq_i$ partial order be a total order, while condition (ii) requires to be transitive.

\begin{defi}
A group decision-making function combines arbitrary individual $(\succeq_1, \succeq_2,\dots,\succeq_I)$ partial orders
into one partial order, which is also called the collective preference structure\inddef{collective preference structure} of the group. 
\end{defi}

We illustrate the definition of group decision-making function by some simple example.

\begin{pelda}
Be $x,y\in X$ arbitrary, and for all $i$
\[ \alpha_i = \left\{
\begin{array}{ll}
1, & \mbox{ha}\mspace{10mu} x \succ_i y,  \\
0, & \mbox{ha}\mspace{10mu} x \sim_i y, \\
-1, & \mbox{ha}\mspace{10mu}x \prec_i y  .
\end{array}
\right. \]
Let $\beta_i,\beta_2,\dots,\beta_I$ given positive constant, and
$$\alpha = \sum_{i=1}^I \beta_i \alpha_i \koz .$$
The group decision-making function means:
\begin{eqnarray*}
x \succ y & \Longleftrightarrow & \alpha > 0 \\
x \sim y & \Longleftrightarrow & \alpha = 0 \\
x \prec y & \Longleftrightarrow & \alpha < 0 \koz .
\end{eqnarray*}
The \ki{majority rule} \inddef{majority rule} is a special case of it when 
$\beta_1=\beta_2=\dots=\beta_I=1$.
\end{pelda}

\begin{pelda}
An $i_0$ decision maker is called \ki{dictator}\inddef{dictator}, if his or her opinion prevails in group decision-making:
\begin{eqnarray*}
x \succ y & \Longleftrightarrow & x \succ_{i_0} y \\
x \sim y & \Longleftrightarrow &x \sim_{i_0} y \\
x \prec y & \Longleftrightarrow & x \prec_{i_0} y \koz .
\end{eqnarray*}
This kind of group decision-making is also called dictatorship. 
\end{pelda}

\begin{pelda}
In the case of \ki{Borda measure}\inddef{Borda measure}\index{Borda measure}\nevindex{Borda, Jean-Charles de  (1733--1799)}
we assume that $\alpha$  is a finite set and the preferences of the decision makers is expressed by a $c_i(x)$ measure 
for all $x\in X$. For example $c_i(x)=1$, if $x$ is the best, $c_i(x)=2$, if $x$ is the second best alternative for the $i$th
decision maker, and so on, $c_i(x)=I$, if $x$ is the worst alternative. Then
\begin{eqnarray*}
x \succ y & \Longleftrightarrow & \sum_{i=1}^I c_i(x) >  \sum_{i=1}^I c_i(y) \\
x \sim y & \Longleftrightarrow & \sum_{i=1}^I c_i(x) =  \sum_{i=1}^I c_i(y) \\
x \prec y & \Longleftrightarrow & \sum_{i=1}^I c_i(x) <  \sum_{i=1}^I c_i(y) \koz .
\end{eqnarray*}
\end{pelda}

A group decision-making function is called \ki{Pareto}\inddef{Pareto function}\nevindex{Pareto, Vilfredo Federico Damaso (1848--1923)} or \ki{Pareto function}, if for all $x,y\in X$ and $x \succ_i y\koz (i=1,2,\dots,I)$, $x \succ y$ necessarily.
That is, if all the decision makers prefer $x$ to $y$, it must be the same way in the collective preference of the group.  
A group decision-making function is said to satisfy the condition of \ki{pairwise independence}\inddef{pairwise independence  condition}, if any two $(\succeq_1,\dots,\succeq_I)$ and $(\succeq'_1,\dots,\succeq'_I)$  preference structure satisfy the followings. Let $x,y\in X$ such that for arbitrary $i$, $x \succeq_i y$ if and only if $x \succeq'_i y$, and  $y \succeq_i x$
if and only if $y \succeq'_i x$. Then $x \succeq y$ if and only if $x \succeq' y$, and $y \succeq x$ if and only if 
 $y \succeq' x$  in the collective preference of the group.

\begin{pelda}
It is easy to see that the Borda measure is Pareto, but it doesn't satisfy the condition of pairwise independence.
The first statement is evident, while the second one can be illustrated by a simple example. Be $I=2$, $\alpha=\{x,y,z\}$.
Let's assume that 
\begin{eqnarray*}
x \succ_1 z \succ_1 y&& \\
y \succ_2 x \succ_2 z&\koz& 
\end{eqnarray*}
and
\begin{eqnarray*}
x \succ'_1 y \succ'_1 z && \\
y \succ'_2 z \succ'_2 x &\koz .&
\end{eqnarray*}
Then $c(x)=1+2=3, c(y)=3+1=4$, thus $y\succ x$. However $c'(x)=1+3=4, c'(y)=2+1=3$, so $x\succ y$.
As we can see the certain decision makers preference order between $x$ and $y$ is the same in both case,
but the collective preference of the group is different. 
\end{pelda}

Let $\R_I$ denote the set of the $I$-element full and transitive partial orders on an at least three-element $X$ set,
and be $\preceq$ the collective preference of the group which is Pareto and satisfies the condition of pairwise independence.
Then $\preceq$ is necessarily dictatorial. This result originated with Arrow \nevindex{Arrow, Kenneth Joseph} shows that 
there is no such group decision-making function which could satisfy these two basic and natural requirements. 

\begin{pelda}
The method of \ki{paired comparison} \inddef{method of paired comparison}\index{method of paired comparison} is as follows. Be $x,y \in X$
arbitrary, and let's denote $P(x,y)$ the number of decision makers, to which $x \succ_i y$. After that, the collective 
preference of the group is the following:
\begin{eqnarray*}
x \succ y & \Longleftrightarrow & P(x,y) > P(y,x) \\
x \sim y & \Longleftrightarrow &  P(x,y) = P(y,x) \\
x \prec y & \Longleftrightarrow &  P(x,y) <  P(y,x) \koz ,
\end{eqnarray*}
that is $x\succ y$ if and only if more than one decision makers prefer the $x$ alternative to $y$. 
Let's assume again that $X$ consists of three elements, $X=\{x,y,z\}$ and the individual preferences for $I=3$
\begin{eqnarray*}
x \succ_1 y \succ_1 z &&\\
z \succ_2 x \succ_2 y &&\\
y \succ_3 z \succ_3 x &\koz.&
\end{eqnarray*}
Thus, in the collective preference $x\succ y$, because $P(x,y)=2$ and $P(y,x)=1$. Similarly $y\succ z$, because 
$P(y,z)=2$ and $P(z,y)=1$, and $z\succ x$, since  $P(z,x)=2$ and $P(x,z)=1$. Therefore $x\succ y \succ z \succ x$
which is inconsistent with the requirements of transitivity. 
\end{pelda}

The methods discussed so far didn't take account of the important circumstance that the decision makers aren't
necessarily in the same position, that is they can have different importance. This importance can be characterized
by weights. In this generalized case we have to modify the group decision-making methods as required. 
Let's assume that $X$ is finite set, denote $N$ the number of alternatives. We denote the preferences of the decision 
makers by the numbers ranging from 1 to $N$, where 1 is assigned to the most favorable, while $N$ is assigned to 
most unfavorable alternative. It's imaginable that the two alternatives are equally important, then we use fractions.
For example, if we can't distinguish between the priority of the 2nd and 3rd alternatives, then we assign 2.5 to each of them.  
Usually the average value of the indistinguishable alternatives is assigned to each of them. In this way, the problem of
the group decision can be given by a table which rows correspond to the decision makers and columns correspond to 
the decision alternatives. Every row of the table is a permutation of the $1,2,\dots,N$ numbers, at most
some element of it is replaced by some average value if they are equally-preferred.  Figure \ref{fig:tbl3} shows the given 
table in which the last column contains the weights of the decision makers.

\begin{figure}[!t]
$$
\begin{tabular}{|c|cccc|c|}
\hline
Decision makers & 
\multicolumn{4}{|c|}{Alternatives} & Weights \\ & 1 & 2 & \dots & N & \\
\hline $\begin{array}{r}
\textup{1} \\
\textup{2} \\
\vdots \\
$I$
\end{array}$ &
$\begin{array}{c}
a_{11} \\
a_{21} \\
\vdots \\
a_{I1}
\end{array}$ &
$\begin{array}{c}
a_{12} \\
a_{22} \\
\vdots \\
a_{I2}
\end{array}$ &
$\begin{array}{c}
\dots \\
\dots \\
\\
\dots
\end{array}$ &
$\begin{array}{c}
a_{1N} \\
a_{2N} \\
\vdots \\
a_{IN}
\end{array}$ &
$\begin{array}{c}
\alpha_1 \\
\alpha_2 \\
\vdots \\
\alpha_I \\
\end{array}$  \\
\hline
\end{tabular}
$$
\caption{\label{fig:tbl3} Group decision-making table.}
\end{figure}

In this general case the \ki{majority rule}\index{majority rule} can be defined as follows. For all of the $j$ alternatives
determine first the aggregate weight of the decision makers to which the alternative $j$ is the best possibility, then select
that alternative for the best collective one for which this sum is the biggest. If our goal is not only to select the best,
but to rank all of the alternatives, then we have to choose descending order in this sum to rank the alternatives, where
the biggest sum selects the best, and the smallest sum selects the worst alternative. Mathematically, be
\begin{equation}\label{eq38}
f(a_{ij}) = \left\{
\begin{array}{ll}
1, & \mbox{ha}\mspace{10mu} a_{ij}=1,  \\
0 & \mbox{otherwise}  
\end{array}
\right.
\end{equation}
and
\begin{equation}\label{eq39}
A_j = \sum_{i=1}^I f(a_{ij})\alpha_i
\end{equation}
for $j=1,2,\dots,I$. The $j_0$th alternative is considered the best by the group, if
\begin{equation}\label{eq40}
A_{j_0} = \max_j \{A_j\} \koz .
\end{equation}

The formal algorithm is as follows:

\begin{algN}{Majority-Rule($A$)}\inddef{\textsc{Majority-Rule}}
1 \' $A_1 \leftarrow 0, A_2 \leftarrow 0, \dots, A_N \leftarrow 0, max  \leftarrow 0$ \\
2 \' \key{for} \= $i \leftarrow 1$ \key{to} $N$ \\
3 \'  \>  \key{do} \=  \key{for} $j \leftarrow 1$ \key{to} $I$ \\
4 \' \> \> \> \key{do} \key{if} \> \> $a_{ji}=1$ \\
5 \' \> \>  \> \>  \>  \key{then}  $A_i \leftarrow A_i+\alpha_j$ \\
6 \'  \> \key{if} \>  $A_i>max$ \\
7 \' \> \>  \key{then} \>\> $max \leftarrow A_i$ \\
8 \' \> \>  \> \> $ind \leftarrow i$ \\
9 \'  \key{return} \textit{ind}
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. $A_1=A_2=\dots=A_N=0, max=0$
%
%\vspace{4 mm}
%\underline{2.Lépés}. $i=1,2,\dots,N$
%
%\vspace{4 mm}
%\underline{3.Lépés}. $j=1,2,\dots,I$.  \\
%Ha $a_{ji}=1$, akkor $A_i=A_i+\alpha_j$, különben $A_i$ értéke változatlan marad. A $j$ ciklus 
%befejeztével menj a következõ lépésre.
%
%\vspace{4 mm}
%\underline{4.Lépés}. Ha $A_i>max$, akkor $max:=A_i$ és $ind:=i$; különben $max$ és $ind$ értéke változatlan marad. 
%Az $i$ ciklus befejeztével $ind$ adja a megoldást. 
%
%\vspace{4 mm}

Applying the \ki{Borda measure}\index{Borda measure}, let
\begin{equation}\label{eq41}
B_j = \sum_{i=1}^I a_{ij}\alpha_i \koz ,
\end{equation}
and alternative $j_0$ is the result of the group decision if
\begin{equation}\label{eq42}
B_{j_0} = \min_j \{B_j\} \koz .
\end{equation}

The Borda measure can be described by the following algorithm:

\begin{algN}{Borda-Measure-Method($A,\alpha$)}\inddef{\textsc{Borda-Measure-Method}}
1 \' $B_1 \leftarrow 0, B_2 \leftarrow 0, \dots, B_N \leftarrow 0, max  \leftarrow 0$ \\
2 \' \key{for} \= $j \leftarrow 1$ \key{to} $N$ \\
3 \'  \>  \key{do} \=  \key{for} $i \leftarrow 1$ \key{to} $I$ \\
4 \' \> \> \> \key{do} $B_j \leftarrow B_j + a_{ij} \alpha_i$ \\
5 \'  \> \key{if} \>  $B_j>max$ \\
6 \' \> \>  \key{then} \>\> $max \leftarrow B_j$ \\
7 \' \> \>  \> \> $ind \leftarrow j$ \\
8 \'  \key{return} \textit{ind}
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. $B_1=B_2=\dots=B_N=0, max=0$
%
%\vspace{4 mm}
%\underline{2.Lépés}. $j=1,2,\dots,N$
%
%\vspace{4 mm}
%\underline{3.Lépés}. $i=1,2,\dots,I$. \\ $B_j = B_j + a_{ij} \alpha_i$.
%Az $i$ ciklus befejeztével menj a következõ lépésre.
%
%\vspace{4 mm}
%\underline{4.Lépés}. Ha $B_j>max$, akkor $max:=B_j$ és $ind:=j$.
%Az $j$ ciklus befejeztével $ind$ adja a megoldást. 
%
%\vspace{4 mm}

Applying the method of \ki{paired comparison}\index{method of paired comparison}, let with any $j,j'\in X$
\begin{equation}\label{eq43}
P(j,j')=\sum_{\{i|a_{ij}<a_{ij'}\}} \alpha_i
\end{equation}
which gives the weight of the decision makers who prefer the alternative $j$ to $j'$. In the collective decision
$$j\succ j' \Longleftrightarrow P(j,j') > P(j',j) \koz .$$
In many cases the collective partial order given this way doesn't result in a clearly best alternative.
In such cases further analysis (for example using some other method) need on the
$$ S^* = \{j|j\in X \mspace{10mu} \mbox{and theres is no such} \mspace{10mu} j'\in X  \mbox{, for which} \mspace{10mu} j'\succ j\}$$
non-dominated alternative set.

By this algorithm we construct a matrix consists of the $\{0,1\}$ elements, where $a_{jl}=1$ if and only if
the $j$ alternative is better in all then alternative $l$. In the case of draw $a_{jl}=\frac{1}{2}$.

\begin{algN}{Paired-Comparison($A$)}\inddef{\textsc{Paired-Comparison}}
1 \' \key{for} \= $j \leftarrow 1$ \key{to} $N-1$ \\
2 \'  \>  \key{do} \=  \key{for} $l \leftarrow j$ \key{to} $N$ \\
3 \' \> \> \> \key{do} $z \leftarrow 0$ \\
4 \'  \>   \> \> \> \key{for} $i \leftarrow 1$ \key{to} $I$ \\
5 \'  \> \> \> \> \> \key{do} \> \key{if} \>  $a_{ij} > a_{il}$ \\
6 \' \> \>  \> \> \> \> \> \key{then} \>\> $z \leftarrow z + 1$ \\
7 \'  \> \> \> \> \key{if} \>  $z>\frac{N}{2}$ \\
8 \' \> \>  \> \> \>  \key{then} \>\> $a_{jl}\leftarrow 1$ \\
9 \'  \> \> \> \> \key{if} \>  $z=\frac{N}{2}$ \\
10 \' \> \>  \> \> \>  \key{then} \>\> $a_{jl}\leftarrow \frac{1}{2}$ \\
11 \'  \> \> \> \> \key{if} \>  $z<\frac{N}{2}$ \\
12 \' \> \>  \> \> \> \key{then} \>\> $a_{jl}\leftarrow 0$ \\
13 \'  \> \> \> \> $a_{lj} \leftarrow a_{jl}$ \\
14 \'  \key{return} $A$
\end{algN}

%\vspace{4 mm}
%\underline{1.Lépés}. $j=1,2,\dots,N-1$; $l=j,j+1,\dots,N$
%
%\vspace{4 mm}
%\underline{2.Lépés}. $z=0$; $i=1,2,\dots,I$ \\
%Ha $a_{ij} > a_{il}$, akkor $z:=z+1$, különben $z$ értéke marad. Az $i$ ciklus befejeztével menj a következõ lépésre.
%
%\vspace{4 mm}
%\underline{3.Lépés}. Ha $z>\frac{N}{2}$, akkor $a_{jl}:=1$; ha  $z=\frac{N}{2}$, akkor $a_{jl}:=\frac{1}{2}$, és ha
%$z<\frac{N}{2}$, akkor $a_{jl}:=0$. Legyen $a_{lj}:=a_{jl}$. A $j$ és $l$ ciklus befejeztével a mátrix készen lesz.

\begin{pelda}\label{ex17}
Four proposal were received by the Environmental Authority for the cleaning of a chemically contaminated site.
A committee consists of 6 people has to choose the best proposal and thereafter the authority 
can conclude the contract for realizing the proposal.  Figure \ref{fig:tbl4} shows the relative weight of the
committee members and the personal preferences.

\begin{figure}[!t]
$$
\begin{tabular}{|c|cccc|c|}
\hline
Committee  & 
\multicolumn{4}{|c|}{Alternatives} & Weights \\ Members & 1 & 2 & 3 & 4 & \\
\hline $\begin{array}{r}
\textup{1} \\
\textup{2} \\
\textup{3} \\
\textup{4} \\
\textup{5} \\
\textup{6}
\end{array}$ &
$\begin{array}{c}
1 \\
2 \\
1 \\
2 \\
3 \\
1
\end{array}$ &
$\begin{array}{c}
3 \\
1 \\
3 \\
3 \\
1 \\
4
\end{array}$ &
$\begin{array}{c}
2 \\
4 \\
2 \\
1 \\
4 \\
2
\end{array}$ &
$\begin{array}{c}
4 \\
3 \\
4 \\
4 \\
2 \\
3
\end{array}$ &
$\begin{array}{c}
0.3 \\
0.2 \\
0.2 \\
0.1 \\
0.1 \\
0.1 \\
\end{array}$  \\
\hline
\end{tabular}
$$
\caption{\label{fig:tbl4} The database of Example \ref{ex17}}
\end{figure}

Majority rule

Using the \ki{majority rule}\index{majority rule}
\begin{eqnarray*}
A_1&=&0.3+0.2+0.1=0.6 \\
A_2&=&0.2+0.1=0.3 \\
A_3&=&0.1 \\
A_4&=&0 \koz ,
\end{eqnarray*}
so the first alternative is the best.

Using the \ki{Borda measure} \inddef{Borda measure}
\begin{eqnarray*}
B_1&=&0.3+0.4+0.2+0.2+0.3+0.1=1.5 \\
B_2&=&0.9+0.2+0.6+0.3+0.1+0.4=2.5 \\
B_3&=&0.6+0.8+0.4+0.1+0.4+0.2=2.5 \\
B_4&=&1.2+0.6+0.8+0.4+0.2+0.3=3.5 \koz .
\end{eqnarray*}
In this case the first alternative is the best as well, but this method shows equally good the second and third alternatives.
Notice, that in the case of the previous method the second alternative was better than the third one.


In the case of the method of  \ki{paired comparison} \index{method of paired comparison}

\begin{eqnarray*}
P(1,2)&=&0.3+0.2+0.1+0.1=0.7 \\
P(2,1)&=&0.2+0.1=0.3\\
P(1,3)&=&0.3+0.2+0.2+0.1+0.1=0.9 \\
P(3,1)&=&0.1 \\
P(1,4)&=&0.3+0.2+0.2+0.1+0.1=0.9 \\
P(4,1)&=&0.1 \\
P(2,3)&=&0.2+0.1+0.1=0.4 \\
P(3,2)&=&0.3+0.2+0.1=0.6 \\
P(2,4)&=&0.3+0.2+0.2+0.1+0.1=0.9 \\
P(4,2)&=&0.1 \\
P(3,4)&=&0.3+0.2+0.1+0.1=0.7 \\
P(4,3)&=&0.2+0.1=0.3 \koz .
\end{eqnarray*}
Thus $1\succ 2, 1\succ 3, 1\succ4, 3\succ 2, 2\succ 4$ and $3\succ 4$. These references are showed by Figure \ref{fig:abra8}.
The first alternative is better than any others, so this is the obvious choice. 

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.8.eps}
\caption{The preference graph of Example \ref{ex17}\label{fig:abra8}}
\end{center}
\end{figure}

%\epskep{5.8}{A \ref{ex17} példa referencia gráfja.\label{fig:abra8}}
\end{pelda}

In the above example all three methods gave the same result. However,  in several practical cases one can get 
different results and the decision makers have to choose on the basis of other criteria. 

\begin{gyak}
\ujgyak \label{jat4.1}
Let's consider the following group decision-making table:

\begin{figure}[!h]
$$
\begin{tabular}{|c|ccccc|c|}
\hline
Decision makers & 
\multicolumn{5}{|c|}{Alternatives} & Weights \\ & 1 & 2 & 3 & 4 & 5 & \\
\hline $\begin{array}{r}
1 \\
2 \\
3 \\
4
\end{array}$ &
$\begin{array}{c}
1 \\
1 \\
5 \\
4
\end{array}$ &
$\begin{array}{c}
3 \\
4 \\
4 \\
3
\end{array}$ &
$\begin{array}{c}
2 \\
5 \\
1 \\
2
\end{array}$ &
$\begin{array}{c}
5 \\
2 \\
3 \\
1
\end{array}$ &
$\begin{array}{c}
4 \\
3 \\
2 \\
5
\end{array}$ &
$\begin{array}{c}
3 \\
2 \\
2 \\
1 \\
\end{array}$  \\
\hline
\end{tabular}
$$
\caption{\label{fig:extbl1} Group decision-making table}
\end{figure}
Apply the majority rule.
\ujgyak \label{jat4.2}
Apply the Borda measure to the previous exercise.
\ujgyak \label{jat4.3}
Apply the method of paired comparison to Exercise  \ref{jat4.1}.
\ujgyak \label{jat4.4}
Let's consider now the following group decision-making table:

\begin{figure}[!h]
$$
\begin{tabular}{|c|ccc|c|}
\hline
Decision makers & 
\multicolumn{3}{|c|}{Alternatives} & Weights \\ & 1 & 2 & 3 & \\
\hline $\begin{array}{r}
1 \\
2 \\
3 \\
4
\end{array}$ &
$\begin{array}{c}
1 \\
3 \\
2 \\
1
\end{array}$ &
$\begin{array}{c}
2 \\
2 \\
1 \\
3
\end{array}$ &
$\begin{array}{c}
3 \\
1 \\
3 \\
2
\end{array}$ &
$\begin{array}{c}
1 \\
1 \\
1 \\
1 \\
\end{array}$  \\
\hline
\end{tabular}
$$
\caption{\label{fig:extbl2} Group decision-making table}
\end{figure}
Repeat Exercise \ref{jat4.1} for this exercise.
\ujgyak \label{jat4.5}
Apply the Borda measure to the previous exercise.
\ujgyak \label{jat4.6}
Apply the method of paired comparison to Exercise \ref{jat4.4}.
\end{gyak}

\index{collective decision-making|)}

\section{Applications of Pareto games}\label{sec5}
\index{Applications of Pareto games|(}

Let $I$ denote again the number of decision makers but suppose now that the decision makers have more than one
objective functions separately. There are several possibility to handle such problems: 

\begin{enumerate}
\item[(A)]
In the application of multi-objective programming, let $\alpha_i$ denote the weight of the $i$th decision maker, and let
$\beta_{i1},\beta_{i2},\dots,\beta_{i c(i)}$ be the weights of this decision maker's objective functions. Here $c(i)$ denote
the number of the $i$th decision maker's objective functions. Thus we can get an optimization problem with
the $\sum_{i=1}^I c(i)$ objective function, where all of the decision makers' all the objective functions mean the objective function
of the problem, and the weights of the certain objective functions are the $\alpha_i \beta_{ij}$ sequences.
We can use any of the methods from Chapter \ref{sec1}. to solve this problem.

\item[(B)]
We can get another family of methods in the following way. Determine an utility function for every decision maker
(as described in Chapter  \ref{subsec11}.), which compresses the decision maker's preferences into one function.
In the application of this method every decision maker has only one (new) objective function, so 
any methods and solution concepts can be used from the previous chapters.  

\item[(C)] 
A third method can be given, if we determine only the partial order of the certain decision makers defined on an alternative set by some method
instead of the construction of utility functions. After that we can use any method of Chapter  \ref{sec4}. directly. 
\end{enumerate}

\begin{pelda}\label{ex18}
Modify the previous chapter as follows. Let's suppose again that we choose from four alternatives, but assume now that
the committee consists of three people and every member of it has two objective functions. The first objective function
is the technical standards of the proposed solution on a subjective scale, while the second one are the odds of the exact
implementation. The latter one is judged subjectively by the decision makers individually by the preceding works of the supplier.
The data is shown in Figure \ref{fig:tbl5}., where we assume that the first objective function is judged on a subjective
scale from 0 to 100, so the normalized objective function values are given dividing by 100.
Using the weighting method we get the following aggregate utility function values for the separate decision makers:

\vspace{4mm}

\noindent 1. Decision maker
$$
\begin{array}{lrcl}
\mbox{First alternative:} & 0.9(0.5)+0.9(0.5) & = & 0.9 \\
\mbox{Second alternative:} & 0.75(0.5)+0.8(0.5) & = & 0.775 \\
\mbox{Third alternative:} & 0.8(0.5)+0.7(0.5) & = & 0.75 \\
\mbox{Fourth alternative:} & 0.85(0.5)+0.8(0.5) & = & 0.825
\end{array}
$$

\noindent 2. Decision maker
$$
\begin{array}{lrcl}
\mbox{First alternative:} & 0.85(0.6)+0.8(0.4) & = & 0.83 \\
\mbox{Second alternative:} & 0.8(0.6)+0.9(0.4) & = & 0.84 \\
\mbox{Third alternative:} & 0.7(0.6)+0.8(0.4) & = & 0.74 \\
\mbox{Fourth alternative:} & 0.9(0.6)+0.85(0.4) & = & 0.88
\end{array}
$$

\noindent 3. Decision maker
$$
\begin{array}{lrcl}
\mbox{First alternative:} & 0.8(0.7)+0.85(0.3) & = & 0.815 \\
\mbox{Second alternative:} & 0.9(0.7)+0.8(0.3) & = & 0.87 \\
\mbox{Third alternative:} & 0.75(0.7)+0.9(0.3) & = & 0.795 \\
\mbox{Fourth alternative:} & 0.7(0.7)+0.8(0.3) & = & 0.73
\end{array}
$$

\begin{figure}[!t]
$$
\begin{tabular}{|c|c|cccc|c|c|}
\hline
Decision maker  & Objective function &
\multicolumn{4}{|c|}{Alternatives} & Objective function & Decision maker \\  & & 1 & 2 & 3 & 4 & weight & weight \\
\hline 
\multirow{2}{*}{1} & 1 & 90 & 75 & 80 & 85 & 0.5 & \multirow{2}{*}{0.4} \\ 
& 2 & 0.9 & 0.8 & 0.7 & 0.8 & 0.5 &  \\ \hline
\multirow{2}{*}{2} & 1 & 85 & 80 & 70 & 90 & 0.6 & \multirow{2}{*}{0.3} \\ 
& 2 & 0.8 & 0.9 & 0.8 & 0.85 & 0.4 &  \\ \hline
\multirow{2}{*}{3} & 1 & 80 & 90 & 75 & 70 & 0.7 & \multirow{2}{*}{0.3} \\ 
& 2 & 0.85 & 0.8 & 0.9 & 0.8 & 0.3 &  \\ \hline
\end{tabular}
$$
\caption{\label{fig:tbl5} The database of Example \ref{ex18}}
\end{figure}

The preferences thus are the following:
$$1\succ_1 4 \succ_1 2 \succ_1 3, 4 \succ_2 2 \succ_2 1 \succ_2 3, \mspace{10mu} \mbox{and}  \mspace{10mu} 2 \succ_3 1 \succ_3 3 \succ_3 4 \koz .$$
For example, in the application of Borda measure
\begin{eqnarray*}
B_1&=&1(0.4)+3(0.3)+2(0.3)=1.9 \\
B_2&=&3(0.4)+2(0.3)+1(0.3)=2.1 \\
B_3&=&4(0.4)+4(0.3)+3(0.3)=3.7 \\
B_4&=&2(0.4)+1(0.3)+4(0.3)=2.3
\end{eqnarray*}
are given, so the group-order of the four alternatives
$$1\succ 2 \succ 4 \succ 3 \koz .$$
\end{pelda}

\begin{gyak}
\ujgyak \label{jat5.1}
Let's consider the following table:

\begin{figure}[!h]
$$
\begin{tabular}{|c|c|ccc|c|c|}
\hline
Decision maker  & Objective function &
\multicolumn{3}{|c|}{Alternatives} & Objective function & Decision maker \\  & & 1 & 2 & 3 & weight & weight \\
\hline 
\multirow{2}{*}{1} & 1 & 0.6 & 0.8 & 0.7 & 0.6 & \multirow{2}{*}{0.5} \\ 
& 2 & 0.9 & 0.7 & 0.6 & 0.4 & \\ \hline
\multirow{2}{*}{2} & 1 & 0.5 & 0.3 & 0.4 & 0.5 & \multirow{2}{*}{0.25} \\ 
& 2 & 0.6 & 0.8 & 0.7 & 0.5 & \\ \hline
\multirow{3}{*}{3} & 1 & 0.4 & 0.5 & 0.6 & 0.4 & \multirow{3}{*}{0.25} \\ 
& 2 &  0.7 & 0.6 & 0.6 & 0.4 &  \\
& 3 & 0.5 & 0.8 & 0.6 & 0.2 &  \\ \hline
\end{tabular}
$$
\caption{\label{fig:extbl3}}
\end{figure}

Let's consider that the objective functions are already normalized. Use method (A) to solve the exercise. 
\ujgyak \label{jat5.2}
Use method (B) for the previous exercise, where the certain decision makers' utility functions are given by the
weighting method, and the group decision making is given by the Borda measure.
\ujgyak \label{jat5.3}
Solve Exercise \ref{jat5.2} using the method of paired comparison instead of Borda measure. 
\end{gyak}

\index{Applications of Pareto games|)}

\section{Axiomatic methods}\label{sec6}
\index{axiomatic methods|(}

For the sake of simplicity, let's consider that $I=2$, that is we'd like to solve the conflict between two decision makers.
Assume that the consequential space $H$ is convex, bounded and closed in $\R^2$, and there is given a  $\mathbf{f}_*=(f_{1*},f_{2*})$
point which gives the objective function values of the decision makers in cases where they are unable to agree.
We assume that there is such $\mathbf{f}\in H$ that $\mathbf{f} > \mathbf{f}_*$. The conflict is characterized by the
 $(H, \mathbf{f}_*)$ pair. The solution obviously has to depend on both $H$ and $\mathbf{f}_*$, so it is some function of them:
$ \mathbf{\phi}(H,\mathbf{f}_*) $.

For the case of the different solution concepts we demand that the solution function satisfies some requirements
which treated as axioms. These axioms require the correctness of the solution, the certain axioms characterize this correctness in
different ways.

In the case of the \ki{classical Nash}\inddef{Nash solution} solution we assume the following:
\begin{enumerate}[(i)]
\item $ \mathbf{\phi}(H,\mathbf{f}_*) \in H$ (possibility)
\item $ \mathbf{\phi}(H,\mathbf{f}_*) \geq \mathbf{f}_*$ (rationality)
\item $ \mathbf{\phi}(H,\mathbf{f}_*)$ is Pareto solution in $H$ (Pareto optimality)
\item If $ H_1 \subseteq H$ and $\mathbf{\phi}(H,\mathbf{f}_*) \in H_1$, necessarily 
$\mathbf{\phi}(H_1,\mathbf{f}_*)=\mathbf{\phi}(H,\mathbf{f}_*)$ (independence of irrelevant alternatives)
\item Be $T:\R^2 \mapsto \R^2$ such linear transformation that 
$T(f_1,f_2)=(\alpha_1 f_1+\beta_1, \alpha_2 f_2+\beta_2)$ is positive for $\alpha_1$ and $\alpha_2$.
Then $\mathbf{\phi}(T(H), T(\mathbf{f}_*))=T(\mathbf{\phi}(H,\mathbf{f}_*))$ (invariant to affine transformations)
\item If $H$ and $\mathbf{f}_*$ are symmetrical, that is $f_{1*}=f_{2*}$ and 
$(f_1,f_2)\in H \Longleftrightarrow (f_2,f_1) \in H$, then the components of $\mathbf{\phi}(H,\mathbf{f}_*)$ be equals
(symmetry).
\end{enumerate}

Condition (i) demands the possibility of the solution. Condition (ii) requires that none of the rational decision makers agree on
a solution which is worse than the one could be achieved without consensus. On the basis of condition (iii) there is no better
solution than the friendly solution. According to requirement (iv), if after the consensus some alternatives lost their possibility,
but the solution is still possible, the solution remains the same for the reduced consequential space. If  the dimension of any of
the objective functions changes, the solution can't change. This is required by (v), and  the last condition means that if
two decision makers are in the absolutely same situation defining the conflict, we have to treat them in the same way 
in the case of solution. 
The following essential result originates from Nash:

\begin{tetel}\label{tetel6}
The (i)-(vi) conditions are satisfied by exactly one solution function, and $\mathbf{\phi}(H,\mathbf{f}_*)$ can be given by as the
\begin{equation}\label{eq44}
\begin{array}{rcl}
(f_1-f_{1*})(f_2-f_{2*}) & \longrightarrow & max \mspace{40mu} ((f_1,f_2)\in H) \\
f_1 & \geq & f_{1*} \\
f_2 & \geq & f_{2*}
\end{array}
\end{equation}
optimum problem unique solution.
\end{tetel}

\begin{pelda}
Let's consider again the consequential space showed in Figure \ref{fig:abra2} before, and suppose that 
$(f_{1*},f_{2*})=(0,-1)$, that is it comprises the worst values in its components. Then Exercise  (\ref{eq44})
is the following:
\begin{eqnarray*}
f_1(f_2+1) & \longrightarrow & max \\
f_2 & \leq & f_1 \\
f_2 & \leq & 3-2f_1 \\
f_2 & \geq & -\frac{1}{2}f_1 \koz .
\end{eqnarray*}
It's easy to see that the optimal solution is  $f_1=f_2=1$.
\end{pelda}

Notice that problem (\ref{eq44}) is a distance dependent method, where we maximize the geometric distance from
the $(f_{1*},f_{2*})$ point. The algorithm is the solution of the (\ref{eq44}) optimum problem. 

Condition (vi) requires that the two decision makers must be treated equally. However in many practical cases this is
not an actual requirement if one of them is in stronger position than the other.

\begin{tetel}
Requirements (i)-(v) are satisfied by infinite number of functions, but every solution function comprises such
 $0\leq \alpha \leq 1$, that the solution is given by as the
\begin{equation}\label{eq45}
\begin{array}{rcl}
(f_1-f_{1*})^\alpha(f_2-f_{2*})^{1-\alpha} & \longrightarrow & max \mspace{40mu} ((f_1,f_2)\in H) \\
f_1 & \geq & f_{1*} \\
f_2 & \geq & f_{2*}
\end{array}
\end{equation}
optimum problem unique solution.
\end{tetel}

Notice that in the case of $\alpha=\frac{1}{2}$, problem (\ref{eq45}) reduces to problem (\ref{eq44}).
The algorithm is the solution of the (\ref{eq45}) optimum problem. 

Many author criticized Nash's original axioms, and beside the modification of the axiom system, more and more
new solution concepts and methods were introduced. Without expose the actual axioms, we will show
the methods judged to be of the utmost importance by the literature.

In the case of the \ki{Kalai--Smorodinsky solution}\inddef{Kalai--Smorodinsky solution}\nevindex{Kalai, Ehud}\nevindex{Smorodinsky, Meir} 
we determine firstly the ideal point, which coordinates are:
$$f_i^* = \max\{f_i|(f_1,f_2)\in H, (f_1,f_2)\geq \mathbf{f_*}\} \koz ,$$
then we will accept the last mutual point of the half-line joining $\mathbf{f_*}$ to the ideal point and $H$ as solution.
Figure \ref{fig:abra9}.  shows the method. Notice that this is an direction dependent method, where the half-line
shows the direction of growing and $\mathbf{f_*}$ is the chosen start point.

The algorithm is the solution of the following optimum problem. 
$$t \longrightarrow max$$
provided that
$$\mathbf{f}_* + t(\mathbf{f}^* - \mathbf{f}_*) \in H \koz .$$

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.9.eps}
\caption{Kalai--Smorodinsky solution.\label{fig:abra9}}
\end{center}
\end{figure}

%\epskep{5.9}{Kalai--Smorodinsky megoldás.\label{fig:abra9}}

\begin{pelda}\label{ex20}
In the case of the previous example $ \mathbf{f}_*=(0,-1)$ and $ \mathbf{f}^*=(2,1)$. We can see in Figure \ref{fig:abra10},
that the last point of the half-line joining $ \mathbf{f}_*$ to $ \mathbf{f}^*$ in $H$ is the intersection point of the half-line 
and the section joining $(1,1)$ to $(2,-1)$.

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.10.eps}
\caption{Solution of Example \ref{ex20}\label{fig:abra10}}
\end{center}
\end{figure}

%\epskep{5.10}{A \ref{ex20} példa megoldása.\label{fig:abra10}}

The equation of the half-line is $$f_2=f_1-1 \koz ,$$ while the equation of the joining section is $$f_2=-2f_1+3 \koz ,$$ so the intersect point:
$f_1=\frac{4}{3}, f_2=\frac{1}{3}$.
\end{pelda}

In the case of the \ki{equal-loss method}\inddef{equal-loss method} we assume, that starting from the ideal point the two
decision makers reduce the objective function values equally until they find a possible solution. This concept is equivalent to the
solution of the
\begin{equation}\label{eq46}
t \longrightarrow min \mspace{40mu} ((f_1^*-t,f_2^*-t) \in H)
\end{equation}
optimum problem. Let $t^*$ denote the minimal $t$ value, then the $(f_1^*-t^*,f_2^*-t^*)$ point
is the solution of the conflict. The algorithm is the solution of the (\ref{eq46}) optimum problem.

\begin{pelda}
In the case of the previous example $\mathbf{f}^*=(2,1)$, so starting from this point going by the $45^\circ$  line,
the first possible solution is the $f_1=\frac{4}{3}, f_2=\frac{1}{3}$ point again.
\end{pelda}

In the case of the method of \ki{monotonous area}\inddef{method of monotonous area} the $(f_1,f_2)$ solution is given by as follows.
The linear section joining $(f_{1*},f_{2*})$ to $(f_1,f_2)$ divides the set $H$ into two parts, if  $(f_1,f_2)$ is a Pareto optimal solution.
In the application of this concept we require the two areas being equal. Figure \ref{fig:abra11} shows the concept. The two areas are
given by as follows:
$$\int_{f_{1*}}^{f_1}(g(t)-f_{2*})dt-\frac{1}{2}(f_1-f_{1*})(g(f_1)-f_{2*})$$
and
$$\frac{1}{2}(f_1-f_{1*})(g(f_1)-f_{2*})+\int_{f_1}^{f_1^*} (g(t)-f_2^*)dt$$
where we suppose that $f_2=g(f_1)$ defines the graph of the Pareto optimal solution. Thus we get a simple equation to determine
the unknown value of  $f_1$.

\begin{figure}[!t]
\begin{center}
\includegraphics[scale=0.35]{5.11.eps}
\caption{The method of monotonous area.\label{fig:abra11}}
\end{center}
\end{figure}

%\epskep{5.11}{A monoton terület módszere.\label{fig:abra11}}

The algorithm is the solution of the following nonlinear, univariate equation:
$$\int_{f_{1*}}^{f_1} (g(t)-f_{2*}) dt - \int_{f_1}^{f_{1*}} (g(t)-f_2^*)dt-(f_1-f_{1*})(g(f_1)-f_{2*})=0 \koz .$$
Any commonly known (bisection, secant, Newton's method) method can be used to solve the problem.

\begin{gyak}
\ujgyak \label{jat6.1}
Consider that  $H=\{(f_1,f_2)|f_1,f_2\geq 0, f_1+2f_2\leq 4\}$. Be  $f_{1*}=f_{2*}=0$.  Use the (\ref{eq44})
optimum problem.
\ujgyak \label{jat6.2}
Assume that the two decision makers are not equally important in the previous exercise. $\alpha=\frac{1}{3}, 1-\alpha=\frac{2}{3}$. 
Solve the  (\ref{eq45}) optimum problem.
\ujgyak \label{jat6.3}
Use the  Kalai--Smorodinsky solution for Exercise \ref{jat6.1}
\ujgyak \label{jat6.4}
Use the equal-loss method for Exercise \ref{jat6.1}
\ujgyak \label{jat6.5}
Use the method of monotonous area for Exercise \ref{jat6.1}
\end{gyak}

\index{axiomatic methods|)}

\begin{fld}
\ujfld{Elsõ feladat címe\label{jat1}}{ 
Prove that the solution of problem  (\ref{eq9}) is Pareto optimal for any positive $\alpha_1,\alpha_2,\dots,\alpha_I$ values.}
\ujfld{Masodik feladat címe\label{jat2}}{ 
Prove that the distance dependent methods always give Pareto optimal solution for $\varrho_1$.
Is it also true for $\varrho_\infty$?}
\ujfld{Harmadik feladat címe\label{jat3}}{ 
Find a simple example for which the direction dependent methods give non Pareto optimal solution. 
\index{Pareto optimal}}
\ujfld{Negyedik feladat címe\label{jat4}}{ 
Suppose in addition to the conditions of \ref{theorem2}. that all of the $f_i$  functions are strictly concave in $x_i$.
Give an example for which there are more than one equilibrium.}
\ujfld{Ötödik feladat címe\label{jat5}}{ 
Prove that the Shapley values result imputation and satisfy the (\ref{eq35})--(\ref{eq36}) conditions.   
\index{Shapley value}\index{imputation}}
\ujfld{Hatodik feladat címe\label{jat6}}{
Solve such a group decision making table where the method of paired comparison doesn't satisfy the requirement of transitivity.
That is there are such $i,j,k$ alternatives for which $i\succ j$, $j\succ k$, but $k\succ i$.}
\ujfld{Hetedik feladat címe\label{jat7}}{ 
Construct such an example, where the application of Borda measure equally qualifies all of the alternatives.
\index{Borda measure}}
\ujfld{Nyolcadik feladat címe\label{jat8}}{ 
Prove that using the  Kalai--Smorodinsky solution for non convex $H$, the solution is not necessarily Pareto optimal.}
\ujfld{Kilencedik feladat címe\label{jat9}}{ 
Show that for non convex $H$, neither the equal-loss method nor the method of monotonous area can guarantee 
Pareto optimal solution.
\index{conflict situations|)}}
\end{fld}

\begin{fejmegj}
Readers interested in multi-objective programming can find addition details and methods related to the topic 
in the \cite{SzidarovszkyG1986} book. There are more details about the method of equilibrium and the
solution concepts of the cooperative games in the \cite{ForgoSz99} monograph.
The \cite{TaylorP2008} monograph comprises additional methods and formulas from the methodology of
group decision making. 
Additional details to Theorem \ref{tetel6} originates from Hash can be found in \cite{Nash1950}.
One can read more details about the weakening of the conditions of this theorem in \cite{HarsanyiS1972}.
Details about the Kalai--Smorodinsky solution, the equal-loss method and the method of monotonous area can
found respectively in  \cite{KalaiS1975}, \cite{Chun1988} and \cite{Anbarci1993}.
Note finally that the \cite{Thomson1994} summary paper discuss the axiomatic introduction and properties of
these and other newer methods.  

The results discussed in this chapter can be found in the book of Molnár Sándor\nevindex{Molnár, Sándor} and
Szidarovszky Ferenc\nevindex{Szidarovszky, Ferenc} \cite{MolnarSz2010} in details.
\end{fejmegj}
