Why I Developed the Nested Shapley Algorithm

One of the problems I have been trying to solve in redesigning the electricity market is deceptively simple:

How should we pay generators for being useful to the electricity system?

Not just for the MWh they happen to sell at a particular moment, but for the underlying value their existence provides to the system.

In the market architecture I have been developing, I deliberately separate two things that are often bundled together.

The Automatic Market Maker (AMM) provides the operational signal. It determines the value of the next unit of energy at a particular place and time as the physical state of the electricity system changes.

Separately, utility-scale generators need a mechanism through which they can recover the non-fuel operating expenditure and capital expenditure associated with building and maintaining the assets that make the system work.

This is effectively my alternative to the existing capacity-market / subsidy / contract architecture.

And for that second problem, I use Shapley values.

The basic idea is:

Create a pot of money for capacity and allocate it between utility-scale generators according to the contribution each generator makes to the electricity system.

Importantly, this is not supposed to guarantee anybody a return.

Investment remains at risk.

Build a useful generator, in a useful place, with useful characteristics, and it should capture more of the available revenue.

Build something the system does not particularly need and there is no reason the market should guarantee that you recover your investment.

The interesting question, then, is:

How do we mathematically measure how useful each generator actually is?

Enter the Shapley value

The Shapley value comes from cooperative game theory.

Imagine we have a collection of generators:

We can take any combination — or coalition — of those generators and ask:

If these were the only generators available, how much demand could the electricity system actually serve?

That gives us a characteristic function:

where (S) is some coalition of generators.

The word feasibly is doing a lot of work here.

In my implementation, this is not simply:

For every coalition, I solve a network-constrained power-flow optimisation which maximises served demand while respecting generator availability, nodal power balance and transmission limits.

That means two 500 MW generators do not necessarily have the same system value.

One might be sitting exactly where generation is desperately needed.

The other might be behind a permanently congested transmission line.

Their nameplate capacities may be identical.

Their contribution to serving demand is not.

That distinction is fundamental.

A tiny worked example

Suppose we have three generators:

Suppose total demand is 100 MW.

After solving the network problem for every possible coalition, imagine we obtain:

Notice what has happened.

Generator C has the same nominal capacity as A.

But C cannot create the same value because the network prevents all of its output from reaching demand.

Now we ask a slightly unusual question.

What is the marginal contribution of each generator as generators progressively join the system?

Take one possible ordering:

A arrives first and increases served demand from 0 to 60 MW.

Its contribution is therefore:

B arrives next and increases served demand from 60 to 100 MW:

C arrives last. Demand is already completely served, so:

But that ordering is arbitrary.

Suppose instead the generators arrive:

C initially contributes:

A then increases served demand from 30 MW to 90 MW:

B finally takes it from 90 MW to 100 MW:

The Shapley value considers all possible orders in which generators could join the coalition and calculates each generator's average marginal contribution.

For this example, the resulting Shapley values are approximately:

They sum to the total value:

So if our capacity pot were £100 million, we could allocate it proportionally:

That is the property I wanted.

We are not simply paying generators according to their installed MW.

We are asking:

How much additional useful electricity-system capability does this asset create, given everything else that already exists?

Redundancy matters.

Location matters.

Network constraints matter.

The availability of other generators matters.

Ultimately, what matters is marginal contribution to the system as a whole.

That is precisely the sort of investment signal I want a market to produce.

There is, however, a rather enormous problem

Shapley values are beautiful mathematically.

Computationally, they are horrible.

With (n) generators there are:

possible coalitions.

For three generators, that's only:

Easy.

For 10:

Still manageable.

For 20:

Now things are getting interesting.

At 50 generators:

And at 1,000 generators you are somewhere around:

possible coalitions.

In my case, evaluating a coalition is not just a cheap arithmetic operation either.

Every coalition requires solving the network-constrained characteristic function.

So a full Shapley calculation for a realistically sized electricity system rapidly becomes physically impossible to compute.

This isn't a minor implementation detail.

It determines whether Shapley values are something interesting to write about in a paper or something you could actually use in an electricity market.

And I am rather obsessed with the latter.

So how do people normally get around this?

There is already a substantial literature on making Shapley calculations tractable.

A common family of approaches is essentially sampling.

Instead of evaluating every possible coalition, evaluate some subset of them and use those observations to estimate the Shapley values.

Monte Carlo methods, stratified sampling and related techniques can dramatically reduce the computational burden.

Those are perfectly sensible approaches.

But I became interested in a different question.

The electricity network isn't an arbitrary collection of independent players.

