Sikuli – a scripting language based on screenshots

There is a pretty cool, new scripting language, Sikuli which is a “research project developed by User Interface Design Group, MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)“. The cool thing is that you can automate GUI interactions by using screenshots of buttons, sliders, input boxes, etc. But rather before I start to explain how it works, just check out the video.

The language itself is based on Jython and thus you can use Jython to do almost everything you like and it is fairly simple to use:

Example: Sikuli Code

So now you finally can automate your optimal FarmVille production schedule by having Sikuli interact with the applet . Just put your production schedule into Sikuli and let it do the rest. Here is a GMPL model (based on the AMPL model from O.R. by the Beach – I just changed “;” and removed the “option” lines) for determining the optimal production schedule that maximizes cash. Can be solved to optimality with GLPK in 0.1 secs – the Sikuli code is left as an exercise

param T;
set Horizon := 0..T;
set Crops;

param TotalArea;
param InitialArea;
param InitialMoney;
param PlowCost;
param Growth{Crops};
param Cost{Crops};
param Revenue{Crops};

var Plant{Crops,Horizon} integer >= 0;
var Area{Horizon} >= 0, <= TotalArea;
var Money{Horizon} >= 0;

maximize z: Money[T] + 4*PlowCost;

subject to

area0: Area[0] = InitialArea + sum {i in Crops} Plant[i,0];

area{t in 1..T}:  Area[t] = Area[t-1]
      + sum {i in Crops} Plant[i,t]
      - sum {i in Crops : t >= Growth[i]} Plant[i,t-Growth[i]];

money0: Money[0] = InitialMoney - sum {i in Crops} (PlowCost + Cost[i])*Plant[i,0];

money{t in 1..T}: Money[t] = Money[t-1]
      - sum {i in Crops} (PlowCost + Cost[i])*Plant[i,t]
      + sum {i in Crops : t >= Growth[i]} Revenue[i]*Plant[i,t-Growth[i]];

solve;

display z;
display {i in Crops, t in Horizon : Plant[i,t] > 0} Plant[i,t];
display Area,Money;

data;

param T := 36;
set Crops := SB EP WH SY;
param TotalArea := 144;
param InitialArea := 0;
param InitialMoney := 323;
param PlowCost := 15;

param:

Growth   Cost   Revenue :=
SB      1      10       35
EP     12      25       88
WH     18      35      115
SY      6      15       63;

end;

Microbes outsmarting engineers/mathematicians (reloaded)

A paper on solving combinatorial optimization problems with biological organisms made it into Science. The paper “Rules for Biologically Inspired Adaptive Network Design” by Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P. Bebber, Mark D. Fricker, Kenji Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki explains that under certain circumstances, a certain microbe can reconstruct a version of the Tokyo rail system. From the abstract:

Transport networks are ubiquitous in both social and biological systems. Robust network performance involves a complex trade-off involving cost, transport efficiency, and fault tolerance. Biological networks have been honed by many cycles of evolutionary selectionpressure and are likely to yield reasonable solutions to such combinatorial optimization problems. Furthermore, they develop without centralized control and may represent a readily scalable solution for growing networks in general. We show that the slime mold Physarum polycephalum forms networks with comparable efficiency, fault tolerance, and cost to those of real-world infrastructure networks—in this case, the Tokyo rail system. The core mechanisms needed for adaptive network formation can be captured in a biologically inspired mathematical model that may be useful to guide network construction in other domains.

Whereas the authors do not claim any real (i.e., mathematical) optimality etc. and probably the solution quality is similar to solutions that one would obtain with simulated annealing or ant colony optimization, i.e., sub-optimal solutions in many cases, a well-read website, Spiegel Online belonging to the Spiegel magazine run a story about the article a couple of days ago giving the whole thing a slightly different touch – this reminded me very much of a blog post of Mike. The article starts with (in German – I will provide a hopefully faithful translation afterwards):

Was Ingenieure mit großem Aufwand versuchen, scheint für den Schleimpilz Physarum polycephalum eine Kleinigkeit: Verkehrswege möglichst effizient zu bauen.
Translation: What Engineers try to achieve with a lot of effort, is a trivial task for the slime mold Physarum polycephalum: The construction of efficient (traffic-) networks.

Here, the witty author already gives a first indication and an executive-style summary of his opinion. And just in case you haven’t got the point that engineers and in particular discrete optimization people are superfluous, money-eating artifacts of times where excess capital had to be burnt in order to keep inflation low, the author stresses his point even further by making clear that the microbe is really dumb.

