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:

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:

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:

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.

Now, the efficient market hypothesis has three forms:

  1. 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.
  2. 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.
  3. 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!

Copyright © 2022-2023, TheHans255. All rights reserved.