GLPK 4.41 released

A new version of the GNU Linear Programming Kit (GLPK)  has been released – see here for GLPK tutorials. An updated version of the GUSEK windows GUI will follow probably soon. From the release notes:

GLPK 4.41 — Release Information
********************************

Release date: Dec 21, 2009

GLPK (GNU Linear Programming Kit) is intended for solving large-scale
linear programming (LP), mixed integer linear programming (MIP), and
other related problems. It is a set of routines written in ANSI C and
organized as a callable library.

In this release:

The following new API routines were added:

glp_transform_row     transform explicitly specified row
glp_transform_col     transform explicitly specified column
glp_prim_rtest        perform primal ratio test
glp_dual_rtest        perform dual ratio test

For description of these new routines see a new edition of the
reference manual included in the distribution.

The following API routines are deprecated: lpx_transform_row,
lpx_transform_col, lpx_prim_ratio_test, lpx_dual_ratio_test.

Some improvements were made in the MIP solver (glp_intopt).

The SQL table driver used to read/write data in MathProg models
was changed to allow multiple arguments separated by semicolon
in SQL statements. Thanks to Xypron <xypron.glpk@gmx.de>.

Two new options were added to the glpsol stand-alone solver:
–seed value (to initialize the pseudo-random number generator
used in MathProg models with specified value), and
–ini filename (to use a basis previously saved with -w option
as an initial basis on solving similar LP’s).

Two new MathProg example models were included. Thanks to
Nigel Galloway <nigel_galloway@operamail.com> and Noli Sicad
<nsicad@gmail.com> for contribution.

Scripts to build GLPK with Microsoft Visual Studio 2010 for
both 32-bit and 64-bit Windows were included. Thanks to Xypron
<xypron.glpk@gmx.de> for contribution and testing.

See GLPK web page at <http://www.gnu.org/software/glpk/glpk.html>.

GLPK distribution can be ftp’ed from <ftp://ftp.gnu.org/gnu/glpk/> or
from some mirror ftp sites; see <http://www.gnu.org/order/ftp.html>.

Heading off to AFBC 2009

I am on my way to the 22nd Australasian Finance and Banking Conference 2009 in Sydney. So, what the hell, is a mathematician doing on a finance conference? Well, basically mathematics and in particular optimization and operations research. I am thrilled to see the current developments in economics and finance that take computational aspects, which ultimately limit the amount of rationality that we can get, into account (I wrote about this before here, here, and here). In fact, I am convinced that these aspects will play an important role in the future, especially for structured products. After all, who is going to buy a structure where it is impossible to compute the value? Not even to talk about other complications such as bad data or dangerous model assumptions (such as static volatilities and correlations which are still used today!). Most valuation problems though can be cast as optimization problems and especially the more complex structured products (e.g., mean variance optimizer) do explicitly ask for a solution to an optimization problem in order to be valuated. For the easier structures, Monte Carlo based approaches (or bi-/trinomial trees) are sufficient for pricing. As Arora, Barak, Brunnermeier, and Ge show in their latest paper, for more complex structures (e.g., CDOs) these approaches might fall short capturing the real value of the structures, due to e.g., deliberate tampering.

I am not going to talk about aspect of computational resources though: I will be talking about my paper “Optimal Centralization of Liquidity Management” which is joined work with Christian Schmaltz from the Frankfurt School of Finance and Management. The problem that we are considering is basically a facility location problem: In a large banking network, where and how do you manage liquidity? In a centralized liquidity hub or rather in smaller liquidity centers spread all over the network. Being short on liquidity is a very expensive matter, either one has to borrow money via the interbank market (which is usually dried up or at least tight in tougher economical conditions) or one has to borrow via the central bank. If both is not available, the bank goes into a liquidity default. The important aspect here is that the decision on the location and the amount of liquidity produced, is driven to a large extent by the liquidity demand volatility. In this sense a liquidity center turns into an option on cheap liquidity and in fact, the value of a liquidity center can be actually captured in an option framework. The value of the liquidity center is the price of the exact demand information – the more volatility we have, the higher this price will be and the more we save when we have this information in advance. The derived liquidity center location problem implicitly computes the prices of the options which arise as marginal costs in the optimization model. Here are the slides:

View this document on Scribd

