📈 economics

When Frictions Disappear: Computational Accessibility and Decentralized Adjustment

This paper demonstrates that in decentralized economic systems with discrete actions and shared constraints, the computational difficulty of identifying welfare-maximizing equilibria—even when they exist and are easily verifiable—creates a gap between equilibrium existence and accessibility, leading to path-dependent outcomes and suboptimal welfare despite rapid convergence.

Original authors: Stephen Lewarne, Anton Kamenov

Published 2026-07-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Stephen Lewarne, Anton Kamenov

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Just Because a Solution Exists Doesn't Mean You Can Find It

Imagine you are in a massive, dark warehouse filled with millions of boxes. Somewhere in this warehouse, there is a "Golden Box" that contains a treasure worth a million dollars. You know the Golden Box exists. You also know that if someone handed it to you, you could easily verify it's the real thing.

However, the warehouse is so huge and the boxes are arranged in such a complex way that finding the Golden Box by walking around and checking one box at a time is practically impossible. You might find a "Silver Box" that is still very valuable, but you'll never stumble upon the Golden one because the path to it is blocked by the way the other boxes are arranged.

This paper argues that our modern economy is like that warehouse. Even if we remove all the traditional "frictions" (like slow internet, bad information, or expensive shipping costs), we might still fail to find the best possible economic outcome. Not because we are stupid or uninformed, but because the problem of finding the best solution is mathematically too hard for a decentralized system to solve.

The Core Problem: The "Combinatorial" Maze

The authors focus on situations where many different people (firms, drivers, power plants) need to make choices, but those choices depend on shared, limited resources (like truck routes, electricity grid space, or factory slots).

The Old View: Economists used to think that if we just removed the obstacles (frictions), the market would naturally find the best outcome.
The New View: The authors say that even with perfect information and no obstacles, the sheer number of possible combinations is too vast. It's like trying to solve a puzzle where every piece you place changes which other pieces fit.

The Analogy: The Dinner Party Seating Chart

Imagine you are hosting a dinner party for 50 people. You have 50 seats, but some guests hate sitting next to each other, some need to be near the kitchen, and some need to be near the window.

The Ideal Scenario: There is one perfect seating arrangement where everyone is happy.
The Reality: You don't have a supercomputer to calculate the perfect arrangement instantly. Instead, you ask guests to move one by one.
- Guest A says, "I'll move to the window."
- Guest B says, "Okay, I'll move to the kitchen."
- Guest C says, "I can't sit there anymore, I have to move to the back."

Each person makes a small, logical move to make their life better right now. They are acting rationally. They have all the information. But because they are only looking at their immediate neighborhood, they might get stuck in a "good enough" arrangement where everyone is happy, but it's not the perfect arrangement.

The paper calls this Local Optimization vs. Global Optimization.

Local: "I am moving to a better seat right now."
Global: "This is the best possible arrangement for the whole party."

The problem is that the system can get "stuck" in a good arrangement and never find the perfect one, simply because no single person has the power or the view to see the whole picture.

Key Findings in Simple Terms

1. Convergence is Fast, but Efficiency is Low
The paper ran computer simulations where 50 companies tried to find the best way to use 100 resources.

Result: The companies found a stable solution very quickly (in just a few rounds of changes).
The Catch: The solution they found was only about 75% as good as the theoretical best solution. In some cases, it was less than 50% as good.
Takeaway: Just because the market settles down quickly doesn't mean it settled on the best outcome.

2. The "Path Dependence" Trap
Who moves first matters.

If Company A grabs the best resource first, the system settles into a "good" outcome.
If Company B grabs it first, the system settles into a "better" outcome.
Once the first company grabs the resource, the second company can't take it back, even if it would make the whole economy richer. The system is "locked in" to a path.

3. Policy Still Matters (Even Without Frictions)
Usually, we think government policy is only needed to fix "frictions" like traffic jams or lack of information.

The Paper's Twist: Even if there are no traffic jams and everyone knows everything, the government can still help.
How? By acting as a "traffic cop" for the starting line. A temporary policy (like a short-term subsidy or a priority rule) can change who moves first. This nudges the system onto a different path, leading to a much better final outcome.
Crucial Point: The policy doesn't need to solve the whole puzzle. It just needs to steer the decentralized system onto the right "track" so it doesn't get stuck in a bad spot.

Why This Matters for the Future

We often hear that Artificial Intelligence and the internet will solve all our economic problems by making information perfect and coordination easy.

This paper warns us: That might not be true.
Even with super-fast computers and perfect data, the problem of arranging millions of interacting parts (like supply chains or energy grids) is mathematically "NP-hard" (a fancy way of saying "impossible to solve perfectly in a reasonable time").

As we get better at technology, the "frictions" of communication will disappear, but the "friction" of complexity will remain. We might have a system that is incredibly fast and rational, yet still fails to find the best possible outcome because the map is too big to navigate.

Summary

The Myth: If we remove all obstacles, the market will automatically find the best solution.
The Reality: The map of possibilities is too complex. Rational people making small, local improvements can get stuck in a "good" solution that isn't the "best" one.
The Lesson: We need to pay attention not just to what the best solution is, but how we get there. Sometimes, a little bit of government guidance (to change the starting path) is necessary to help the market find the treasure, even when everyone is smart and informed.

Technical Summary: When Frictions Disappear: Computational Accessibility and Decentralized Adjustment

