Thoughts on "Markets Are Efficient if and only if P=NP", Part 2

View Part 1 here

This blog post is a response to the 2010 paper "Markets are efficient if and only if P = NP" by Philip Maymin. The paper's synopsis is as follows:

I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient. Specifically, markets become increasingly inefficient as the time series lengthens or becomes more frequent. An illustration by way of partitioning the excess returns to momentum strategies based on data availability confirms this prediction.

The paper has never been published to my knowledge, but is available on Arxiv here: https://arxiv.org/abs/1002.2284

ALSO: A DISCLAIMER: I AM NOT A FINANCIAL ADVISER AND CLAIM NO SPECIAL KNOWLEDGE OF THE FINANCIAL SECTOR. Most of my understanding of finances comes from self-study of asset classes and experience with my own funds, and it is quite possible that this understanding is partially or completely wrong. While I aim to provide correct information for the best of my ability, I do not intend to encourage or discourage any specific financial decisions in this post, and do not take responsibility for any financial decisions thus made.

Now that we've spent some time discussing how the paper attempts to link the efficient market hypothesis and the P = NP problem and its shortcomings, we ask ourselves: how would we attempt to link these two problems? While I don't claim to have a solid answer, at least one that would link the two problems together, I have some ideas on how a computational framework for a market can be constructed.

Our Basic Framework: Agents, Assets, and a Book of Exchanges

How would you define a market, anyway? You could probably consider the key feature of a market to be the action of exchange - that is, when two or more parties, each with something (either tangible or metaphysical) the other wants, agree to give each other the wanted things. For instance, two children agreeing to exchange a different baseball card from their collection, a man exchanging five dollars with a grocery store for a loaf of bread, or a woman exchanging 8 hours of work for a company in a given day in exchange for a daily wage from that company. A market is a system in which exchanges like these are facilitated.

From there, we can define a few other items:

An asset is a unit that is being exchanged. This could be currency, a share of a stock, food, metals, or other resources. It could also be rendered services, including asset production, repair work, etc.
An agent is a party making an exchange - a person, a corporation, etc. They have a set of assets that they hold onto and can exchange, and can also produce, consume, and destroy assets over time.

We can likely make a generalization and say that the fundamental action of our market is giving assets from one agent to another, where no return of assets necessarily occurs. This would allow us to generalize the concept of agent to include anything that can hold, produce, or consume assets - for instance, we can include the Sun, which does nothing but produce large amounts of sunlight each day, and we can also include plants and animals, which convert that sunlight into other products. None of these agents can be negotiated with for exchange, but their presence can account for the existence of some assets that we would otherwise just have to assume exist in some set quantity, and thus allow us to make more accurate calculations on those assets' value.

An essential feature of the market is time - within a given instant, every agent in the market is only able to produce or consume a limited quantity of assets, can only make a certain quantity of exchanges, etc. Agents are able to give assets to or exchange assets with each other, but they are limited by their state - factors such as location, health, and access to communications, which determine whether or not a given exchange can be made. Agents must expend resources to either maintain or change their state as they wish.

Within the specific markets economists like to study, such as the New York Stock Exchange, there is also the concept of public advertisement of exchanges. That is, among a well-known set of assets, an agent can publish their desire to either buy an asset for some set price, or advertise their possession of an asset and their desire to sell it for some set price. When a buy order and a sell order for the same asset appear together at the same price and quantity, the two agents can meet and perform the exchange at that price and quantity. We will call this book of advertised exchanges, well, a book of exchanges, and we will assume that its contents can be known to all agents that take at least a cursory interest in them and need expend only a small quantity of resources to access them (that is, it is public).

Note that the presence of a book of exchanges, in order to work efficiently, requires our market to have a few more characteristics:

Technically, every asset in a system is unique - they are, after all, made of atoms and other fundamental particles, which all have their own position and characteristics, and there are endless variations in how they can be arranged to match the forms we observe them as. You could specify unique assets in a book of exchanges, but in order for more than one exchange of the same asset to exist, it must be possible to group assets into fungible groups - that is, for the purposes of the desired exchange, any of a given set of assets will be considered identical.
In order for assets to have a quantitative value, there must also be a currency - that is, a set of assets, all entirely fungible with each other, to which all other assets can be compared by value. The value of the currency itself need not be fixed, though it is better if it remains relatively stable - for instance, gold has been a popular choice of currency in real markets because any instance of gold (when melted down) can be considered identical to any other instance of gold with the same mass, and it breaks down very little over time, if at all. All of the exchanges in our book are between the currency and some other asset.
All of the exchanges that are ever filled by the book, as well as any exchanges that are advertised in the book but are later canceled, are recorded permanently in a ledger that is just as public as the book.

Note also that it is possible for agents to make exchanges independent of the book, and there is also other public and private information that can exist in the system.

Defining the Efficient Market Hypothesis