Characterizing border bases using polyhedral combinatorics

Gábor Braun from the Hungarian Academy of Sciences and I just managed to finish our article “Border bases and order ideals: a polyhedral characterization” which is an extension of our former work that was restricted to degree-compatible order ideals. The article addresses an old problem in computer algebra that Gröbner bases and border bases are usually computed with respect to a term ordering (basically a total ordering on the monomials that is compatible with multiplication). Whereas for Gröbner bases this makes sense, for border bases, relying on a (degree-compatible) term ordering excludes a large number of potential border bases though, as the associated order ideal cannot be obtained by a term ordering.

More precisely, for a given zero-dimensional , a border basis arises from a special decomposition of a polynomial ring into (as vector spaces) where is subset of the monomials with the property that whenever and then it follows that — a subset with this property is an order ideal. Every order ideal that induces such a decomposition is in one-to-one correspondence with a border basis (as a consequence of the directness of the sum). In case the order ideal and the associated decomposition is induced by a Gröbner basis and its underlying term ordering, we can compute a border basis using the classical border basis algorithm (a specialization of Mourrain’s generic algorithm). We do not have to worry about any combinatorial complications here.

The situation completely changes when we want to compute border bases for arbitrary order ideals. First of all, not every order ideal does actually support a border basis. For a given order ideal that supports a border basis though, one can adapt the classical border basis algorithm to be able to compute the border basis (with respect to this order ideal) as well. Thus the main problem that we are facing is to identify those order ideals that do support a border basis (of a given zero-dimensional ideal). The combinatorial challenge that we are facing then is that we have to ensure two opposite conditions: On the one hand, we need to ensure that our complementary basis forms an order ideal and at the same time we have to ensure that the decomposition is direct, i.e., we obtain constraints on the dimension and linear independence of certain sub vector spaces. This gives rise to a nice combinatorial problem that can be captured using polyhedral combinatorics. In fact, for a given zero-dimensional one can define a 0/1 polytope, the order ideal polytope, whose integral points are in one-to-one correspondence with all those order ideals that do actually support a border basis. We were also able to show that optimizing over the integral hull of the order ideal polytope is NP-hard and thus it is unlikely that we can obtain a nice characterization of the integral points. This underlines the fact that lots of the combinatorial structure in an ideal is reflected in the factor spaces and the complementary bases.

The impact of estimation errors on CDO pricing

Another interesting, nicely written paper about valuating and pricing CDOs is “The Economics of Structured Finance” from Coval, Jurek, and Stafford which just appeared in the Journal of Economic Perspectives. It nicely complements the paper of Arora, Barak, Brunnermeier, and Ge titled “Computational Complexity and Information Asymmetry in Financial Products” (see also here). The authors argue that already small estimation errors in correlation and probability of default (of the underlying loans) can have devastating effect on the overall performance of a tranche. Whereas the senior tranches remain quite stable in the presence of estimation errors, the overall rating of the junior and mezzanine tranches can be greatly affected. Intuitively this is clear, as the junior and the mezzanine tranches act as a cushion for the senior tranches (and in turn the junior tranches are a protection of the mezzanine tranches). What is not so clear though at first is that this effect is so pronounced, i.e., smallest estimation errors lead to a rapid decline in credit quality of these tranches. In fact, what happens here is that the junior and mezzanine tranches pay the price for the credit enhancement of the senior tranches. And the stability of the latter with respect to estimation errors comes at the expense of highly sensitive junior and mezzanine tranches.

This effects becomes even more severe when considering CDO^2, where the loans of the junior and mezzanine tranches are repackaged again. These structures possess a very high sensitivity to slightest variations or estimation errors in the probability of default or correlation.

In both cases, slight impressions in the estimation can have severe impacts. But also, considering it the other way around, slight changes in the probability of default or the correlation due to changed economic conditions can have devastating effect on the value of the lower prioritized tranches.

So if you are interested in CDOs, credit enhancement, and structured finance you should give it a look.

Information asymmetry, complexity, and structured products

Sorry for the long inactivity, but I am totally caught up in end-of-year wrapping up. I have to admit that I find it quite dissatisfying when you realize the year is almost over and there are still so many things on your list that should have been done… So the last months of the year somehow always end up in total chaos…. anyways…