Er gehört zu den ältesten Lebensformen – und Intelligenz würde man dem schleimigen Winzling wohl kaum zusprechen.
Translation: It (the microbe) belongs to one of the oldest life forms on earth and this little slimy thing is far from being intelligent.

If one takes a closer look at the article and especially the graph of the underlying network that the magic microbes reconstructed, the graph is almost trivial (from Fresh Photos):

If you checkout the spiegel online article which also provides pictures (I didn’t want to include those for obvious reasons), the time scale shows that obtaining the final solution took the magic microbe 26 hours. Needless to say that probably trivial branch-and-bound would do the job in less than 10 secs.

In times where it is chic to suck at mathematics, a stupid microbe outperforming a whole branch of engineering and mathematics provides perfect justification for dismissing mathematics as the most decadent form of barrenness. And what is really questionable, is that in times where mathematical illiteracy is responsible to a large extent (together with greed and dismissal of the principle of universality) for the latest financial meltdown there are still authors that somewhat give the impression that the underlying mathematical problems are trivial and provide a jaded view.

We need a wikipedia page for that, distinguishing folklore optimization (yeah, every pseudo-consulting outlet does optimization) and mathematical optimization. Something that really distilles the point. Unfortunately, this page here is not really informative for the non-expert!!

A polyhedral characterization of border bases

Tomorrow I will give a talk on a recent paper which is joint work with Gábor Braun from the Alfréd Rényi Institute of Mathematics. It deals with the polyhedral characterization of all admissible order ideals (and hence border bases) that exist for a given zero-dimensional ideal. As a hardness result, it also follows that determining an optimal order ideal (w.r.t. to a linear objective function) is NP-hard. This is in particular interesting as it shows that not only computing the L-stable span (the vector space approximation of the ideal) is hard but also choosing a ‘nice’ basis which is a mere basis transformation from a linear algebra point of view (see also my previous post for some more details). Here are the slides:

View this document on Scribd

The GNU Linear Programming Kit (GLPK) : Resources, Tutorials…

I just put together some more resources, tutorials, and information about the GNU Linear Programming Kit (GLPK). The page can be found here.

If you have some information, links, etc., that you would like to see there, just drop me a line.

Information asymmetry and beating the market

Recently, I was wondering how much money you can effectively gain by investing, given a certain information advantage: Suppose that you want to invest some money, for the sake of simplicity say $10,000. Can you assume to be able to extract an average-exceeding return from the market given that you have an information advantage? If you believe in the strong form of the efficient market hypothesis then the answer is no of course. If not, then is it at least theoretically possible?

Let us consider a simplified setting. Suppose that we can invest (long/short) in a digital security (e.g., digital options) with payouts 0 and 1 (with a price of 0.5) and let us further suppose that it pays out 1 with a probability of 50%. Now assume that we have a certain edge over the market, i.e., we can predict the outcome slightly more accurately, say with accuracy. If we have a good estimate of our edge, we can use the Kelly Criterion to allocate our money. The Kelly Criterion, named after John L. Kelly, Jr determines the proportional amount of money to bet from own bankroll so that the overall utility is maximized – this criterion is provably optimal. It was presented by Kelly in his seminal 1956 paper “A New Interpretation of Information Rate“. In this paper Kelly links the channel capacity of a private wire (inside information) to the maximum amount of return that one can extract from a bet. While this bound is a theoretical upper bound, it is rather strong in its negative interpretation: If you do not have any inside information (which includes being just smarter than everybody else or other intangible edges) you cannot extract any cash. The Kelly Criterion arises as an optimal money management strategy derived from the link to Shannon’s Information Theory and in its simplest form it can be stated as:

where are the odds, the probability to win, and the probability to lose. So in our setting, where we basically consider fair coin tosses whose outcomes we can predict with accuracy, an edge of 1% or 100bps is considerable. Using the money management strategy from above (neglecting taxes, transaction fees, etc.), we obtain:

100bp edge

with an initial bankroll of $10,000, y-axis is log10(bankroll), x-axis is #bets. The five lines belong to the %5, 25%, 50%, 75%, and 95% percentiles computed on the basis of 5,000 Monte-Carlo runs. So even the 5% percentile sees a ten-fold increase of the bankroll after roughly 4,100 bets, whereas the 95% percentile is already at a 100-fold increase. In terms of real deals the number of bets is already considerable though — after all, which private investor does 4,000 transactions??

