TY - GEN
T1 - Network pollution games
AU - Anastasiadis, Eleftherios
AU - Deng, Xiaotie
AU - Krysta, Piotr
AU - Li, Minming
AU - Qiao, Han
AU - Zhang, Jinshan
N1 - Publisher Copyright:
Copyright © 2016, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Algorithmic mechanism design
KW - Approximation algorithms
KW - Planar graphs
KW - Pollution control
UR - https://www.scopus.com/pages/publications/85014183603
M3 - 会议稿件
AN - SCOPUS:85014183603
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 23
EP - 31
BT - AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016
Y2 - 9 May 2016 through 13 May 2016
ER -