On "Incentive Compatibility" in High-Frequency Trading

Today, I was reading a survey paper on convex optimization in risk management (naturally, the applications were financial), when I started thinking about high-frequency trading and how to rationally design the exchange. From the game theoretic perspective, designing such an exchange becomes less than straightforward when the interaction of rational, self-interested buyers and sellers is taken into consideration. I decided to just do this "exercise" on the bus, on my way to Maju camp for RT. (Like many, I was unaware of the 3 month shift in the deadline for doing my IPPT. Still, the exercise would be good for me. My running has deteriorated to a sad state.)

High frequency trading entails computers making lightning-fast trades, and trading agents (such as brokerages) holding positions for as little as a few seconds. As of the end of last year, it accounted for about two-thirds of trades in the US and about half of those in Europe. Last year, the Singapore Exchange (SGX) launched a new trading engine called Reach, advertising it as the world's fastest. It is unfortunate that details on how trades are cleared are not readily available for scrutiny. While the potential harm of poorly designed exchange mechanisms is not huge, inefficiencies commensurate with the frequency of trading can arise.

My objective, here, is to design an exchange so buyers and sellers have incentives to truthfully declare the maximum they are willing to buy at and the minimum they are willing to sell at. This is because given a trading mechanism that is not "truthful", outcomes can be highly inefficient (and possibly ill-defined). Here, inefficiency means that trades that might benefit some buyer and some seller might not happen. With a truthful mechanism, efficient allocations can be made that "maximize social welfare". It was thus my objective to design a good trading mechanism without paying an untenable "price of truthfulness".

Now, on to the topic at hand. In a sense, a stock exchange is not very much different from a traders’ wet market. In fact, the technical difficulties of achieving efficiency in the wet market are more severe than in the high-frequency trading market place. This is a surprising plus of the latter over the former. (This will become clear later.)

In both cases, buy and sell quotes have to be matched and cleared. (And much faster in the electronic market place.) This is when game theory seems to rear its ugly ugly head. A theorem due to Roger Myerson and Mark Satterthwaite tells us that there is no "efficient" way to trade a good between two individuals unless the lowest amount the seller is willing to sell the good at exactly matches the highest amount the buyer is willing to pay for it (i.e.: there is no buyer or seller surplus and that trade leaves no one better off, a pointless trade). This means that there are incentives to posture, pretend and hide the maximum value that one is willing to pay or the minimum value that one is willing to sell at. Anyone who has been to a market in Bangkok or Bali sees this first hand. (My girlfriend loves bargaining. I however, do not have the taste for it, perhaps making me manifestly unsuitable for wheeling and dealing.)

This unfortunate fact has correspondingly unfortunate effects on clearing trades. Let us say that a trade is matched for 1 share and the buy bid is at B (say 10) and the sell bid is at S (say 5). It is clear that the buyer must pay at most B (10) and the seller must be paid at least S (5). If the exchange stipulates that the trade clears at the any number between B and S (say the mid-point), then incentives exist for buyers to shave down (and for sellers to inflate) their bids in order to get a better deal. This is unfortunate as we need true valuations to make good allocation decisions. (In this context, "allocation" refers to clearing trades and "welfare maximization" is desirable. Also, we are not concerned about buyers inflating their bids and for sellers to shave theirs down as more trades are encouraged, and possible real losses lead to a natural restriction of this.)

