001.docx DOI: 10.3303/CET2189078 Paper Received: 29 June 2021; Revised: 21 August 2021; Accepted: 24 November 2021 Please cite this article as: Tan R.R., Aviso K., Walmsley T., 2021, P-graph Approach to Solving a Class of Stackelberg Games in Carbon Management, Chemical Engineering Transactions, 89, 463-468 DOI:10.3303/CET2189078 CHEMICAL ENGINEERING TRANSACTIONS VOL. 89, 2021 A publication of The Italian Association of Chemical Engineering Online at www.cetjournal.it Guest Editors: Jeng Shiun Lim, Nor Alafiza Yunus, Jiří Jaromír Klemeš Copyright © 2021, AIDIC Servizi S.r.l. ISBN 978-88-95608-87-7; ISSN 2283-9216 P-graph Approach to Solving a Class of Stackelberg Games in Carbon Management Raymond R. Tana,*, Kathleen Avisoa, Timothy Walmsleyb a Chemical Engineering Department, De La Salle University, Manila, Philippines b Ahuora – Centre for Smart Energy Systems, School of Engineering, University of Waikato, Hamilton, New Zealand raymond.tan@dlsu.edu.ph Climate change mitigation can be achieved through the large-scale deployment of different carbon management technologies in industry. Governments will also play an important role in creating regulatory environments that incentivize low-carbon investments by self-interested private firms. In game theory, a class of problems known as Stackelberg (or leader-follower) games can be used to model such government-industry interactions. In a Stackelberg game, government is represented as an upper-level decision-maker (leader) and industry acts as the lower-level decision-maker (follower). The government’s problem is to set regulations and incentives so that industry’s rational profit-maximizing reaction aligns closely with the government objectives; the latter is assumed to be directed towards environmental protection on behalf of the general public. In this work, a P-graph based approach to solving a special class of Stackelberg game is developed. The leader is assumed to have binary variables for technology options, while the follower controls binary and continuous variables within the process networks formed by the available options (i.e., determined by the leader). The algorithm is illustrated on a case study involving the deployment of different negative emissions technologies (NETs). The combined use of biochar (BC) and direct air capture (DAC) is found to give near-optimal land and water footprints for the leader when the follower optimizes for cost. 1. Introduction Carbon dioxide (CO2) removal (CDR) using negative emissions technologies (NETs) will be needed in the coming decades to bring climate change under control (Haszeldine et al., 2018). NETs remove CO2 from the atmosphere using different physical, chemical, or biological pathways and sequester the carbon in various ecological compartments. Examples include direct air capture (DAC), bioenergy with carbon capture and storage (BECCS), enhanced weathering, biochar application, and reforestation/afforestation. A recent review of NET options can be found in Minx et al. (2018). Use of NETs for carbon management will require deployment at the scale of multiple Gt/y and may have significant sustainability implications (Smith et al., 2019). Process Integration (PI) principles will be needed to ensure that their CDR potential is maximized within global resource and environmental footprint limits (Tan et al., 2020). Decision analysis tools will be needed to select the best options in any given context while considering different criteria (Tapia, 2021). As with other environmental technologies, NETs will be subject to government-industry dynamics. Government provides a strategic and regulatory framework (theoretically for the public good) which then serve as parameters for industry to make profit-maximizing choices. Such interactions between two agents or players can be modelled using leader-follower or Stackelberg games. In game theory, a Stackelberg game is defined as a non- cooperative game between a leader (e.g., government) and a follower (e.g., industry). The leader has the capability to anticipate the follower’s future decisions, while the follower is only able to react to decisions that the leader has already made (Simaan and Cruz, 1973). The leader seeks a decision to which the follower’s rational reaction (i.e., that which is optimal for the follower’s interests) results in the best outcome for the leader. Since the follower’s decision-making problem is embedded within the leader’s problem, Stackelberg games can also be formulated as bi-level mathematical programming models. Typical applications of Stackelberg games to green engineering problems focus on determining economic incentives to induce industry to make use of environmentally preferred technologies. This approach has been demonstrated for water recycling in industrial 463 parks (Aviso et al., 2010), planning of fuel supply chains (Gao and You, 2017), selection of cleaner technologies for manufacturing (Chalmardi et al., 2019), and utilization of organic fertilizers in farms (Cobo et al., 2020). In general, bi-level mathematical programming models cannot be solved directly using conventional optimization algorithms. Even relatively simple bi-level linear programs can have non-convex feasible regions that result in computational challenges (Bard, 1998). For special classes of bi-level mathematical programming problems, exact solutions can be found by conversion into an equivalent single-level problem that can be solved using conventional solvers. Alternatively, interactive heuristic techniques can be used to give good approximate solutions (e.g., Aviso et al., 2010). A review of different solution strategies and algorithms is given by Sinha et al. (2018). Two clear research gaps can be seen in the literature. First, despite the implications of leader-follower dynamics on the future deployment of NETs, there are no publications that have dealt with the problem of using Stackelberg games. Second, there has been limited use of graph theoretic solution methods for Stackelberg games, and none have been reported for the problem of carbon management using NETs. To address these research gaps, a methodology is developed for solving a special class of Stackelberg games using P-graph. The latter is a graph theoretic computing framework that was originally developed to solve Process Network Synthesis (PNS) problems in plant design. The P-graph framework is a powerful decision support tool because of its intrinsic capability to enumerate optimal and near-optimal solutions to an engineering problem, where a list of such options may be valuable to a decision-maker (Friedler et al., 2019). The rest of this paper is organized as follows. Section 2 states the formal problem statement. Section 3 gives a brief overview of P-graph methodology and its extension to the current problem. Section 4 demonstrates the algorithm on a case study involving selection and deployment of NETs for carbon management. Section 5 gives the conclusions and suggests directions for future research. 2. Problem statement The formal problem statement addressed by this work is: • Given a set of NETs; • Given a set of economic (e.g., energy, financial resources) and environmental (e.g., CO2, water, land) streams; • Given input/output coefficients linking the streams to the NETs; • Given the leader’s (government’s) binary decision vector signifying selection or non-selection of NETs; • Given the follower’s (industry’s) binary decision vector signifying the selection or non-selection of NETs as a sub-set of technologies allowed by the leader, and continuous decision vector denoting the scale or capacity of selected NETs; • Given payoff or objective functions of the leader and the follower; The same linearity assumptions used in conventional PNS problems are also assumed to hold true. The leader (government) defines environmental objectives on behalf of the general public, while the follower (industry) has a purely economic objective function. The problem is to determine the leader’s Stackelberg strategy – i.e., the set of sanctioned technologies for which the follower’s rational reaction leads to the best possible payoff for the leader. 3. P-graph framework P-graph methodology is a graph-theoretic framework for solving PNS problems. A P-graph is a bipartite graph consisting of M-type nodes that denote streams and O-type nodes that denote processes. Arcs signify the existence of physical relationships between streams and processes. Axioms common to all PNS problems provide mathematical foundations (Friedler et al., 1992a) for the rigorous development of the component algorithms of the P-graph framework (Friedler et al., 1992b). These algorithms are Maximal Structure Generation (MSG), Solution Structure Generation (SSG), and Accelerated Branch-and-Bound (ABB). The purpose of MSG is to generate a maximal structure (i.e., a non-redundant, rigorous superstructure) from a set of component process units (Friedler et al., 1993). Unlike a conventional ad hoc superstructure, the maximal structure is guaranteed to be free of human error. The purpose of SSG is to enumerate all structurally feasible process networks that can be formed from the available processes (Friedler et al., 1992b). Each solution structure is a subset of the maximal structure. Both MSG and SSG use only structural information (i.e., the presence of physical connections between streams and processes). The purpose of ABB is to provide rapid optimization once flowrate and techno-economic data are given (Friedler et al., 1996). ABB also allows near- optimal solutions to be generated in case these are of interest to the designer. Different software implementations of P-graph are available. P-graph Studio (P-graph, 2021) is an online tool that can implement 464 MSG, SSG, and ABB. The first two algorithms are also available in stand-alone Visual Basic for Applications code (Lao et al., 2020). The classical PNS problem was originally defined in the context of plant design applications, but P-graph applications have diversified in the past decade (Sangalang et al., 2021). Cabezas et al. (2018) give a review of notable green engineering applications. Friedler et al. (2019) discuss prospects for future applications of the framework. P-graph has also been used to handle PNS-like problems involving economic (Aviso et al., 2015), ecological (Lao et al., 2020), decision-theoretic (Low, et al., 2020), and causality (Tan et al., 2021) networks. A solution algorithm has been developed in this work for solving a special class of Stackelberg games using P- graph. The procedure for solving the problem defined in Section 2 is as follows: • Enumerate all structurally feasible technology networks with SSG. • Solve the follower’s MILP problem within each enumerated structure to generate optimal solutions, as well as near-optimal solutions within a specified tolerance. This step involves imposing the network structure defined by the leader as a constraint on the inner MILP problem of the follower. • Evaluate the leader’s payoff function for each optimal solution of the follower. • Identify the solution structure or structures in which the follower’s solution maximizes the leader’s payoff. The procedure is illustrated with a case study in the next section. 4. Case study This case study illustrates the application of the algorithm to the problem of large-scale NET deployment. The leader (government) is assumed to have regulatory control over technology options; the follower (industry) is assumed to optimize its objectives within the regulatory parameters set by the state by selecting the scale of use of the allowed technologies. The government seeks to minimize environmental footprints by identifying sanctioned technologies so that industry’s rational reaction meets a system-wide CDR target. The techno-economic data for the NETs are based on previously published estimates (Smith et al., 2016) and are summarized in Table 1. The alternatives considered are bioenergy with carbon capture and storage (BECCS), reforestation (R), soil carbon sequestration (SCS), biochar (BC), direct air capture (DAC), and enhanced weathering (EW). Note that SCS and BC rely on carbon sequestration in raw and carbonized biomass. The different NETs may be either net energy consumers or producers; it is therefore essential to account for their interactions with the energy infrastructure (Creutzig et al., 2019). Table 2 provides the techno-economic data for clean energy technologies (Ali, 2020). The P-graph representation of the problem’s superstructure is shown in Figure 1 where the rectangular nodes represent the different technologies (e.g., NETs, clean energy technologies) and the circular nodes indicate the flow of streams (e.g., land, water, and energy requirements, CDR). The cost data are associated with the rectangular nodes and is scaled proportional to the degree by which the NET or clean energy technology is used in the system. In addition, arrows indicate the flow of streams into and out of the different technologies. An example of how streams are connected to the rectangular nodes is demonstrated with the BECCS unit illustrated in Figure 2. This shows that the BECCS requires 0.40 ha of land, 2.50 kt of water and 8.7 GJ of energy to remove 1 t of CO2. Similar representation can be done for the other technologies using the information shown in Tables 1 and 2. Table 1: Techno-economic data for NETs (Smith et al., 2016) Technology Land footprint (ha/t) Water footprint (kt/t) Energy demand (GJ/t) Cost (USD/t) BECCS 0.40 2.50 8.7 132 R 0.60 2.35 0 108 SCS 33.0 0 0 40 BC 0.87 0 -20 1200 DAC 0.001 0.11 45.8 2080 EW 1.22 0.0015 46.2 5887 Table 2: Techno-economic data for clean energy technologies (Ali, 2020) Technology Land footprint (ha/GJ) Water footprint (t/GJ) CDR (t/GJ) Cost (USD/GJ) NGCC 0 0.93 -0.14 14.56 Hydropower 0.0001 3.64 -0.01 16.08 Windpower 0.0001 0 -0.01 20.11 465 Using P-graph Studio (P-graph, 2020), all structurally feasible networks can be generated using SSG, which for this case led to 374 structures. Land and water footprint constraints are critical for the scale-up of NETs (Smith et al., 2016), Then, given resource footprint constraints of 1 x 106 kt of water and 20,000 ha of land, the SSG structures are optimized to remove 1,000 t of CO2 (i.e., the government’s stated CDR aim) for minimum total costs incurred by the system using the SSG-LP algorithm, which resulted in 12 optimized SSG structures. These structures correspond to the possible MILP solutions of the follower. The results are then organized based on increasing cost, and the 12 optimal and near-optimal solutions are shown in Table 3. The negative entries listed under the water and land footprint indicates that these were the resources consumed in a particular solution structure. Table 3 also indicates the technologies selected for each solution. In most solutions (except for solution numbers 3 and 8), the system generates just enough energy needed by the selected NETs to achieve 1,000 CDR. For solutions 3 and 8, the technologies selected (e.g., R and SCS) did not require any energy to achieve the required CDR. NGCC was not selected as an energy provider in any of the solutions because of its high generation of CO2. The follower’s optimal solution that resulted in the lowest cost (i.e., solution structure 1) adopts the use of DAC and Hydropower. Figure 1: Maximal structure of system a) b) Figure 2: Representation of BECCS in a) conventional process unit diagram and b) P-graph The follower’s optimal solution results in the exhaustion of all available land (20,000 ha), but this will not be a desirable solution to the leader. The leader’s (government) payoff function can then be evaluated based on the solutions identified by the follower. Government is concerned with the management of resources, so its objective will be the minimization of either land or water footprint (or a Pareto optimal combination of both). The minimum land footprint is achieved by solution structure 8 which selects the use of reforestation. The minimum water footprint is achieved by solution structure 11 by employing BC, EW and SCS. However, solution structure 11 466 also exhausts all available land. Further examination of the solutions shows that a reasonable solution might be structure 9, which achieves a relatively low cost (20 % of the worst solution) at low environmental footprint where the land footprint is only 10 % of the worst performance in land footprint and 4.4 % of the worst performance in water footprint. Solution 9 employs BC and DAC. Table 3: Optimal and near optimal solutions of the follower Solution Footprint BC BECCS DAC EW Hydro NGCC R SCS Wind Cost (‘000 USD) Land (ha) Water (kt) 1 -20,000 -201    761 2 -20,000 -80    774 3 -20,000 -943   1,010 4 -20,000 -46    1,221 5 -20,000 -1,107    1,250 6 -20,000 -1,093    1,252 7 -20,000 -1,009    1,296 8 -600 -2,350  2,458 9 -1,993 -110   2,858 10 -778 -2,500   3,154 11 -20,000 -6    10,707 12 -16,149 -8   13,868 5. Conclusions A solution algorithm has been developed in this work for solving a special class of Stackelberg games using P- graph. A bi-level game-theoretic framework is applied where the leader (i.e., the government) has discrete technology choices, while the follower (i.e., industry) has control over continuous variables within the technology parameters defined by the leader. The algorithm relies on exhaustive enumeration of structurally feasible technology networks via SSG and optimization of the corresponding partial problems using LP. The Stackelberg solution is determined by selecting the structure for which the leader’s payoff function is optimal. The algorithm is demonstrated using a case study on NETs for carbon management. Future work can extend this work by considering variants with continuous variables in the leader’s problem to allow for calibration of taxes or subsidies. Its applicability to large-scale problems should be investigated. The algorithm can also be embedded in the next generation of P-graph software or implemented with alternative languages such as Visual Basic for Applications or Python. Acknowledgment We are grateful to the P-graph Studio software development and support team at the University of Pannonia in Hungary. Walmsley’s research has been supported by project Ahuora, an Advanced Energy Technology Platform, funded by the New Zealand Ministry of Business, Innovation and Employment. References Ali B., 2020, A methodology for the sustainability of power generation through integration of impacts on water, air, land, and cost, Resources, Conservation and Recycling, 158, 104830. Aviso K.B., Tan R.R., Culaba A.B., Cruz Jr. J.B., 2010, Bi-level fuzzy optimization approach for water exchange in eco-industrial parks, Process Safety and Environmental Protection, 88, 31–40. Aviso, K.B., Cayamanda, C.D., Solis, F.D.B., Danga, A.M.R., Promentilla, M.A.B., Yu, K.D.S., Santos, J.R., Tan, R.R., 2015, P-graph approach for GDP-optimal allocation of resources, commodities and capital in economic systems under climate change-induced crisis conditions, Journal of Cleaner Production, 92, 308–317. Bard, J.F., 1998, Practical bilevel optimization: Algorithms and applications, Springer, Dordrecht, Netherlands. Cabezas H., Argoti A., Friedler F., Mizsey P., Pimentel, J., 2018, Design and engineering of sustainable process systems and supply chains by the P-Graph framework, Environmental Progress and Sustainable Energy, 37, 624–636. Chalmardi, K., Camacho-Vallejo, J.-F., 2019, A bi-level programming model for sustainable supply chain network design that considers incentives for using cleaner technologies, Journal of Cleaner Production, 213, 1035–1050. 467 Cobo, S., You, F., Dominguez-Ramos, A., Irabien, A., 2020, Noncooperative game theory to ensure the marketability of organic fertilizers within a sustainable circular economy, ACS Sustainable Chemistry and Engineering, 8, 3809–3819. Creutzig, F., Breyer, C., Hilaire, J., Minx, J., Peters, G.P., Socolow, R., 2019, The mutual dependence of negative emission technologies and energy systems, Energy & Environmental Science, 12, 1805–1817. Friedler, F., Tarjan, K., Huang, Y.W., Fan, L.T., 1992a, Graph-theoretic approach to process synthesis: Axioms and theorems, Chemical Engineering Science, 47, 1973–1988. Friedler, F., Tarjan, K., Huang, Y.W. Fan, L.T., 1992b, Combinatorial algorithms for process synthesis, Computers and Chemical Engineering, 16, 313–320. Friedler, F., Tarjan, K., Huang, Y.W., Fan, L.T., 1993, Graph-theoretic approach to process synthesis: Polynomial algorithm for maximal structure generation, Computers and Chemical Engineering, 17, 929–942. Friedler, F., Varga, J. B., Fehér, E., Fan, L.T., 1996, Combinatorially Accelerated Branch-and-Bound Method for Solving the MIP Model of Process Network Synthesis, In: Floudas, C.A., Pardalos, P.M., Eds., State of the Art in Global Optimization: Computational Methods and Applications, 609–626, Springer, Dordrecht, Netherlands. Friedler F., Aviso K.B., Bertok B., Foo D.C.Y., Tan R.R., 2019, Prospects and Challenges for Chemical Process Synthesis with P-Graph, Current Opinion in Chemical Engineering, 26, 58–64. Gao, J., You, F., 2017, Game theory approach to optimal design of shale gas supply chains with consideration of economics and life cycle greenhouse gas emissions, AIChE Journal, 63, 2671–2693. Haszeldine, R.S., Flude, S., Johnson, G., Scott, V., 2018, Negative emissions technologies and carbon capture and storage to achieve the Paris Agreement commitments, Philosophical Transactions of the Royal Society A: Mathematical, Physical, and Engineering Sciences, 376, 20160447. Lao, A., Cabezas, H., Orosz, A., Friedler, F., Tan, R., 2020, Socio-ecological network structures from process graphs, PLoS One, 15, e0232384. Low, C.X., Ng, W.Y., Putra, Z.A., Aviso, K.B., Promentilla, M.A.B., Tan, R.R., 2020, Induction approach via P- Graph to rank clean technologies, Heliyon, 6, e03083. Minx J.C., Lamb W.F., Callaghan M.W., Fuss S., Hilaire J., Creutzig F., Amann T., Beringer T., De Oliveira Garcia W., Hartmann J., Khanna T., Lenzi D., Luderer G., Nemet G.F., Rogelj J., Smith P., Vicente Vicente J.L., Wilcox J., Del Mar Zamora Dominguez M., 2018, Negative emissions – Part 1: Research landscape and synthesis, Environmental Research Letters, 13, 063001. P-graph, 2021. P-Graph Studio , Accessed 15/06/2021. Sangalang, K.P.H., Belmonte, B.A., Ventura, J.-R.S., Andiappan, V., Benjamin, M.F.D., 2021, P-graph method for optimal synthesis of Philippine agricultural waste-based integrated biorefinery, Chemical Engineering Transactions, 83, 103–108. Simaan, M., Cruz, Jr., J.B., 1973, On the Stackelberg strategy in nonzero-sum games, Journal of Optimization Theory and Applications, 11, 533–555. Sinha, A., Malo, P., Deb, K., 2018, A review on bilevel optimization: From classical to evolutionary approaches and applications, IEEE Transactions of Evolutionary Computation, 22, 276–295. Smith, P., Adams, J., Beerling, D.J., Beringer, T., Calvin, K.V, Fuss, S., Griscom, B., Hagemann, N., Kammann, C., Kraxner, F., Minx, J.C., Popp, A., Renforth, P., Vicente Vicente, J.L., Keesstra, S., 2019, Land- management options for greenhouse gas removal and their impacts on ecosystem services and the Sustainable Development Goals, Annual Review of Environment and Resources, 44, 255–286. Smith, P., Davis, S.J., Creutzig, F., Fuss, S., Minx, J., Gabrielle, B., Kato, E., Jackson, R.B., Cowie, A., Kriegler, E., Van Vuuren, D.P., Rogelj, J., Ciais, P., Milne, J., Canadell, J.G., McCollum, D., Peters, G., Andrew, R., Krey, V., Shrestha, G., Friedlingstein, P., Gasser, T., Grübler, A., Heidug, W.K., Jonas, M., Jones, C.D., Kraxner, F., Littleton, E., Lowe, J., Moreira, R.B., Nakicenovic, N., Obersteiner, M., Patwardhan, A., Rogner, M., Rubin, E., Sharifi, A., Torvanger, A., Yamagata, Y., Edmonds, J., Yongsung, C., 2016, Biophysical and economic limits to negative CO2 emissions, Nature Climate Change, 6, 42–50. Tan, R.R., Aviso, K.B., Lao, A.R., Promentilla, M.A.B., 2021, P-graph causality maps, Process Integration and Optimization for Sustainability, 5, 319-334. Tan, R.R., Bandyopadhyay, S., Foo, D.C.Y., 2020, The role of process integration in managing resource constraints on negative emissions technologies, Resources, Conservation and Recycling, 153, 104540. Tapia, J.F.D., 2021, A risk-based decision support tool for selection and evaluation of negative emissions technologies, Chemical Engineering Transactions, 83, 97–102. 468 078.pdf P-graph Approach to Solving a Class of Stackelberg Games in Carbon Management