This is a summary of the course Decision Modeling taught at the Université Paris Saclay - CentraleSupélec by Professor Brice Mayag in the academic year 23/24. Most of the content of this document is adapted from the course notes by Mayag, [1], so I won’t be citing it all the time. Other references will be provided when used.

Contents

1 Introduction

1.1 Models

There are many definition of what a model is, depending on the perspective used. For example, a model can be understood as a ’standard or example for imitation or comparison’ or as a ’person employed to wear clothing ot pose with a product for purposes of display and advertising’. Nonetheless, in the context of decision modeling, which is the one in which we are interested, the definition of model is:

Models are useful to enhance our understanding of the world to improve our decision making, and they enable us to elaborate a scientific methodology to solve a problem in a duplicable way and with the aim of reducing bias in mind.

A model is said to be deterministic if the outcomes are precisely determined through known relationships among states and events. This kind of models always produce the same output when given the same input. On the other hand, a model is probabilistic (or stochastic) when all the data that it tries to explain is not known with certainty.

For example, the Newtonian model for gravity is deterministic, while a prediction model for college acceptance is probabilistic.

Deterministic models are used in domains such as Multi-Attribute Decision Making or Linear Programming, among others; while probabilistic models are used in queuing problems, simulations, etc.

We can also classify the data that is used to define a model into qualitative and quantitative. The former refers to data that is expressed in terms of words, while the latter is data easily expressed using numbers. An example of qualitative data is the hair color of people in class, and for quantitative data is the height of people in class.

We can be more precise in our wording, and call the models that we are talking about formal models, which refer to those models that provide a precise statement of the components of the model and their relationships, usually by means of mathematical equations. This make them easy to communicate precisely and the ability to give replicable results. However, being formal does not mean being true. A model can fail to represent the reality that it tries to describe.

1.2 Decision Theory and Decision Analysis

Decisions appear in many domains, including Mathematics, Economics, Computer Sciences, Psychology,...

In the previous definition, a Decision Process refers to a strategy of intervention, such as aid, communication or justification, among others. There are many ways to provide decision aid and no single way to compare methods. This, together with the fact that different models may lkead to different recommendations, makes it hard to assess when a Decision Analysis model is ’good’ or, more appropriately, ’suitable’.

Therefore, we cannot compare decision making to solving a well-defined problem, as the former is highly dependent on opinions, interests and, more generally, different human factors involved. In every decision process, there are several possible interventions, among which we can find imagining compromises, communicating, coordinating, controlling, motivating or conducting change.

There are many different models used in Decision Analysis nowadays, with the advantages of:

• Providing a clear language that can be leveraged as a communication tool

• Capturing the essence of a situation, acting a structuration tool

• Answering ’what-if ’ questions, serving as a exploration tool

On the other hand, their drawbacks are their high complexity and opaqueness. In addition, in many situations people could argue that such models are not necessary because they already know how to take decisions and they would over-complicate the process; or would ask for higher-level explanations or ideas that are not suitable for formalization; or would rather rely on their intuition.

1.3 Main Steps of Developing a Decision Model

1. Formulation: translate the problem scenario into a mathematical model.

   This involves the definition of the problem and the development of a decision model, i.e., the definition of the variables or measurable quantities that vary, and the parameters or measurable quantities inherent to the problem.

2. Solution: solve the mathematical expressions from the formulation.

   This process involves the development of the solutions by correctly manipulating the model to arrive at the best solution, and the testing of the solution, to check that it works as expected and meets the expectations.

3. Interpretation: discover the implications of the results.

   This is usually done by conducting sensitivity analysis, i.e., testing the different outcomes obtained under a variety of states; and implementing results, enacting the solutions and monitoring the performance.

The outlined process is very high level, and there are many possible problems that can arise:

• Defining the problem: we can find conflicting viewpoints that impact differently the stakeholders.

• Model development: it is not always easy to find the formal model that describes the problem at hand, and it is usual to make adaptations.

• Acquering data: can be hard in some scenarios, as well as checking its validity and correctness.

• Developing a solution: we can find many limitations, such as only finding one answer, finding approximate answers, prohibitive computing times,...

• Implementation: it is crucial that the solution is feasible to be implemented, both from a managerial point of view and from the user perspective.

1.4 Decision’s Algorithm & Transparency

Decisions made by algorithms can be opaque because of technical and social reasons, in addition to being made purposely opaque to protect intellectual property.

Usually, we find contradictory objectives when developing an algorithm, because simpler algorithms are usually time intensive, while algorithms that are very efficient are very complex are hard to understand.

This concept is opennes about the purpose, structure and underlying actions of the algorithms used to search for, process and deliver information. Two important properties of transsparency are:

• Explanability: systems and institutions that use algorithm decision making are encouraged to produce explanations regarding both the procedures followed by the algorithm and the specific decisions that are made. This is specially relevant in public policy contexts.