I came across a very interesting, recent paper (via Mike’s blog post – read also his excellent post) by Arora, Barak, Brunnermeier, and Ge with the title “Computational Complexity and Information Asymmetry in Financial Products” – the authors also provide an informal discussion of the relevance for derivative pricing in practice. As I worked with structured products myself for some time, this paper raised my interest and if you are interested in the trade-off between, say, full rationality and bounded-rationality when it comes to pricing, you should definitely give it a look as well.

The paper deals with the effect of information asymmetry between the structuring entity (which is often also the seller) and the buyer of a structure. The considered derivatives in the paper are CDO like structures and, running the risk of over-simplification, the main points are as follows:

1. Having a set of assets that should be structured into derivatives, here CDOs, a malicious structurer can hide a significant amount of junk assets when assigning the assets to the derivatives. More precisely, the structurer can ensure that the junk assets are overrepresented in a certain subset of the derivatives to be structured which significantly deteriorates their value.
2. A buyer with full-rationality (which can here perform exponential time computations) can actually detect this tampering by testing all possible assignment subsets and verifying that there is actually an/no over-representation.
3. On the other hand, a buyer with limited computational resources, say which is only capable of performing polynomial time computations (the standard assumption when considering efficient algorithms that behave well in the size of the input) cannot detect that the assignments of the assets to the derivatives has been tampered.
4. Under some additional assumptions, the tampering is even ex post undetectable.
5. The authors propose different payoff function that are more resistant to tampering in the sense that heavy, detectable tampering is needed to skew the payoff profile significantly.

Now the authors devise a model similar to Akerlof’s lemons. Stated in a simplified way, the buyer, knowing that he cannot detect the tampering, will assume that a tampering has been performed and is only willing to pay the adjusted price factoring in the potential tampering of the structure – adverse selection. The honest structurer is not willing to sell his derivatives for the reduced price and leaves the market. This effect, based on the information asymmetry between buyer and seller (which was exemplified in Akerlof’s paper using the market of used cars) in the classical setting would lead to a complete collapse of the market as it would repeat ad infinitum until nobody would be left willing to trade. Countermeasures stopping this vicious circle are warranties in the case of the cars. The variant considered here for the structured products will likely converge to the point where the maximum amount of tampering has been performed and buyers and sellers expectations or levels of information are aligned.

What particularly fascinated me is the type of problem encoded to establish intractability. Contrary to the classical NP-hard problems known in optimization that mostly ask for some kind of an optimal combinatorial solution, the authors use the densest subgraph problem/assumption which asserts that deciding between two random distributions (here the fair one and the tampered one) cannot be done in polynomial time (provided that the tampering is not too obvious). In particular:

Densest subgraph problem. Let be a bipartite graph with out-degree for all vertices in . The densest subgraph problem for is to distinguish between the two distributions:

1. which is obtained by choosing for every vertex in an amount of neighbors in  randomly. (what would be the fair assignment)
2. which is obtained by first choosing and with and , and then choosing neighbors for every vertex outside of , and random neighbors for every vertex in . Then we choose random additional neighbors in for every vertex in . (which means that we choose some assets and some derivatives a priori and we prefer to add edges between those sets — slightly simplified. On the rest we do random assignments)

Then the densest subgraph assumption states that whenever, as functions of are chosen sufficiently moderate, then we cannot distinguish between those two distributions, i.e., we cannot detect the tampering with a polynomial time algorithm:

Densest subgraph assumption. Let be such that , then there is no and poly-time algorithm that distinguishes between and with advantage .

Note that the vertices correspond to the structures and the to the underlyings/assets. Although asymptotically intractable, what would be interesting to know is what one can do in practice for reasonable instance sizes, i.e, up to which degree one would be actually able to detect tampering. As Mike already said:

In particular, if a group put out 1000 groupings of financial instruments, and I needed to solve the densest subgraph problem on the resulting instance, I would work very hard at getting an integer program, constraint program, dynamic program, or other program to actually solve the instance (particularly if someone is willing to pay me millions to do so).  If the group then responded with 10,000 groupings, I would then simply declare that they are tampering and invoke whatever level of adverse selection correction you like (including just refusing to have anything to do with them).  Intractable does not mean unsolvable, and not every size instance needs more computing than “the fastest computers on earth put together”.

