Nonadditive Shortest Paths: Subproblems in Multi-Agent Competitive Network Models

A variety of different multi-agent (competitive) network models have been described in the literature. Computational techniques for solving such models often involve the iterative solution of shortest path subproblems. Unfortunately, the most theoretically interesting models involve nonlinear cost or utility functions and they give rise to nonadditive shortest path subproblems. This paper both describes some basic existence and uniqueness results for these subproblems and develops a heuristic for solving them.