Unfortunately, an edge of 100bp is very optimistic and for, say, for 50bp edge the situation already looks a quite different: the 50% percentile barely reaches a ten-fold increase after 10,000 bets.

50bp edge

And now let us come to the more realistic scenario when considering financial markets. Here an edge of 10bp is already considered significant. Given all the limitations as a private investor, i.e., being further down the information chain, sub-optimal market access, etc., assuming an edge of 10bp would be still rather optimistic. In this case, using an optimal allocation of funds, we have the following:

10bp edge

Here the 25% percentile actually lost money and even the 50% percentile barely gained anything over 10,000 bets. In the long run also here a strictly positive growth occurs, but for 10bp it takes extremely long: While you might be able do 4,000 deals over the course of say 10 – 30 years. Here even after 100,000 bets the 5% percentile barely reaches a 29% gain (over 100,000 bets!!). Given transaction costs, taxes, fees, etc., in reality the situation looks worse (especially when considered more complicated financial structures). So it comes all down to the question, how large your edge is.

Although extremely simplified here, a similar behavior can be shown for more complicated structures (using e.g., random walks).

European Capital of Culture: Ruhr.2010

The European Capital of Culture for 2010 is Essen in Germany, on behalf of the Ruhr Area (“Ruhrpott” or “Ruhrgebiet” as we say) and its several cities (e.g. Bochum, Dortmund, Gelsenkirchen, Duisburg, Oberhausen, …). The official homepage can be found here [9]. As I grew up in Essen and practically lived there the first “part” of my life I thought I take the opportunity and provide you with some background information and links, just in case you are in Germany in 2010 and you have a chance to visit that diverse and really interesting area. Unfortunately, some of the articles are in German only, but I tried to provide English resources whenever possible.

According to wikipedia, the Ruhr Area is the fourth largest urban area in Europe with some 7.3 million inhabitants. What is special about this area is its unique industry culture and the transformation in the 90’s away from heavy industry to a more service oriented area (see [2], [3], [4], German only). As you can imagine, this transition brought a lot of initial problems and desperation to people heavily relying on heavy industry for their income and the fact that those people could not be easily moved to different jobs (see [1], German only). Now that this transition is (almost) complete, the Ruhr Area presents its distinguished face to the world as the European Capital of Culture. Also check out the special issue on Spiegel ([3], German only) about Ruhr.2010.

Events and must-sees:

An event planer with events scheduled in 2010 can be found in [8] and following the same link, you can also find the Top-10 attractions in the Ruhrpott (according to Spiegel and I kinda agree).

Impressions from the Ruhr Area:

In [5] you can listen to some “typical” sounds of the Ruhr Area. These sound recordings were taken by Richard Ortmann and represent some of the day to day noises you would have heard (and partly still would hear today). Also check out his sound archive with a more comprehensive collection of sound nostalgia [6]. Probably one of the most famous songs about the Ruhr Area is Herbert Grönemeyer’s “Bochum” (about one of the big cities in this area):

Right now, 09.01.2010 15:47, there is a live show about Ruhr.2010 as the European Capital of Culture on ZDF (one of the German main tv stations). You can find it also in the ZDF mediathek [7] together with many other shows and pictures about the Ruhr Area where you can watch it for free.

Here are a few pictures from various photographers depicting the Ruhr Area:

1. Ruhr.2010
2. Ruhr.2010 (2)
3. Ruhr.2010 (3)

References:

[1]: “Wir sind die Dinosaurier – und wir wollen nicht aussterben” – Spiegel 11.02.2007 (German only)
[2]: Von der stinkenden Brühe zum Lebenselexier – Spiegel 29.08.2007 (German only)
[3]: Kulturhauptstadt Ruhr.2010 – Spiegel 08.01.2010 (German only)
[4]: Industrie in XXL – Spiegel 22.06.2009 (German only)
[5]: Der Pulsschlag aus Stahl verklingt – Spiegel 20.10.2007 (German only – but for the sounds it does not matter)
[6]: Richard Ortmann – Sound Archive (German only – but for the sounds it does not matter)
[7]: ZDF mediathek’s Ruhr.2010 collection (tv shows and pictures)
[8]: Spiegel Ruhr.2010 event planer including Top 10 attractions (German only – but rather self-explaining)
[9]: Ruhr.2010 – official homepage

Let us have a securitization party

The concept of securitization is very versatile. From Wikipedia:

