Skip to search boxSkip to navigationSkip to main content

Network Pollution Games

  • Eleftherios Anastasiadis
    ,
  • Xiaotie Deng
    ,
  • Piotr Krysta(corresponding author)
    ,
  • Minming Li
    ,
  • Han Qiao
    ,
  • Jinshan Zhang
*Corresponding author for this work
Scholary Output:
Contribution to journal
Article
Research
Peer-review

Open access

Abstract

<p>The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, which can be thought of as the sources of pollution in the network. The edges between agents represent the effect of spread of pollution. The government who is the regulator, is responsible for the maximization of the social welfare and sets bounds on the levels of emitted pollution in both local areas as well as globally in the whole network. We first prove that the above optimization problem is NP-hard even on some special cases of graphs such as trees. We then turn our attention on the classes of trees and planar graphs which model realistic scenarios of the emitted pollution in water and air, respectively. We derive approximation algorithms for these two kinds of networks and provide deterministic truthful and truthful in expectation mechanisms. In some settings of the problem that we study, we achieve the best possible approximation results under standard complexity theoretic assumptions. Our approximation algorithm on planar graphs is obtained by a novel decomposition technique 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. For trees we design a two level dynamic programming approach to obtain an FPTAS. This approach is crucial to deal with the global pollution quota constraint. It uses a special multiple choice, multi-dimensional knapsack problem where coefficients of all constraints except one are bounded by a polynomial of the input size. We furthermore derive truthful in expectation mechanisms on general networks with bounded degree.</p>

Publication Information

Output type

Scholary Output:
Contribution to journal
Article
Research
Peer-review

Original language

English (US)

Pages from-to (Number of pages)

Pages 124-166 (43 pages)

Journal (Volume, Issue Number)

Algorithmica (Volume 81, Issue 1)

Publication milestones

  • Published - 01/15/2019

Publication status

Published - 01/15/2019

ISSN

0178-4617

Publication IDs

  • Scopus: 85044788560

Publication metrics

Metrics

Scopus
citations
Fractional count
1
Fractional count
0.17
Fractional count
5
Fractional count
0.83
Fractional count
1
Fractional count
1

PlumX, opens in new tab

Captures
58
Citation count
7

Funding Details

Acknowledgements X. Deng was supported by the National Science Foundation of China (Grant No. 61173011) and a Project 985 grant of Shanghai Jiaotong University. P. Krysta and J. Zhang were supported by the Engineering and Physical Sciences Research Council under Grant EP/K01000X/1. M. Li was partly supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 117913). H. Qiao was supported by the National Science Foundation of China (Grant No. 71373262).
FundersFunding numbers
Research Grants Council of the Hong Kong Special Administrative Region, China
71373262
Department of Neurosurgery, Renji Hospital, Shanghai Jiaotong University
-
EPSRC
EP/K01000X/1
NSFC
61173011, 985