  This paper focuses on two commonly used path assignment policies for agents
traversing a congested network: self-interested routing, and system-optimum
routing. In the self-interested routing policy each agent selects a path that
optimizes its own utility, while the system-optimum routing agents are assigned
paths with the goal of maximizing system performance. This paper considers a
scenario where a centralized network manager wishes to optimize utilities over
all agents, i.e., implement a system-optimum routing policy. In many real-life
scenarios, however, the system manager is unable to influence the route
assignment of all agents due to limited influence on route choice decisions.
Motivated by such scenarios, a computationally tractable method is presented
that computes the minimal amount of agents that the system manager needs to
influence (compliant agents) in order to achieve system optimal performance.
Moreover, this methodology can also determine whether a given set of compliant
agents is sufficient to achieve system optimum and compute the optimal route
assignment for the compliant agents to do so. Experimental results are
presented showing that in several large-scale, realistic traffic networks
optimal flow can be achieved with as low as 13% of the agent being compliant
and up to 54%.
