# Investment vs. reward in a competitive knapsack problem

arXiv: https://arxiv.org/abs/2101.10964 · HTML: https://mlsanity.com/paper/2101.10964/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 11 references that are in the map.
- First posted on arXiv 26 Jan 2021.

## Builds on (most cited first, 3 of 3)

- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero](https://mlsanity.com/paper/1905.11623/) (2019)

## Built on by (most cited first, 2 of 2)

- [Scaling Laws for a Multi-Agent Reinforcement Learning Model](https://mlsanity.com/paper/2210.00849/) (2022)
- [AlphaZero Neural Scaling and Zipf's Law: a Tale of Board Games and Power Laws](https://mlsanity.com/paper/2412.11979/) (2024)

## Abstract (arXiv)

Natural selection drives species to develop brains, with sizes that increase with the complexity of the tasks to be tackled. Our goal is to investigate the balance between the metabolic costs of larger brains compared to the advantage they provide in solving general and combinatorial problems. Defining advantage as the performance relative to competitors, a two-player game based on the knapsack problem is used. Within this framework, two opponents compete over shared resources, with the goal of collecting more resources than the opponent. Neural nets of varying sizes are trained using a variant of the AlphaGo Zero algorithm. A surprisingly simple relation, NA/(NA+NB), is found for the relative win rate of a net with NA neurons against one with NB. Success increases linearly with investments in additional resources when the networks sizes are very different, i.e. when NA ll NB, with returns diminishing when both networks become comparable in size.