Another point might be that there are potentially billions of ways of tampering structured products. Especially when the payoff profiles are highly non-linear (e.g., FX-ratchet swaps with compounding coupons) deliberate over-/underestimation of parameters might completely change the valuation of the structures. The proposed framework highlights that there might be ways of tampering that we cannot detect in the worst case, even ex-post (under additional assumptions). But before we can actually detect tampering we have to be aware of this kind of tampering and we have a real problem if tampering is undetectable ex post – how to prove it? This is in some sense related to the stated open question 3: Is there an axiomatic way of showing that there are no tamper-proof derivatives – slightly weakened: with respect to ex-post undetectability.

I could also very well imagine that when giving a closer look to traded structures (especially the nasty OTC ones), that there will be more pricing problems that are essentially intractable. It is almost like one of the main hurdles so far to establish intractability was the more stochastical character of prizing problems while hardness is often stated in terms of some kind of combinatorial problem. An approach like the one proposed in the article might overcome this issue by establishing hardness via distinguishing two distributions.

Sketch your perfect picture

Check this out:

We present a system that composes a realistic picture from a simple
freehand sketch annotated with text labels. The composed picture
is generated by seamlessly stitching several photographs in agreement
with the sketch and text labels; these are found by searching
the Internet. Although online image search generates many inappropriate
results, our system is able to automatically select suitable
photographs to generate a high quality composition, using a filtering
scheme to exclude undesirable images. We also provide a novel
image blending algorithm to allow seamless image composition.
Each blending result is given a numeric score, allowing us to find
an optimal combination of discovered images. Experimental results
show the method is very successful; we also evaluate our system using
the results from two user studies.

Here is the video:

And the link to the paper — they actually use dynamic programming for parts of their algorithm.

Arms race in quantitative trading or not?

Rick Bookstaber recently argued that the arms race in high frequency trading, a form of quantitative trading where effectively time = money , results in a net drain of social welfare:

A second reason is that high frequency trading is embroiled in an arms race. And arms races are negative sum games. The arms in this case are not tanks and jets, but computer chips and throughput. But like any arms race, the result is a cycle of spending which leaves everyone in the same relative position, only poorer. Put another way, like any arms race, what is happening with high frequency trading is a net drain on social welfare.

It is all about milliseconds and being a tiny little bit faster:

In terms of chips, I gave a talk at an Intel conference a few years ago, when they were launching their newest chip, dubbed the Tigerton. The various financial firms who had to be as fast as everyone else then shelled out an aggregate of hundreds of millions of dollar to upgrade, so that they could now execute trades in thirty milliseconds rather than forty milliseconds – or whatever, I really can’t remember, except that it is too fast for anyone to care were it not that other people were also doing it. And now there is a new chip, code named Nehalem. So another hundred million dollars all around, and latency will be dropped a few milliseconds more.

In terms of throughput and latency, the standard tricks are to get your servers as close to the data source as possible, use really big lines, and break data into little bite-sized packets. I was speaking at Reuters last week, and they mentioned to me that they were breaking their news flows into optimized sixty byte packets for their arms race-oriented clients, because that was the fastest way through network. (Anything smaller gets queued by some network algorithms, so sixty bytes seems to be the magic number).

Although high-frequency trading is basically about being fast and thus time is the critical resource, in quantitative trading, in general, it is all about computational resources and having the best/smartest ideas and strategies. The best strategy is worthless if you lack the computational resources to crunch the numbers and, vice versa, if you do have the computational power but no smart strategies this does not get you anywhere either.

Jasmina Hasanhodzic, Andrew W. Lo, Emanuele Viola argue in their latest paper “A Computational View of Market Efficiency” that efficiency in markets has to be considered with respect to the level of computational sophistication, i.e., as market can (appear to) be efficient for those participants which use only a low level of computational resources, whereas it can be inefficient for those participants that invest a higher amount of computational resources.

In this paper we suggest that a reinterpretation of market efficiency in computational terms might be the key to reconciling this theory with the possibility of making profits based on past prices alone. We believe that it does not make sense to talk about market efficiency without taking into account that market participants have bounded resources. In other words, instead of saying that a market is “efficient” we should say, borrowing from theoretical computer science, that a market is efficient with respect to resources S, e.g., time, memory, etc., if no strategy using resources S can generate a substantial profit. Similarly, we cannot say that investors act optimally given all the available information, but rather they act optimally within their resources. This allows for markets to be efficient for some investors, but not for others; for example, a computationally powerful hedge fund may extract profits from a market which looks very efficient from the point of view of a day-trader who has less resources at his disposal—arguably the status quo.