Let us take a step back and consider how we might obtain matching buy-sell bids to clear. For simplicity, we consider 1 share blocks. (Though it is trivial to execute with blocks of varying sizes.) From the perspective of economics, we would like to incentivize people to truthfully inform the exchange of the lowest price one is willing to sell at (for buyers) and highest price one is willing to pay (for sellers). This allows efficient allocations. This incentive can be built into the exchange by making it possible for buyers and sellers to capture more trade surplus (the difference between transacted price and one's valuation) by bidding truthfully.

Consider the following matching procedure: pick the highest buy bid and match it with the lowest sell bid and pass that match on to clearing. This means that matches, from the pool of unsatisfied bids, are made so as to maximize the total trade surplus of that match. So "potential trade surplus reaped" will be used as an incentive for all to bid truthfully. Tentatively we will leave this at that, noting that a payment rule (to determine the clearing price) is needed to make this precise. Before getting to that, we return to the apparently ugly problem mentioned above.

I made a number of mistakes on that bus. I've thought asymmetric buyer-seller rules would work (noting that agents would buy essentially as often as they sell); I thought randomization would save the day. All those would not work. It turns out that there is a direct cost to economic efficiency that has to be paid to ensure truthfulness. What would please the board of any exchange implementing this mechanism is that the exchange can pick up what is left on the table. Let me explain.

The key requirement for truthfulness is that, all other bids being fixed, a buyer and seller pair should not be able to affect their gains by changing their bids. Changing their bids should only affect whether their trade is cleared first, and it should be clear that trades cleared first generate more "potential trade surplus". Thus, given a top buy bid B1 and second highest buy bid B2, and lowest sell bid S1 and second lowest sell bid S2, the buy price and the sell price should be functions of B2 and S2, (B2+S2)/2 being the obvious choice. If these differ (albeit slightly), the exchange pockets the difference as a "facilitation" commission.

Now moving back to the matching rule, we see that the leading buyer has no incentive to bid anything other than the maximum he is willing to pay as that would not increase his expected trade surplus (and possibly decrease it). A similar case is true for leading sellers. Ostensibly, we have achieved incentive compatibility in high-frequency exchanges.

Unfortunately, it still is not clear cut as (1) "non-leading" buyers may raise their bids and "non-leading" sellers may lower their bids to get a better match, and (2) there may be a timing issue. Due to these limitations, quotes were added to the title and "incentive compatible" was used as opposed to "truthful". Yet, these issues are far from fatally damaging to the mechanism outlined above.

On (1), the problem is ameliorated by the fact that for approximately evenly spaced buy bids and similarly spaced sell bids, non-leading bidders stand to lose if they manipulate. In fact, it can be shown that if buy bids are evenly spaced and sell bids are evenly spaced with a different spacing, if a non-leading buyer raises his bid, he only stands to gain if the "sell-side spacing" is more than twice that on the "buy-side", which is highly unlikely to persist in sustained trading by the "symmetry" of buying and selling (i.e.: the use of similar models for asset valuation) and the price mechanics led by supply and demand. A similar argument holds for sellers hoping to gain by pretending to be willing to sell for less. On (2), An agent might wonder what if a lower sell bid comes in over the next second and by posting a buy bid now, it is missed? However, in so far as things are uncertain, and one expects to lose money by holding back, this problem is not so severe. (Woo! Hand-waving. Doesn't this take you back to your school days.)

This has been a fun exercise in mechanism design. (Writing this up took longer than thinking about it.) It is quite amusing that the incentive problems in a simple setting like a traders’ wet market are more intractable than in a high-frequency exchange. Hopefully, it has demonstrated the value of the marriage of economics and computer science in our world.

---

Postscript 1: I feel that mechanism design has an important role to play in the evolution of the public and private spheres in Singapore. As I am embarking on a PhD in Decision Sciences at NUS Business School, I hope that I’ll be able to make some contributions in this arena. It would be appropriate to thank David Parkes for introducing me to this wonderful field. The commute up north to take his class (and missing another class I wanted to take that was back-to-back with it) was well worth it.

Postscript 2: The aforementioned matching can be done efficiently using priority queues. Certain specialized implementations are blazingly fast.

Postscript 3: An electronic marketplace may become even more interesting if a combinatorial element is introduced. That is, if bundles of different stocks in some proportions have a synergistic value. This adds horrid computational issues, and may be of dubious value. One question might be: given that in general, trades like this cannot be cleared fast, is there a non-trivial restricted class of trades that can?

---

Afternote 1: If the exchange would like to obtain additional revenue from each transaction or a government would like to tax transactions, it should be done as a fixed proportion of the buyer-seller trade surplus. This will preserve incentive compatibility.

Afternote 2: One of thoughts that went through my mind on that bus ride was how to sensibly do short selling in high-frequency trades. Now that this post has evolved into what it has become, this is a little off-topic. While I do not see the grave dangers of naked short selling (selling shares one does not own without first having actual shares borrowed), I feel it distorts supply/demand signals in markets and can have ill-defined effects. I was thinking of an auction for loaning shares for shorting, where the price would be the interest rate or a rental rate. A simple sequential VCG auction might be used for this.

Afternote 3: Note that this does not maximize trading volumes. To maximize trading volumes, the lowest sell bid might be matched with the lowest feasible buy bid, but this destroys incentive compatibility. This loss of potential volume, might be an additional price of incentive compatibility. It is unclear which is more costly: the price of untruthfully higher sell bids and untruthfully lower buy bids, or the price of incentive compatibility. Yet, these are hypotheticals. What is certain is, the mechanism outlined above has nice revenue properties.

Afternote 4: In view of Postscript 1, it would be interesting to compare (in simulation) this mechanism and, supposing this is not how it is done now, existing trading mechanisms. The main thing to look out for would be the total (exchange-measured) trade surplus. To do this, asset prices might generated using a (possibly very) noisy factor model, and agent valuations might be generated using (possibly bad) estimates of the aforementioned factor model. Trading strategies may then be simulated given these synthetic pieces of information.

Afternote 5: In a purely symmetric buy-sell environment, this reduces to the median price mechanism, which is nice. It is also trivially efficient since whoever values the goods the most gets them first (and whoever values them the least get rid of them soonest).

Afternote 6: Obtaining full incentive compatibility may be a matter of selecting different prices for buyer and seller using distributions on the "enclosed" bidders. This becomes a matter of using the empirical distribution to compute adaptive probabilities of setting the buy price at B2 and the sell price at S2. In these cases, the "exchange" pockets the difference to enforce incentive compatibility.

Badminton and Incentive Compatibility

I was doing my In-Camp Training this week when I read about the fiasco in Olympic badminton. I wanted to write a post about how the rules are such that they encourage bad behavior, but on coming back I found that Robert Kleinberg had already written something about the matter, titled Olympic Badminton is Not Incentive Compatible. Rather than re-work the same argument (and do so with a considerably poorer literature review), I'd like to point to his article.

At the end of his post, he wonders why shenanigans like that do not happen more in sports. I'd conjecture that advertising revenue has something to do with it. "Side payments" such as ad revenue provide subsidiary incentives to exhibit some "honor on the field". Which is probably why top teams are incentivised to be at the top of their game almost all the time. Picture perfect sporting moments bring in ad money. So it is all about payments. In sports like badminton, these payments are not substantial enough to detract from strategic skiving.

Disrepute aside, this is a wonderful example of how poor non-incentive compatible institutions generate bad outcomes for society.