# zbMATH — the first resource for mathematics

Network pollution games. (English) Zbl 1417.91390
Summary: 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.
##### MSC:
 91B76 Environmental economics (natural resource models, harvesting, pollution, etc.) 91A43 Games involving graphs 68Q25 Analysis of algorithms and problem complexity 68W25 Approximation algorithms
Knapsack
Full Text:
##### References:
 [1] Air quality in Europe - 2014 Report. European Environment Agency Report No. 5/2014. http://www.eea.europa.eu/publications/air-quality-in-europe-2014. Accessed 5 Oct 2015 [2] EU Emissions Auctions. https://www.theice.com/publicdocs/How_the_Auctions_Operate.pdf. Accessed 5 Oct 2015 [3] Emissions Auctions. https://www.theice.com/emissions/auctions (2014). Accessed 5 Oct 2015 [4] State of the Air 2014 Report. American Lung Association, 30 April, 2014. http://www.stateoftheair.org/2014/key-findings/. Accessed 5 Oct 2015 [5] Anastasiadis, E., Deng, X., Krysta, P., Li, M., Qiao, H., Zhang, J.: Network pollution games. In: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 23-31. International Foundation for Autonomous Agents and Multiagent Systems (2016) · Zbl 06622018 [6] Anastasiadis, E., Deng, X., Krysta, P., Li, M., Qiao, H., Zhang, J.: New results for network pollution games. In: Computing and Combinatorics: 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings, vol. 9797, p. 39. Springer (2016) · Zbl 06622018 [7] Appel, K.I., Haken, W.: Every planar map is four colorable, vol. 98. American mathematical society Providence, RI (1989) · Zbl 0681.05027 [8] Baker, BS, Approximation algorithms for np-complete problems on planar graphs, J. ACM (JACM), 41, 153-180, (1994) · Zbl 0807.68067 [9] Banister, D., The sustainable mobility paradigm, Transp. Policy, 15, 73-80, (2008) [10] Bansal, N.; Korula, N.; Nagarajan, V.; Srinivasan, A., Solving packing integer programs via randomized rounding with alterations, Theory Comput., 8, 533-565, (2012) · Zbl 1297.68259 [11] Belitskaya, AV, Network game of pollution cost reduction, Contrib. Game Theory Manag., 6, 24-34, (2013) [12] Caprara, A.; Kellerer, H.; Pferschy, U.; Pisinger, D., Approximation algorithms for knapsack problems with cardinality constraints, Eur. J. Oper. Res., 123, 333-345, (2000) · Zbl 0961.90131 [13] Chau, C.-K., Elbassioni, K., Khonji, M.: Truthful mechanisms for combinatorial ac electric power allocation. In: Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems, pp. 1005-1012. International Foundation for Autonomous Agents and Multiagent Systems (2014) [14] Conrad, K.; Wang, J., On the design of incentive mechanisms in environmental policy, Environ. Resour. Econ., 3, 245-262, (1993) [15] Dasgupta, P.; Hammond, P.; Maskin, E., On imperfect information and optimal pollution control, Rev. Econ. Stud., 47, 857-860, (1980) · Zbl 0459.90012 [16] Dasgupta, Sanjoy: Christos H Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill Inc., (2006) [17] Dobzinski, S., Nisan, N.: Mechanisms for multi-unit auctions. In: Proc. of the 8th ACM conference on Electronic commerce, pages 346-351. ACM, (2007) · Zbl 1188.91079 [18] Dong, B.; Ni, D.; Wang, Y., Sharing a polluted river network, Environ. Resource Econ., 53, 367-387, (2012) [19] Dorner, S.; Shi, J.; Swayne, D., Multi-objective modelling and decision support using a bayesian network approximation to a non-point source pollution model, Environ. Model. Softw., 22, 211-222, (2007) [20] Dughmi, S.; Roughgarden, T., Black-box randomized reductions in algorithmic mechanism design, SIAM J. Comput., 43, 312-336, (2014) · Zbl 1301.68158 [21] Farrell, J., Information and the coase theorem, The J. Econ. Perspect., 1, 113-129, (1987) [22] Fullerton, D.; West, SE, Can taxes on cars and on gasoline mimic an unavailable tax on emissions?, J. Environ. Econ. Manag., 43, 135-157, (2002) · Zbl 1008.91093 [23] Garey, MR; Johnson, DS, The rectilinear steiner tree problem is np-complete, SIAM J. Appl. Math., 32, 826-834, (1977) · Zbl 0396.05009 [24] Gianessi, LP; Peskin, HM; Young, GK, Analysis of national water pollution control policies: 1. A national network model, Water Resour. Res., 17, 796-802, (1981) [25] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1981) · Zbl 0492.90056 [26] Hurwicz, L., The design of mechanisms for resource allocation, Am. Econ. Rev., 63, 1-30, (1973) [27] Innes, R., Regulating automobile pollution under certainty, competition, and imperfect information, J. Environ. Econ. Manag., 31, 219-239, (1996) · Zbl 0908.90074 [28] Karp, L.; Livernois, J., Using automatic tax changes to control pollution emissions, J. Environ. Econ. Manag., 27, 38-48, (1994) · Zbl 0854.90037 [29] Katsikarelis, I.: Computing bounded-width tree and branch decompositions of k-outerplanar graphs. arXiv preprintarXiv:1301.5896 (2013) [30] Khanna, S., Motwani, R.: Towards a syntactic characterization of ptas. In: Proceedings of the 28th STOC, pp. 329-337. ACM (1996) · Zbl 0922.68058 [31] Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 767-775. ACM (2002) · Zbl 1192.68367 [32] Khot, S.; Regev, O., Vertex cover might be hard to approximate to within 2- $$\varepsilon$$, J. Comput. Syst. Sci., 74, 335-349, (2008) · Zbl 1133.68061 [33] Kim, J-C; Chang, K-B, An optimal tax/subsidy for output and pollution control under asymmetric information in oligopoly markets, J. Regul. Econ., 5, 183-197, (1993) [34] Kloks, T.: Treewidth: Computations and Approximations, vol. 842. Springer, New York (1994) · Zbl 0825.68144 [35] Krysta, P.; Telelis, O.; Ventre, C., Mechanisms for multi-unit combinatorial auctions with a few distinct goods, J. Artif. Intell. Res., 53, 721-744, (2015) · Zbl 1325.91026 [36] Kulik, A., Shachnai, H.: On lagrangian relaxation and subset selection problems. In: International Workshop on Approximation and Online Algorithms, pp. 160-173. Springer, New York (2008) · Zbl 1209.68647 [37] Kulik, A.; Shachnai, H., There is no EPTAS for two-dimensional knapsack, Inf. Process. Lett., 110, 707-710, (2010) · Zbl 1234.68153 [38] Kwerel, E.: To tell the truth: Imperfect information and optimal pollution control. The Review of Economic Studies, pp. 595-601 (1977) · Zbl 0376.90039 [39] Lavi, R.; Swamy, C., Truthful and near-optimal mechanism design via linear programming, J. ACM (JACM), 58, 25, (2011) · Zbl 1281.91091 [40] McKitrick, R., A cournot mechanism for pollution control under asymmetric information, Environ. Resour. Econ., 14, 353-363, (1999) [41] Montgomery, DW, Markets in licenses and efficient pollution control programs, J. Econ. Theory, 5, 395-418, (1972) [42] Ni, D.; Wang, Y., Sharing a polluted river, Games Econ. Behav., 60, 176-186, (2007) · Zbl 1155.91449 [43] Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory, vol. 1. Cambridge University Press, Cambridge (2007) · Zbl 1130.91005 [44] Petrosjan, L.; Zaccour, G., Time-consistent shapley value allocation of pollution cost reduction, J. Econ. Dyn. Control, 27, 381-398, (2003) · Zbl 1027.91005 [45] Pritchard, D.; Chakrabarty, D., Approximability of sparse integer programs, Algorithmica, 61, 75-93, (2011) · Zbl 1218.68198 [46] Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R., A new proof of the four-colour theorem, Electron. Res. Announc. Am. Math. Soc., 2, 17-25, (1996) · Zbl 0865.05039 [47] Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216-226. ACM (1978) · Zbl 1282.68143 [48] Segerson, K., Uncertainty and incentives for nonpoint pollution control, J. Environ. Econ. Manag., 15, 87-98, (1988) [49] Singh, RM; Datta, B., Artificial neural network modeling for identification of unknown pollution sources in groundwater with partially missing concentration observation data, Water Resour. Manag., 21, 557-572, (2007) [50] Spulber, DF, Optimal environmental regulation under asymmetric information, J. Public Econ., 35, 163-181, (1988) [51] Stavins, R.N.: Policy instruments for climate change: how can national governments address a global problem. U. Chi. Legal F., p. 293 (1997) [52] Stavins, RN, Experience with market-based environmental policy instruments, Handb. Environ. Econ., 1, 355-435, (2003) [53] Talberg, A., Swoboda, K.: Emissions trading schemes around the world. Parliament of Australia, Viewed (2013) [54] Trujillo-Ventura, A.; Ellis, JH, Multiobjective air pollution monitoring network design, Atmos. Environ. A Gen. Top., 25, 469-479, (1991) [55] Vazirani, V.V.: Approximation Algorithms. Springer, New York (2013) [56] Viana, M.P., Strano, E., Bordin, P., Barthelemy, M.: The simplicity of planar networks. Scientific reports, 3, Article number 3495 (2013) [57] Vörösmarty, CJ; McIntyre, PB; Gessner, MO; Dudgeon, D.; Prusevich, A.; Green, P.; Glidden, S.; Bunn, SE; Sullivan, CA; Reidy Liermann, C.; etal., Global threats to human water security and river biodiversity, Nature, 467, 555-561, (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.