COST SHARING AND APPROXIMATION

Central to this thesis are problems in which a group of users can benet from building and jointly using some kind of infrastructure, be it a set of supply depots, service stations, or a communication or transportation network. We study two important questions related to these kinds of scenarios: (1) how to build the shared facility that satises the needs of a given set of users in a cost-eective way, and (2) how to split the cost of the shared facility among the participating users in a fair and reasonable way. In the rst part of the thesis, we seek to design cost sharing functions with desirable game-theoretic properties. We are looking for cost sharing functions that are fair, and encourage cooperation among users. This is captured in the notion of cross-monotonicity: it says that a cost share of any user should never increase as more people join the system, and never decrease when players leave. Towards this end, we develop a new technique to generate such cross-monotonic cost shares using a primal-dual type process, and use it to design cross-monotonic cost shares for several NP-hard optimization problems