What the Knapsack Problem Can Teach Us About Capital Allocation

Imagine you are Ali Baba, standing in front of a huge rock that’s covering the mouth of a cave which houses the plunder of a band of thieves. “Open, Sesame!”, you say, and the rock moves to give you access to a huge pile of treasures – gold and silver coins in heaps, silk, brocade and jewellery. You stuff your sack with as many gold coins as possible and carry them back home on your donkey and hide it underground. By now you would have recognized the story as “Ali Baba and the Forty Thieves” – a folktale from One Thousand and One Nights. For many observers and participants of the start-up ecosystem, 2021 felt like being inside one such cave of infinite treasures, awash with liquidity that was there for the taking. And with that, many plans to conquer the world were laid!

We’re barely two months in, and it’s clear 2022 looks nothing like 2021. Public markets, led by tech stocks, have fallen anywhere from 10%-70% in the US and even India’s tech stocks have fallen 20%-50% from their peaks. We are starting to hear about capital raises taking longer, term-sheets being renegotiated, valuations slashed and some funds offering down rounds. We have seen this story a number of times since 2006, when Sequoia Capital India started operating in the region. While we can’t profess we know if this is the beginning of a real downturn, what we can say is that the mood is rapidly turning sombre and the days of easy money are probably over.

But cheer up; you are Ali Baba, remember? You do have a sack full of gold coins you took home from the cave. Assuming you haven’t spent it already, maybe it’s time to rethink the world domination plan? Now you have a new sack to fill – let’s call it the knapsack. This sack will contain the set of things your gold coins can be spent on. Your job is to maximize the value of this knapsack, armed with the knowledge that the bag has finite space and you have finite gold coins. How do you propose we go about this? This is the capital allocation exercise I would encourage every founder to do as you plan for the next 18-24 months.

So where do we get started? Maybe there is something we can learn from the combinatorial optimization problem called the Knapsack problem which is popular in computer science. The Knapsack problem is defined in Wikipedia as follows:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

You probably see the similarity now. Our knapsack is the company – we need to maximize its value (or grow it optimally) by choosing a set of initiatives to focus on, each of which has a different payoff and cost, within the resources we have in hand.

One of the popular solutions (computationally fast but not necessarily always the most optimal) to the Knapsack problem is called the ‘Greedy algorithm’, where the set of items are sorted in a non-increasing order by the ratio of the objects’ value by weight and then the knapsack is filled starting with the highest value per weight object and then the next, until the knapsack hits its maximum weight.

To prioritize our company’s efforts and initiatives to maximize our knapsack’s value while remaining within our resources, we need to first define our version of the Greedy algorithm. Here are a couple of options to consider as a metric to rank order your initiatives:

• If you are a balance sheet light business, the best metric to focus on is Gross Margin per dollar of invested capital
• If balance sheet is involved, a more suitable metric may be the traditional Return on Capital Employed (RoCE)

For example, if an investment of a million dollars can be used to open up a new geography (and hence a new vector of growth and increased revenues) or can be spent on marketing to strengthen brand and hence possibly pricing power (resulting in higher gross margins on current revenue base), the above framework can help make that choice if our knapsack can only accommodate one of the two.

This is of course a simplistic framework and doesn’t capture the many other things that a founder needs to balance in their business – including what is core and what is non-core, investments in improving long-term competitive moats, new product launches for sustaining growth over a few years, etc. But we all know that there is fixed space in the knapsack and we will have to force ourselves to prioritize in this changing market environment. In other words, it’s time to start thinking more seriously about capital allocation.

More tactically, here are some things to consider when it comes to capital allocation in the current environment:

• Managing optionality: In bull markets, investors feel generous and value optionality but in normal markets a much higher discount is applied or, even worse, no value is given to initiatives focused on optionality. Reconsider how much capital is allocated in building optionality.
• M&A vs organic growth: We often see M&A activity rise when markets are bullish and reduce dramatically when markets go soft. It may be a good idea to ask if capital allocated to buy (or bulk up) may have better payoffs than building yourself especially since valuations maybe more favorable (hence higher GM/invested $).
• Desire to stick to core/familiar: As markets turn, most companies tend to go back to their core and stick to the familiar. It may be worthwhile asking if that is indeed a better approach than focusing on RoI based decision making. For example, when covid struck one of our companies decided to hunker down and focus on their home market when there was a smaller but much more profitable opportunity in another global market. In hindsight if we had allocated more resources to the better market, we would have driven more value creation in the medium term.
• Using absolute thresholds: Most founders forget that equity is the most expensive way to finance growth, and in bear markets it becomes even more expensive. So if you choose to invest in an initiative, the return on that capital should definitely exceed the cost of the equity. A simple thumb rule like this will help us prioritize and kill marginal initiatives.

Being a smart reader you would have by now also figured that Ali Baba himself would have used a version of the Greedy algorithm and hence picked gold coins versus other treasures (maximum value/weight ratio). But the most important thing Ali Baba would have made sure of is that his sack has no holes, so he doesn’t lose gold coins along his way home! After all, we need to save those gold coins in the first place to have a chance to allocate capital better.

Recommended Reads

Here are three articles I read over the last few weeks that I found interesting:

Why we say “Cheese”: Producing the smile in snapshot photography: This scholarly article, published in 2005, is a fascinating read (warning: it’s long but you can skim and get the gist!) that traces the history of how we moved from saying “prunes” to saying “cheese” when putting our best face forward for the camera. It’s also more than a little prescient in today’s Instagram world where the pout – which is more ‘prunes!’ than ‘cheese!’ – reigns supreme It does feel life has come full circle!

Inside the Company Trying to Solve the Global Bicycle Shortage is the story of how Trek’s fortunes changed when bicycle sales exploded when COVID hit, and how CEO John Burke moved faster than others to capitalize on the opportunity.

A Common Weed Has Just Shaken the Foundations of Biology: This post talks about a significant reported observation about gene mutations in a common weed called mouse-ear cress. It turns out that gene mutations may be less random vs what was believed so far.

If you have time for a longer read, here are two books I’d like to recommend:

Solve For Happy: Engineer Your Path to Joy, by Mo Gawdat.

I’m really enjoying this book on audible, which narrated by the author himself. I was at a small group event where Mo spoke about his days at Google and covered a wide range of topics. I learnt about his book and soon was listening to his journey of recovery and happiness after a major setback in life. His message that happiness is our default state strongly resonated with me.

The Cold Start Problem: Using Network Effects to Scale Your Product, by Andrew Chen.

This is a really good book when it comes to understanding network effect businesses. Andrew brings to life several examples of the early days of some of the most successful companies built on network effects, including Uber, Snapchat and Airbnb, and also explores why some products failed to take off. Highly recommended for startup founders – there is some learning for all even if you don’t directly think of your business as a marketplace business.

Do write in at ravi.gv@siteadmin.peakxv.com if any of my interests intersect with yours! Click here to read more articles on Sequoia’s blog. I’m also on LinkedIn and Twitter.