Full Bins, Clean Sheets, Can't Lose
Vol #144: August 31st, 2023
The bin packing problem is elegantly obtuse.
It fits into that fun class of puzzles that are easy to understand and see the real world implications of, but devilishly gnarly and wild once you crack the top off.
In computer science, bin packing is an optimization question about how to most efficiently fit objects of assorted sizes into the fewest number of fixed size bins. In the real world you can visualize this as a group of Boy Scouts lined up with various tents and stoves, while trying to scrape together the fewest number of adults with cars to take them and their gear camping.
Ask any parent, packing a car is both art and science. With one car you have a specific but slightly different constraint. This variation is called the knapsack problem - fitting the items of maximum value into the single bin. But with multiple cars the problem expands quickly. No matter how much of a shape rotator you are, once the number of items enters double digits it might as well be unbounded.
The crux of the bin packing problem is that it’s intuitive but impossible*. Given a fixed number of vehicles and rucksacks, there’s necessarily a limited number of solutions, and at least one will be the best. But there’s no direct way to find out what that is without a lot of trial and error.
On a more technical level, a trading related example would be quote updating. When I as an individual want to tweak the legs of my broken wing butterfly, I go into TradeHawk and manually update the price or strikes. Medium frequency strategies might do this algorithmically through an API sending cancel and replace orders.
Any high frequency participant is going to be sending a lot of price and size updates to the market, and most exchanges give market makers a specific method and pipe to do so. Depending on the exchange matching engine’s architecture, liquidity providers get a batch process to send in their quote updates for many symbols all at once. Given that for each participant these updates tip into the billions before lunch, it’s in everyone’s interest to do this as efficiently as possible.
When the market moves, you have both a bin and a knapsack problem. NVDA has 2528 strikes - with bid/asks on calls and puts you’re talking 10,000 prices and 10,000 more sizes. If a bombshell about microchips hits the news feed, everyone is in a footrace to drop the call bids and raise the put offers. When J-Pow says something that moves the whole market, it’s a stampede.
There’s a rough prioritization that you can do to think about quote updating here. We know that delta is the sensitivity of the options price to a move in the underlying, so naturally the options with the biggest deltas should be at the front of the line.
You can also think about which options are the most likely to be the victim of adverse selection. Things don’t stay out of line in SPY or AAPL for very long, and if you’re slow to update even a low delta option, with the tightness of markets and depth of liquidity you’re quickly going to get picked off. Further down the volume tiers, there are less eyeballs and also less confidence in pricing to make sniping delta moves worth it.
The severity of a pickoff is inversely proportional to the liquidity in the name. Sure your lagging bid in AAPL will quickly get dinged for a penny or two more than it’s worth, but there are 918 other strikes that are a few pennies wide where you can lay off this risk. And if you really hate it, there’s probably enough depth to immediately trade out.
Stale quotes in the rink-a-dink Canadian miner or upstart pharmaceutical company will eventually get lifted. This is where you are likely to wear that position until expiration. Lagging on delta updates now has you with a vol position in something that only trades by appointment. Risk starts asking about your vega number or short stock position because the silicon hamsters couldn’t run fast enough to keep your sheets clean.
For options market makers, the problem is not just one of pure mathematical optimization, but one layered with a probabilistic nuance of where their greatest risk lies. That sounds like it would complicate the problem, but in many ways it also provides the path for best approximating the solution that is most adapted to this specific need.
As alluded to earlier, the bin packing problem is not directly solvable. It’s “NP Hard.” For someone that’s only quantitative enough to be dangerous, that basically means there’s no algorithmic solution. You can’t take an equation or follow a formula to deterministically allocate them optimally. You can only start squeezing things in, and seeing what fits. Not technically impossible, just not cleanly reducible.
An important distinction in the problem space is whether the values arrive in series, and must be irrevocably allocated one after the other; or whether the entire data set can be seen in advance. Knowing the strike counts of all your products to update is fixed and knowable ex-ante. On a conceptual level, orderflow arrives randomly and position sizing relative to risk limits might also be framed as a serial or “on-line” version of the bin packing problem.
Sitting at the end of a conveyor belt and dropping the next widget into a bin can be optimized a few different ways. You can allocate the next unit to the first available bin it fits in, or you can allocate it to the bin it fits “best” in. Are we filling precisely or quickly?
If you have the whole list in front of you, there is a brute force best way, but there are also some quick sorts that get you very close. If you learned calculus by drawing rectangles under a curve, the number of rectangles to estimate the optimal bin distribution is fortunately not very high. A sorted list can then apply any of the on-line logic with better accuracy, and even add classifications; e.g. the packing can be optimized by the relative size of that unit to the total population of units.
The bin packing question of course has practical applications. Making API queries efficiently will allow for better data granularity. Finding one less parent to drive to Hoyt Scout Reservation.
I think it also exposes some interesting metacognitive lessons about problem solving. When I first stumbled across this in the quote packaging scenario, not having written much software outside hacky VBA and my TI-83 calculator, I assumed there would be a graceful solution. Isn’t that what computers did?
It’s encouraging to know that even the smartest and most technical minds can’t solve these riddles which are viscerally understood but of Gordian proportions. It’s also important to recognize the power of the estimation techniques, and how a little bit of structure can go a long way.
In personal finance, the problem of “NP Hardness”1 is how much money do I need to retire? It’s so simple. I just want to be able to do these things and pay for them - what’s the number?
Financial advisors will bring out estimation methods, use rebalancing algorithms like the 60/40 portfolio, and cite the 99th percentile Monte Carlo simulation of the Trinity Study. But there’s no right answer. If you want to “guarantee” that you won’t end up short, in 100% of the cases you’ll shuffle off this mortal coil with more than you needed.
The reason these platitudes are so popular is because they also tend to work pretty well. In many scenarios allocating to that risky private placement would be worth it. But given the uncertainty and risk of failure, keeping it simple is consistently best. Drop it in the next bin that fits.
When faced with a really complicated problem, knowing that being simple gets you pretty far is reassuring. After all, Alexander the Great just cut the famous knot in half.
A Note from Our Sponsor: TheTape.Report
We track short term trades with our three times a week newsletter “Trading Opportunity with TheTape” This also includes a subscription to our weekly newsletter focused on “Portfolio Design with TheTape” for longer term investors.
Both newsletters come with access to a suite of reports at TheTape.Report. Learn how to analyze opportunity through the lens of liquidity and spreads with our Real Time Research, and bolster your own trading with in depth analytics.
Every report comes with a seven day free trial.
Find out more on our website.
This week on Trading Opportunity with TheTape we covered:
The Sound of Settlements: 3M cuts a deal on earplugs, but plastics problems loom
Bankers Drop Ballast: Can a GS restructuring save DJ D-Sol?
Does Intervention Breed Volatility?: A look at how options markets are reacting to China's trading tax cuts
For Portfolio Design with TheTape, we talked about the relationship between interest rates and volatility:
Let the Chips Fall: $NVDA is a darling, how much longer does the ride go?
This stretches the analogy of what a true NP Hard problem is. Objectives are unique for each individual and market conditions are constantly changing. True NP Hard problems have defined constraints like bin packing, or the traveling salesman problem where you must find the optimal route between a list of cities of fixed distances apart.