Helping Wall Street Cheat With Theory
How to create “bad” derivatives that cannot be detected
Sanjeev Arora is the one of the most creative theorists in the world. He helped create the concept of Probabilistically Checkable Proofs along with Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy. On his own he found a wonderful approximation algorithm for the Euclidean TSP, and has done many other terrific things. I was at Princeton when we hired him, and it was clear back then that he was special.
Today I had planned to talk about some of the papers of FOCS 2009, but will instead talk about a new paper of Arora with Boaz Barak, Markus Brunnermeier, and Rong Ge (ABBG) on finance. I really like their paper, and it seems to me to be one of those seminal papers that could launch a whole subfield.
Sanjeev is currently the PI of a large NSF project looking into intractability and P=NP. He is also the creator and current head of the theory committee that has and continues to try to work with NSF to get more support for theory. The previous head was Richard Karp who did an excellent job running the committee for a number of years.
I feel like saying stop the presses. But this is not being printed so I guess that does not apply anymore. In one of my favorite movies, The Paper, there is a scene where the main character an editor of a newspaper, played by Michael Keaton, is told by one of his reporters, played by Randy Quaid, “you got to say it.” They are standing next to the high speed printing system. Papers are streaming by at a huge rate, and they want to stop the printing and change the lead story, since the the paper being printed has gotten it completely wrong. Quaid says again to Keaton you’ve got to say it. Finally, Keaton yells “stop the presses.” Of course nothing happens right away, next See the movie if you want to know more. I really like this flick.
As newspapers go out of business and news becomes electronic, what will we get to say in the future? Re-boot the servers?
Well that’s what I am doing today. So let’s turn to the world of finance and the paper of ABBG.
Let’s Play Cards
I am no expert on finance, so to explain ABBG I will use an analogy of playing a card game.
Imagine that there are two players Alice and Bob who wish to play a simple game of cards. Alice has a standard deck of playing cards and she is the dealer. Suppose she shuffles the cards and then deals out a “hand” of one card to Bob. He wins if the hand is a red card; otherwise, he loses. If Alice shuffles fairly, Bob has exactly a chance of winning—it is a fair, if boring game. I could make the game more realistic, but that would change nothing except make the analysis more involved.
The problem with the game is the simple phrase: If Alice shuffles fairly. What happens if Alice cheats? She could cheat in a number of ways; here are some that I have arranged in increasing order of skill required by Alice:
- The deck might be a stacked deck. Suppose that Alice has changed the deck so that it consists of only black cards. Then, Bob will have no chance of winning. Or she could have removed one red card and replaced it with a black one, then Bob’s chance of winning is reduced to . Note, Alice requires no special skills; she can be shuffling away and let Bob cut the deck as much as he likes. The game is a still losing one for Bob.
- The deck might be a marked deck. In this case Alice cheats by having the deck contain all the usual cards, but the backs of the cards are “marked” so that she can tell whether or not a card is a red or a black card. Then, she just shuffles away until she sees that the top card is black, she then stops and deals the top card to Bob.
- The deck might be a real deck. In this case Alice cheats by not shuffling the deck properly. She could have originally arranged that the red cards so they are on the top of the deck. With a few careful shuffles of the right kind, she can vastly lower Bob’s chance of winning. Even worse if she is a really good “card mechanic” she can show Bob the deck—that is she can fan out the faces of the cards and show them to Bob. The cards will look to be in a random order. But if she can execute the correct type of shuffles, then she can force that Bob always gets a black card. Essentially, she undoes the “random” order of the cards by performing careful shuffles and moves a black card to the top. This requires quite a bit of skill: a word of advice, never play cards with magicians.
Let’s Play Derivatives
Again there are two players who I will still call Alice and Bob. Alice is now creating financial derivatives and trying to sell them to Bob and to others. Before I even explain what a derivative is you probably can guess the high level insight: Alice creating the derivative is the same as Alice dealing the cards. If Alice creates them fairly, then Bob is okay. However, just as Alice can cheat at cards, she can cheat at derivatives. The reason Alice can cheat is the same as before: Alice may have extra information that she can exploit to cheat Bob. In a sense there is no surprise that Alice could cheat at cards, but that Alice could cheat at derivatives is the main result of ABBG.
With all due respect I do not mean to diminish the brilliant insight of ABBG—I really like their paper. My goal is to explain that what is happening with derivatives is very much the same as cheating at cards.
However, there are a number of interesting technical differences between cheating at cards and cheating at derivatives. One of them, by the way, is that the stakes are vastly larger. People play card games for stakes in the thousands or even hundred of thousand dollars, but banks “play derivatives” for billions.
The ABBG Result As A Card Game
My usual disclaimer: read their paper for the details and full statements of their results. I would like to give a high level view of their basic model, what they assume, and what they prove.
As I understand the key idea is that Alice has a collection of assets . She then creates derivatives where each is a random subset of size of the assets. Each asset will then either fail or succeed. The derivative pays off if at least one-half of the assets in it succeed; otherwise, it does not pay off. If Bob buys the derivative , then he wins if a majority of his assets succeed; otherwise, he loses.
Clearly, Alice and Bob are playing a type of game. Here is a way to model this as a card game. Alice has a deck of cards of the assets and she deals Bob a hand that consists of cards. That is his derivative. Later on, it is revealed which assets fail and which succeed, and Alice and Bob can determine who won the game.
In the derivative model Alice actually creates a number of derivatives at once. I must admit that I am not sure why this is done, but apparently it is the way that derivatives work. More on this later on.
Let’s model this as a card type of game. We will use cards to stand for assets and hands to stand for derivatives. Each card has a label on the back and a color red/black on the front. From Alice’s perspective, red stands for failure and black for success. Thus, for Alice, a winning hand is one with a majority of black cards. We will also assume that there are an equal number of red and black cards in the deck.
Alice has copies of a special deck of cards. Each deck has cards. All of these decks are identical. Alice shuffles the first one and deals out a hand of cards—this is the first derivative. She then takes the second deck and deals out another hand, and so on until all hands have been dealt.
These hands define the derivatives. Note, it is important that assets can be in more than one derivative, since Alice may wish to sell more than derivatives. Thus, it is critical that Alice has multiple copies of the deck.
If Alice has no idea which asset with fail or succeed in the future, this is a fine game. However, if Alice knows that some of the assets are more likely to fail than others, then she can cheat. The ABBG paper calls these lemons. Note, since the back of the cards are marked with the name of the asset it is like the cards are marked.
Even if Alice does not have a perfect mapping from an asset to its color, Alice could possibly cheat. She can do that if she has some partial information about the color of the cards. She does this by the way she deals out the cards to make the hands. Her goal is to get more black cards into hands, so she will win those hands. Even some partial information here is enough to greatly increase the odds in her favor.
The ABBG Result
In the ABBG paper the type of theorems they prove rely on two key points about the abilities of Alice and Bob.
The first concerns Alice. She must have some partial information about the lemons, the color of the cards, if she is going to cheat Bob. The exact number of lemons and how much they affect the cost to Bob is a technical point. I suggest you read their paper to get the exact results.
The second concerns Bob. If he is going to be unable to detect that Alice is cheating he must be computationally limited. In any cheating scam the person being cheated must be limited in their ability to detect the cheating, or it will be discovered. In the examples of ways that Alice can cheat at cards, Bob must not notice certain things. In one case, he must not notice that the deck is all black cards, in another that the deck has been marked, and in the last that the deck is in a pre-arranged order. His ability to detect Alice cheating in these ways gets harder: the first is easy—just look at the deck, while the last is quite hard—it is hard to notice that she is executing perfect shuffles. Notice that the more skill Alice uses to cheat, the harder it is for Bob to detect it. In similar ways, ABBG demonstrates clever skillful ways of cheating that makes it extremely hard for Bob to detect.
The ABBG results depend on Bob being limited in his computational ability. In particular, Bob must not be able to detect that Alice has dealt the hands in a non-random manner. The only way that Bob can detect this is their main theorem; in order for Bob to discover that Alice has cheated him in constructing the derivatives he must be able to discover that a graph has a dense subgraph. The intuition behind this result is that if Alice deals the hands, that is creates the derivatives, in a non-random manner the structure of the sets will define a graph that deviates enough from randomness to leave a proof of her cheating. However, the key insight is that detecting this is an intractable problem.
In summary, the ABBG phenomena is:
The exact statement of this result is technical, but I believe that the above captures the key insights that they have made. Here is an example, in their terminology of the type of results that they prove:
Theorem: When , , an subgraph will generate an extra lemon cost of at least .
What this is saying is: Alice can cheat and cause a certain amount of extra loss over fair play. For the meaning of the symbols see ABBG, but the symbols denote the main parameters of their model: the number of assets, the size of the derivative, the number of lemons, and so on.
Is ABBG Really A Problem?
The last thing Wall Street seems to need is advice from theorists on how to cheat. They seem to have done quite well on their own in the past and in recent times. Just say Bernie Madoff—if you type “bernie” into Google he immediately comes up—I feel sorry for anyone named Bernie.
The core of the cheating described in ABBG, in our terminology, is that Alice deals out more black cards than she would if the dealing was completely random. Thus, Bob can only detect that Alice is cheating if he is able to discover that she is dealing in this way. The clever insight of the ABBG paper is that this detection is equivalent to detecting a dense subgraph in a graph.
The conventional wisdom is that this is a hard problem. You all know that I have some doubts about this, but even with those aside this is a reasonable issue.
- A problem can be hard in theory, but might be easy in practice. One needs to know the size of the graphs that are used in practice, since even worst case algorithms could do well.
- Another possibility is that there might be good approximation algorithms that work on the graphs ABBG uses.
- Finally, the problems they create are “planted” versions of the dense subgraph problem. I think that this version of the subgraph problem could be simpler.
Overall I think that I would not want to have to solve these problems. But the simple claim that they are “intractable” is one that the authors, I am sure, would agree is a claim that needs to be carefully checked.
One thing we know is that when there is a trust problem in a digital system often we can overcome the trust issue. Sometimes this requires quite simple ideas, sometimes this requires modern cryptography, and sometimes something in between. I think there could be a number of ways to make it so Alice cannot cheat when creating the derivatives.
One idea that comes to mind is some protocol that forces her to really use proper random bits in constructing the derivatives. You could imagine that Bob is protected in this way. Another approach might be to let Bob select his own random derivative. This would not allow Alice to cheat, but would allow Bob to cheat. If he was the one with knowledge about the assets, then he could cheat Alice.
The key insight seems to be that this is a crypto problem that we have seen before: having two or more parties agree on a random string. I think that this can be done. Perhaps the most interesting question is can some special properties of derivatives be used to make the protocol more efficient.
Are there other types of ways to cheat in markets? Also one neat question might be how to develop a protocol that will allow both parties to be sure that all is well? I expect that we will see many more papers on this topic.