{'fraction_non_alphanumeric': 0.02118893466745144, 'fraction_numerical': 0.0005885815185403178, 'mean_word_length': 5.4638783269961975, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
1 Influencing Selfish Behavior in Congestion Games with Unknown Price-Sensitive Users

This paper focuses on the derivation of taxation mechanisms for improving system-level behavior in congestion games with unknown price-sensitive users. Here, a taxation mechanism represents a general rule for assigning local taxation functions to edges in a given network, e.g., Pigovian taxes or marginal-cost taxes. Recent results have identified taxation mechanisms that lead to optimal system-level behavior for the considered class of games; however, these mechanisms require that a system-designer has a complete characterization of network structure and the users’ sensitivities. Furthermore, the robustness of these mechanisms to mis-characterization in this information is unknown. With these issues in mind, this paper focuses on the derivation of robust taxation mechanisms – that is, taxation mechanisms that provide strong efficiency guarantees irrespective of the underlying network or user characteristics. With this goal in mind, we define a scaled marginal-cost taxation mechanism in which the edge taxation functions are derived without explicit knowledge of the network structure or the users’ sensitivities. We then derive the optimal scaled marginal-cost taxation mechanism that limits worst-case inefficiencies over these uncertainties for the class of parallel-network congestion games with affine latency functions. In other words, we derive the scaled marginal-cost taxation mechanism that optimizes the price of anarchy. Note that viewing the price of anarchy as a design objective represents a significant departure from most of the price of anarchy results in the existing literature.