Political Arbitrage

This blog has been inactive since I've moved the materials to our University course management system. However, I thought this one might be of interest to a wider audience.

I put together a small illustration of linear programming using the real-money political prediction markets. I thought looking for arbitrage opportunities between markets would be an interesting discussion. This idea was sparked by a post on www.fivethirtyeight.com about trading behavior on www.intrade.com It's a tiny data set, so ideal for the classroom.

Since real money is at work in these markets, my hypothesis was that the usual no-arbitrage assumption would be live and well. Wrong. Turns out there is a lovely arbitrage opportunity between www.intrade.com and the British tote boards. It's grown over the last few days to a guaranteed $113 (after fees) return on a $1000 investment as of this morning.

Here's a pdf presentation if you're interested in these calculations.

Not sure what to make of this.

Updates

Lecture notes and demonstration codes have been brought up to date. Please note the demonstration codes require the student edition of Xpress-IVE, and have associated data files. The data files should be located in the same directory as the Mosel code in order to work properly.

Matlab Script for Active Set Method

I've posted the Matlab script we did in class today as a demonstration of the active set method for solving linear programs. Remember, this script is quite crude though it does demonstrate the basic elements of the algorithm, and could be a starting point for the homework problem. If you did want to develop it further, my suggestions would be (with difficulty measured on a five-* scale):

1. Encapsulate in a function, and a document the lp data structure. (*)
   
2. Include feasibility checks, argument checks, etc. (*)
   
3. Accomodate equality constraints as a constraint type (**)
   
4. As we discussed in class, do efficient updates to a representation of the matrixinverse rather equation solving at each vertex (***)
   
5. Accomodate degenerate constraints (****)
6. Implement a Phase I/Phase II stategy for initial feasibility (**)
7. Validate that the code is sparse matrix friendly (**)

If you did all that, you'd actually have a pretty nice and useful tool.

Today's Lecture, Homework Solutions, and Preparation for next time

I've posted the notes from today's lecture. These are a revision of what was presented in class today in order to correct a few typos, to simplify the presentation, and to include more complete notes for our toy example. I've also posted a solution to the homework that was due today.

As preparation for Wednesday, I urge you to work through to an optimal solution for our example using the active set method. In class we completed the first iteration. Completing the example by hand will provide you helpful insights when it comes time to craft a Matlab implementaton of the algorithm.

A Question Regarding Homework #1:

Here's a question I received regarding the problem in Homework #1:

In reading the problem statement for this week's homework, I have one question.You expressed the time necessary for production of each product with relation to each unit in a table that is slightly confusing.

For Product 1 am I to assume that production involves .8 hours on Unit A PLUS .4 hours on Unit 2 PLUS .2 hours on Unit 3?... or is it meant to be that Product 1 takes .8 hours on Unit 1 OR .4 hours on Unit 2 OR .2 hours on Unit 3? Please let me know which situation it is as this will affect my equations. Thanks.

That's a good question. Yes, you should assume production requires processing through all of the units indicated indicated in the table. That is, Product 1 will require 0.8 hours in A PLUS 0.4 hours in B Plus 0.2 hours in C. The second alternative in your question is actually quite interesting, and a bit more challenging. We'll be touching on that class of problem in about a week's time.

For Next Class Meeting ...

During the next class meeting we'll be demonstrating numerical solution to our toy linear programming example using two tools. In preparation, please

1. Carefully look over Chapter 1 of the Gueret notes distributed today. That should help you assimilate many of the details we'll be going over in class.
2. Please download and test the Xpress-IVE package. The web address is for this package is in my earlier post on "Textbooks and Software." You'll want to be sure you have a working version in order keep up with the class exercises and homework.

Additional Resources

I got a few questions regarding other texts relevant to the themes of this course. Let me mention a few nascent 'classics' frequently cited in the research literature. Optimization and Operations Research are long-standing research fields, with a corresponding rich literature. So this is a mere sampling biased towards those sources I've found especially helpful:

Texts & Monographs

• Boyd, Stephen, and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. This book, written by leading experts in the field, describes the wide range of engineering applications amenable to computationally tractable convex optimization. By arrangement with the publisher, the book is also available for download from the author's web page.
  
• Nocedal, Jorge, and Stephen Wright. Numerical Optimization. Springer, 2000.
  
• Fletcher, R. Practical Methods of Optimization, 2nd Edition. John Wiley & Sons, New York, 2000. This is a modestly revised version of a book first published in 1987. The book offers a survey of unconstrained and constrained optimization, emphasizing basic theory, concepts, and the mathematical principles underlying solver implementations. It is superbly written that is a pleasure to read.
  
• Gill, P. E., and W. Murray. Practical Optimization. Academic Press, 1981. This superbly written book provides an excellent introduction to optimization methods circa early 1980's. Since it predates the profound contributions from interior point techniques, and convex optimization, the material is now somewhat dated. But that doesn't diminish the quality of its exposition on important topics in optimization.
  
• Bertsekas, Dimitri. Nonlinear Programming. Athena Press, 1999. Though mathematically more rigorous then Fletcher, or Gill, this superbly written book is an excellent reference for understanding how nonlinear solvers actually work.
  

Algebraic Modeling Languages

• AMPL: Fourer, Robert, David M. Gay, and Brian W. Kernighan. AMPL: A Modeling Language for Mathematical Programming, 2nd Edition. Brooks/Cole - Thomson, Pacific Grove, CA, 2003. This is definitive guide to AMPL, a widely used modeling language. More information, including downloads of a student edition of the AMPL system, is available from the web site http://www.ampl.com.
• MathProg/GLPK: MathProg is closely related to an earlier version of AMPL, and closely integrated with the open source system GLPK for linear programming. The software system and documentation are available for download from the project website.
• CVX: CVX is a new, and somewhat experimental modeling language for "Disciplined Convex Programming" based in Matlab. It effectively incorporates a modeling language into Matlab. The software and documentation are available for download from the authors website. This is not for the faint of heart.
  

Web Sites

• The e-optimization community (http://www.e-optimization.com/) is hosted by INFORMS -- the Institute for Operations Research and Management. This web site offers a comprehensive overview of resources for optimization.
• OR-Notes - a collection of notes on various introductory topics in operations research.
• Optimization for Engineering Systems -- An on-line textbook by Ralph Pike.