[figure]

Representing and aggregating preferences using a stochastic interpretation

François Glineur

Faculté Polytechnique de Mons

Euro XVI Brussels, July 13, 1998

Representing and aggregating preferences using a stochastic interpretation

[figure]

[figure: Outline]

Introduction

• Markov chains

• Preference relations

Stochastic method

• Single preference relation

• Going multicriteria

• Introducing incomparability

Illustrations

• Some preference relations

• Factory location

Conclusions

François Glineur, FPMs  Page 2  Euro XVI, Brussels

[figure]

[figure]

Markov chains

\overline{Definitions}

E = set of n states = {E_{i}} X = set of random variables = {X_{t}} where t is discrete time index and X_{t} ∈ E X is a finite discrete-time Markov chain iff

• X_{t} depends only on X_{t−1} (markovian, memoryless process)

• This dependence is time-invariant (homogeneous process)

X completely defined by matrix M = {p_{i,j}} where

p_{i,j} = ℙ(X_{t} = E_{j} | X_{t−1} = E_{i})

Representation as a valued directed graph (nodes ≡ states, arcs ≡ transitions)

François Glineur, FPMs  Page 3  Euro XVI, Brussels

[figure]

Example and properties

M =(\begin{matrix}\frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & \frac{1}{4} & \frac{3}{4} \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{matrix} ) [figure: E_{1}; 1/2; 1/2; E_{2}; 1/3; 1/3; 1/3; E_{3}; 1/4; 3/4; E_{4}; 1/2; 1/2]

M is a stochastic matrix (row sum equal to 1) Let a_{0} be the initial probability distribution (corresponding to X_{0})

1. It is possible to compute a_{i} (distribution of X_{i}) recursively (from a_{i−1}) ∀i

2. Under a regularity assumption, the sequence {a_{i}} tends to a limit a independent of initial distribution a_{0}

3. This limit a is called stationary distribution, and is efficiently computable (left eigenvector or linear system)

In the example, a =(_{0} _{0} \frac{2}{5} \frac{3}{5} )

François Glineur, FPMs  Page 4  Euro XVI, Brussels

[figure]

[figure]

Preference relations

\overline{Definitions}

A = set of n alternatives = {A_{i}} R = binary relation on A (⊆ A × A) Let a, b, c ∈ A. Relation R is

• reflexive if a R a

• complete if a R b or b R a

• symmetric if a R b ⇒ b R a

• asymmetric if a R b ⇒ b ¬R a

• transitive if a R b, b R c ⇒ a R c Relation R is understood as ≤, which means a R b ⇔ a is not strictly preferred to b I ≡ indifference part of R, defined by a I b ⇔ a R b and b R a S ≡ strict preference part of R, defined by a S b ⇔ a R b and b ¬R a I is symmetric and reflexive, S is asymmetric, R = I ∪ S

François Glineur, FPMs  Page 5  Euro XVI, Brussels

[figure]

Representations and examples

• Matrix representation {r_{i,j}} with r_{i,j} equal to 1 if A_{i} R A_{j}, 0 otherwise

• Representation as a directed graph (nodes ≡ alternatives, arcs ≡ relation R)

For example, A = {a, b, c} and R = {(a, c), (c, a), (a, b), (b, c), (a, a), (b, b), (c, c)} is reflexive and complete

M =(\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) [figure: a; b; c]

François Glineur, FPMs  Page 6  Euro XVI, Brussels

[figure]

Some preference relations

Let R be a complete and reflexive relation

• If S and I are both transitive, R is a complete preorder (weak order). It is possible to assign a number v_{i} to each alternative such that A_{i} R A_{j} ⇔ v_{i} ≤ v_{j}

• If S is transitive et I = {(a, a)} ∀a ∈ R, R is a total order. It is possible to assign a distinct number v_{i} to each alternative such that A_{i} R A_{j} ⇔ v_{i} ≤ v_{j}

• If it is possible to assign a real interval U_{i} = [v_{i} v′_{i}] to each alternative such that A_{i} I A_{j} ⇔ U_{i} ∩ U_{j} ≠ ∅ and A_{i} S A_{j} ⇔ v′_{i} < v_{j}, R is a (total) interval order. S is transitive but I isn’t.

• If it is possible to assign a real interval U_{i} = [v_{i}v′_{i}] to each alternative such that A_{i} I A_{j} ⇔ U_{i} ∩ U_{j} ≠ ∅, A_{i} S A_{j} ⇔ v′_{i} < v_{j} and no interval is strictly included in another one, R is a (total) semiorder. S is transitive but I isn’t.

