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.

Authors

• Eleftherios Anastasiadis London Southbank University
• Xiaotie Deng CFCS, School of Computer Science & CMAR, Institute for AI, Peking University
• Piotr Krysta
• Minming Li City University of Hong Kong
• Han Qiao University of Chinese Academy of Sciences
• Jinshan Zhang

Keywords

• Algorithmic mechanism design
• approximation algorithms
• planar graphs
• pollution control