It has physical structure.

Generators are connected to buses.

Buses are connected through lines.

Lines form branches, corridors, regions and wider networks.

Some generators are electrically close together.

Some are electrically substitutable.

Others may be separated by major constraints.

So rather than randomly throwing away coalition evaluations, could I exploit the physical architecture of the thing I was actually modelling?

Then I came across Raquel Alonso-Pedrero's work

While researching this problem, I came across work by Raquel Alonso Pedrero, Pietro Pisciella and Pedro Crespo del Granado:

“Fair investment strategies in large energy communities: A scalable Shapley value approach.”

Their problem was different from mine.

They were looking at large energy communities and the problem of fairly allocating the benefits associated with shared energy investment — including the sort of problem you might encounter where an apartment block or energy community collectively invests in rooftop solar.

The important thing for me wasn't that their application was identical to mine.

It wasn't.

It was the structure of the solution.

Rather than treating a large population as one enormous flat cooperative game, their work showed how structure and hierarchical decomposition could make Shapley-inspired allocation scalable.

That got me thinking.

My electricity system already had a hierarchy.

In fact, the hierarchy was sitting there in the physical network.

So:

What if I grouped electrically similar generators together, calculated Shapley values between those groups, and then disaggregated the resulting value back down to the individual generators?

That became the hypothesis behind what I call Nested Shapley.

Let the electricity network reduce the problem

Suppose instead of having 1,000 independent generators, the physical structure of the network allows them to be represented by 25 meaningful generator clusters.

The combinatorial problem changes from:

to:

That is still a substantial computation.

But it has gone from literally impossible to something we can engineer around.

And the important point is that these aren't arbitrary statistical clusters.

I wanted the clustering to have a physical interpretation.

In my implementation, generators can be clustered according to three main conditions.

First, they should sit on the same main transmission corridor.

Second, they should be electrically close.

Third, there must be sufficient internal transmission capacity for the generators to be meaningfully substitutable without violating the network constraints.

So instead of asking Shapley to reason about every generator independently, we create electrically coherent meta-generators.

We calculate Shapley between those clusters.

Then we split each cluster's value back among its constituent generators.

In the formulation I tested, that final disaggregation is proportional to generator capacity.

Hence:

Nested Shapley.

But doesn't grouping generators destroy the answer?

This was the bit I didn't know beforehand.

It was a hypothesis.

My intuition was that generators which are physically close, connected through sufficiently unconstrained parts of the network and effectively substitutable from the wider system's perspective should be able to behave as a single player in the higher-level cooperative game.

But intuition isn't enough.

So I tested it.

I constructed a benchmark network containing 13 generators where it was still computationally possible to calculate the full generator-level Shapley value.

That gave me the ground truth.

I then ran Nested Shapley:

generators → physical clusters → cluster-level Shapley → proportional disaggregation back to generators

and compared the two.

The result was rather lovely.

Across all 13 generators, the Nested Shapley allocation exactly reproduced the full generator-level Shapley allocation to the numerical precision of the experiment:

for every generator.

For completeness, the allocations were:

In other words, on the benchmark system, I got the computational saving without any loss of allocation accuracy.

That result matters.

I wasn't merely making Shapley faster by accepting a noisier estimate.

I had found conditions under which the physical structure of the electricity network allowed me to compress the game without changing the allocation.

The underlying idea is that where generators within a cluster are sufficiently substitutable from the perspective of the wider network, the cluster can be treated as a single meta-player.

The cluster earns its Shapley value.

That value can then be disaggregated back to the individual generators.

The computational saving is enormous

The underlying reason is simple.

Full Shapley scales approximately with:

where (|G|) is the number of generators.

Nested Shapley instead moves the expensive part of the calculation to:

where (|C|) is the number of physically meaningful clusters, followed by a comparatively trivial linear disaggregation back to generators.

And normally:

That changes the nature of the idea.

Shapley stops being merely an elegant theoretical answer to:

"What would a fair allocation look like?"

and starts becoming a candidate answer to:

"How could we actually calculate this for an electricity system?"

And the real electricity system won't have 13 generators

This point is important to me.

A solution that works beautifully with 10, 20 or 50 generators but collapses when exposed to the real electricity system isn't actually a solution.

In this mechanism, I am specifically using the Shapley-based revenue stream for utility-scale generators.

I am not proposing that every solar panel, EV, heat pump, household battery or other behind-the-meter asset should receive this form of capacity revenue.

Those assets generally have another primary purpose: heating a home, providing mobility, lowering a household's electricity bill, operating a business or industrial process, and so on.

