ProtocolDesign · Designing Optimal Protocols for Resource Allocation Games

Designing Optimal Protocols for Resource Allocation Games

The main goal of the project ''Protoco Design" was to design protocols for resource allocation problems, where independent decision makers interact. Primary application examples include traffic networks and telecommunication networks. The space of feasible protocols is characterized by normative properties such as (1) pure equilibrium existence of the strategic game induced by the protocol, (2) convergence towards equilibria by learning dynamics, (3) good efficiency properties of equilibria, (4) scalability and decentralization of the protocol and (5) their computational complexity. Within the project, the Workpackages (1-5) were to be accomplished. In Workpackage 1, the selection of application domains in terms of informational assumptions and practically relevant strategy spaces were to be developed. In Workpackage 2, the goal was to establish a link between resource allocation games on one side and mechanism design, social choice and implementation theory on the other side. In Workpackage 3, the goal was to obtain structural insights/characterizations of feasible protocols within the design spaces developed in WP 1. In Workpackage 4, the computational complexity of protocols was addressed and the goal was to devise polynomial time computable protocols with good welfare properties. Finally, in Workpackage 5, the goal was to empirically test the designed protocols on real-world instances. The project results cover virtually all project goals layed out in Workpackages (1-5). Regarding the work packages WP 1-4, I developed (together with P. von Falkenhausen) a new model for decentralized resource allocation that incorporates network design problems (used in the design of telecommunication networks) as well as facility location problems (WP 1). We completely characterized the space of pure Nash equilibria inducible by decentralized protocols. Based on this characterization, we developed protocols that lead to best possible (worst-case) welfare properties of the equilibria induced (WP 2-3). We also address for the first time the computational complexity of protocol design and show on the one hand log(n) hardness of computing the best protocol (n is the number of players) as well as an algorithm computing a protocol having matching performance guarantee of log(n) (WP 4). Closely related to WP 3 and WP 4, together with Britta Peis, I developed a decentralized protocol to share resources and for this protocol we completely characterized equilibrium existence and also devised a polynomial time algorithm to compute equilibria for a large class of resource sharing games. With Max Klimm and Britta Peis, we characterized equilibrium existence for the important class of integral splittable congestion games using the fair cost sharing protocol. For work package 5, we empirically evaluated the toll mechanism on general networks. For this we implemented several toll mechanisms and evaluated them on realistic networks. We obtained very good results showing that already for a few number of tolerable edges, the price of anarchy drops dramatically. The results in WP 5 may have an impact for traffic planers in order to reduce traffic congestion in cities. Our results give traffic planers some mathematical tools to compute the right tolls for parts of the street network, thus, there is a potential effect on society with regard to reducing congestion.

Data: CORDIS, © European Union