Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: users of the network and owners (operators) of the network. Owners of the network post a price for usage of the link they own; users of the network select routes based on price and level of use by other users. One challenge in these games is that there are two levels of competition: one, among the owners to abstract users to their link so as to maximize profit; and second, among users of the network to select routes that are cheap yet not too congested. Interestingly, we observe that: (i) an equilibrium may not exist; (ii) it might not be unique; (iii) the network performance at equilibrium can be arbitrarily inefficient.<\/p>\n
Our main result is to observe that a slight regulation on the network owners market solves all three issues above. Especially, if the authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge then: the game among the link operators has a unique strong Nash equilibrium and the users\u2019 game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. We then ask, can we compute great tolls that minimize total users\u2019 payments? We show that this optimization problem reduces to a linear program in the case of single-commodity series-parallel networks. Starting from the same linear program, we obtain multiplicative approximation results for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a surprising bound, which only depends on the topology of the networkcase we obtain a surprising bound, which only depends on the topology of the network.<\/p>\n","protected":false},"excerpt":{"rendered":"
Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: users of the network and owners (operators) of the network. Owners of the network post a price for usage of the link they own; users of the network select routes based on price and level of use by other […]<\/p>\n","protected":false},"featured_media":393656,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"research-area":[13561,13548,13547],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-393599","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-research-area-algorithms","msr-research-area-economics","msr-research-area-systems-and-networking","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/t7kAXL10MDw","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/393599"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/393599\/revisions"}],"predecessor-version":[{"id":393614,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/393599\/revisions\/393614"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/393656"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=393599"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=393599"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=393599"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=393599"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=393599"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=393599"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=393599"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}