–
David Pennock:
[…] Each order is associated with a decision variable x that ranges between 0 and 1, encoding the fraction of the order that the auctioneer can accept. There is one constraint per outcome that ensures that the auctioneer never loses money across all outcomes. The choice of objective function depends on the auctioneer’s goals, but something like maximizing the fill fraction makes sense.
Once the program is set up, the auctioneer solves for the x variables to determine which orders to accept in full (x=1), which to accept partially (0<-x<-1), and which to reject (x=0). The program can be solved either in batch mode, after waiting to collect a number of orders, or in continuous mode immediately as new orders arrive. Batch mode corresponds to a call market. Continuous mode corresponds to a continuous auction, a generalization of the continuous double auction mechanism of the stock market.
Each order consists of a price, a quantity, and an outcome bundle. Traders can just as easily bet on single outcomes, negations of outcomes, or sets of outcomes (e.g., all Western Conference NBA teams). Every order goes into the same pool of liquidity no matter how it is phrased.
Price quotes are queries to the linear program of the form “at what price p will this order be accepted in full?” (I believe that bounds on the dual variables of the LP can be interpreted as bid and ask price quotes.) […]
Go reading all the post. There is a bunch of good comments…- the best was submitted by Mike Giberson…-
Thanks Chris, for keeping my name on MO’s front page, even when I haven’t had anything substantive to say for a few weeks.
.
But in response to your mention of my comment, I’d say that the best comments are the one’s Pennock makes in the body of his post. I’ve spent a bit of spare time reading some of the articles he cited, trying to better understand. What would help me now is for some of the geniuses out there to think a little more about his post and then explain more of the implications of using the LP approach.
.
For example, Pennock has a nice quip about the LP formulation and the Hanson LMSR, but it seems to me more could be said. Also, I think with some clever device an LP formulation could be used to address the combinatorial markets issues that Pennock raises at the end of the post, but it isn’t the kind of cleverness that I can do so I’m hoping someone else will write about it.
Thanks Mike. I agree more should be said about LP vs. LMSR. If the market creator has subsidy available, in many ways LMSR solves the liquidity and information propogation problems much better than LP. So LP is "best" only if there is no possiblity for a patron to subsidize the market.
The Chen et al. paper is probably the closest one to your question about how to use LP in the context of a combinatorial market. We also have some new papers coming out that discuss the use of LMSR for a combinatorial market. Here is one:
http://arxiv.org/abs/0802.1362