Network pollution games

We introduce a new network model of the pollution control problem and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, that could be thought of as sources of pollution, and edges between agents represent the effect of spread of pollution. The government as the regulator is responsible to maximize the social welfare while setting bounds on the levels of emitted pollution both locally and globally. Our model is inspired by the existing literature in environmental economics that applies game theoretical methodology to control pollution. We study the social welfare maximization problem in our model. Our main results include hardness results for the problem, and in complement, a constant approximation algorithm on planar graphs. Our approximation algorithm leads to a truthful in expectation mechanism, and it is obtained by a novel decomposition technique of planar graphs to deal with constraints on vertices. We note that no known planar decomposition techniques can be used here and our technique can be of independent interest.