François Glineur, FPMs  Page 7  Euro XVI, Brussels

[figure]

[figure]

Some preference relations

• Total order (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})

[figure: a; b; c]

• Total preorder (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})

[figure: a; b, c]

• Interval order (\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix})

[figure: {; [; a; ]; [; b; ]; [; c; ]; }; d]

• Semiorder (\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix})

[figure: [; a; ]; [; b; {; ]; [; }; d; c; ]]

François Glineur, FPMs  Page 8  Euro XVI, Brussels

[figure]

\overline{Theorems}

Let R a preference relation without equivalent alternatives (a and b are equivalent iff a R x ⇔ b R x and x R a ⇔ x R b ∀x ∈ A)

• If R is a semiorder, there is a unique total order underlying R. It is induced by the numbers {v_{i}} (or {v′_{i}}). Moreover, if rows and columns of the matrix representation of R are sorted in that order, we get a step-type matrix.

• If R is an interval order, there are two total orders underlying R. Moreover, if rows (and columns) of the matrix representation of R are sorted in the first (and second) order, we also get a step-type matrix.

• (\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}) is a step-type matrix

François Glineur, FPMs  Page 9  Euro XVI, Brussels

[figure]

[figure]

Stochastic method

Single preference relation

Let R be a complete and reflexive binary preference relation. We proceed as follows :

1. Build a Markov chain : Associate to each alternative A_{i} a state E_{i}

2. Choose the transition probabilities, requiring the following conditions to hold • p_{i,j} > 0 when A_{i} R A_{j}

• p_{i,j} = 0 when A_{i} ¬R A_{j}

• Matrix {p_{i,j}} is stochastic

3. Compute the stationary distribution and rank the alternatives according to the resulting probabilities

Justification

Intuitively, the process always moves from an alternative to a better or equivalent alternative. It is thus sensible to expect a high probability for the best alternatives in the stationary distribution.

François Glineur, FPMs  Page 10  Euro XVI, Brussels

[figure]

Choice of {p_{i,j}}

We want the value of p_{i,j} to be independent from other alternatives than A_{i} and A_{j}

If A_{i} R A_{j}, let p_{i,j} = \frac{1}{n}, otherwise let p_{i,j} = 0

But M is not stochastic ⇒ set p_{i,i} according to

p_{i,i} = 1 − ∑_{j≠i} p_{i,j}

With this choice, the Markov process can be described as :

1. I am currently in state E_{i}

2. Choose randomly a state E_{j} (uniformly)

3. If A_{i} R A_{j}, move to state E_{j}, otherwise stay in E_{i}

François Glineur, FPMs  Page 11  Euro XVI, Brussels

[figure]

\overline{Examples}

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) gives M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{2}{3} \end{matrix} )

[figure: a; b; c]

Stationary distribution is ( \frac{1}{4}  \frac{1}{4}  \frac{1}{2} ) : c is the

best, a and b follow.

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}) gives M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{2}{3} & \frac{1}{3} \\ 0 & 0 & 1 \end{matrix})

[figure: a; b; c]

Stationary distribution is (_{0} _{0} _{1}) : c is the best but we have no information about the other alternatives (no way to escape from c)

François Glineur, FPMs  Page 12  Euro XVI, Brussels

[figure]

Better choice of {p_{i,j}}

Let’s add a neutral state E_{0}, representing no alternative, such that p_{0,0} = 0 and p_{0,i} = \frac{1}{n}. Transitions from this state do not favor any alternative. We keep the rule

If A_{i} R A_{j}, let p_{i,j} = \frac{1}{n}, otherwise let p_{i,j} = 0

but choose the p_{i,0} to make the matrix stochastic, i.e.

p_{i,0} = 1 − ∑_{j≠0} p_{i,j}

With this choice, the Markov process can be described as

1. I am currently in state E_{i}

2. Choose randomly a state E_{j} (uniformly)

3. If A_{i} R A_{j}, move to state E_{j}, otherwise move to neutral state E_{0}

François Glineur, FPMs  Page 13  Euro XVI, Brussels

[figure]

\overline{Examples}

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) gives M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

Stationary distribution is ( \frac{7}{27}  \frac{6}{27}  \frac{9}{27}  \frac{5}{27} ) : c

is the best, b is the worst

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}) gives M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & \frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

Stationary distribution is ( \frac{4}{27}  \frac{6}{27}  \frac{9}{27}  \frac{8}{27} ) : c

is the best, a is the worst

\overline{Property}

If R is a total preorder, the probabilities from the stationary distribution are ranked according to R