More precisely, it is even argued that the high-complexity traders gain from the low-complexity traders (of course, within the studied, simplified market model – but nonetheless!!):

The next claim shows a pattern where a high-memory strategy can make a bigger profit after a low-memory strategy has acted and modified the market pattern. This profit is bigger than the profit that is obtainable by a high-memory strategy without the low-memory strategy acting beforehand, and even bigger than the profit obtainable after another high- memory strategy acts beforehand. Thus it is precisely the presence of low-memory strategies that creates opportunities for high-memory strategies which were not present initially. This example provides explanation for the real-life status quo which sees a growing quantitative sophistication among asset managers.

Informally, the proof of the claim exhibits a market with a certain “symmetry.” For high-memory strategies, the best choice is to maintain the symmetry by profiting in multiple points. But a low-memory strategy will be unable to do. Its optimal choice will be to “break the symmetry,” creating new profit opportunities for high-memory strategies.

So although in pure high-frequency trading, the relevance of smart strategies might be smaller and thus it is more (almost only?) about speed, in general quantitative trading it seems like (again in the considered model) that the combination of strategy and high computational resources might generate a (longer-term) edge. This edge cannot necessarily be compensated with increased computational resources only, as you still need to have access to the strategy. The considered model considers memory as a the main computational/limiting resource. One might argue that it reflects the sophistication of the strategy along with the real computational resources implicitly, as limited memory might not be able to hold a complex strategy. On the other hand a lot of memory is pointless without a strategy using it. So both might be considered to be intrinsically linked.

An easy example illustrating this point is maybe the following. Consider the sequence “MDMD” and suppose that you can only store, say these 4 letters. A 4-letter-strategy might predict something like “MD” for the next two letters. If those letters though represent the initial of the weekdays, the next 3 letters will be “FSS”. It is impossible though to predict this sequence solely using information about the past on the last 4 letters. The situation changes if we can store up to 7 letters “FSSMDMD”. Then a prediction is possible.

One point of the paper is now that the high-complexity traders might fuel their profits by the shortsightedness of the low-complexity traders. And thus an arms race might be a consequence (to exploit this asymmetry on the one hand and to protect against exploitation on the other). To some extent this is exactly what we are seeing already when traders with “sophisticated” models, that for example are capable of accounting for volatility skew, arbitrage out less sophisticated traders. On the other hand, it does not help to use a sophisticated model (i.e., more computational resources) if one doesn’t know how to use it, e.g., a Libor market model without an appropriate calibration (non-trivial) is worthless.

Interesting things to read…

I just came back from the ISMP in Chicago and as I didn’t write a single line about it (I feel guilty :S), I at least wanted to share a few interesting links with you.

1. Terry Tao’s talk on mathematics and the internet [pdf]
   (Source: Michael Nielsen’s Blog)
2. The impact factor’s Matthew effect: a natural experiment in bibliometrics
   “Using an original method for controlling the intrinsic value of papers–identical duplicate papers published in different journals with different impact factors–this paper shows that the journal in which papers are published have a strong influence on their citation rates, as duplicate papers published in high impact journals obtain, on average, twice as much citations as their identical counterparts published in journals with lower impact factors. The intrinsic value of a paper is thus not the only reason a given paper gets cited or not; there is a specific Matthew effect attached to journals and this gives to paper published there an added value over and above their intrinsic quality. “
   (Source: Michael Nielsen’s Blog)

3. US Top All-Time Donors 1989-2008
   Slightly off-topic but I actually have to admit that I was surprised
   (Source: Michael Nielsen’s Blog)
4. The Status of the P Versus NP Problem (L. Fortnow)
   A nice summary about P Versus NP, why it is so hard and about potential consequences if the question would be settled.
5. The Arms Race in High Frequency Trading (R. Bookstaber)
   “A second reason is that high frequency trading is embroiled in an arms race. And arms races are negative sum games. The arms in this case are not tanks and jets, but computer chips and throughput. But like any arms race, the result is a cycle of spending which leaves everyone in the same relative position, only poorer. Put another way, like any arms race, what is happening with high frequency trading is a net drain on social welfare.”
