Network-Dependent Allocation: A Computational Economics Framework for AI-Mediated Selection Systems
Allocation Beyond Ranking: Non-Separable Valuations in AI-Mediated Selection
Working Paper Notice
This is a working paper and has not been peer-reviewed. The theoretical framework is presented for research discussion and should not be cited as peer-reviewed research. The findings and propositions are subject to revision based on feedback and further analysis.
Status: Draft — Not for Citation in Peer-Reviewed Contexts
Downloads & Citation
How to Cite This Paper
HomeSelf Research. (2026). Network-Dependent Allocation: A Computational Economics Framework for AI-Mediated Selection Systems. HomeSelf Research Initiative, Working Paper NDA-2026-001.
Available formats: APA | MLA | Chicago | Harvard | BibTeX
Abstract
This working paper presents a computational economics framework for analyzing allocation problems in AI-mediated selection systems where valuations are network-dependent. The core problem addresses systems where the value of selecting an artifact depends on which other artifacts are selected simultaneously, violating the independence assumption underlying traditional ranking-based selection.
The framework introduces the Network-Dependent Allocation (NDA) problem: selecting a subset R of artifacts with cardinality constraint K that maximizes a non-separable valuation function V(R).
We establish three core propositions: (1) No ranking function can produce optimal allocations for all capacity constraints under non-separable valuations; (2) NDA generalizes several NP-hard allocation problems; (3) For monotone submodular valuations, the greedy algorithm achieves (1 - 1/e) approximation.
The paper concludes by identifying protocol infrastructure requirements for systems that must reason about network-dependent valuations, emphasizing that representation protocols must encode network structure rather than isolated artifact scores.
Keywords
JEL Classification
Journal of Economic Literature (JEL) classification codes for this working paper:
Core Allocation Problem
Where R is a subset of artifacts, K is capacity constraint, and V may be non-separable
Introduction
The Shift to AI-Mediated Selection
Traditional information discovery systems rely on ranking: artifacts are ordered by independent scores, and users consume the top results. This model assumes that the value of including an artifact in a selection set depends only on that artifact's intrinsic properties.
AI-mediated selection systems fundamentally change this assumption. When AI systems reason over representations to construct selections, the value of including an artifact may depend on:
- Complementarities: What other artifacts provide complementary information
- Substitutabilities: What artifacts serve as alternatives
- Network effects: How the artifact interacts with the overall selection structure
- Reasoning coherence: How well the selection forms a coherent narrative
Theoretical Framework
Problem Formulation
The Network-Dependent Allocation (NDA) problem is defined as selecting a subset R of artifacts with cardinality constraint K that maximizes a potentially non-separable valuation function V(R).
Non-Separable Valuations
A valuation function V is separable if it can be decomposed into independent artifact values. When this condition fails, the valuation is non-separable, and ranking-based selection cannot preserve optimal allocations.
Core Propositions
Proposition 1: Ranking Incompleteness
For any non-separable valuation V, no ranking function exists that produces optimal allocations for all capacity constraints K.
Proof sketch: Assume such a ranking exists. Consider two capacity constraints K₁ ≠ K₂. Since V is non-separable, optimal selections cannot both correspond to the same top-K rankings. Contradiction.
Proposition 2: NP-Hardness
NDA generalizes several known NP-hard problems: Maximum Coverage, Maximum Weight Independent Set, and Budgeted Maximum Coverage are all special cases of NDA.
Reduction proofs show these problems are special cases of NDA, establishing NP-hardness.
Proposition 3: Approximation Bounds
For monotone submodular valuations, the greedy algorithm achieves a (1 - 1/e) approximation. For general valuations, no constant-factor approximation exists unless P=NP.
Computational Implications
Exact Computation
For small problem sizes (|U| ≤ 20), exhaustive search or branch-and-bound can find optimal allocations. For larger instances, exact computation becomes intractable.
Approximation Algorithms
- Greedy Algorithm: Iteratively add the artifact with highest marginal value. Achieves (1 - 1/e) for submodular V.
- Local Search: Start with an initial selection and iteratively improve by swaps.
- Linear Programming Relaxation: Solve continuous relaxation, then round.
Scope of the Framework
This framework applies to:
- • Selection systems where AI agents reason over representations to construct selections
- • Allocation problems with capacity constraints (K is binding)
- • Systems where valuation V(R) may depend on selection structure, not just individual artifact scores
- • Problems where ranking-based selection is observed to produce suboptimal outcomes
Applicability conditions:
- • The selection set R is constructed under a cardinality constraint |R| ≤ K
- • Valuations may be non-separable: V(R) ≠ Σ V({r}) for r ∈ R
- • Representations exist that encode network structure or complementarity information
What This Paper Does NOT Claim
To prevent misinterpretation, this working paper explicitly does NOT claim:
- ✗Universal economics theory: This framework is specific to AI-mediated selection systems with network-dependent valuations. It does not claim to generalize to all economic allocation problems.
- ✗AGI theory: This paper is not about artificial general intelligence, AI consciousness, or long-term AI safety. It focuses on allocation problems in contemporary selection systems.
- ✗Replacement for classical economics: NDA complements, rather than replaces, existing economic theories of allocation, mechanism design, and welfare economics.
- ✗Proof of all AI behavior: The propositions apply under stated assumptions. Real-world AI systems may violate these assumptions or exhibit behaviors outside the framework.
- ✗Dependence on VPR validity: The theoretical framework does NOT depend on Verified Property Records (VPR) adoption. VPR is mentioned only as an illustrative example of structured representation that could support NDA computation. The framework exists independently of any specific implementation.
References
Version History
- • Initial working paper publication
- • Core theoretical framework established
- • Propositions 1-3 formalized
- • SSRN/Google Scholar metadata included