**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 x**_{j }?

**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**