• Accountability: institutions should be held responsible for decisions made by the algorithms they use, even if it is not feasible to explain in detail how the algorithms produce their results.

2 Preferences as binary relations

Definition 2.1. Given a set X, a binary relation, R, is a subset of ordered pairs of elements in X:

We can write ∈ R or, equivalently, xRy.

Relations can be expressed as directed graphs. For instance, a relation R of a set X can be represented as the graph G_R = , where N_X are the nodes, representing each element in X and E_R are the edges, representing each pair in R. The edges are constructed in such a way that e = ∈ E_R ⇐⇒ xRy.

Another way to represent relations is using matrices. We can construct a matrix M_R by

where

Example 2.2. The previous example can be represented with the following matrix:

Depending on how a relation is constructed, it can possess different properties. Some interesting properties are defined as follows:

Example 2.3. A semi-transitive relation example.

✓	✓	×

In addition, we can define paths and cycles on relations, analogously as how it is done in graph theory:

Definition 2.3. A path from x ∈ X to y ∈ X exists if there are x₁,...,x_n ∈ X such that

A path is called a cycle if the it goes from x to x.

For every relation, we can extract two subrelations, as its symmetric part and its asymmetric part:

Definition 2.4. Given a binary relation R on X, we can define its symmetric part, I, as

and its asymmetric part, P, as

The symmetric part is denoted by I because we can understand this as the all the indiferent pairs of R. In others words, if we understand a relation as a preference over the elements in X, then xRy would mean x is at least as convenient as y. Therefore, if we have xRy and yRx, we could think of them as equally convenient, so the decision between them is indiferent. On the other hand, the asymmetric part is denoted by P, from preference, following a similar reasoning.

When we have two different relations, R and R′, on the same set, X. We can define their concatenation:

Definition 2.5. Let R and R′ be two relations on X. We define their concatenation as

The following proposition establishes different relationships between the concepts we have seen so far:

There are some relations that fulfill several of the properties that we have seen, and that hold special characteristics. For instance:

Exercise 2.1. Let B be a binary relaiton on a set X = defined by

aBa,aBb,aBc,aBd,aBe,aBf
bBb,bBc,bBd,bBe,bBf
cBc,cBd,cBe,cBf
dBb,dBc,dBd,dBe
eBd,eBe,eBf
fBe,fBf

Give a matrix and a graph representation of B

The matrix form of B is the following:

And the graph representation:

Is B reflexive? Symmetric? Asymmetric? Transitive? Negative transitive? Semi-transitive?

• Reflexive: Yes, since xBx,∀x ∈ X.

• Symmetric: No, aBb but not.

• Asymmetric: No, eBf but fBe.

• Transitive: No, dBe and eBf, but not dBf.

• Negative transitive: No, not and not but fBf.

• Semi-transitive: Yes. Let’s do this little by litte.

  If we take x = a, then aBt,∀t, so it will hold. If y = a, then x such that xBa, so it will hold. Same happens if z = a. Finally, if t = a, then aBz,∀z ∈ X, so it also holds.

  If we eliminate a (since we have seen all cases in which a is involved), we obtain the relation:

  

  Using the same argument, b will work now. When we remove it, we get:

  

  And once again we can use c. When we remove it, we get:

  

  Now we can repeat the same with e, and when we remove it we obtain a two-element relation, which is always semi-transitive.

Exercise 2.2. Let B and B′ be two equivalence relations on a set X:

Prove that B ∩ B′ is an equivalence relation, where

We need to see that B ∩ B′ is reflexive, symmetric and transitive:

• Reflexive: take x ∈ X, then xx ⇐⇒ xBx ∧ xB′x, which holds since B and B′ are reflexive.

• Symmetric: take x,y ∈ X such that xy. This means that xBy ∧ xB′y. Since B and B′ are symmetric, we obtain that yBx ∧ yB′x, and therefore yx.

• Transitive: take x,y,z ∈ X such that xy ∧ yz. This means that xBy,xB′y,yBz and yB′z. Now, since B and B′ are transitive, we obtain xBz and xB′z, so xz.

Is B ∪ B′ an equivalence relation, where

Reflexivity and symmetry are preserved, but what about transitivity? It is not... Take X = and the relations

Then, they are both equivalence relations, but their union is not. This is shown below:

As we can see, in the union, we find and , but not , so it is not transitive.

Could we have the same conclusions if B and B′ are two complete preorders on a set X?

We are been asked if B ∩ B′ and B ∪ B′ are also complete preorders. The answers to both questions is no.

In the case of the intersection, the transitivity is preserved, following the same argument we did for equivalence relations, but completeness is not preserved. To see this, take X = and the relations

B :	≻
B′ :	≻.

Then, the intersection is

which is not complete.

As for the union, the opposite happens. Completeness is preserved, because the relations involved are complete. However, transitivity is not preserved. As a counter example, take the following graph visualization:

As we can see, in the union, we find and but not .

References