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 ${\dots}$ 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 ${52}$ 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 ${50\%}$ 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 ${25/52 < 0.5}$. 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 ${n}$ assets ${\{a_{i},\dots,a_{n}\}}$. She then creates derivatives ${S_{1},\dots,S_{m}}$ where each ${S_{i}}$ is a random subset of size ${D}$ of the assets. Each asset will then either fail or succeed. The derivative ${S_{i}}$ pays off if at least one-half of the assets in it succeed; otherwise, it does not pay off. If Bob buys the derivative ${S_{k}}$, 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 ${\{a_{i},\dots,a_{n}\}}$ and she deals Bob a hand that consists of ${D}$ 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 ${a_{i}}$ 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 ${m}$ copies of a special deck of cards. Each deck has ${n}$ cards. All of these decks are identical. Alice shuffles the first one and deals out a hand of ${D}$ cards—this is the first derivative. She then takes the second deck and deals out another hand, and so on until all ${m}$ hands have been dealt.

These hands define the ${m}$ derivatives. Note, it is important that assets can be in more than one derivative, since Alice may wish to sell more than ${n/D}$ 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 ${a_{i}}$ 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:

1. With enough lemons Alice can create non-random derivatives that will generate extra cost for Bob;
2. With limited computational ability Bob will be unable to detect that Alice has acted in a non-random manner.

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 ${d-b > 3\sqrt D}$, ${n/N \ll d/D}$, an ${(m,n,d)}$ subgraph will generate an extra lemon cost of at least ${(1-2p-o(1))mV \approx n\sqrt{N/M}}$.

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 ABBG paper has nevertheless caused a quite stir among finance bloggers. For example look at this, this, and this.

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.

Solutions?

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.

Open Problems

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.

1. October 22, 2009 7:23 am

Nice writing style. Looking forward to reading more from you.

Chris Moran

October 22, 2009 9:35 am

It does not appear that this type of cheating was the cause of the financial crisis. It is not clear if the banks (e.g. the ones dealing the derivatives) were getting better ones, or if they were just using worthless (e.g. subprime) derivatives to inflate their books and they were incentivized (i.e. paid) to make these inflated numbers.

What I do not understand about the result is that suppose Alice deals Bob and herself some derivatives such that her derivatives are much better than Bob’s. Then the returns come in and Bob is upset because he lost money and Alice made money, but he can not prove that Alice cheated. But then they repeat, and again Alice makes money and Bob loses money. After k steps, if Bob always loses money, would he then have a proof that he is being cheated since his results deviate from the average value of the returns?

October 22, 2009 12:46 pm

First, Alice will only have an advantage not a sure win. Second, Bob would have to loss quite a few for him to have a good case that he is being cheated I believe.

October 22, 2009 6:49 pm

But if Alice is a financial authority such as a Bank, then there are many Bobs, Bob_1, Bob_2, etc. And ALL of them should be at a disadvantage (assuming that Alice is taking advantage of the opportunity to cheat). Aggregating over all the Bobs, it may be possible to see that they got less than expected.

If all the Bobs get together, can they then prove that they were swindled?

October 22, 2009 1:36 pm

Economies (interrelated markets) are constantly subject to stochastic shocks. Think about a price vector in a given time whose entries are randomly changed. Arbitrage and speculation are respectivelly space and time symmetrization transformations over this vector effected at a microeconomic level by risk avoiding agents (hedgers) and earning-looking agents (speculators) and having as macroeconomic effect the driving of markets towards equilibrium (wich is the (highly unestable) symmetric situation on wich no agent can make advantage from any move, until a new stochastic shock happens).

Derivatives in general are the finantial instruments wich allow agents to hedge/speculate (on any physical or finantial underlying) and as such are highly benefitial for economic sectors and economies (i recall having “dealed” once as hedger in a sector whose underlying was subject to frequent climatic shocks, but on which due to low volume of transactions there was not a futures market for it and we could not even diversify geographically our purchases…horrible!).

To deal with derivatives is usually a fair game, but mortgage derivatives markets have been….not even a casino !

p.d: some finantial bloggers make the usual (journalist) mistake of forgetting that NP-completeness is an “asymptotic” concept and taking as a fact the (possibly true) conjecture P!=NP.

October 22, 2009 6:39 pm

Dick:

Thanks for the blog post on our work.

The reason we think of seller generating many CDOs is that with a single derivative there is no doubt that no buyer would buy it. They will assume that the seller would try to sell his lemons first. Indeed, the case of a singe CDO has been studied in economic theory. The intractability arises only with high-volume sellers.

By the way, all the relaxations of the densest subgraph problem you mention are believed to be intractable. I agree with you that for moderate parameter sizes there are probably ways to get around the intractability. But keep in mind two things (a) current pricing and rating algorithms use monte carlo methods and would not solve densest subgraphs even for moderate parameters. So at the very least those should be changed. (b) the market is not very transparent so it is unclear even how to put together the graph we are talking about.

I recommend that your readers should look at our FAQs for the paper (http://intractability.princeton.edu/blog/2009/10/new-paper-on-complexity-and-financial-derivatives/) which addresses many of these points.

October 22, 2009 7:43 pm

I agree completely. I have no doubt that your problems are quite hard. You know my view about potential surprises but I think you are just fine. It was a pleasure to post on this pretty paper.

October 22, 2009 6:46 pm

You assert that “planted” dense subgraph may actually be easier, whereas authors clearly state in the paper that it is thought to be hard “on average” version of dense subgraph.

This actually is their basis to claim problem is hard as cryptography i.e. approximation won’t give definite answer at all.

Any concrete insight as to easiness “planted” dense subgraph?

October 22, 2009 7:45 pm

The reason I say that planted “could” be easier is that we have had work done in the past on related problems. Whenever you plant something and assert that it is “worst case” you need to be careful. The authors are world experts and have been quite careful about the issues on planted versions. However, I thought it was reasonable to raise this as an issue. Also see Arora comment on this very issue.

October 22, 2009 11:03 pm

I see.

I am (almost) an algebraic geometer, so I’m not fluent with complexity topics, barely starting. Could you please direct me at similar problems from the past? Sorry if I ought to know that from basic textbook.

October 22, 2009 10:55 pm

I think you left Laszlo Babai, Lance Fortnow, and Leonid Levin off the list of people who should be cited for blessing us with PCPs. (Not that I’m trying to start a discussion about who should be given credit, but just that I felt their names should appear at least somewhere in this post, even if in the comments.)

October 23, 2009 7:04 am

I agree. My list was just the same as the 2001 Gödel Prize list. Had to make some cutoff. But agree with you. Thanks.

8. October 23, 2009 9:13 pm

oh i really wanted to know what happens in the movie Paper after the ‘nothingness’ that follows once Keaton says “stop the presses”