Securitization is a structured finance process that distributes risk by aggregating debt instruments in a pool, then issues new securities backed by the pool. The term “Securitisation” is derived from the fact that the form of financial instruments used to obtain funds from the investors are securities. As a portfolio risk backed by amortizing cash flows – and unlike general corporate debt – the credit quality of securitized debt is non-stationary due to changes in volatility that are time- and structure-dependent. If the transaction is properly structured and the pool performs as expected, the credit risk of all tranches of structured debt improves; if improperly structured, the affected tranches will experience dramatic credit deterioration and loss. All assets can be securitized so long as they are associated with cash flow. Hence, the securities which are the outcome of Securitisation processes are termed asset-backed securities (ABS). From this perspective, Securitisation could also be defined as a financial process leading to an issue of an ABS.

The cash flows of the initial assets are paid according to seniority of the tranches in a waterfall-like structure: First the claims of the most senior tranche are satisfied and if there are remaining cash flows, the claims of the following tranche are satisfied. This continues as long as there are cash-flows left to cover claims:

Individual securities are often split into tranches, or categorized into varying degrees of subordination. Each tranche has a different level of credit protection or risk exposure than another: there is generally a senior (“A”) class of securities and one or more junior subordinated (“B,” “C,” etc.) classes that function as protective layers for the “A” class. The senior classes have first claim on the cash that the SPV receives, and the more junior classes only start receiving repayment after the more senior classes have repaid. Because of the cascading effect between classes, this arrangement is often referred to as a cash flow waterfall. In the event that the underlying asset pool becomes insufficient to make payments on the securities (e.g. when loans default within a portfolio of loan claims), the loss is absorbed first by the subordinated tranches, and the upper-level tranches remain unaffected until the losses exceed the entire amount of the subordinated tranches. The senior securities are typically AAA rated, signifying a lower risk, while the lower-credit quality subordinated classes receive a lower credit rating, signifying a higher risk.

In more mathematical terms, securitization basically works as follows: take your favorite set of random variables (for the sake of simplicity say binary ones) and consider the joint distribution of these variables (pooling). In a next step determine percentiles of the joint distribution (of default, i.e. 0) that you sell of separately (tranching). The magic happens via the law of large numbers and the central limit theorem (and variants of it): although each variable can have a high probability of default, the probability that more than, say x% of those default at the same time decreases (almost) exponentially. Thus the resulting x-percentile can have a low probability of default already for small x. That is the magic behind securitization which is called credit enhancement.

So given that this process of risk mitigation and tailoring of risks to the risk appetite of potential investors is rather versatile, why not applying the same concept to other cash flows that bear a certain risk of default and turn them into structured products

(a) Rents: Landlords face the problem that the tenant’s credit quality is basically unknown. Often, a statement about the tenant’s income and liabilities should help to better estimate the risk of default. But this procedure can, at best, serve as an indicator. So why not using the same process to securitize the rent cash flows and sell the corresponding tranches back to the landlords. This would have several upsides. First of all, the landlord obtains a significantly more stable cash flow and depending on the risk appetite could even invest in the more subordinated tranches. This could potentially reduce rents as the risk premium charged by the landlord due to his/her potentially risk averse preference could be reduced to the risk neutral amount (plus some spreads, e.g., operational and structuring costs). The probability of default could be significantly easier estimated for the pooled rent cash flows as due to diversification it is well approximated by the expected value (maybe categorized into subclasses according to credit ratings). Of course, one would have to deal with problems such as adverse selection and the potentially hard task to estimate the correlation – which can have a severe impact on the value of the tranches (see my post here).

(b) Sport bets: Often these bets as random variables have a high probability of default, e.g., roughly 50% for a balanced win/loss bet). In order to reduce the risk due to diversification a rather large amount of cash has to be invested to obtain a reasonable risk profile. Again, securitizing those cash flows could create securities with more tailored risk profiles that could be of interest to people that are rather risk averse on the one hand and risk affine gamblers on the other hand.

(c) …

That is the wonderful world of structured finance

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>.

UPDATE (01.01.2010): New version of GUSEK is also available:

I’ve updated the Gusek project on SourceForge:
http://gusek.sourceforge.net

Release 0.2.8 changes:
- GLPK updated to 4.41.
- Added Java files support (as in native SciTE).
- Added gnuplot files support (testing – thanks to Noli Sicad).

Gusek provide an open source LP/MILP IDE for Win32,
packing a custom version of the SciTE editor linked to the
GLPK standalone solver (glpsol.exe).

Best Regards (and happy new year!),
Luiz Bettoni

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.