MTH5114 - Linear Programming and Games - 2023/24
Topic outline
-
- Seminar Solutions - Week 8 (Q2) - in the definition of unboundedness, it is supposed to say C^T x >= k instead of <=.
- Solutions to Coursework 3 (Weeks 8,9,10) - For the solution to Week 8, Q1(a), there were some incorrect signs (next to 400).
-
Each week, I will upload my written lecture notes in the weekly sections and these written notes will form the examinable content for the module.
Here I also providing printed lecture notes (from a previous version of this module taught by Dr Justin Ward). These printed lecture notes cover essentially the same material as we will cover but provide more detail and explanation in places. Depending on their learning style, some students prefer to work from the printed notes and others from the written notes, while others use a combination. Therefore I have made both available.
Please note that the division into weeks for the printed notes might slightly mismatch how we proceed but should broadly be the same. Please email me if you find any issues either with these printed notes or the written notes or if you're unsure about something in the notes.
-
Topics Covered:
- Introduction to the module.
- Background and notation from linear algebra.
- Definition of a linear program.
- Procedure for transforming a linear program to standard inequality form.
- Definition of feasible and optimal solutions (this was not covered and will be covered next week).
By the end of Week 1, you should be able to:
- Identify the parts of a mathematical optimisation program.
- Define concepts like linear combinations, linear equations, and linear inequalities.
- Define what is meant by a linear program.
- Convert a given linear program into standard inequality form.
- Define and understand the concepts of a feasible solution and an optimal solution of a linear program (will be covered next week).
-
Topics covered:
- Definition of feasible and optimal solutions (which we didn't manage to cover last week)
- Modelling production problems with linear programs.
- Modelling transportation problems with linear programs.
- Basic geometry of lines in the plane (if reading the printed notes, this is in Week 3 printed notes).
By the end of Week 2, you should be able to:
- Formulate linear programs to model production problems.
- Formulate linear programs to model transportation problems.
-
Topics covered:
- Geometry of lines in 2 dimensions (partially covered at the end of Week 2).
- Solving LPs in 2 dimensions via sketching.
- Definition of infeasible and unbounded linear programs.
- Generalisations to higher dimensions (only very briefly mentioned)
- Definitions of convex combinations and extreme point solutions.
By the end of Week 3, you should be able to:
- Sketch the feasible regions of linear programs in 2 dimensions and find their solutions .
- Explain what it means for a linear program to be infeasible or unbounded.
- Understand what is meant by an extreme point solution, and a convex combination, and how these concepts work geometrically.
-
Many real-world operational problems involve e.g. identifying the best possible way of producing goods, allocating resources, or transporting goods subject to a set of constraints. This module introduces you to the practical modelling of such problems, together with the mathematical theory behind the most widespread tools for solving them. You will learn how to model common operational problems as linear programs, as well as the underlying theory of linear programming. Building on these concepts, you will also learn basic game theory towards the end of the module. Game theory is about modelling and understanding situations that arise when competing agents interact strategically and rationally to maximise their gains. This has applications in the social sciences and economics.This module is primarily a theoretical module but with clear practical applications. As such it includes a blend of fundamental theorems with proofs, alongside practical algorithms and modelling techniques.
-
Topics covered:
- Definitions of convex combinations and extreme point solutions (covered in week 3)
- Procedure for converting an LP to standard equation form.
- Proof that every LP with an optimal solution has an optimal extreme point solution.
- Definition of basic feasible solutions.
- Proof that a solution is an extreme point solution if and only if it is a basic feasible solution (proof by example given in lectures - full proof in printed lecture notes).
By the end of Week 4, you should be able to:
- Convert a linear program to standard equation form using slack variables.
- Explain what a basic feasible solution to a linear program is, and determine whether a given solution is a basic feasible solution..
- Prove results about convex combinations, extreme points, and basic feasible solutions of linear programs.
-
Topics covered:
- The Simplex algorithm for problem with a feasible origin
- Detecting unbounded linear programs using the simplex algorithm (partially covered and will continue next week)
By the end of Week 5, you should be able to:
- Carry out the tasks to run the Simplex algorithm on small examples:
- Produce an initial tableau from linear program with a feasible origin.
- Perform pivot operations on a valid tableau to obtain a new tableau.
- Determine when an optimal solution has been found and determine its objective value and the values it assigns to variables from the tableau.
- Determine if a linear program is unbounded by using the simplex algorithm (partially covered and will continue next week)
-
Topics covered:
- How the simplex algorithm determines unboundedness of a linear program (continuation from last week)
- Basic feasible solutions revisited
- Geometry of the simplex algorithm (non-examinable)
- The 2-phase simplex algorithm
- Termination of the simplex algorithm (non-examinable)
By the end of Week 6, you should be able to:
- Carry out the 2-phase simplex algorithm to solve general linear programs
-
-
Topics covered:
- The dual of a linear program
- The Weak Duality theorem
- Strong Duality Theorem
By the end of Week 8, you should be able to:
- Find the dual of a given linear program
- Explain the concept of weak duality, and the related theorem.
- Find the optimal solution to the dual of a program using its optimal simplex tableau.
- The dual of a linear program
-
Topics covered:
- Complementary Slackness
- Interpretation of the dual
- Modelling min-max, max-min, and piecewise linear concave and convex objectives
By the end of Week 9, you should be able to:
- Write the complementary slackness conditions for a given program and solutions to it and its dual.
- Use complementary slackness to check whether or not a given solution is optimal.
- Give an intuitive interpretation for dual variables, and make decisions or recommendations based on them
- Formulate linear programs to model problems with a min-max or a max-min objective and that involve maximising a piecewise linear concave function.
-
Topics covered:
- Modelling min-max, max-min, and piecewise linear concave and convex objectives
- Zero-sum two-player strategic games
- The theory of rational choice
- Security levels
- Nash equilibria
By the end of Week 9, you should be able to:
- Give the payoff matrix for a simple two-player zero-sum game.
- Explain the concepts of (pure) strategies and security levels.
- Use the concept of a player's security level to say when a pure Nash equilibria exists for a 2-player zero-sum game.
- Modelling min-max, max-min, and piecewise linear concave and convex objectives
-
Topics covered:
- Mixed strategies
- Security levels and general Nash equilibria for mixed strategies
- Linear programming and security levels
- Every 2-player zero-sum game has a (mixed) Nash equilibrium
By the end of Week 10, you should be able to:
- Explain the concepts of security levels and general Nash equilibria for mixed strategies
- Compute security levels for mixed strategies and compute when a pair of strategies forms a Nash equilibirum
- Give a linear program to find a mixed strategy with best security level
- Understand how duality is used to show that every 2-player zero-sum game has a Nash equilibrium
-
-
-
-
-
The document below provides detailed information about the exam. It is only partially complete and will be updated at the end of week 12. Please note that this year's exam contains a bookwork question which was not the case in previous years; please read the document below for more details.
- Exam information (last updated Tue 16 April)
Below are links to past papers.
- 2023 Exam [Solutions] This exam serves as a good indicator of the structure, style and length of the 2024 exam except that the 2024 exam will have a bookwork question; see the Exam information document above for examples of such questions. Also the 2024 exam is 3 hours long and you are not allowed to bring any notes.
- 2022 Exam [Solutions] (This says mock exam on the cover but is in fact the 2022 exam.)
- 2021 Exam [Solutions]
- 2020 Exam. [Solutions]
-
Topics covered:
- General (non-zero-sum) 2-player games
- Best responses
- Pure and mixed Nash equilibria in general games
- The Prisoner's Dilemma (discussed in printed notes)
- Braess's Paradox (discussed in printed notes - non-examinable)
By the end of Week 12, you should be able to:
- Explain the concept of the best response to a strategy.
- Define the concept of a pure and mixed Nash equilibrium for a general 2-player game.
- Find best responses and use them to identify pure Nash equilibria for general 2-player games.
-
Here is a list of books from the library (including 2 available online) that may be useful for supplementing the lecture material. These are completely optional.
Note that different authors have different conventions for "standard forms" of linear programs: some use equation form, some use inequality form, and some may even use minimisation programs as their "standard"! If you consult these, you should make sure you understand how this affects the presentation of results.