6. Stockmeyer’s Approximate Counting Method (R.J. Lipton)
   Great blog post on approximate counting.
7. Multitasking Muddles Brains, Even When the Computer Is Off (Wired)
   On the perils of preemptive multi-tasking and just quickly checking emails yet again…
8. Goldman and High Frequency Trading (R. Bookstaber)
   related to 5. above.
9. Not with a Bang but a Whimper – The Risk from High Frequency and Algorithmic Trading (R. Bookstaber)
   related to 5. above.

Rejecta Mathematica – your paper just got an extra life

A few weeks ago The Economist ran an article (thx for the pointer) on Rejecta Mathematica, an open access journal that offers an outlet for papers that do not necessarily fit well into any other journal or have been rejected for various other reasons. From The Economist article:

PAUL LAUTERBUR, the father of magnetic-resonance imaging, had his seminal paper rejected when he first submitted it to Nature. Peter Higgs, eponymous predictor of physics’s missing boson, faced similar trouble with Physics Letters. But Lauterbur went on to win a Nobel prize for his work, and Dr Higgs is an odds-on favourite to get one soon. A good, rejected paper, then, is by no means an oxymoron.

And that observation is the basis of Rejecta Mathematica, an open-source academic journal that recently went online. As its name suggests, the new journal publishes only papers that, like Lauterbur’s and Dr Higgs’s, have been previously submitted to, and rejected by, others. With Annals of Mathematics, one of the best, denying entry to more than 300 last year alone, Rejecta could be busy.

The inaugural issue from July 2009 is available here. Don’t miss out on the letter from the editors in that issue which provides insight into the why, who, how, and when. From the letter:

First, there is ample evidence that in the traditional review process, significant (even Nobel prize-winning) research is occasionally overlooked and groundbreaking work is some-times actively shunned [2–4]. Perhaps this is most dramatically illustrated in the fact that at least “36 future Nobel Laureates encountered resistance on [the] part of scientific journal editors or referees to manuscripts that dealt with discoveries that on [a] later date would assure them the Nobel Prize” [5]. While it would be presumptuous for us to assume that we can spot significant work that others may have missed, we can provide a venue to introduce rejected work to the community and  increase the chances that its value will be appreciated sooner rather than later.

Second, there is also evidence that a research community can derive value from a centralized repository of rejected papers, even when (and perhaps especially when) the results are either incorrect or not significant enough to warrant consideration for a ma jor international prize. Rejecta Mathematica can benefit authors looking for feedback on their work, wanting to warn the community against false starts (i.e., the classic “null results” that never see the light of day, only to be repeated by others) [6, 7], or wanting to illuminate the occasional vagaries of the peer review process to enhance accountability and scientific integrity [8]. Our journal can also benefit readers who want access to “minor results” that may be useful but not publishable in isolation. Indeed, Rejecta Mathematica has existed in folklore for many years as a fictitious place to send papers that were never to see the light of day, and the concept of a formal repository for rejected papers hoping to be discovered and revived (called Rejuvenatable Mathematics) has also been proposed [9].

Mario AI Competition 2009

Yesterday I learned about the Mario AI Competition 2009 (thx for the pointer). The goal of the competition is to provide an agent that automatically navigates through a version of the Mario game:

This competition is about learning, or otherwise developing, the best controller (agent) for a version of Super Mario Bros.

The controller’s job is to win as many levels (of increasing difficulty) as possible. Each time step (24 per second in simualated time) the controller has to decide what action to take (left, right, jump etc) in response to the environment around Mario.

We are basing the competition on a heavily modified version of the Infinite Mario Bros game by Markus Persson. That game is an all-Java tribute to the Nintendo’s seminal Super Mario Bros game, with the added benefit of endless random level generation. We believe that playing this game well is a challenge worthy of the best players, the best programmers and the best learning algorithms alike.

Sounds like a perfect application for some optimization and in fact Robin Baumgarten programmed an agent partly based on the A* algorithm. Check out the video below to see how fast the agent is actually moving through the levels:

A comment on the youtube video: “So I undestand correctly: da computer will play video games for us, so we have more free time? Way cool.”