Problem Statement
Traditional economic policy analysis often relies on the presence of frictions—such as asymmetric information, transaction costs, or sticky prices—to explain market failures and justify intervention. The prevailing intuition suggests that as technology reduces these frictions (e.g., via AI, digital platforms, and improved search), decentralized systems will naturally converge to efficient equilibria.

This paper challenges that intuition by identifying a structural constraint that persists even in the absence of traditional frictions: combinatorial feasibility. The authors argue that in many modern economic environments (supply chains, infrastructure allocation, procurement), the difficulty is not a lack of information or coordination costs, but the sheer number of feasible configurations. A welfare-relevant allocation may exist, be easy to verify once proposed, and be stable, yet remain computationally inaccessible to decentralized agents who rely on local adjustment processes. The core problem is the divergence between equilibrium existence and operational accessibility.

Methodology
The paper employs a formal theoretical model and computational simulations to isolate the effects of feasibility constraints on decentralized adjustment.

Theoretical Model:
- Environment: A combinatorial allocation economy with $N$ firms and $R$ resources. Each firm chooses one discrete action from a finite set, where each action consumes a specific vector of resources.
- Constraints: Feasibility is determined by shared resource capacities. An allocation is feasible only if aggregate resource use does not exceed capacity.
- Dynamics: The paper analyzes a sequential best-response process. Firms update their actions one at a time, choosing the highest-payoff action that remains feasible given the current actions of others. This process is computationally trivial for individual agents (local optimization).
- Equilibrium Concept: The process converges to a "pure feasible equilibrium" (an absorbing state where no firm can profitably switch to another feasible action).
Computational Complexity Analysis:
- The paper formalizes the distinction between local improvement (finding a better feasible action) and global equilibrium selection (identifying the welfare-maximizing equilibrium among all feasible equilibria).
- It utilizes a reduction from the 3-SET PACKING problem (Garey and Johnson, 1979) to demonstrate that determining whether a welfare-relevant equilibrium exists is NP-hard.
- This establishes that while verifying a candidate equilibrium is efficient (polynomial time), identifying a welfare-superior equilibrium from the set of all feasible equilibria is computationally intractable in the general case.
Simulations:
- The authors simulate an economy with 50 firms and 100 resources, where firms have multiple sourcing plans.
- They compare the terminal welfare of decentralized sequential best-response dynamics against a "benchmark" allocation generated via randomized global search (approximating the welfare maximum).
- The simulations vary resource density to test the sensitivity of accessibility to constraint tightness.

Key Results

Convergence vs. Efficiency: The decentralized adjustment process converges rapidly (often in fewer than 3 update sweeps) to a stable absorbing state. However, this convergence does not guarantee efficiency. In the simulations, decentralized adjustment achieved only 75.6% of the benchmark welfare on average, with some runs achieving less than 50%.
Computational-Dynamic Gap: There is a fundamental gap between the ability of agents to optimize locally and the system's ability to reach a global optimum. Local improvement is computationally easy; global welfare selection is NP-hard.
Path Dependence: Because the process is sensitive to the order of updates and initial conditions, different adjustment paths lead to different absorbing equilibria. A welfare-superior equilibrium may exist but remain unreachable if the system enters a "basin of attraction" for a lower-welfare equilibrium.
Policy Persistence Without Frictions: The paper demonstrates that temporary policy interventions (e.g., a short-term subsidy) can permanently alter the final allocation. By changing the order in which resources are claimed during the intervention, the policy can steer the system toward a specific absorbing state that persists even after the policy is removed and the environment returns to baseline. This occurs not because of adjustment costs, but because the intervention alters the feasible set for subsequent agents.

Key Contributions

Conceptual Distinction: The paper introduces computational accessibility as a distinct determinant of economic outcomes, separating it from equilibrium existence and efficiency. It argues that an allocation's practical relevance depends on whether decentralized systems can reliably discover it.
Reframing Market Failure: It identifies a new source of inefficiency that does not rely on information asymmetry, bounded rationality, or transaction costs. Instead, inefficiency arises from the interaction between discrete choices and shared feasibility constraints in combinatorial environments.
Policy Implications: It suggests that policy remains relevant even in frictionless environments. The role of policy shifts from "correcting distortions" to path selection—influencing the trajectory of decentralized adjustment to guide the system toward more desirable absorbing states.

Significance and Claims
The paper claims that as traditional frictions (search costs, information gaps) diminish due to technological progress, the combinatorial structure of allocation problems may become the primary constraint on efficiency.

Existence is Insufficient: The mere existence of a welfare-maximizing equilibrium is not a sufficient condition for its realization. If the equilibrium is computationally inaccessible, the economy will settle on a locally stable but globally suboptimal outcome.
Limits of Decentralization: Even with fully rational, informed agents and zero adjustment costs, decentralized systems cannot be guaranteed to identify welfare-relevant equilibria in combinatorial settings.
The Role of Adjustment Dynamics: Economic analysis must shift focus from static equilibrium conditions to the dynamics of adjustment. The process by which feasible allocations are constructed becomes as important as the allocations themselves.
Modest Claim on Government Capability: The authors explicitly state they do not claim governments can solve these NP-hard problems better than markets. Governments face the same computational limits. The argument is that because no agent (centralized or decentralized) can reliably solve the global problem, the path taken to reach an equilibrium becomes the critical economic variable, making policy interventions that influence this path potentially effective.

In summary, the paper argues that in a world of abundant information and low friction, the "friction" that remains is the computational difficulty of navigating a vast space of interdependent feasible options, leading to persistent inefficiencies and path dependence that traditional equilibrium analysis fails to predict.