Famke Nouwens
Topic 1 – Simplex algorithm
Linear program contains:
1. Decision variables
2. Objective function: linear expression of decision variables, to be minimized or maximized.
3. Constraints: linear expressions of decision variables, which are required to be ≤, =, ≥ a
constant c.
Underlying assumptions for LP’s:
- Linearity of all expressions is key
- Linearity implies the following assumptions:
• Proportionality: marginal returns are constant, no scale effects
• Additivity: impact of different decision variables sums up
• Divisibility: allow any fractional numbers (can be excluded → integer programming)
A solution to an LP provides information about the minimum/maximum attainable value of the
objective function, which values the decision variables must have in order to achieve this and which
constraints are binding: bottlenecks that prevent further improvement.
Simplex method: algorithm that searches through the feasible region for a numerical solution to an
LP.
- Feasible solution: solution that satisfies all the constraints.
- Feasible region: set of all feasible solutions.
Topic 2 – Monte Carlo algorithm
Monte Carlo Simulation: statistical method used in simulation of data, where a computational
algorithm is used that relies on repeated random sampling to compute its results → randomized
algorithm. It is often used when it is infeasible or impossible to compute an exact result with a
deterministic algorithm.
Monte Carlo simulation gives the decision-maker a range of possible outcomes and the probabilities
they will occur for any choice of action. It is named after the grand casino
in Monaco at Monte Carlo, which is well-known around the world as an
icon of gambling.
The most common example to explain Monte Carlo simulations is the
Buffon Needle Experiment to approximate the value of π. The experiment
is as follows; we randomly drop N number of needles of size L onto a piece
of paper which is divided by parallel strips of length 2L. After randomly dropping these needles,
identify number of needles which touch the lines dividing the paper and the total number of needles
dropped (N).
The situations when you should use this method is when you need to estimate an outcome where
there is a high level of uncertainty in the result. This methodology is commonly used in the finance
industry for stock forecasting due to the level of randomness and uncertainty in the stock market.
Topic 3 – Monty Hall problem
, The Monty Hall problem is named after Monty Hall, the host on the show Let’s Make A Deal. The
problem is about three doors: two doors contain a goat and one door contains a million dollars. You
are asked to pick a door, and will win whatever is behind it.
Let's say you pick door 1. Before the door is opened, someone who knows what's behind the doors
(Monty Hall) opens one of the other two doors. This door will always contain a goat. You are then
asked if you wish to change your choice to the third door still unopened (i.e., the door which neither
you picked nor he opened). The Monty Hall problem is deciding whether you do.
The correct answer is that you always want to switch. If you do not switch, you have the expected
1/3 chance of winning the money, since no matter whether you initially picked the correct door,
Monty will show you a door with a goat. But after Monty has eliminated one of the doors for you (he
will never reveal the money), switching doors gives you a 2/3 chance you will win the money
(counterintuitive though it seems).
Topic 4 – Prisoner’s dilemma
Game theory: models strategic behaviour of agents who understand that their actions affect the
actions of other agents.
What is a game?
- Set of players (N)
- Set of strategies for each player (Si where 𝑖 ∈ {1,2, … , 𝑁})
- Strategy profile which consists of a strategy for each player
- Payoffs to each player for every possible strategy profile
Two-player game: two players act simultaneously, and both maximize their own payoff
The prisoner's dilemma is a paradox in decision analysis and game theory in which two individuals
acting in their own self-interests do not produce the optimal outcome. The idea is that two people
who cannot communicate with each other have to choose their own strategy, and this will always
produce a suboptimal outcome.
The typical prisoner's dilemma is set up in such a way that both parties choose to protect themselves
at the expense of the other participant. As a result, both participants find themselves in a worse
state than if they had cooperated with each other in the decision-making process.
Examples of prisoner’s dilemma in the real world are tragedy of the commons and cartels.
Topic 5 – Nash and Pareto optima
Nash equilibrium: solution concept of non-cooperative games. A Nash equilibrium is found if each
player has chosen a strategy and no player can benefit by changing strategies while the other players
keep theirs unchanged. All games with finite players and strategies have at least one NE.
Pareto optimum: measure of efficiency/optimality. A solution is Pareto optimal if there is no way a
party can be (strictly) better off without making another party worse off. There are often many
Pareto solutions in a game.
Difference: with Nash only one player can change their strategy to whereas with Pareto both players
can change strategy to see if there is a better outcome.
Prisoner 2
Stay silent (cooperate) Betray the other
Stay silent (cooperate) (1, 1) → Pareto-optimal (5, 0) → Pareto-optimal
Prisoner 1
Betray the other (0, 5) → Pareto-optimal (3, 3) → Nash-equilibrium
Topic 1 – Simplex algorithm
Linear program contains:
1. Decision variables
2. Objective function: linear expression of decision variables, to be minimized or maximized.
3. Constraints: linear expressions of decision variables, which are required to be ≤, =, ≥ a
constant c.
Underlying assumptions for LP’s:
- Linearity of all expressions is key
- Linearity implies the following assumptions:
• Proportionality: marginal returns are constant, no scale effects
• Additivity: impact of different decision variables sums up
• Divisibility: allow any fractional numbers (can be excluded → integer programming)
A solution to an LP provides information about the minimum/maximum attainable value of the
objective function, which values the decision variables must have in order to achieve this and which
constraints are binding: bottlenecks that prevent further improvement.
Simplex method: algorithm that searches through the feasible region for a numerical solution to an
LP.
- Feasible solution: solution that satisfies all the constraints.
- Feasible region: set of all feasible solutions.
Topic 2 – Monte Carlo algorithm
Monte Carlo Simulation: statistical method used in simulation of data, where a computational
algorithm is used that relies on repeated random sampling to compute its results → randomized
algorithm. It is often used when it is infeasible or impossible to compute an exact result with a
deterministic algorithm.
Monte Carlo simulation gives the decision-maker a range of possible outcomes and the probabilities
they will occur for any choice of action. It is named after the grand casino
in Monaco at Monte Carlo, which is well-known around the world as an
icon of gambling.
The most common example to explain Monte Carlo simulations is the
Buffon Needle Experiment to approximate the value of π. The experiment
is as follows; we randomly drop N number of needles of size L onto a piece
of paper which is divided by parallel strips of length 2L. After randomly dropping these needles,
identify number of needles which touch the lines dividing the paper and the total number of needles
dropped (N).
The situations when you should use this method is when you need to estimate an outcome where
there is a high level of uncertainty in the result. This methodology is commonly used in the finance
industry for stock forecasting due to the level of randomness and uncertainty in the stock market.
Topic 3 – Monty Hall problem
, The Monty Hall problem is named after Monty Hall, the host on the show Let’s Make A Deal. The
problem is about three doors: two doors contain a goat and one door contains a million dollars. You
are asked to pick a door, and will win whatever is behind it.
Let's say you pick door 1. Before the door is opened, someone who knows what's behind the doors
(Monty Hall) opens one of the other two doors. This door will always contain a goat. You are then
asked if you wish to change your choice to the third door still unopened (i.e., the door which neither
you picked nor he opened). The Monty Hall problem is deciding whether you do.
The correct answer is that you always want to switch. If you do not switch, you have the expected
1/3 chance of winning the money, since no matter whether you initially picked the correct door,
Monty will show you a door with a goat. But after Monty has eliminated one of the doors for you (he
will never reveal the money), switching doors gives you a 2/3 chance you will win the money
(counterintuitive though it seems).
Topic 4 – Prisoner’s dilemma
Game theory: models strategic behaviour of agents who understand that their actions affect the
actions of other agents.
What is a game?
- Set of players (N)
- Set of strategies for each player (Si where 𝑖 ∈ {1,2, … , 𝑁})
- Strategy profile which consists of a strategy for each player
- Payoffs to each player for every possible strategy profile
Two-player game: two players act simultaneously, and both maximize their own payoff
The prisoner's dilemma is a paradox in decision analysis and game theory in which two individuals
acting in their own self-interests do not produce the optimal outcome. The idea is that two people
who cannot communicate with each other have to choose their own strategy, and this will always
produce a suboptimal outcome.
The typical prisoner's dilemma is set up in such a way that both parties choose to protect themselves
at the expense of the other participant. As a result, both participants find themselves in a worse
state than if they had cooperated with each other in the decision-making process.
Examples of prisoner’s dilemma in the real world are tragedy of the commons and cartels.
Topic 5 – Nash and Pareto optima
Nash equilibrium: solution concept of non-cooperative games. A Nash equilibrium is found if each
player has chosen a strategy and no player can benefit by changing strategies while the other players
keep theirs unchanged. All games with finite players and strategies have at least one NE.
Pareto optimum: measure of efficiency/optimality. A solution is Pareto optimal if there is no way a
party can be (strictly) better off without making another party worse off. There are often many
Pareto solutions in a game.
Difference: with Nash only one player can change their strategy to whereas with Pareto both players
can change strategy to see if there is a better outcome.
Prisoner 2
Stay silent (cooperate) Betray the other
Stay silent (cooperate) (1, 1) → Pareto-optimal (5, 0) → Pareto-optimal
Prisoner 1
Betray the other (0, 5) → Pareto-optimal (3, 3) → Nash-equilibrium
