Avoiding perverse incentives in affine congestion games

In engineered systems whose performance depends on user behavior, it is often desirable to influence behavior in an effort to achieve performance objectives. However, doing so naively can have unintended consequences; in the worst cases, a poorly-designed behavior-influencing mechanism can create a perverse incentive which encourages adverse user behavior. For example, in transportation networks, marginal-cost tolls have been studied as a means to incentivize low-congestion network routing, but have typically been analyzed under the assumption that all network users value their time equally. If this assumption is relaxed, marginal-cost tolls can create perverse incentives which increase network congestion above un-tolled levels. In this paper, we prove that if some network users are unresponsive to tolls, any taxation mechanism that does not depend on network structure can create perverse incentives. Thus, to systematically avoid perverse incentives, a taxation mechanism must be network-aware to some extent. On the other hand, we show that a small amount of additional information can mitigate this negative result; for example, we show that it is relatively easy to avoid perverse incentives on affine-cost parallel-path networks, and we fully characterize the taxation mechanisms that minimize congestion for worst-case user populations on such networks.