### This is a DRAFT home page for a course of 24 lectures to Cambridge MMath/MASt (Part III) students. It will next be given in autumn of 2015.

### MATERIAL BELOW IS FOR THE 2011 COURSE, WHICH I WILL BE EDITING OVER SUMMER 2015.

## Course notes

Here are notes. I aim to make each lecture a self-contained unit on a topic, with notes of 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

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

## Examples sheets

## Feedback

The course finishes xx Decmber 2015.

## Past exam questions

Here is single fille of all the tripos examination questions on the course from 2001 to last June.

### Past Exam Papers

## 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]