They can still interact economically with the electricity system through the operational market and respond to AMM price signals.

But they are not the investment class this particular revenue mechanism is designed for.

This revenue stream is intended for utility-scale generation assets whose commercial purpose is to provide capability to the electricity system.

Even within that narrower scope, however, the number of players can easily become large enough for exact Shapley computation to become completely impractical.

A future power system may contain large numbers of wind farms, solar farms, batteries, nuclear units, gas generators, hydro resources and other utility-scale technologies distributed across the network.

So we still cannot respond by saying:

"The mathematics works perfectly, provided we don't have too many generators."

😂

This is perhaps where my engineering background makes me approach economic problems differently.

Physical and computational limitations are part of the problem definition.

Computation takes time.

Communications have latency.

Networks have constraints.

Measurements contain errors.

Processors have finite capability.

Algorithms have complexity.

A market mechanism intended to allocate real money across a real electricity system has to acknowledge those facts.

I believe solutions should work in practice, not merely at economic equilibrium on a whiteboard.

Neoclassical economics has entered the chat. 😂

What signal does this actually create for investors?

This brings us back to why I wanted Shapley values in the first place.

I don't want the electricity market to say:

"Build 500 MW and we'll pay you because you built 500 MW."

I want it to say:

"Build something useful and you can earn revenue in proportion to the value it creates for the system."

If another generator already provides exactly the same capability in exactly the same place, your marginal contribution may be small.

If the network cannot deliver your output to where it is required, your contribution may be smaller.

If you provide capacity in a constrained part of the network where demand otherwise cannot be served, your contribution may be large.

If the system desperately needs your capability during periods when others are unavailable, that should appear in your contribution.

That is much closer to what I mean by a market investment signal.

There is a pot of investment/capacity revenue available to utility-scale generators.

Generators compete for their share of it by being useful to the system.

Nobody is automatically entitled to recover their investment.

Capital is genuinely at risk.

That distinction is important.

I am not trying to devise another centrally administered mechanism in which somebody predicts which technologies should be built, decides how much money they should receive and then guarantees their returns through some long-term contract.

The market should reveal the value.

The investor should take the risk.

And the mechanism should reward the assets that turn out to provide the greatest contribution to the system.

Two signals, not one

This also illustrates a wider principle in the market architecture I have been developing.

I don't think we should expect a single electricity price to perform every economic function simultaneously.

There are two conceptually different questions.

The first is:

What is the marginal value of another unit of energy here, right now?

That is the job of my Automatic Market Maker.

The second is:

How valuable is the existence and availability of this utility-scale generation asset to the system over time?

That is the problem I am using Shapley values to address.

The AMM provides the operational signal.

Shapley provides the investment and non-fuel cost-recovery signal.

That separation matters enormously in a system increasingly dominated by technologies whose marginal fuel cost is zero or close to zero.

Instead of trying to make one marginal electricity price somehow recover fuel costs, fixed costs, investment costs, flexibility value, scarcity value, network value and political objectives simultaneously, we can design mechanisms for the actual economic functions we need them to perform.

The operational market determines the value of energy.

The investment mechanism determines how the fixed-cost revenue available to utility-scale generators is distributed according to system contribution.

Different problem.

Different signal.

Different mechanism.

A nice example of how research actually happens

I also like this piece of the PhD because it is a good example of how research actually develops.

I didn't sit down one morning and decide:

"Today I shall invent Nested Shapley."

I had a problem.

Shapley values gave me the allocation properties I wanted.

Then I discovered that the obvious implementation was computationally ridiculous.

So I looked at how other researchers had approached Shapley scalability.

That led me to Raquel Alonso-Pedrero and her co-authors' work.

Their problem wasn't my problem.

But there was an idea in their solution that made me look differently at mine.

I realised that the physical electricity network itself might provide the structure required to reduce the dimensionality of the cooperative game.

I formed a hypothesis.

I wrote the algorithm.

I tested it against the exact solution.

And, at least on the benchmark system, it worked without sacrificing allocation accuracy while dramatically reducing the computational problem.

That is now the Nested Shapley algorithm.

So a very big thank you to Raquel Alonso Pedrero for inspiring this particular line of thinking.

Her research gave me the conceptual nudge that eventually led me to ask:

Why approximate away the complexity randomly when the physics of the electricity network might tell us how to simplify the problem?

And I think that question reaches beyond Shapley values.

As electricity markets become increasingly digital and computational, we should stop treating the physical architecture of the system as an inconvenient constraint to be added to economic models afterwards.

The physics can help us design the market itself.