From this basic model of agents, assets, and a book of exchanges, we can now make some definitions that will let us formulate the efficient market hypothesis.

The market price of an asset is the midpoint between all buy and sell orders in the book of exchanges for that asset, defined in the number of units of currency each of those orders are compared to.
The true price of an asset is the value that the market price of the asset "should be", which is its value in direct comparison to the other assets in the market. The true price of an asset is reflected in factors such as how much it is needed (its demand), how much of it exists/can be made (its supply), and any ability it has to produce other assets.
A piece of information is any fact that is known about an asset, which can have an effect on both its market price and true price. Buy and sell orders, which are instances of supply and demand, constitute pieces of information. Other pieces of information can also be published, such as information about any agents connected to an asset and any other assets they themselves control.

Now, the efficient market hypothesis has three forms:

Strong: The current market price of an asset is efficiently reflected in all information about an asset - that is, every detail, public and private, that could determine its true price is reflected in the market price.
Semi-Strong: The current market price of an asset is efficiently reflected in all publicly available information about an asset - that is, all the buy and sell orders in the book of exchanges and the ledger, and any other pieces of information with the same level of access, but not anything more clandestine.
Weak: The current market price of an asset is efficiently reflected in all publicly available exchanges, but not necessarily any other pieces of information.

How do these take shape in our system of agents and assets? Simply put, when a new piece of information is introduced to the market (within the factors of the version of the efficient market hypothesis we are trying to prove), the true price of the asset will change, and the market will modify the contents of the book of exchanges (creating new orders, filling orders, or canceling orders) in order to make the market price of the asset reflect the true price. Each agent can perform their own calculations (spread over the ever-ticking flow of time) to make these changes, and because all three forms of the efficient market hypothesis designate changes to the book as new information, each such change will trigger more calculation until it is determined that the market price and the true price match.

From here, we can finally tie in the P = NP problem by defining efficiency as polynomial time efficiency. In other words, we can say that the market is efficient if and only if it takes time polynomial to the number of agents in the market and the number of pieces of information for the asset (which set is determined by the version of the efficient market hypothesis we are trying to prove). If any agent has to do computation exponential to the number of pieces of information, or if a correction of the market price requires an exponential number of book changes (or worse, requires an infinite number of book changes, perhaps because the market price oscillates around the true price), then the market is not efficient.

To then state that the act of correcting the market price to the true price is intimately connected to the P = NP problem, we must then prove that it is equivalent to some other NP-Complete problem, such as the traveling salesman or knapsack problem. I don't claim to have any idea how to do this, unfortunately.

Determining Agent Motivations

It should become readily apparent, however, that one factor in how we define our agents has been left out: what, exactly, are these agents trying to do? In order to make the necessary changes to the book of exchanges to make the market price the true price, there must be a contingent of agents in the market that would have a desire to do that, and they must have the power to do it despite the actions of other agents in the system. This aspect of the problem is made more complicated by the fact that, since we are defining mindless resource producers such as the Sun as agents, we cannot give all agents in our system the same set of goals.

Fortunately, we can look to the field of artificial intelligence to help us. Artificial intelligence algorithms, including the most basic ones like searching a set graph of decisions to play chess, run on a utility function that attaches a number to a given state that an intelligent agent (that is, the object running the algorithm) might find itself in. In the chess example, the simplest utility function gives a -1 for a lost game, a 1 for a won game, a 0 for a draw, and does not give a value for games still in progress. The AI generally tries to take actions that maximize this utility function and sorts through decisions rather handily on that premise - the hard part is calculating the utility function, such as giving estimates for how good a chess position is when the game isn't over yet.

For a rather simple utility function in the market, we can just give an agent that enjoys maximizing its wealth as much as possible. That is, it looks at all of the assets in its possession, converts them to their value in the market's currency, and tries to make that value go up as much as it can through exchanges in the market. Plenty of real players in the market try to do this, and it would create a good framework for a hypothetical market if all players were trying to do this.

Another utility function can come from that fact that most market players have physical needs. We could state that each agent has a quantity and set of assets that they need to consume at regular intervals - food, water, shelter, etc. - and that the utility of the agent is maximized when it is consuming those resources and goes down when one or more of them is deficient. Those resources are destroyed when consumed, driving the need for continued demand in the market for more of those resources.

(Connected to this is the idea that most, if not all, market players are mortal, and can be removed from the system entirely if their needs are not met. A full exploration of this idea might also include agent-to-agent actions such as bustKneecaps(), but including them veers away from connecting the efficient market hypothesis and the P=NP problem and more into making statements about how a real-world market works vs an idealized model).

That's it for me for now on this paper. An altogether interesting read, and while I don't believe it creates the connection it claims to, it offers an interesting discussion on how that connection might be made. I might come back to it if I can determine some novel way to show NP-completeness in this problem, or if I can write some interesting simulations to show these hypothetical agents in action. Either way, see you all again soon!