Network pollution games



Anastasiadis, E, Deng, X, Krysta, P, Li, M, Qiao, H and Zhang, J
(2016) Network pollution games. In: 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), 2016-5-9 - 2016-5-13.

[img] Text
PollutionGames.pdf - Author Accepted Manuscript

Download (349kB)

Abstract

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.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 21 Jun 2016 08:50
Last Modified: 19 Jan 2023 07:36
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3001464