Network Design Games
Interacting selfish users
Facility Location
Problem Statement
What is known? algorithms
What is network design
I
Steiner Tree
What is network design
I
Steiner Tree
What is network design
II
Rent-on-Buy
(connected facility location)
What is network design
II
Rent-on-Buy
(connected
facility location)
What is known? algorithms
What is a game?
Cost-sharing vs. Nash?
How to evaluate a game?
Cost sharing Games
Cost Sharing
What is “fair cost” share?
Core: fair cost-sharing
Is there fair & budget
balanced cost-sharing?
Outline
What is known?
Core and linear programming
Linear Programming
Linear Programming
LP Duals Û
Cost-shares
Core and linear programming
»Approximation algorithm
Dealing with limited
individual utility: should all clients get connected?
How to deal with utilities?
How to deal with utilities?
Is core good enough?
Is core good enough?
From cost sharing game to
mechanism design
Stronger desirable property
From cost-sharing to
mechanism design
Are cost shares population
monotone ?
population monotone cost
shares?
More on monotone cost-shares
Monotone cost-shares from
any cost-shares?
Primal-Dual algorithm for
monotone cost-sharing
Cost-sharing problem for
facility location
Exact cost-sharing
Idea of Approximate
cost-sharing algorithm
Primal-Dual Algorithm (1)
Primal-Dual Algorithm (2)
Primal-Dual Algorithm (3)
Primal-Dual Algorithm (4)
Primal-Dual Algorithm:
Trouble
Primal-Dual Algorithm (5)
Primal-Dual Algorithm (6)
Are the cost-shares
monotone?
How to make monotone cost
shares
Monotone Primal-Dual
How good is cost-share xj ?
Feasibility + fairness ??
How much smaller is x £ α?
Approximate budget balance =
approximation quality
Approximate budget balance =
approximation quality
rent-or-buy network design
rent-or-buy cost-sharing
rent-or-buy cost-sharing
rent-or-buy cost-sharing
rent-or-buy cost-sharing
Rent-or-buy cost-sharing
competitive?
Conclusion