Cross-monotonic Cost-Sharing Methods for Network Design Games

Game Theory;Network Design;Cost-Sharing Methods;Combinatorics and Optimization

Wheatley, David

University of Waterloo

关键词: Game Theory;    Network Design;    Cost-Sharing Methods;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3317/1/thesis%20final%20copy.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In this thesis we consider some network design games that arise from commonnetwork design problems. A network design game involves multiple players whocontrol nodes in a network, each of which has a personal interest in seeing theirnodes connected in some manner. To this end, the players will submit bids toa mechanism whose task will be to select which of the players to connect, howto connect their nodes, and how much to charge each player for the connection.We rely on many fundamental results from mechanism design (from [8], [9] &[5]) in this thesis and focus our efforts on designing and analyzing cost-sharingmethods. That is, for a given set of players and their connection requirements,our algorithms compute a solution that satisfies all the players’ requirementsand calculates ’fair’ prices to charge each of them for the connection.Our cost-sharing methods use a primal-dual framework developed by Agrawal,Klein and Ravi in [1] and generalized by Goemans &Williamson in [3]. We modifythe algorithms by using the concept of death-time introduced by K¨onemann,Leonardi & Sch¨afer in [6].Our main result is a 2-budget balanced and cross-monotonic cost sharingmethod for the downwards monotone set cover game, which arises naturallyfrom any downwards monotone 0, 1-function. We have also designed a 2-budgetbalanced and cross-monotonic cost sharing method for two versions of the edgecover game arising from the edge cover problem. These games are special casesof the downwards monotone set cover game. By a result by Immorlica, Mahdian& Mirrokni in [4] our result is best possible for the edge cover game.We also designed a cross-monotonic cost sharing method for a network designgame we call the Even Parity Connection game arising from the T-Joinproblem that generalizes proper cut requirement functions. We can show ouralgorithm returns cost shares that recover at least half the cost of the solution.We conjecture that our cost sharing method for the even parity connection gameis competitive and thus 2-budget balance.