In this thesis we consider some network design games that arise from common
network design problems. A network design game involves multiple players who
control nodes in a network, each of which has a personal interest in seeing their
nodes connected in some manner. To this end, the players will submit bids to
a mechanism whose task will be to select which of the players to connect, how
to 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-sharing
methods. That is, for a given set of players and their connection requirements,
our algorithms compute a solution that satisfies all the players’ requirements
and 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 modify
the 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 sharing
method for the downwards monotone set cover game, which arises naturally
from any downwards monotone 0, 1-function. We have also designed a 2-budget
balanced and cross-monotonic cost sharing method for two versions of the edge
cover game arising from the edge cover problem. These games are special cases
of 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 design
game we call the Even Parity Connection game arising from the T-Join
problem that generalizes proper cut requirement functions. We can show our
algorithm 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 game
is competitive and thus 2-budget balance.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/3317 |
| Date | January 2007 |
| Creators | Wheatley, David |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.002 seconds