On the Structural Limits of Ranking Under Non-Separable Valuation
A Theoretical Framework for Allocation Under Non-Separable Valuation
Publication
Archived on Zenodo
10.5281/zenodo.20680894
June 13, 2026
v1
Yes
Research Publication Notice
This is a research publication and has not been peer-reviewed. It is presented for research discussion and may be cited as a research publication. Findings are subject to revision.
Status: Research Publication — Version 1.0 — June 2026
Epistemic Status
Propositions 1-3 are formally stated and argued with proof sketches, but full formal proof validation is pending peer review.
NP-hardness claims reference established computational complexity classes (Maximum Coverage, Budgeted Maximum Coverage).
Governance implications (Layer 3) are speculative and require empirical validation.
Downloads & Citation
How to Cite This Paper
Patrone, M. (2026). On the Structural Limits of Ranking Under Non-Separable Valuation. Research Publication. Zenodo. https://doi.org/10.5281/zenodo.20680894
Available formats: APA | MLA | Chicago | Harvard | BibTeX
Abstract
This research publication presents a theoretical framework for analyzing allocation problems where valuations are non-separable. 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 distinguishing retrieval from allocation as formally distinct problem classes, with implications for the design of selection systems that must reason about network-dependent valuations.
Keywords
JEL Classification
Journal of Economic Literature (JEL) classification codes for this research publication:
Core Allocation Problem
Where R is a subset of artifacts, K is capacity constraint, and V may be non-separable
Introduction
Selection Under Non-Separable Valuation
Traditional selection 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.
When selection systems reason over structured 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
- Coherence: How well the selection forms a coherent set
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 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 research publication explicitly does NOT claim:
- ✗Universal economics theory: This framework is specific to 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 systems may violate these assumptions or exhibit behaviors outside the framework.
References
Version History
- • Initial research publication
- • Core theoretical framework established
- • Ranking sufficiency theorem formalized
- • Zenodo publication v1