François Glineur, FPMs  Page 14  Euro XVI, Brussels

[figure]

[figure]

Going multicriteria

R = set of preference relations {R_{i}} where R_{i} is complete and reflexive. These relations are weighted by {w_{i}} whose sum is equal to 1. M_{i} = stochastic matrix for each R_{i} (computed as above). Let

M = ∑_{i} w_{i}M_{i}

M is also stochastic and describes a Markov chain. We rank the alternatives according to the probabilities from the resulting stationary distribution.

1. I am currently in state E_{i}

2. Choose randomly a relation R_{p} (according to the {w_{i}})

3. Choose randomly a state E_{j} (uniformly)

4. If A_{i} R_{p} A_{j}, move to state E_{j}, otherwise move to neutral state E_{0}

François Glineur, FPMs  Page 15  Euro XVI, Brussels

[figure]

\overline{Examples}

r = 2, w_{1} = \frac{1}{3} and w_{2} = \frac{2}{3}

M_{1} = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & \frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix}) M_{2} = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{9} & \frac{5}{9} \\ \frac{2}{9} & \frac{2}{9} & \frac{1}{3} & \frac{2}{9} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

R_{1} : [figure: b; a; c] R_{2} : [figure: b; a; c]

Stationary distribution is ( \frac{16}{79}  \frac{24}{79}  \frac{21}{79}  \frac{18}{79} ) : b

is the best, a is the worst

François Glineur, FPMs  Page 16  Euro XVI, Brussels

[figure]

[figure]

Expressing incomparability

\overline{Method}

In light of Arrow’s theorem, we shouldn’t expect good properties from a preference analysis method producing a total preorder. ⇒ Weaken the relation produced by our method No distinction between A_{i} S A_{j} et A_{i} I A_{j} (indifference and strict preference) When A_{i} and A_{j} are indifferent, choose something less radical than p_{i,j} = \frac{1}{n} :

• If A_{i} S A_{j}, let p_{i,j} = \frac{1}{n}

• If A_{i} I A_{j}, let p_{i,j} = \frac{α}{n}

• Otherwise let p_{i,j} = 0

where α is a parameter to choose between 0 and 1

François Glineur, FPMs  Page 17  Euro XVI, Brussels

[figure]

Now, the Markov process can be described as

1. I am currently in state E_{i}

2. Choose randomly a relation R_{p} (according to the {w_{i}})

3. Choose randomly a state E_{j} • If A_{i} S_{p} A_{j}, move to state E_{j}

• If A_{i} I_{p} A_{j}, move to state E_{j} with probability α and to neutral state E_{0} with probability 1 − α

• Otherwise, move to state E_{0}

Use the family of total preorders parameterized by α to deduce a partial preorder :

• If A_{i} is better than A_{j} for all values of α, declare A_{i} > A_{j}

• If A_{i} is worse than A_{j} for all values of α, declare A_{i} < A_{j}

• Otherwise, A_{i} and A_{j} are not comparable

François Glineur, FPMs  Page 18  Euro XVI, Brussels

[figure]

\overline{Examples}

Total order

Total preorder Interval order Semiorder

François Glineur, FPMs  Page 19  Euro XVI, Brussels

[figure]

\overline{Properties}

If R is a total preorder, the rankings obtained match R ∀α ∈ [0 1] If R is a semiorder, the rankings obtained match the unique total order underlying R ∀α ∈]0 1[ If R is an interval order, the rankings obtained letting α tend to 0 and 1 match the two total orders underlying R ⇒ there is at least one case of incomparability

\overline{Usage}

To select the best alternative, choose among those being ranked first for at least one value of α (these ones being incomparable) The more a crossing is close to 0 or 1, the less the associated incomparability is strong

François Glineur, FPMs  Page 20  Euro XVI, Brussels

[figure]

Illustrations - Semiorders

François Glineur, FPMs  Page 21  Euro XVI, Brussels

[figure]

[figure]

Factory location

• 5 numerical criteria : Price, Transport, Environment, Residential, Competition

• Use of thresholds to compute a semiorder for each criterion

François Glineur, FPMs  Page 22  Euro XVI, Brussels

[figure]

[figure]

Conclusions

Stochastic method

• Intuitive principle

• Graphical results

• No parameter value to choose

• Easy to implement

Multicriteria analysis

• Natural generalization

• Sensitivity analysis easy to perform

• Cardinal information allowed

Further research

• Theoretical properties (independence)

• Valued relations

François Glineur, FPMs  Page 23  Euro XVI, Brussels