This is the home page for a course of 24 lectures to Cambridge MMath/MASt (Part III) students.
It will be given M, W, F at 11am in MR14, starting October 9, 2015, and ending December 2.

Course notes

Here are  course notes. I aim to make each lecture a self-contained unit on a topic, with notes of typically four A4 pages. If you think you find a mistake in the notes, check that you have the most recent copy (in case a correction has already been made). Otherwise, please let me know and I will make the correction.

Course Blog

After each lecture I will be writing a few comments in the course blog: to emphasize an idea, answer an interesting question (which perhaps a student sends to me in email or asks in lecture).

Examples sheets

There will be 3 examples sheets and classes for these, in which I will discuss their solutions.

Tuesday November 3: 16:00-18:00 MR14
Tuesday December 1: 16:00-18:00 MR14
Tuesday January 19: 16:00-18:00 MR14

Feedback

The course finishes 2 December 2015.

Past exam questions

Exam papers are available for past years starting in 2001:
2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001

Recommended books and notes

You can find these books in libraries around Cambridge. Clicking on the title link will show you where the book can be found.

1. M.S. Bazaraa, J.J. Jarvis and H.D. Sherali: Linear Programming and Network Flows, Wiley (1988).

2. D. Bertsimas, J.N. Tsitsiklis: Introduction to Linear Optimization. Athena Scientific (1997).

3. N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory. Cambridge University Press (2007).

4. M. Osborne, A. Rubinstein: A Course in Game Theory. MIT Press (1994).

Other resources and further reading

5. S. Arora, B. Barak: Computational Complexity - A Modern Approach. Cambridge University Press (2009).

6. S. Boyd and L. Vandenberghe: Convex Optimization. Cambridge University Press (2004).

7. H. Moulin: Axioms of Cooperative Decision Making. Cambridge University Press (1988).

8. A. D. Taylor: Social Choice and the Mathematics of Manipulation. Cambridge University Press (2005).

Schedules

• Lagrangian sufficiency theorem. Lagrange duality. Supporting hyperplane theorem. Sufficient conditions for convexity of the optimal value function. Fundamentals of linear programming. Linear program duality. Shadow prices. Complementary slackness. [2]

• Simplex algorithm. Two-phase method. Dual simplex algorithm. Gomory’s cutting plane method. [3]

• Complexity of algorithms. NP-completeness. Exponential complexity of the simplex algorithm. Polynomial time algorithms for linear programming. [2]

• Network simplex algorithm. Transportation and assignment problems, Ford-Fulkerson algorithm, max-flow/min-cut theorem. Shortest paths, Bellman-Ford algorithm, Dijkstra’s algorithm. Minimum spanning trees, Prim’s algorithm. MAX CUT, semidefinite programming, interior point methods. [5]

• Branch and bound. Dakin’s method. Exact, approximate, and heuristic methods for the travelling salesman problem. [3]

• Cooperative and non-cooperative games. Two-player zero-sum games. Existence and computation of Nash equilibria in non-zero sum games, Lemke-Howson algorithm. Bargaining. Coalitional games, core, nucleolus, Shapley value. Arrow's theorem, Gibbard-Satterthwaite theorem. Mechanism design. Vickrey-Clarke-Groves mechanisms. Auctions, revenue equivalence, optimal auctions. [9]