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