Essays on Sustainable Operations ManagementbySanjith GopalakrishnanB.S., M.S., Indian Institute of Technology – Madras, 2014a thesis submitted in partial fulfillmentof the requirements for the degree ofDoctor of Philosophyinthe faculty of graduate and postdoctoral studies(Business Administration)The University of British Columbia(Vancouver)July 2020c© Sanjith Gopalakrishnan, 2020The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the thesis entitled:Essays on Sustainable Operations Managementsubmitted by Sanjith Gopalakrishnan in partial fulfillment of the requirements for thedegree of Doctor of Philosophy in Business Administration.Examining Committee:Professor Daniel Granot, Sauder School of BusinessCo-supervisorProfessor Frieda Granot, Sauder School of BusinessCo-supervisorProfessor Kathryn Harrison, Political ScienceUniversity ExaminerProfessor Harish Krishnan, Sauder School of BusinessUniversity ExaminerAdditional Supervisory Committee Members:Professor Werner Antweiler, Sauder School of BusinessSupervisory Committee MemberProfessor Mahesh Nagarajan, Sauder School of BusinessSupervisory Committee MemberiiAbstractThis dissertation comprises three independent essays on sustainable operations management.In the first essay, we consider supply chains with joint production of carbon emissions,operating under either a carbon tax or an internal carbon pricing regime. Supply chain lead-ers, such as Walmart, are assumed to be environmentally motivated to induce their suppliersto abate their emissions. We derive a footprint-balanced scheme for reapportioning the totalcarbon emissions amongst the firms in the supply chain. This allocation scheme, which isthe Shapley value of an associated cooperative game, is shown to be transparent and easy tocompute. Further, when the abatement cost functions of the firms are private information, itincentivizes suppliers to exert pollution abatement efforts that minimize the maximum devi-ation from the socially optimal pollution level. Finally, it is the unique allocation mechanismsatisfying certain contextually desirable properties.The second essay analyzes a Canadian federal mandate to factor in upstream emissionsduring the environmental impact assessment of fossil fuel energy projects. We employ a co-operative game-theoretic model and propose the nucleolus mechanism to apportion upstreamemission responsibilities. The nucleolus allocation avoids the distortionary effects of doublecounting and exhibits a certain contextually desirable consistency property. We develop apolynomial-time algorithm to compute the nucleolus and further provide an implementationframework in terms of two easily stated and verifiable policies. We also provide lower-boundguarantees on the welfare gains it delivers to firms and on the incentives it offers them toadopt emission abatement technologies.In the third essay, we consider the operations of bike-sharing systems. Despite theirgrowing popularity as a sustainable urban transport option, bike-share programs in severalcities such as Seattle and Montreal have run into financial difficulties due to low ridership andhigh operational costs. Further, their environmental benefits are ambiguous since a majorityof users are observed to substitute from public transport or walking. We develop a consumertransport mode choice model to analyze the economic and environmental implications of threekey operational levers: the pricing structure, station coverage and density, and frequency ofrebalancing operations.iiiLay SummaryIn response to the increasing threat of global climate change, governments in several regionshave begun to institute new environmental regulations, such as carbon taxes, upon busi-nesses. In parallel, green business models have also emerged that attempt to align profitmotives with environmental objectives. This dissertation is comprised of three essays: inthe first two, we examine environmental regulations placed on supply chain emissions, andin the third essay, we examine a novel green business model of bike-sharing. Employinggame-theoretic methods and case studies, we analyze these regulations and the bike-sharingbusiness model along economic and environmental dimensions. The primary objective of thisdissertation is to develop and apply analytical tools to aid in the design of better regulationsand business models that can achieve the desired environmental objectives while minimizingand distributing the economic burden fairly.ivPrefaceVersions of Chapters 2 and 3 have been submitted for publication. Chapter 4 will be refor-matted and submitted for publication.Chapter 2 is co-authored with Professors Daniel Granot, Frieda Granot, Greys Sosˇic´, andHailong Cui. Chapters 3 and 4 are co-authored with Professors Daniel Granot and FriedaGranot. In all chapters, I was a primary contributor and I was involved in developing themodels, carrying out the analysis, and reporting the results, as presented in this dissertation.Therefore, I also assume full responsibility for editorial and technical mistakes, if any arefound. However, at the same time, all my co-authors have provided invaluable intellectualguidance and devoted tremendous time and effort on these projects.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Incentives and Emission Responsibility Allocation in Supply Chains . . . 52.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.3 The GREEN Game Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3.1 Cooperative Game Definitions and Model . . . . . . . . . . . . . . . . 122.3.2 The Shapley Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Footprint Balance and Emission Abatement Incentives . . . . . . . . . . . . . 142.4.1 Generalized Comparative Statics . . . . . . . . . . . . . . . . . . . . . 152.4.2 Shapley Allocation and Abatement Incentives . . . . . . . . . . . . . . 172.5 Properties of the Shapley Allocation . . . . . . . . . . . . . . . . . . . . . . . 202.6 Case Study – Walmart’s Jeans Supply Chains . . . . . . . . . . . . . . . . . . 222.6.1 Levi Strauss’ & Co.’s Environmental Initiatives . . . . . . . . . . . . . 232.6.2 Walmart-Nautica Supply Chain . . . . . . . . . . . . . . . . . . . . . . 252.6.3 Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28vi3 Consistent Allocation of Emission Responsibility in Fossil Fuel SupplyChains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1 Introduction and Literature Review . . . . . . . . . . . . . . . . . . . . . . . 313.2 Model Development . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2.2 A Cooperative Game Model . . . . . . . . . . . . . . . . . . . . . . . . 373.2.3 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2.4 Welfare, Incentives and the Regulator’s Problem . . . . . . . . . . . . 403.3 The Nucleolus Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.4 An Implementation Framework and Stability Analysis . . . . . . . . . . . . . 463.4.1 Endogenous Formation of Alliances . . . . . . . . . . . . . . . . . . . . 503.4.2 Stability of Alliance Structures . . . . . . . . . . . . . . . . . . . . . . 523.5 Structural Properties and Implications . . . . . . . . . . . . . . . . . . . . . . 533.6 Fairness, Welfare and Incentive Considerations . . . . . . . . . . . . . . . . . 563.7 Case Study – Trans Mountain Pipeline System . . . . . . . . . . . . . . . . . 613.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664 Bike-Sharing Systems: An Analysis of Operational Strategies . . . . . . . 684.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.2 Model Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.2.1 Bike Share System Operator . . . . . . . . . . . . . . . . . . . . . . . 704.2.2 Consumer’s Mode Choice Model . . . . . . . . . . . . . . . . . . . . . 724.3 Operational Decisions and Bike-Sharing Demand . . . . . . . . . . . . . . . . 734.3.1 Drivers of Mode Choice . . . . . . . . . . . . . . . . . . . . . . . . . . 744.3.2 Transportation Mode Choice . . . . . . . . . . . . . . . . . . . . . . . 764.4 Continuous Approximation for Bike Rebalancing Distance . . . . . . . . . . . 794.5 Qualitative Implications and Extensions . . . . . . . . . . . . . . . . . . . . . 81Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Appendix A Chapter 2 – Proofs and Technical Results . . . . . . . . . . . . . 93Appendix B Chapter 3 – Proofs and Technical Results . . . . . . . . . . . . . 101Appendix C Chapter 3 – Carbon Footprinting Computations . . . . . . . . . 117Appendix D Chapter 3 – Further Numerical Results . . . . . . . . . . . . . . 120Appendix E Chapter 4 – Proofs and Numerical Parameters . . . . . . . . . 123viiList of TablesTable 2.1 GHG emissions through the cycle of a pair of jeans. ‡Percentage is calcu-lated with respect to the scope including stages 1 to 5 only. . . . . . . . . 26Table 3.1 GHG emissions estimation for each stage in the fossil fuel supply chain andthe comparison of four alternative concordant allocation mechanisms (unit:kt CO2Eq/day). The emissions estimation only accounts for seven in-situoil sands and heavy oil projects that are expected to contribute around224,500 bbl/day of capacity between 2016 and 2019. . . . . . . . . . . . . . 63Table 4.1 Drivers of mode choice for the different modes of transport . . . . . . . . . 75viiiList of FiguresFigure 2.1 Worst-case loss of efficiency, ∆(φ) (units: kgCO2E), in the Nautica-Walmartsupply chain is minimized at the Shapley allocation rule, Φ (left panel).The efficiency gap, δ(Φ,a) (units: kgCO2E), is concave increasing in thecarbon price, pS (units: ¢/kgCO2E) (right panel). The ratio of first-bestemissions to the emissions supported in equilibrium by the Shapley mech-anism, f∗1,2/fΦ1,2, as a function of the carbon price, pS (bottom panel). . . 27Figure 3.1 Illustrating the Upstream Responsibility game model for a simple fossilfuel supply chain. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Figure 3.2 Abatement cost plot with a set of socially desirable emission reductiontechnologies under a carbon price pt = pS (left panel). Technology adop-tion incentives for firm i by the mechanism x and the baseline allocationx (right panel). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Figure 3.3 Illustrative examples with a simple supply chain and policy-compliant al-locations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Figure 3.4 Game tree H(Γ) corresponding to an alliance formation game Γ in a typicalfossil fuel supply chain. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Figure 3.5 Illustrating the structural properties of the nucleolus allocation mechanism(Example 3.4). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Figure 3.6 A map of the Trans Mountain pipeline expansion project and a schematicof the supply chain associated with the pipeline. . . . . . . . . . . . . . . 62Figure 3.7 Region of potentially available technologies rendered profitable by the fourallocation mechanisms (left panel). The social environmental welfare andfirm welfare generated by the four mechanisms as a function of the carbonprice, pt (right panel). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Figure 4.1 Timeline of Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73Figure 4.2 Disutilities of the various modes of transport and mode choice as a functionof travel distance (units: km). . . . . . . . . . . . . . . . . . . . . . . . . . 78ixFigure 4.3 Comparison between approximation for r(ν,N,R,K, λ) from Theorem 4.2and numerical estimates of rebalancing distance for simulated bike-sharingnetworks of different sizes N distributed over a region of unit-distance radius. 81Figure D.1 A simple fossil fuel supply chain. . . . . . . . . . . . . . . . . . . . . . . . 120Figure D.2 Region of potentially available technologies rendered profitable by the fourallocation mechanisms (left panel). The social environmental welfare andfirm welfare generated by the four mechanisms as a function of the carbonprice, pt (right panel). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121xAcknowledgmentsI am deeply grateful to my advisors, Professor Daniel Granot and Professor Frieda Granot,for their constant support, patience, and encouragement. Their expertise, attention to detail,and the academic freedom they provided made my PhD an enriching intellectual experience.I have benefited immensely from their wise mentorship, the lessons of which extend acrossall spheres of academic life.I want to thank Professor Mahesh Nagarajan for his guidance, and the time and effort heexpended towards making me a better researcher. His support has played a huge role in myacademic development and for this, I am immensely grateful to him.I also thank my committee member, Professor Werner Antweiler, for his useful feedbackon my projects. His course on environmental management shaped the direction of this the-sis. I am grateful to Professor Dale Griffin for his contributions to my academic training. Iwould also like to thank Professor Tim Huh, Professor Harish Krishnan, and Professor HasanCavusoglu. The perspectives I gained from them on research and teaching were truly valu-able. Thanks are also due to Elaine Cho and Rita Quill for enabling a conducive academicenvironment.I must thank several of my fellow graduate students at the Sauder School of Business fortheir friendship and the many wonderful conversations which made my time at UBC thatmuch more enjoyable.Finally, and most importantly, my deepest gratitude is towards my parents, my brother,and Lavisha. This journey would not have been possible without their unconditional loveover the years.xiChapter 1IntroductionA global consensus has evolved gradually around the need to balance economic growth withenvironmental sustainability. Recently, in response to the impending risks due to climatechange, the 2015 Paris Climate Agreement sets out an objective to pursue efforts to limit thetemperature increase to 1.5◦C above pre-industrial levels (Paris Agreement 2015). To achievethis objective, the United Nations Environment Programme (UNEP 2019) finds that a 7.6%year-over-year reduction in global annual emissions is necessary. This changing landscapehas required existing businesses to move beyond solely focusing on economic profitabilityand to also consider the environmental aspects of their operations. It has also, in somecases, facilitated the growth of entirely new sustainable business models such as the sharingeconomy.The field of sustainable operations management similarly integrates considerations ofenvironmental sustainability within traditional lines of enquiry, as well as, explores newavenues of research. It thereby plays a critical role in identifying business and policy solutionsfor environmental challenges. As identified by Atasu et al. (2020), two major themes ofresearch within sustainable operations management have been: (i.) operations managementfor a low-carbon economy, and (ii.) sustainable business model innovation. The formerstream studies the optimal design of regulations such as carbon accounting, carbon taxes,cap-and-trade etc. and their impacts on firms operational decisions and adoption of cleanertechnologies (see, for example, Caro et al. 2013, Jira and Toffel 2013, Plambeck and Taylor2013, Sunar and Plambeck 2016, Drake 2018). The latter stream considers the operationaldesign and environmental outcomes of novel business models such as, for example, onlinegrocery (Belavina et al. 2016), and sharing economy models (Bellos et al. 2017, Agrawal etal. 2019, Orsdemir et al. 2019).This thesis comprises of three independent essays. The first two essays broadly fall underthe first theme of designing better policies or regulations that suitably incentivize firms toachieve desired environmental objectives. The third essay on bike-sharing business models1follows the second theme.Greenhouse gas emissions from the supply chains of just the 2,500 largest global corpora-tions account for more than 20% of global emissions. Further, the direct emissions of firmsaccount for only about 14% of their total emissions with the rest of it coming from their sup-ply chains (Matthews et al. 2008). Therefore, rationalizing emissions in supply chains couldmake an important contribution towards meeting the global CO2 emission reduction targetstied to the 2015 Paris Climate Agreement. This motivates our first essay where we considersupply chains with joint production of GHG emissions. That is, supply chains wherein theactions of an individual firm influences not only its own direct emissions but also influencesemissions at other stages in the supply chain. This is often the case in practice. We supposethat the leader of such a supply chain (for example, Walmart) is environmentally motivatedand strives to reduce supply chain emissions. The supply chain leader identifies joint re-sponsibilities, in view of the ability of firms to directly or indirectly influence the emissions ofvarious processes in the supply chain, and apportions the net supply chain emissions amongstthe constituent firms by leveraging its knowledge. The supply chain leader’s objective is toincentivize firms to exert suitable actions that reduce the overall supply chain emissions.The supply chain leader, in our model, aims to do so by redistributing the total carbon taxburden on the supply chain, in view of the joint responsibilities for emissions. We adopt acooperative game theory methodology to derive a fair and transparent scheme for apportion-ing the total carbon emissions in the supply chain, which is shown to incentivize firms toexert, in some sense, optimal abatement efforts to reduce their pollution. Via a case studybased on the Walmart-Nautica jeans’ supply chain, we illustrate how our proposed emissionre-apportionment mechanism could be implemented by supply chain leaders to achieve supplychain emission reductions.In the second essay, we focus on a recent Canadian environmental regulation directedat proposed energy projects. Faced with increasing stakeholder pressure from environmen-tal thinktanks and NGOs, the Canadian federal government announced on January 27, 2016that the energy regulator, National Energy Board, later superseded by the Impact AssessmentAgency of Canada, would factor in upstream emissions during the environmental impact as-sessment stage for proposed energy projects (Canada 2016). This has significant implicationsfor several pipeline projects across Canada (such as the Trans Mountain pipeline expansion)that transport crude oil or refined products to refineries and shipping terminals, and other en-ergy projects. The upstream emissions attributable to a proposed project could be comparedagainst a rejection threshold level of emissions whereby the regulator sets a predeterminedlevel of upstream emissions beyond which the project will be rejected (Schaufele 2016), oras in the case of the approval granted to the Trans Mountain pipeline project, the regulatorcould also require the firm to offset some or all of the associated upstream emissions.2However, a rejection threshold policy or offset requirements that take into account all up-stream emissions of an energy project would have to be calibrated, depending on the stage ofthe supply chain the project is situated at, or otherwise it risks inducing distortionary effectsby favouring upstream energy projects over more downstream ones. This is primarily a con-sequence of double counting by attributing to each entity in the supply chain all associatedupstream emissions. We address these concerns and develop an emission responsibility ac-counting mechanism for energy supply chains that avoids the distortionary economic effects ofdouble counting while embodying the principle of upstream emission responsibility mandatedby the Canadian federal government. Furthermore, the mechanism we propose exhibits a con-sistency property that is especially important in a regulatory context wherein energy supplychains span multiple legal jurisdictions. We also provide a simple implementation frame-work for our proposed mechanism in terms of two easily stated and compliance-verifiablepolicies. Our results could be of interest to energy regulators and energy companies aimingto strike a balance between energy and economic needs and environmental concerns. Theyimply that a mandated, centrally determined and binding emission responsibility allocationscheme can be replaced, in some sense, by a decentralized scheme that provides a degreeof freedom to entities in energy supply chains to collectively arrive at an apportionment ofpollution responsibilities that is beneficial from the entire supply chain’s perspective. Such adecentralized policy framework, that calls upon supply chain entities to collaborate with theirpartners, may also catalyze ancillary environmental benefits. Importantly, we contextualizeour discussion with a case study on the proposed expansion of the Trans Mountain pipelinein Western Canada.In the third essay, we focus on the operations of bike-sharing systems. Bike sharingprograms have rapidly gained in popularity and a key reason being that they present asustainable and green urban transport option complementing the existing modes of transport.Despite the growing popularity of bike sharing, systems in several major cities, such asSeattle’s Pronto and Bixi in Montreal, have run into financial difficulties. High operationalcosts arising from system rebalancing, theft and vandalism, coupled with lower than projectedlevels of ridership are commonly identified as the major contributing factors.On the other hand, the environmental benefits of a bike-sharing program, as a consequenceof reduced vehicular emissions from individuals substituting away from personal automobiles,might be less substantial than presumed. For example, the 2014 survey report of the CapitalBike Share Program in Washington D.C. notes that - “40% percent of respondents wouldhave ridden a bus or train if Capital Bikeshare had not been available for the most recenttrip, another 37% would have walked to their destination, only 12% of respondents wouldhave driven or ridden in a car.” Another survey of bike-share users in Portland estimatedthat only up to a quarter of the users had substituted away from cars. Further, typically3the rebalancing operations are carried out with trucks which results in significant carbonemissions. Both these factors suggest that in certain cases, the environmental benefits ofbike-sharing programs might be overstated. Lending further evidence, Fishman et al. (2014),using surveys and bike trip data, study the environmental impact of bike share programsacross four cities world-wide, and find that the London bike-share system had a net negativeenvironmental impact.This motivates our third essay where we consider three key strategic and operationaldecisions faced by bike share operators - the coverage and density of the system, the pricingmodel and the frequency of rebalancing. Our objective is to provide insights to planners todesign bike-sharing systems that are financially viable with high ridership and low operationalcosts, which maximize environmental benefits.4Chapter 2Incentives and Emission ResponsibilityAllocation in Supply Chains2.1. IntroductionIn view of the urgency and challenges of mitigating climate change, it should be noted thatgreenhouse gas (GHG) emissions from the supply chains of the 2,500 largest global corpora-tions accounts for more than 20% of global GHG emissions (van Hoek et al. 2019). Further,typically, the emissions associated with the direct operations of a company are far exceededby the indirect emissions associated with its supply chain. Indeed, the average ratio of supplychain to direct carbon emissions is 5.5, and for the retail sector, this ratio is much higherat 10.9 (Carbon Disclosure Project (CDP) 20191). Therefore, accounting and rationalizingemission responsibility in supply chains could make an important contribution to achievingthe desired global CO2 emission reduction targets (Paris Agreement 20152).Increased attention, visibility, and stakeholder pressures, have motivated several organi-zations to integrate environmental concerns in the formal and informal governance of theirsupply chains (Huang et al. 2019). Walmart is one of the companies that has embraced its re-sponsibility to protect the environment and reduce emissions in its vast supply chain. To actupon its environmental goals, Walmart, since 2007, has started to collect data to assess GHGemissions of its supply chain. To facilitate the rationalization of its supply chain, Walmartis collaborating with academics and environmental third-party groups to identify processesin its supply chain that generate significant carbon emissions (Oshita 2011, Plambeck 2012).The United States federal government followed suit in 2009, when a new Presidential Ex-ecutive Order required federal agencies to set reduction targets and track the reduction of1https://www.cdp.net/2https://treaties.un.org/pages/ViewDetails.aspx?src=TREATY&mtdsg no=XXVII-7-d&chapter=27&lang=en5GHG emissions, including those associated with their supply chains3, and many corporationshave similarly joined the efforts to collect information about their GHG emissions. The CDPSupply Chain Program is a collaboration of multinational corporations that have requestedinformation about their key suppliers’ GHG emissions as well as their vulnerabilities andopportunities associated with climate change.It is well recognized that the actions of an individual firm in a supply chain, aside frombeing responsible for its own direct emissions, can often influence emissions at other stagesin the supply chain. As an example, the packaging design choice by a manufacturer is likelyto impact the distributor’s transport emissions. Similarly, in the oil industry, the choiceof crude oil blends and diluents added at the extraction stage affects emissions associatedwith shipping and transportation across oil pipelines, as well as emissions during the refiningstage (ICCT 2014). Therefore, to improve environmental performance, motivated supplychain leaders need to understand the interrelated sources of emissions in their supply chains.In particular, to incentivize firms to reduce overall supply chain emissions, suppliers shouldbe held responsible both for their own direct emissions, as well as for emissions by other firms,which they can jointly reduce. That is, aside from direct emission responsibility, supply chainleaders should attribute indirect emission responsibilities to firms which can lower emissionsat other stages in the supply chain by, e.g., expertise and innovation sharing, or by modifyingtheir operational decisions, product design, material selection, or packaging design (see, e.g.,Benjaafar et al. 2013, Gallego and Lenzen 2005, LS & Co. 2017, HP Living Progress Report20144, and Herman Miller 20165).Recognizing the urgency of mitigating climate change, more than 60 regional and nationalgovernments have implemented policies that price carbon emissions6. In that respect, ouressay can be viewed as modeling the challenges and opportunities facing supply chain leadersoperating under a carbon tax regime, wherein a regulator levies a penalty on the emissionsgenerated by the firms in the supply chain. The supply chain leaders, such as Walmart, areassumed to be environmentally motivated whose objective is to incentivize constituent firmsto reduce the overall supply chain emissions. In the presence of a carbon tax regime, theyaim to achieve this objective by leveraging their knowledge on the sources of pollution, andredistributing the total carbon tax burden among the firms in the supply chain.We note, however, that it has been suggested, e.g., by Aldy and Gianfrate (2019), thateven companies operating in areas without carbon tax legislation must prepare for potentialincreases in their operating costs due to carbon prices. Companies in such settings can benefit3https://www.whitehouse.gov/the-press-office/president-obama-signs-executive-order-focused-federal-leadership-environmental-ener.4http://www8.hp.com/h20195/v2/GetDocument.aspx?docname=c041527405http://www.smartfurniture.com/hermanmiller/environmental.html6https://carbonpricingdashboard.worldbank.org/map data6by using internal carbon pricing as it helps them to measure and manage risks associated withexisting pricing regimes and to identify risks and opportunities and use them to adjust theirstrategies. For example, in 2012, Microsoft implemented an internal carbon-pricing systemthat assigned responsibilities to each unit for their direct and indirect carbon emissions. In2020, Microsoft is doubling up on their efforts to mitigate emissions7, and aim, for example,to cut their carbon emissions, direct and the entire supply chain’s, by more than half by 2030.In July 2020, Microsoft will start phasing in their current internal carbon tax of $15/metricton, to cover all Scope 1 (direct and on-site), 2 (indirect from energy usage) and 3 (otherindirect) emissions. Moreover, as clarified by Microsoft, “Unlike some other companies, ourinternal carbon tax isn’t a ‘shadow fee’ that is calculated but not charged. Our fee is paidby each division in our business based on its carbon emissions, and the funds are used topay for sustainability improvements”. Thus, our essay can also be viewed as modelling thechallenges and opportunities facing firms such as Microsoft, that aim to implement effectiveinternal carbon pricing in their supply chains to achieve sustainability objectives and togenerate funds for sustainability projects.We adopt a cooperative game theory methodology to derive a fair and transparent schemefor apportioning the total GHG emissions in the supply chain, which is shown to incentivizefirms to exert, in some sense, optimal abatement efforts to reduce their pollution. Indeed,we examine the problem of apportioning emission responsibility in supply chains from threedifferent and complementary perspectives. Firstly, we consider the application of cooperativegame theory methodology to our setting, and in particular, the Shapley value, a commonlyused allocation method. We then proceed to justify its suitability as an allocation mechanismin our context. In particular, we show that it belongs to the core of an associated cooper-ative game and, additionally, it is easy to compute (Theorem 2.1). As such, it overcomesthe main drawback of the Shapley value for general cooperative games, stemming from itscomputational intractability in many cases. Secondly, we consider the incentives for emissionabatement point of view, bearing in mind that Caro et al. (2013) showed that footprint-balanced allocation rules, i.e. rules that allocate precisely the entire pollution among thesupply chain members, in general, cannot achieve first-best emission reduction efforts. Fol-lowing their line of enquiry, we consider situations when footprint balance might be a naturalrequirement and are able to show that when the pollution abatement cost functions of thefirms are private information, as is typically the case, the Shapley value incentivizes suppliersto exert pollution abatement efforts that, among all footprint-balanced allocation schemes,minimize the maximum deviation from the socially optimal pollution level (Theorem 2.4).Thirdly, we consider some potentially desirable properties that a pollution responsibility al-location mechanism should satisfy and discuss their implications on supply chain welfare7https://blogs.microsoft.com/blog/2020/01/16/microsoft-will-be-carbon-negative-by-2030/7and implementation. We then demonstrate that the Shapley value is the unique allocationmechanism satisfying these properties (Theorem 2.6).Finally, in this essay, we assume that the GHG emissions from all processes in the supplychain are known. We acknowledge, though, that there are numerous difficulties involved incalculating GHG emissions from all supply chain members. Nevertheless, consistent attemptsare being made by firms to measure GHG emissions in their supply chains. Indeed, it is gen-erally suggested that firms should follow the Corporate Accounting and Reporting Standardby the GHG Protocol8, which clarifies the accounting methodology, and also provides exam-ples of multiple firms, such as the Ford Motor Company, that have successfully implementedtheir emissions accounting procedures. It should be further noted in that regard that it wasalready reported several years ago (CDP 2011), that 75 multinational companies, such asWalmart, Dell, Amazon, Ford and Vivendi, have inquired with nearly 8,000 of their suppliersabout their carbon emissions9. We also note that, for instance, Apple provides environmentalreports for their products10 which detail GHG emissions from different stages in a product’slifecycle, Timberland provides “green index” for their products,11 which details GHG emis-sions, chemicals used, and resource consumption, and the Innovation Center for U.S. Dairyprovides emissions for fluid milk and other dairy products. Good illustrative examples of cal-culating the carbon footprint at different parts in the supply chain are provided, for example,by the New Belgium Brewing Company for a 6-pack of their Fat Tire Amber Ale12 and byLevi’s and their 501 jeans13.The plan of the essay is as follows. In §2.2, we provide a brief literature review. In §2.3,we present our two-stage model and adopt a cooperative game-theoretic approach for thesecond-stage supply chain emission responsibility apportionment, to be referred to as theGREEN game. In §2.4, we consider the emission abatement incentives offered to the firms inthe first-stage, in a setting wherein the abatement costs are private information to the firms,and reveal the ability of the Shapley allocation to incentivize suppliers to exert, in some sense,optimal abatement efforts. In §2.5, we present some additional contextual desirable propertiessatisfied by the Shapley allocation, which are then used to develop two characterizations forthe Shapley mechanism to allocate emission responsibilities in supply chains. We perform acase study in §2.6 on the Walmart-Nautica jeans supply chain to contextualize our results.Finally, some concluding remarks are provided in §2.7. All proofs are presented in AppendixA.8https://ghgprotocol.org/corporate-standard9http://www.prnewswire.com/news-releases/companies-blind-to-climate-risks-in-half-their-supply-chains-finds-largest-global-study-300209209.html10http://www.apple.com/environment/reports/11http://greenindex.timberland.com12http://www.newbelgium.com/Files/the-carbon-footprint-of-fat-tire-amber-ale-2008-public-dist-rfs.pdf13http://levistrauss.com/wp-content/uploads/2015/03/Full-LCA-Results-Deck-FINAL.pdf82.2. Literature ReviewOur work is broadly related to two streams of literature. Firstly, there is a growing areaof study concerning sustainable supply chain management, and in particular, supply chainemission accounting and apportioning of shared emissions. Gallego and Lenzen (2005) areprimarily concerned with allocations of GHG emission responsibilities which are footprintbalanced. Their non-game-theoretic model has some features in common with our modellingframework. Specifically, somewhat similar to us, they suggest that GHG emission responsibil-ities should be shared among all supply chain members who have directly or indirectly createdthese emissions, and it can be shown that their allocations belong to the core of our GREENgame. Plambeck (2012) elaborates on some of the challenges facing firms that try to reducetheir GHG emissions through operations and supply chain management, Sunar and Plambeck(2013) investigate three allocation methods of carbon emissions among co-products, Benjaa-far et al. (2013) study the potential synergies and emission reductions from cooperation ina supply chain (see also Chen et al. 2019) and Corbett and DeCroix (2001), and Corbett etal. (2005) study shared-savings contracts in supply chains and their environmental impact.Caro et al. (2013) study a similar process-based model of joint production of GHGemissions in a supply chain wherein the total emissions can be decomposed into processes,and each process possibly influenced by a number of firms, and focus on the incentivesinduced by emission allocation mechanisms. Their modelling framework for identifying jointresponsibility is identical to ours and from an emission abatement incentives perspective,our approach to induce optimal abating efforts by firms in a supply chain can be viewed ascomplementary to that of Caro et al. (2013). Specifically, when a central planner allocatesemissions to individual firms in the supply chain and imposes a cost on them proportional tothe emissions allocated, they find that even if the carbon tax is the true social cost of carbon,emissions need to be over-allocated to induce optimal effort levels. However, as noted bythe authors, while double counting may be feasible to implement in vertically integratedfirms, “regulators and supply chains are unlikely to implement incentive mechanisms basedon extensive double counting”. In fact, to avoid double counting, the GHG Protocol advisesthat “companies should take care to identify and exclude from reporting any Scope 2 or Scope3 emissions that are also reported as Scope 1 emissions by other facilities, business units, orcompanies included in the emissions inventory consolidation.”We therefore address the complementary question and investigate the impact on emissionabating efforts of allocation rules which, by contrast, are restricted to be footprint-balanced.Specifically, we show that when firms’ abating cost functions are private information, then,restricted to footprint-balanced linear allocation rules, the Shapley value allocation inducesabating efforts which minimize the maximum deviation from the socially optimal pollution9level (Theorem 2.4).Secondly, we also contribute to the literature on cooperative game theory and its appli-cations in operations management. Cooperative game theory finds applications in severalallocation problems in supply chains (see Nagarajan and Sosˇic´ 2008, for a review). In par-ticular, the Shapley value has been applied as a profit or cost-sharing mechanism in tran-shipment (e.g., Granot and Sosˇic´ 2003, and Sosˇic´ 2006), inventory pooling (Kemahliog˘lu-Ziyaand Bartholdi 2011) and information sharing in supply chains (Leng and Parlar 2009).Our work is also related to a branch of the game-theoretic literature concerned withcost allocation problems on graphs. Indeed, our GREEN game model can be shown to bea generalization of the tree game model (Megiddo 1978), which in turn is an extension ofthe airport game, e.g., Littlechild and Owen (1973), wherein airport landing fees have to beallocated among airlines using a common runway. The class of highway games (e.g., C¸ifc¸iet al. 2010), wherein players are responsible for the cost associated with an arbitrary butcontiguous set of arcs in a weakly acyclic graph, can also be viewed as a generalization ofairport games.Finally, we note that our work is also related to the extensive literature on carbon borderadjustments in environmental economics (Eyland and Zaccour 2014, Larch and Wanner 2017,Bo¨hringer et al. 2015, Kortum and Weisbach 2017). The practical administrative issuespertaining to carbon border adjustments addressed in this stream of literature such as the(i) difficulties associated with estimating the embodied emissions in supply chain trade, (ii)the cost of obtaining this information from suppliers, and (iii) the possibility of suppliermisrepresentation, also concern our work.2.3. The GREEN Game ModelWe consider a supply chain consisting of several firms, such as suppliers, manufacturers andassemblers, who are cooperating in the joint production of a final product or products. Wemodel joint production in the supply chain as in Caro et al. (2013) and Battaglini (2006).We denote the set of firms in the supply chain by N = {1, . . . , n}, and M = {1, . . . ,m} isthe set of distinct processes in the supply chain. Let f = [f1, . . . , fm] denote the total supplychain carbon footprint vector consisting of the emissions associated with all processes in thesupply chain. The carbon emission, fj , at each process j can be jointly influenced by theactions undertaken by some subset of firms N j ⊆ N . For example, the emissions at thetransportation stage in a supply chain will be directly influenced by the operational decisionsmade by the distributor, but could also be lowered by an assembler, who is packaging theproducts more efficiently. We consider a firm i to be directly or indirectly responsible for thepollution at a process j if its actions could influence the emissions, fj . Following Caro et al.10(2013), we therefore represent the responsibilities of the firms for the pollution of the variousprocesses in the supply chain by a (0, 1)-matrix, B = (bi,j), for i ∈ N and j ∈ M , wherebi,j = 1 for i ∈ N and j ∈M , if and only if i ∈ N j .We suppose that the supply chain is operating under a carbon tax regime wherein aregulator levies a carbon penalty denoted by pS > 0 per ton of carbon emissions in the supplychain. Further, we assume that the supply chain leader, such as Walmart, is motivated toreduce emissions in their supply chains. The supply chain leader strives to do so by leveragingits knowledge reflected by the matrix B, about the joint responsibilities for pollution in thesupply chain. The supply chain leader aims to identify a pollution allocation rule to apportionthe total emissions,∑j∈Mfj , of the supply chain, in a manner which leverages its insight aboutjoint pollution responsibilities, so as to incentivize firms to take suitable actions to reducethe total supply chain emissions. Formally, a pollution allocation rule φ is defined on theset of firms N , set of processes M , and the responsibility matrix B. Then, the allocationrule φ is a function φ(B, f) which allocates to each firm, i, its total pollution responsibility,φi = φi(B, f), such thatn∑i=1φi =m∑j=1fj .The supply chain leader in Caro et al. (2013) is also assumed to be motivated by en-vironmental concerns. However, in their model, the supply chain leader voluntarily decidesto offset the supply chain emissions and then can, via payments, incentivize supply chainpartners to reduce their emissions. In contrast, in our model, the role of the supply chainleader is more limited. Its objective continues to be achieving lower supply chain emissions.However, it aims to do so by leveraging its knowledge about the joint production of pollution,while redistributing the total carbon tax burden on the supply chain.Our model can be interpreted as a two-stage model with the following sequence of decisionsin each stage:Stage 1: Each firm i in the supply chain exerts efforts towards reducing emissions, fj , ofthose processes j that it can influence, i.e., i ∈ N j .Stage 2: The net supply chain emissions,∑j∈Mfj , are allocated amongst the supply chainfirms according to the predetermined allocation mechanism, {φi}i∈N , such that∑i∈Nφi =∑j∈Mfj . Then, from each firm i, the corresponding carbon penalty, pSφi, is collected.The allocation mechanism adopted in the second-stage will naturally affect the incentivesoffered to firms to exert efforts to abate emissions in the first stage. In the remainder ofthis section, we therefore, address the problem of allocating emissions to firms in the supplychain. To that end, we employ cooperative game theory methodology to formally considerthe allocation of the total supply chain emissions,∑j∈Mfj , among the constituent firms.112.3.1 Cooperative Game Definitions and ModelTo present our game-theoretic formulation, we first introduce some definitions and notation.A (cost) cooperative game in a characteristic function form is the pair (N, c), where N isthe set of players and c is the characteristic function such that for each S ⊆ N , c(S) is thecost that can be attributed to S. The core, C((N, c)), of a game (N, c) is one of the mostfundamental solution concepts. It consists of all vectors x = (x1, x2, . . . , xn) which allocatethe total cost, c(N), among all players in N such that no subset of players, S, is allocated morethan the cost, c(S). Formally, C((N, c)) = {x ∈ Rn : x(S) ≤ c(S),∀S ⊂ N, x(N) = c(N)},where x(S) =∑j∈S xj . The core of a game could be empty, and if non-empty, it usuallydoes not consist of a unique allocation vector. The characteristic function of a game (N, c)is said to be concave if c(S ∪ {i})− c(S) ≤ c(Q ∪ {i})− c(Q) for all i /∈ S and Q ⊆ S ⊆ N .The game (N, c) is said to be monotone if for all Q ⊆ S ⊆ N, c(Q) ≤ c(S), and is said tobe concave if its characteristic function, c, is concave. The core of a monotone game, if notempty, consists only of non-negative allocation vectors and the core of a concave game isnon-empty (Shapley 1971).We now specialize the above development to our particular context of apportioning emis-sions in a supply chain. The set of players, N , consists of all members of the supply chain,“costs” are replaced with “emissions”, and for a set of firms S, let bS,j = 1 if at least onefirm in S is responsible for the pollution of process j, i.e., if bi,j = 1 for some i ∈ S, and 0otherwise. Then, the total pollution, cG(i), that can be attributed, perhaps not exclusively,as the responsibility of player i is given by,cG(i) =∑j∈Mfjbi,j . (2.1)Similarly, the total pollution, cG(S), that can be attributed to a subset of firms, S, perhapsnot exclusively, is given by,cG(S) =∑j∈MfjbS,j . (2.2)Then, the total pollution that has to be allocated to all firms in the supply chain isgiven by cG(N). We refer to the pair, (N, cG), as the GHG Responsibility - Emissions andEnvironment (GREEN) game associated with the supply chain, where N is the set of players(i.e., firms), and the characteristic function14 cG(S) is as defined above for all subsets S of14Note that in GREEN games, as well as, e.g., airport games, highway games or related games such as thoseinduced by joint cleaning a polluted river, c(S) does not represent the “cost” that S would incur if it severedits cooperation with the rest of the players and acted alone, since the option of acting alone is not possible inthese situations. That is, e.g., the option of constructing a different runway or highway serving only S is notfeasible. In these situations, c(S) was chosen in the literature to represent, e.g., either the cost that S wouldincur if it acted alone, or the cost it would have incurred had it been able to act alone, or some agreed upon12N .Example 2.1. To clarify the above discussion, consider N = {1, 2, 3} to be the set of firmsin a three-player supply chain, M = {m1,m2,m3} to denote the set of processes, and f =[f1, f2, f3] corresponds to the supply chain carbon footprint vector over the processes. Supposethat while firms 2 and 3 are individually responsible for pollution at processes m2 and m3,respectively, all three firms can jointly influence the emissions of process m1. Therefore, theresponsibility matrix is given by, B = (bi,j), where, b1,1 = b2,1 = b3,1 = 1, b2,2 = b3,3 = 1,while the rest of the entries in B are all 0. Denote the GREEN game by (N, cG). Then,cG({1}) = f1, cG({2}) = cG({1, 2}) = f1 +f2, cG({3}) = cG({1, 3}) = f1 +f3, cG({1, 2, 3}) =cG({2, 3}) = f1 + f2 + f3.Proposition 2.1. The GREEN game (N, cG) is concave.Proposition 2.1 implies that the core of (N, cG) is non-empty. Further, it also impliesthat a commonly employed solution concept for general cooperative games, the Shapley value(Shapley 1953), belongs to the core.2.3.2 The Shapley AllocationThe Shapley value (Shapley 1953), Φ(c), of a cooperative game, (N, c), is the unique allocationwhich satisfies the following axioms:1. Symmetry: If players i and j are such that for each coalition S not containing i and j,c(S ∪ {i})− c(S) = c(S ∪ {j})− c(S), then Φi(c) = Φj(c).2. Null Player: If i is a null player, i.e., c(S ∪ {i}) = c(S) for all S ⊂ N , then Φi(c) = 0.3. Efficiency: ΣNΦi(c) = c(N).4. Additivity: Φ(c1 + c2) = Φ(c1) + Φ(c2) for any pair of cooperative games (N, c1) and(N, c2).It was shown by Shapley (1953) that (Φi(c)), given by (2.3) below, is the unique allocationrule which satisfies the above four axioms.Φi(c) =∑{S:i∈S}(|S| − 1)!(n− |S|)!n!(c(S)− c(S \ {i})). (2.3)upper bound for the cost that S should incur. In GREEN games, the value of c(S) is induced by desirableregulations that view firms responsible for the pollution they create either directly or indirectly, which, insome sense, is an upper bound for the responsibility that should be attributed to S.13Note that the Shapley allocation provides a direct link between players’ marginal contri-butions and their corresponding allocations. Young (1985) has provided an alternative ax-iomatization of the Shapley value wherein the additivity axiom is replaced with a compellingmonotonicity axiom. In general, the Shapley value is perceived as a fair and “justifiable”allocation method, and it is not surprising that it was extensively considered as an allocationmethod in a variety of settings, including, in the airport game previously mentioned, forgenerating airport landing fees (Littlechild and Owen 1973).We now provide a characterization of the Shapley value for GREEN games. We recallthat for each process, j, j ∈ M , N j denotes the set of firms that can affect the emissions ofprocess j, i.e., i ∈ N j if and only if bi,j = 1.Theorem 2.1. The allocation according to which the pollution, fj, of each process j isallocated equally among all firms in N j is the Shapley value of (N, cG).Remark 2.1. As noted previously, we assume that the emissions from all processes in thesupply chain are measurable, and our primary focus is on the “second stage” problem ofconstructing a fair allocation mechanism which accounts for direct and indirect pollutionresponsibilities. However, we observe that Theorem 1 implies that the Shapley allocation isdecomposable on the set of processes in the supply chain. This implies therefore that the lackof accurate information about emissions associated with certain processes in the supply chainshall not hinder the application of the Shapley allocation to the rest of the processes.By Theorem 2.1, the Shapley value of GREEN games is easy to compute and has a naturalfairness property. Indeed, it can be viewed as a “common-sense” allocation mechanism thatholds each firm equally responsible for the emissions of each process for which it is directly orindirectly responsible. Since, the abatement efforts exerted by the firms during the first-stageare typically non-verifiable and non-contractible, the Shapley allocation is only a function ofthe emissions themselves and not of the abatement efforts.In the next section, we investigate the first-stage abatement decisions induced by theadoption of the Shapley allocation in the second stage to apportion supply chain emissions.Specifically, we demonstrate that the “common-sense” solution motivates, in some sense,optimal abating efforts by firms to reduce pollution. It is interesting to note that theseresults only depend on the expression of the Shapley allocation, as given by Theorem 2.1,and are independent of the GREEN game formulation, which yielded this allocation.2.4. Footprint Balance and Emission Abatement IncentivesThe choice of allocation mechanism employed in the second stage of our model will clearlyinfluence the emission reduction efforts exerted by the firms in the first stage. As elaborated14previously, in the second stage, we implicitly restrict our attention to allocation mechanismsthat are footprint-balanced. Caro et al. (2013) demonstrate that footprint balanced allo-cation rules, in general, cannot achieve first-best emission reduction efforts. However, incertain situations footprint balancedness is an intrinsic constraint while designing a pollutionallocation mechanism. Accordingly, we investigate in this section the first-stage pollutionabatement incentives that can be generated by footprint balanced emission responsibilityallocations. Specifically, in Theorem 2.4 we prove that, under some assumptions on theabatement cost functions, the Shapley allocation rule induces suppliers to employ abatingefforts that minimize the maximum deviation from the socially optimal pollution level.As will be clarified subsequently, one approach to prove Theorem 2.4, which we presentin Appendix A, involves the application of the implicit function theorem. We note, however,that such an approach imposes some technical assumptions that could be difficult to verify,and which restrict the generality of the results derived. Therefore, we also present an alternateapproach to prove Theorem 2.4, involving fewer technical assumptions, by following, and tosome extent, extending the monotone comparative statics methods of Topkis (1978, 1998),and Milgrom and Roberts (1990). Our extension is of independent interest with potentialapplications in equilibrium analyses of other game theoretic models of supply chains.In the next subsection we develop the monotone comparative statics results which will besubsequently used to prove Theorem 2.4.2.4.1 Generalized Comparative StaticsIn the following discussion, we closely follow the notation and definitions of Topkis (1998) andJensen (2018). Consider an objective function u(x, t), where t ∈ T is a vector of parameters,x ∈ X ⊆ R is a single-dimensional decision variable, X is convex, and T is a convex subsetof a real vector space. Let G(t) denote the set of maximizers for the following optimizationproblem, and assume that all maxima are interior points in X,G(t) = arg maxx∈Xu(x, t). (2.4)A real-valued function f(x) with x ∈ X ⊆ R is quasi-concave in x if the level sets,Sα = {x : f(x) ≥ α}, are convex for all α ∈ R. The following definition by Jensen (2018)introduces the notion of quasi-concave differences.Definition 2.1. (Quasi-Concave Differences). The function u : X × T 7→ R is said toexhibit quasi-concave differences if for all δ > 0 in a neighbourhood of 0, u(x, t)− u(x− δ, t)is quasi-concave in (x, t).An intuitive understanding of a function u(x, t) that satisfies the quasi-concave differencesproperty is that the influence of the decision variable, x, on the function u, reduces as the15parameter t increases. For thrice differentiable functions, we refer the reader to Lemma 3 inJensen (2018) which provides a condition on the derivatives that characterizes quasi-concavedifferences. Let g(t) denote the greatest selection amongst the set of maximizers, G(t), i.e.,g(t) = sup G(t).Theorem 2.2. Let T be a convex subset of a real vector space and X ⊆ R be a convex subsetof reals. Then, if u(x, t) : X × T 7→ R exhibits quasi-concave differences, g : T 7→ R isconcave.The above theorem follows directly from Jensen (2018) who proves a more general result.However, for our purposes, it is sufficient to restrict our attention to the greatest maximizer,g(t), a single-dimensional real decision variable, x, and a constraint set, X, that is invariantwith respect to the parameter t. In the appendix, for the sake of completeness, we provide aproof of Theorem 2.2 drawing upon the results of Jensen (2018). The above result is remi-niscent of Topkis’ (1978) theorem which demonstrates monotonicity of the optimizer subjectto the objective function satisfying the closely related increasing differences propert, whereu(x, t) is said to possess the increasing differences property if for all δ > 0 in a neighbourhoodof 0, u(x, t) − u(x − δ, t) is increasing in t (Topkis 1978). Indeed, the main achievement ofJensen (2018) can be viewed as a second order extension of Topkis’ theorem.We now consider a collection of non-cooperative games, Γ(t) = (N,X, {ui(·, t) : i ∈ N}),that are parametrized by t ∈ T , where N denotes the set of all players, X is a compactand convex set of action vectors, and ui(x, t) corresponds to a continuous payoff function forplayer i given the action vector x ∈ X. For player i ∈ N , let Xi ⊂ R denote its own action set,and X−i correspond to the action set for the rest of the players in N\{i}. Γ(t) is said to bea supermodular game if for each player i ∈ N , Xi is a compact subset of R, and ui(xi, x−i, t)has increasing differences in (xi, x−i). These requirements imply that the action of a playeris complementary with the actions of other players (Topkis 1998). The monotonicity of theequilibrium actions for the game Γ(t) in t does not immediately follow from Topkis’ (1978)results on the monotonicity of optima. However, Milgrom and Roberts (1990) employ Topkis’theorem alongside fixed-point arguments to develop conditions on the parametrized space ofgames such that the extremal equilibria of Γ(t) are monotonic in t. We now provide ananalogous result characterizing sufficient conditions for the greatest equilibrium of Γ(t) to beconcave in t ∈ T .For parameter value t ∈ T , let x˜(t) = {x˜i(t) : i ∈ N} denote the greatest equilibriumaction vector of Γ(t). Following Definition 1, ui(xi, x−i, t) satisfies the quasi-concave differ-ences property if for all δ > 0 in the neighbourhood of 0, ui(xi, x−i, t) − ui(xi − δ, x−i, t) isquasi-concave in (xi, x−i, t).16Theorem 2.3. Suppose that Γ(t) = (N,X, {ui(·, t) : i ∈ N}) is a collection of supermodulargames parametrized by t ∈ T where T is a convex subset of a real vector space. Further, foreach player i ∈ N , suppose that ui(xi, x−i, t) satisfies the quasi-concave differences property.Assume that all equilibria of Γ(t) are interior for all t ∈ T . Then, the greatest equilibriumaction vector of Γ(t), x˜(t), is concave in t ∈ T .The above theorem states that for parametrized supermodular games that additionallysatisfy the quasi-concave differences property, the greatest equilibrium action vector is con-cave in the parameter. Theorem 2.3, much like its counterpart for optimization problems,Theorem 2.2 due to Jensen (2018), is of independent interest for economic modelling appli-cations and constitutes an important methodological contribution of this essay.2.4.2 Shapley Allocation and Abatement IncentivesLet Pi denote the set of processes in the supply chain whose pollution can be influenced byfirm i via the exertion of costly efforts. That is, process j ∈ Pi if and only if bi,j = 1. In thefirst-stage of our model, we allow the firms to exert costly pollution abatement efforts so asto jointly reduce pollution in the supply chain. Formally, each firm i can introduce emissionreduction efforts, eij ∈ [0, 1], towards process j ∈ M . For clarity, the efforts, eij , could alsocorrespond to indirect efforts and actions by firm i such as component design or packagingdecisions which affect the direct emissions of other firms in the supply chain.In contrast with the implicit treatment in §2.3 of the footprint of a process j, fj , asa constant scalar input, in this section, fj is considered to be a symmetric differentiabledecreasing function of the emission reduction efforts, fj({eij : i ∈ N j}) = fj(ej). Weassume that fj(ej) is submodular in ej , that is, for firms i, k ∈ N j , ∂2fj/∂eij∂ekj ≤ 0.This reflects the complementary nature of emission reduction efforts exerted by firms in thesupply chain. In addition, we assume that the first partial derivatives, ∂fj/∂eij , are convexin ej for i ∈ N j . The abatement cost incurred by a firm i towards exerting the effort, eij ,aij(eij) : [0, 1] → [0, A] is also assumed to be strictly increasing, convex and with a non-negative third derivative, that is, ∂aij/∂eij is convex. The commonly assumed model ofpollution abatement in the literature is of linear emission reduction with quadratic or cubicabatement costs (e.g., see Subramanian et al. 2007, and Parry and Toman 2002). We employsuch a cubic abatement cost model in our numerical analysis in §2.6.3, and it is easily seenthat these models satisfy all our assumptions.As noted by Caro et al. (2013), linear sharing rules are the only type of allocation rulesobserved in practice and, moreover, non-linear differentiable rules could be replaced by linearsharing rules which would lead to the same outcome in the decentralized pollution reductiongame (Bhattacharya and Lafontaine 1995). Therefore, we limit our attention in the second-17stage to only linear allocation rules, φ = {λij : i ∈ N, j ∈ M}, that are footprint balanced,given by∑i∈Njλijfj = fj and λij ≥ 0, for all processes j. In a decentralized supply chain,given the linear allocation rule φ, the first-stage emission reduction efforts exerted arise asan equilibrium of a non-cooperative game, G(φ), with each player optimizing its own payofffunction as follows, thereby ensuring incentive compatibility,{eφij : j ∈ Pi} = arg mineij∑j∈Piaij(eij) +∑j∈PipSλijfj(ej). (2.5)The social first-best pollution emissions value for the supply chain, f∗ =∑j∈Mfj(e∗j), isobtained by solving the following optimization problem15,e∗ = arg mine∑i∈N, j∈Piaij(eij) +∑j∈MpSfj(ej). (2.6)Given the linear allocation rule φ, let fφ =∑j∈Mfj(eφj ) be the supply chain emissionsupported by the greatest equilibrium of the decentralized game.16 The following propositionfollows immediately from Proposition 2 of Caro et al. (2013) and demonstrates that in supplychains with joint production of pollution, footprint balanced emission sharing rules cannotachieve first-best emission reduction efforts in the decentralized game, that is, fφ > f∗.Proposition 2.2. For supply chains with joint production of pollution, that is, if there existsj ∈M such that |N j | > 1, then, for all linear allocation rules φ, fφ > f∗.We therefore next address the question of identifying a unique best allocation mechanism,in terms of incentivizing emission reduction efforts, amongst the class of linear sharing ruleswhich are footprint balanced. Since the pollution abatement technologies available to a firmand the corresponding cost functions, aij , are typically private information17, the metricwe adopt to evaluate a footprint-balanced allocation is its worst-case performance over allpossible private abatement cost functions.Definition 2.2. (Loss of Efficiency and Worst-Case Loss of Efficiency).i. Loss of efficiency due to a sharing rule φ with a collective cost vector a is given byδ(φ,a) = fφ − f∗ > 0.ii. The worst-case loss of efficiency is defined as ∆(φ) = maxa∈Aδ(φ,a) for all i ∈ N , j ∈ Pi,where A is the space of functions satisfying the abatement cost assumptions.15As in Caro et al., (2013), we assume that abatement efforts, though costly, don’t affect the firms’ revenuesfrom their core operations.16If there are multiple equilibria, we take the one with the greatest efforts, i.e., the one minimizing the totalsupply chain emissions.17See, e.g., Malueg and Yates (2009), Ross (1999).18The parametrized first-stage non-cooperative game, G(φ), can be decomposed into |M |supermodular games. We then apply the results of §2.4.1 to prove that the equilibriumefforts eφ are concave in φ. We prove these results in Lemma A.2 in Appendix A. Thisallows us to derive the following central result which identifies the Shapley allocation as afootprint-balanced linear sharing rule that minimizes the worst-case loss of efficiency.Theorem 2.4. For every linear allocation rule φ that is different from the Shapley allocation,Φ, ∆(φ) ≥ ∆(Φ).In the absence of the tools developed in §2.4.1, the second-order comparative staticsneeded to obtain the above theorem can only be performed by invoking the implicit functiontheorem twice over. As Jensen (2018) notes, this in turn will imply that “a host of unnecessarytechnical assumptions must be imposed – so even when the implicit function theorem providessufficient conditions for concavity, these will not be the most general conditions”. Suchtechnical assumptions made to simplify the analysis shall render challenging the identificationof the most general conditions that drive the result. Indeed, in the appendix we provide analternate proof of Theorem 2.4 that solely relies on the implicit function theorem and thereforeneeds to employ additional restrictive separability assumptions.We further point out that the symmetry of the Shapley allocation, as embodied by theShapley’s symmetry axiom (Shapley 1953), is not the driver of Theorem 2.4, since thereare other allocation mechanisms that satisfy this symmetry axiom. Indeed, if the loss ofefficiency were to be measured with respect to the total social cost, instead of the sociallyoptimal supply chain emission level, then the worst-case loss of efficiency may no longer beminimized by the Shapley allocation.Finally, we demonstrate in Theorem 2.5 below that, for the Shapley allocation rule, Φ, thegap δ(Φ,a), between the supply chain emissions supported by the decentralized equilibrium,fΦ, and the social first-best supply chain emissions, f∗, is bounded.Theorem 2.5. Consider a supply chain that employs the Shapley allocation rule, Φ, as theemission apportionment mechanism. Let f0 denote the baseline emissions of the supply chain,that is, when firms do not exert emission abatement efforts. Then,δ(Φ,a)f0 − f∗ =fΦ − f∗f0 − f∗ ≤ 1−1maxj∈M|N j |Theorem 2.5 bounds the gap, δ(Φ,a), in terms of the extent of joint production of pollu-tion in the supply chain. Trivially, if there is no joint production of pollution in the supplychain, i.e., for each process in the supply chain, there exists a unique firm that can influenceits emissions, then the Shapley rule coincides with the total producer responsibility rule,19and achieves full efficiency. That is, δ(Φ,a) = 0. Further, in §2.6, we perform a numericalcomparative statics analysis and demonstrate that the efficiency gap, δ(Φ,a), is concave in-creasing in the prevailing carbon price pS . Additional related numerical illustrations are alsoprovided in §2.6.Remark 2.2. As previously mentioned in Footnote 15, following Caro et al. (2013), weassume that the revenue from core operations of the supply chain is unaffected. Then, supplychain profits are maximized when the total carbon penalty paid by the supply chain is mini-mized. Therefore, it follows from Theorem 2.4 that the Shapley allocation rule minimizes thecarbon penalty paid by the supply chain, and equivalently maximizes supply chain profits, ina worst-case sense. Similarly, the bounds obtained in Theorem 2.5 also translate into boundson the decentralized supply chain profits in relation to the first-best supply chain profits.2.5. Properties of the Shapley AllocationIn this section, we reveal that the Shapley allocation satisfies some additional properties thatare contextually desirable from welfare and implementation perspectives. In fact, we showthat it can be uniquely characterized by these properties, which provides a complementaryapproach to the problem of allocating emissions responsibility in a supply chain. Axiomati-zations characterize a proposed solution mechanism on the basis of a certain set of propertiesand, as such, clarify the domain of applicability, and the strengths and limitations of theproposed solution concepts. To the extent that these properties are viewed as desirable, theymake a more compelling case for the adoption of the proposed mechanism in the particularcontext. Axiomatic characterizations, such as Shapley’s (1953) original characterization ofthe Shapley value, have played a key role in the development of cooperative games solutionconcepts in the game-theoretic literature. In related contexts, such as airport games andhighway games, other axiomatizations of the Shapley value were developed, e.g., by Dubey(1982), Sudho¨lter and Zarzuelo (2017) and Rosenthal (2017).First, recall that f = [f1, f2, . . . , fm] denotes the total supply chain carbon footprintvector consisting of the pollution of all processes in the supply chain, and Pi denotes the setof processes that can be influenced by actions of firm i, i.e., j ∈ Pi iff bi,j = 1. Further, let P˜idenote the set of processes with non-zero pollution that i is responsible for. That is, j ∈ P˜i,iff bi,j = 1 and fj > 0. We recall that a pollution allocation rule φ is a function, φ(B, f),which allocates to each firm, i, its responsibility, φi = φi(B, f), towards the total pollutionsuch thatn∑i=1φi =m∑j=1fj . We now consider certain intuitive properties which could naturallybe expected from a pollution allocation rule. We also discuss their relevance in terms of thesupply chain welfare generated by the allocation rule and its implementation.20No Free Riding: For any firm i and footprints f ′ ≥ f , such that f ′j = fj for all processesj for which bi,j = 1, φi(f′) = φi(f).The no free riding property requires that if the total pollution increases, but for some firm,the pollution of the processes it is responsible for are unchanged, then the firm’s allocationremains the same. In other words, an increase in pollution allocation for a firm is justifiableonly if the pollution of the processes it has influence over increases. Equivalently, it alsoprevents free-riding of firm i on pollution abatement improvements by other firms on processesfirm i is not responsible for. Lange (2006) also discusses the negative effects of free-riding andnotes that preventing it improves the chances of cooperation in environmental agreements.Further, and most importantly, it can be easily seen that an allocation rule which does notsatisfy the no free riding property can be modified into an allocation rule that offers the sameemission reduction incentives to the firms in the supply chain at a strictly lower supply chaincost. Therefore, the supply chain welfare associated with a pollution allocation rule violatingthe no free riding property can always be improved upon.Process history independence: Let f ′ ≥ f and f˜ ′ ≥ f˜ be footprints such thatf ′j = fj and f˜′j = f˜j for all processes j ∈M\{k}, f ′k = f˜ ′k and fk = f˜k. Then, for any firm i,φi(f′)− φi(f) = φi(f˜ ′)− φi(f˜).Process history independence states that the change in responsibilities of the firms due toa change in pollution of any process is independent of the pollution levels of other processes.Process history independence emphasizes the ease of interpretation of an allocation rule. Itimplies that firms can find out the effect of an increase or decrease in the pollution level of aprocess independently of the pollution levels of other processes. Thus, it enhances the trans-parency of the effects of investment in pollution abatement technologies on the attributedemission responsibility. Further, and importantly, in a supply chain that is operating acrossmultiple time-periods, an allocation mechanism which is not process history independentwould incentivize firms to engage in manipulating or delaying the adoption of cleaner tech-nologies in their processes. Thus, process history independence also ensures that the firmsdo not engage in strategic gaming of technology adoption decisions.Disaggregation Invariance: Consider a supply chain with n firms, set of processesM , and a corresponding responsibility matrix B. Suppose firm i chooses to disaggregateand represent itself as firms i1 and i2, such that Pi1 ∪ Pi2 = Pi and Pi1 ∩ Pi2 = ∅. Thedisaggregated supply chain now has n + 1 firms, an identical set of processes M , and acorresponding responsibility matrix B′, with n + 1 rows, wherein row bi, corresponding torow i in B has been replaced with rows b′i1and b′i2in B′. Then, φ is said to be disaggregationinvariant if for a firm j 6= i, φj(B, f) = φj(B′, f), and φi1(B′, f) + φi2(B′, f) = φi(B, f).Invariance of a pollution responsibility allocation to disaggregation of the supply chain isdiscussed by Lenzen et al. (2007) and also by Rodrigues and Domingos (2008). They argue21that pollution responsibility allocations to firms should not change when a manufacturer,instead of selling directly, decides to disaggregate and sell via a distributor who creates noadditional pollution. A pollution allocation rule that is not invariant under disaggregationwould provide incentives for firms to resort to manipulation by de-merging while reportingemissions. Therefore, disaggregation invariance ensures a form of strategy-proofness of theallocation mechanism and assumes significance from an implementation perspective.It is easy to show that the Shapley allocation, Φ, satisfies all the above properties. Infact, coupled with the natural firm equivalence property, which requires that two firms thatare responsible for an identical set of polluting processes receive identical allocations,18 andfirm nullity, which states that a firm which is not responsible for any polluting process beallocated zero responsibility, we derive a unique characterization of the Shapley allocationprovided in Theorem 2.6. Firm equivalence is a fundamental equity principle that enhancesthe acceptability of a pollution responsibility allocation mechanism.Theorem 2.6. The Shapley allocation, Φ, is the unique footprint balanced pollution allocationrule which is uniquely characterized by each of the following sets of independent properties:i. Process history independence, firm equivalence, and firm nullity.ii. Disaggregation invariance, firm equivalence, and no free riding.Finally, we note that a similar axiomatic approach in the context of environmental re-sponsibilities is adopted by Rodrigues et al. (2006), who consider an input-output frameworkand impose six properties to derive a unique indicator of environmental responsibility. Morerecently, Kander et al. (2015) and Domingos et al. (2016) pursue this line of inquiry toallocate responsibilities to countries towards emissions arising from global trade.2.6. Case Study – Walmart’s Jeans Supply ChainsThere are a variety of reasons for firms to be concerned with GHG emissions arising fromtheir supply chains. While the financial impact of emission taxes in an increasing numberof regions might be a reason, it has also been established that consumers do value the envi-ronmental sustainability of brands (Luchs and Kumar 2015; Nielsen 2018). Since emissionsoccur throughout the supply chain, it can be useful for leaders to account for the emissionsfrom their supply chain members and identify opportunities for joint reduction of emissions.As elaborated in §2.1, Walmart is one of the companies that has embraced its responsibilityto protect the environment and reduce emissions in its vast supply chain. Since their ownoperations account for roughly only 10% of their total supply chain GHG emissions, Walmart18We note that firm equivalence is a weaker requirement than the classical axiom of symmetry in the originalaxiomatic characterization of the Shapley value.22has acknowledged the need to engage with their suppliers to realize a significant impact. Forthe purpose of this analysis, we focus on its apparels, and specifically, on its jeans brandsand their supply chains.Walmart offers a wide variety of jeans brands ranging across Levi Strauss & Co. (LS &Co.), Jordache, Lee, Wrangler, Democracy, Nautica, Gloria Vanderbilt and so on. We findconsiderable variation in the extent of sustainability initiatives undertaken by the brands.For instance, we were unable to find any public disclosure of information by Democracyand Nautica on their environmental performance. This does not necessarily imply that thesecompanies are not working with their supply chain members towards reducing their emissions,however, we do note that environmentally-conscious companies typically opt to share theirefforts and initiatives with the public. In that regard, we note that some consumers groupare recommending “no buy” for Nautica’s products in view of the lack of transparency oftheir sustainability initiatives.19Across the various jeans brands, LS & Co. appears to be the most concerned with theiroverall environmental impacts engaging in sustainability efforts on several fronts. In this casestudy, we focus on two of Walmarts immediate suppliers, LS & Co. and Nautica. Based onthe efforts undertaken by LS & Co. to reduce its supply chain emissions, we illustrate howWalmart can identify and assign indirect responsibilities to members in the Nautica supplychain. We then analyze the incentives and supply chain emission reductions achieved by theShapley mechanism.2.6.1 Levi Strauss’ & Co.’s Environmental InitiativesAccording to their 2018 Carbon Disclosure Project report20, LS & Co. is engaged with itssuppliers on different levels in efforts to reduce supply chain emissions. LS & Co. estimatesthat 99% of their total GHG emissions come from Scope 3 categories, and intends to workclosely with their suppliers to establish targets for emission reductions and share practicesaround energy efficiency. In 2017, they engaged about 37% of their suppliers, focusing onthose supplying a high volume of products and with significant potential for improvementopportunities. They collect suppliers’ energy use and GHG emissions data annually (throughthe Sustainable Apparel Coalition’s Higg Facility Environmental Module), and use this datafor calculation of their Scope 3 emissions and to evaluate suppliers’ engagement strategy. LS& Co. has committed to reduce their Scope 1 and Scope 2 emissions by 90%, and to reduce40% of the emissions across their supply chain by 2025 from a 2016 baseline. We now describesome of their initiatives in greater detail.Material Acquisition. Agricultural emissions from cotton farming is intimately linked19See, for example, https://rankabrand.org/casual-clothing/Nautica/detailed-report20https://www.levistrauss.com/wp-content/uploads/2018/03/Levi-Strauss-Annual-Report-2017.pdf23with water usage, and contributes substantially to the environmental footprint of LS & Co.They found that nearly 70% of water withdrawal occurs in the fiber phase (e.g., cottongrowing) while 6% occurs in the fabric production phase (manufacturing). As a result,they are engaging with cotton farmers through participation in the Better Cotton Initiative(BCI), an organization that trains farmers to adopt cotton production practices which useless water, and which also yields as a result other ancillary benefits of reducing pesticide andfertilizer usage, preserving biodiversity, and improving soil health and labor standards. BCIfarmers use up to 18% less water than non-BCI farmers in comparable locations. LS & Co.is also exploring innovative approaches to use recycled cotton, as they estimate that jeansmanufactured with at least 15% recycled cotton saves as much water as that consumed inthe entire manufacturing process. In 2017, LS & Co. sourced 34% of their total cotton (90%of their products are cotton-based) through BCI, with the goal of using 100% sustainablecotton through sources such as BCI by 2020. LS & Co. estimates costs invested in the BetterCotton Initiative at around $85,000.Manufacturing. LS & Co. has begun working with some manufacturers to implementtheir recycle and reuse standards, which outline how garment facilities can safely implementprocesses and equipment within their facilities without compromising product quality andsafety. LS & Co. has partnered with the Natural Resource Defense Council (NRDC) on theClean by Design Program, an initiative to reduce the environmental impact of textile millsin China. Six textile mills in China that supply fabric to LS & Co. participated in thisprogram, achieving a total savings of 57,465 tons of steam and 2.62 million kWh/year over afive-year period.LS & Co. is collaborating with the International Finance Corporation (IFC), the financingarm of the World Bank, to provide access to advisory services and low-cost financing tosuppliers who wish to invest in reducing their energy, emissions, and water footprint, butneed technical support or capital to do it. In 2017, LS & Co. started a pilot program withthe IFC’s Partnership for Cleaner Textile (PaCT) program, whereby LS & Co. is workingwith six of their manufacturers and is covering their cost to undergo a renewable energyassessment. If the on-site renewable investment is feasible, LS & Co. collaborates with IFCon a financing model which provides access to capital for sustainability investments. In lessthen a year, participating suppliers reduced their GHG emissions by an average of 13% andtheir energy use by an average of 22%. LS & Co. plans to expand the PaCT programto more factories and fabric mills, which have a larger carbon footprint than their currentmanufacturing facilities. In 2018, they made a plan to include mills in India, Pakistan, andMexico, with the goal of engaging all wet processing suppliers globally within the next fiveyears. LS & Co. estimate that they will invest around $2,400,000 in more efficient productionprocesses at key supplier locations through the PaCT program in period 2018-2023.24Evidently, as can be seen from the above discussion, LS & Co. is not only making effortsto improve their own carbon footprint. Indeed, they are also actively engaging their suppliersto help them improve their environmental performance, which is in line with Walmart’s visionof reducing emissions across their entire supply chain.2.6.2 Walmart-Nautica Supply ChainAs discussed above, it appears that there are several suppliers of Walmart that are notsufficiently concerned with either their own sustainability or that of their respective supplychains. A possible way to incentivize them to do so, as modelled in this essay, is to holdthem jointly responsible for emissions of their upstream partners whose emissions they caninfluence. Given the successful efforts by LS & Co. to address sustainability issues in itssupply chain, it is reasonable to assume that Walmart could expect its other major suppliers tofollow suit. Huang et al. (2019), in fact, find that such environmental supply chain governanceinvolving monitoring and knowledge sharing across suppliers can lead to significant emissionsreductions for firms as well as suppliers. Therefore, if Walmart’s immediate supplier, say,Nautica, is held jointly responsible for the emissions of some of its supply chain members,then Nautica would be incentivized to work with its suppliers to help them reduce theirfootprint. For instance, similarly to LS & Co., Nautica can help provide funding or expertiseassistance to their mills that want to reduce their energy emissions. It is in this context thatthe allocation scheme proposed in this work can be employed as a transparent mechanismthat can suitably incentivize firms to reduce their joint emissions.LS & Co. created a detailed LCA report (LS & Co. 2015) for the supply chain of Levi’s501 R©jeans for the production year 2012. We present a summary of their results in Table 2.1and assume that the emission values are appropriate representative estimates for the emissionsthat a pair of Nautica jeans generates throughout its different life cycle stages. Indeed, toconfirm the robustness of the emissions data, we further checked an apparel industry-widestudy, Zeller et al. (2017), which included 159 life cycle inventories in compliance withISO 14044. While there was a minor discrepancy between Levi’s and Zeller et al.’s (2017)estimates since the latter included accessories such as leather patches while the former didnot, overall, the data is in line with the apparel industry-wide, category-specific study ofZeller et al. (2017).From Table 2.1, we observe that across the entire life cycle, from material acquisition toend of life, the manufacturing and consumer use stages each contributes 9 kg CO2E and 12.5kg CO2E of the total emissions (33.4 kg CO2E). In comparison, packaging and end of lifeaccount for a much smaller fraction of the emissions respectively.25Raw Materials Manufacturing Assembly Packaging Transportation Consumer Use End of Life TotalStage 1 2 3 4 5 6 7 NAJoint Responsibility 1, 3 2, 3 3 4 5 NA NA NAEmissions (kg CO2E) 2.9 9 2.6 1.7 3.8 12.5 0.9 33.4Percentage ‡ 14.5% 45.0% 13.0% 8.5% 19.0% NA NA 100%Table 2.1: GHG emissions through the cycle of a pair of jeans.‡Percentage is calculated with respect to the scope including stages 1 to 5 only.Naturally, in practice, the processes and the resulting emissions may need to be allocatedat a more granular level than what is represented in Table 2.1. That is, to implementthe carbon emissions allocation scheme in practice, it may be necessary to break down thevarious processes to finer sub-processes, and allocate appropriate pollution responsibilitiesfor the sub-processes using the methodology developed above.Now, for the purpose of our subsequent analysis, we restrict the scope of the supplychain to Stages 1 to 5. This linear supply chain is responsible for a total of 20 kg CO2E ofemissions. We also note that Nautica has direct control over the assembly stages. In linewith the efforts undertaken by LS & Co., suppose that Walmart also holds Nautica jointlyresponsible for emissions from material acquisition and manufacturing. Our objective is toapply the emissions allocation rule developed in this essay to incentivize the firms to exertjoint emission reduction efforts across the supply chain.2.6.3 Numerical AnalysisFor the five-stage Nautica supply chain described above, given the joint responsibilities iden-tified from the knowledge of successful initiatives by LS & Co., it follows from Theorem 2.1that the Shapley allocation rule will split in half the emissions of Stages 1 and 2 between theupstream supply chain member and Nautica. Further, the emissions of the rest of the stageswill be solely attributed to the corresponding supply chain firm by the Shapley rule. Weconsider the supply chain to be operating under a uniform carbon price of pS = 3¢/kgCO2E.This is reflective of carbon tax rates in Canada and is close to the estimated social cost ofcarbon in 2015 (Nordhaus 2015).Material Acquisition. We consider a commonly assumed model of joint pollution abate-ment in the literature, of a linear and separable emission reduction with cubic abatementcosts, to analyze the abatement incentives offered by the Shapley allocation. We note thatour model satisfies the assumptions of §2.4.2 as well as the more restrictive assumptionson the abatement costs discussed in the appendix. Suppose that the emissions, f1, atStage 1 of the supply chain per unit of product (i.e., for each pair of jeans), is given byf1(e11, e31) = f01 − α1(e11 + e31), where f01 = 2.9 denotes the baseline emissions of Stage 1(refer to Table 2.1) and we assume α1 = 1. The assumption of perfect substitutability of26efforts by firms 1 and 3 is reflective of the substitutability of monetary investments in recy-cling. We also performed the numerical analysis with non-separable joint emission productionfunctions and the results were qualitatively similar. The corresponding abatement costs aredenoted by a11(e11) = β11eh11 and a31(e31) = β31eh31 with h = 3. The precise values of the costparameters β11 and β31 are private information, as modelled in §2.4. For the purpose of ournumerical analysis, we assume the supply chain leader’s information about the distributionof these private cost parameters is that β11, β31 ∈ [10, 15].Figure 2.1: Worst-case loss of efficiency, ∆(φ) (units: kgCO2E), in theNautica-Walmart supply chain is minimized at the Shapley allocation rule, Φ(left panel). The efficiency gap, δ(Φ,a) (units: kgCO2E), is concave increasingin the carbon price, pS (units: ¢/kgCO2E) (right panel). The ratio of first-bestemissions to the emissions supported in equilibrium by the Shapley mechanism,f∗1,2/fΦ1,2, as a function of the carbon price, pS (bottom panel).Manufacturing. Suppose that the emissions, f2, at Stage 2 of the supply chain for eachpair of jeans, is given by f2(e22, e32) = f02 − α2(e22 + e32), where f02 = 9 denotes the baselineemissions of Stage 2 and assume α2 = 1. The corresponding abatement costs can be denotedby a22(e22) = β22eh22 and a32(e32) = β32eh32 with h = 3. As above, we also tested non-separable joint emission production functions and the results were qualitatively similar. We27again note that the precise values of the cost parameters β22 and β32 are private informationand, we assume the supply chain leader only knows that β22, β32 ∈ [30, 45].Any linear allocation rule is uniquely parametrized21 by the fraction of pollution at Stage1, that firm 1 is allocated responsibility for, denoted by λ1, and the fraction of pollutionat Stage 2, that firm 2 is allocated responsibility for, denoted by λ2. For all combinationsof (λ1, λ2) such that 0 ≤ λ1, λ2 ≤ 1 and a given realization of the cost parameters, theequilibrium joint efforts exerted by firms in the supply chain towards reducing their emissionscan be computed from the equation (2.5). Then, the computation of the first-best reductionin emissions, given by (2.6), allows us to identify the worst-case loss of efficiency, ∆(φ) =maxaij∈Aδ(φ,a), where A is the space of possible realizations of the private cost functions. Theleft panel of Figure 2.1 is a surface plot of the worst-case loss of efficiency, ∆(φ), over allpossible linear allocation rules, φ, in the supply chain. It is seen that ∆(φ) is minimizedprecisely at the Shapley allocation rule as predicted by Theorem 2.4. Further, we set β11 =β31 = 10 and β22 = β32 = 30, and in the right panel of Figure 2.1, we plot the loss in efficiencyassociated with the Shapley allocation mechanism, i.e., the efficiency gap δ(Φ,a) as a functionof the prevailing carbon price pS . We observe that the efficiency gap is concave increasing inthe carbon price pS . In the bottom panel of Figure 2.1, we plot an alternate measure of theeffectiveness of the allocation mechanism given by f∗1,2/fΦ1,2, where f∗1,2 and fΦ1,2 correspond tothe combined emissions of the material acquisition and manufacturing stages of the supplychain under the first-best setting and under the Shapley mechanism, respectively. We focuson the first two processes because the first-best emissions and the emissions supported by theShapley mechanism across the other three processes are identical. Finally, we note that whenthe carbon price pS = 3¢/kgCO2E, the emissions of the processes 1 and 2 in the first-bestscenario correspond, respectively, to 2.2675 kgCO2E and 8.6348 kgCO2E as compared tothe baseline emissions of 2.9 kgCO2E and 9 kgCO2E, respectively. The Shapley allocationmechanism results in emissions of 2.4527 kgCO2E and 8.7418 kgCO2E for the two processes.That is, f01,2 = f01 + f02 = 11.9 kgCO2E, fΦ1,2 = 11.1945 kgCO2E and f∗1,2 = 10.9023 kgCO2Eand therefore, the Shapley mechanism captures 70.7% of the emissions reduction from thebaseline mechanism as compared to the first-best outcome.2.7. Concluding RemarksWe provide in this essay a methodological contribution to aid in rationalizing CO2 emissionsin supply chains, which account for more than 20% of global GHG emissions. We considersupply chains with dominant leaders who are motivated to reduce pollution in their supply21Without loss of generality, we implicitly assume that the allocation rules satisfy the “no-free riding”property.28chains, that either operate in an environment in which a carbon tax is in effect, or whoimplement an internal carbon-pricing system. We propose that the supply chain leaders canleverage their knowledge on the interrelated sources of pollution in their supply chains, and re-allocate emissions within the supply chain in a footprint-balanced manner. This is equivalentto redistributing the carbon tax burden across the supply chain, and is carried out by thesupply chain leaders so as to incentivize firms to exert efforts to jointly reduce their “indirect”emissions. We formulate the re-apportionment problem as a cooperative game, referred toas the GREEN game, and propose the Shapley value of the GREEN game as a scheme toallocate responsibilities for total emissions in the supply chain. We show that the Shapleyallocation incentivizes abatement efforts that are optimal, in a well-defined sense, when theabatement costs are private information. Finally, we provide a proof of concept by carryingout a case study of the Walmart-Nautica jeans supply chain wherein we contextualize ourresults.In view of the reluctance of suppliers to share information about their GHG emissions(see, e.g., Jira and Toffel 2013), it is important to note that the Shapley value of the GREENgame is both transparent and fair. It is shown to possess some contextual desirable propertieswith implications for welfare and implementation. Methodologically, we also exemplify theutility of an axiomatic development to identify desirable cost sharing mechanisms in supplychains.Future WorkWe note that in our model, as in Caro et al. (2013), firms were assigned joint responsibilitiesfor GHG emissions occuring at other firms in the supply chain exclusively for the reason thatthey can take action to reduce, perhaps at a cost, emissions at those firms. However, respon-sibilities could possibly stem from other considerations. For example, it may be desirable tohold energy producing firms indirectly responsible for the downstream pollution impact oftheir projects, or hold firms responsible for the direct emissions at their upstream suppliers,or require consumers to internalize the cost of the GHG pollution in the supply chains whichare used to produce the products they consume.Indeed, numerous countries use GHG accounting methodologies that make them respon-sible only for the emissions they create within their own borders. For instance, accordingto Porter (2013), about a fifth of China’s emissions are for products consumed outside itsborders, and while Europe emitted only 3.6 billion metric tons of CO2 in 2011, 4.8 billiontons of CO2 were created to make the products Europeans consumed in that year. Natu-rally, our approach, and in particular, the Shapley allocation, could be applied to inform theanalysis and derive footprint-balanced emission responsibility allocation schemes in globalsupply chains or, in general, in instances where the assignment of pollution responsibilities29stem from different reasons.We also note that the problem of incentivizing firms to increase emission abatement effortsin supply chains can be studied in a variety of other related or more general settings. In thiswork, we assume a fixed supply chain structure and we do not model endogeneity of priceswithin the supply chain. Indeed, to better understand the performance of footprint-balancedemission allocation mechanisms, such as the Shapley allocation, it is important to find theireffectiveness to reduce emissions in a more general setting that relaxes these assumptions.Extensions of our work could also incorporate stochasticity in emission output, or imperfector partial monitoring, or repeated interactions among the firms in the supply chain. Finally,a key methodological contribution in this essay is Theorem 2.3, which provides conditionsensuring concavity of equilibrium actions in parametrized non-cooperative games, therebygeneralizing the results of Milgrom and Roberts (1990). We anticipate the result to findseveral applications in disparate domains.30Chapter 3Consistent Allocation of EmissionResponsibility in Fossil Fuel Supply Chains3.1. Introduction and Literature ReviewWith rising awareness on the global impacts of greenhouse gases, countries across the worldare adopting strategies to curb and regulate their carbon emissions. Indeed, fossil fuel burningaccounts for close to 75% of the increase in global CO2 levels in the past 20 years (IPCC2014), and while the share of renewable energy sources is growing, fossil fuels continue todominate, contributing to approximately 65% of electricity generation and powering over 90%of transportation in the United States (EPA 2016).In a globalized world, fossil fuel supply chains are increasingly complex and spread acrossseveral jurisdictions. Fossil fuels are often extracted, refined and ultimately burnt in dif-ferent countries. Accounting and assigning responsibility for these emissions is an essentialcomponent of any integrated climate action program. Harrison (2015) notes that the UnitedNations’ Framework Convention on Climate Change (UNFCCC) only assigns responsibilityfor emissions that occur within a country’s borders. Thus, neither is an exporter of fossilfuels assigned any responsibility towards the inevitable emissions generated while they areburnt, nor is the importer assigned any responsibility towards the extraction emissions asso-ciated with the fossil fuel. Environmental NGOs and activists such as Monbiot (2015) alsoargue for abandoning a wholly consumption-focused approach and to move towards assigningresponsibility to both the producers and consumers of fossil fuels.Although a significant fraction of carbon emissions in the fossil fuel supply chain arisesdownstream during the consumption stage, the upstream stages of extraction and refiningoften contribute close to 20% of the total supply chain emissions (OSM 2019). Unconven-tional petroleum deposits such as the Canadian oil sands typically entail higher upstream31emissions during the extraction, transportation of the denser bitumen through pipelines, andthe refining stages (Charpentier et al. 2009). In most countries, only the direct emissionsof firms have been regulated (Oh et al. 2015). However, acknowledging the necessity ofassigning extended responsibility, the Canadian federal government announced on January27, 2016 that the energy regulator of Canada, National Energy Board (NEB), would factorin upstream emissions during the environmental impact assessment stage for proposed en-ergy projects (Canada 2016). Upstream emissions are defined as emissions associated with“all industrial activities from the point of resource extraction to the project under review”(Canada 2016). This could have significant implications for several pipeline projects acrossCanada that transport crude oil or refined products to refineries and shipping terminals. Theupstream emissions attributable to a proposed project could be compared against a rejec-tion threshold level of emissions whereby the regulator, NEB, sets a predetermined level ofupstream emissions beyond which the project will be rejected or the regulator could insteadrequire the firm to offset some or all of the associated upstream emissions (Schaufele 2016).A rejection threshold policy or offset requirements that take into account all upstreamemissions of an energy project would have to be calibrated, depending on the stage of thesupply chain the project is situated at, otherwise it risks inducing distortionary effects byfavouring upstream energy projects over more downstream ones. This is primarily a conse-quence of double counting by attributing to each entity in the supply chain all associatedupstream emissions. Another drawback of such a double counting method is that with acarbon offset program, it opens up the possibility of multiple parties claiming an offset forthe same reduction in carbon emissions as part of their mitigation efforts, damaging thecredibility of carbon offsetting (Schneider et al. 2014).Our central objective is to develop a consistent accounting and implementation mecha-nism to allocate responsibility for greenhouse gas emissions in fossil fuel supply chains thatpotentially span multiple legal jurisdictions, while avoiding double counting and remainingconcordant with the principle of upstream emission responsibility. We adopt a cooperative-game theoretic model of a fossil fuel supply chain represented by a directed tree, in which theplayers (or nodes) correspond to the extractors, distributors, refineries and end-consumers,and propose the nucleolus of the associated cooperative game as a mechanism to attributeupstream emission responsibilities in fossil fuel supply chains. We further evaluate and justifyour proposed allocation mechanism along five broad criteria that the Government of Canada(2005) has identified as yardsticks to assess environmental policy proposals: (i) environmen-tal effectiveness, (ii) fiscal impact, (iii) economic efficiency, (iv) fairness, and (v) simplicityof administration.32Review of Related LiteratureWe draw upon and contribute to two main streams of literature: emissions accounting insupply chains, and the application of cooperative game theory in supply chain management.In the environmental literature, several methods to allocate shared emission responsibilityhave been proposed by, e.g., Gallego and Lenzen (2005) and Lenzen et al. (2007). Theirnon-game theoretic models share similarities with our approach, as will be further elaboratedin the sequel. The problem of identifying emission responsibility sharing mechanisms has alsoreceived some attention in the supply chain literature in particular contexts and Sunar (2016)provides an overview of some existing research addressing these issues. Sunar and Plambeck(2016) evaluate different methods of allocating carbon emissions among co-products. Ben-jaafar et al. (2013) study simple supply chain settings and their extensions by incorporatingcarbon footprint considerations.Caro et al. (2013) analyze general supply chains with joint production of GHG emissionswherein firms facing a carbon price can jointly affect emissions via costly abatement possibil-ities. They show that when a central planner allocates emission responsibilities to individualfirms in the supply chain, and imposes a cost on them proportional to these responsibilities,then, emissions typically need to be over-allocated to induce socially optimal abatement effortlevels, even if the carbon tax is the true social cost of carbon. However, as noted by Caroet al. (2013), regulators may be unlikely to implement mechanisms that double-count, andif double counting is to be avoided, “allocation rules that are complex, non-continuous, andlikely to be seen as unfair” have to be implemented to induce socially optimal abatementeffort levels.Relatedly, Gopalakrishnan et al. (2018) also consider a general supply chain with jointproduction of GHG emissions, and employ a cooperative game theory approach to addressthe inverse question of identifying a footprint balanced emission allocation mechanism in thissetting. Based on the capabilities of firms to abate indirect emissions in the supply chain, theyformulate a cooperative game, refereed to as the GREEN game, and propose a specific alloca-tion mechanism, the Shapley value of the GREEN game. The Shapley allocation is shown toincentivize suppliers to exert pollution abatement efforts that are worst-case socially optimalwhen the pollution abatement costs are private information. Similar to Gopalakrishnan etal. (2018), in this paper we also employ a cooperative game theory approach for the problemof emission allocation in fossil fuel supply chains. However, unlike Gopalakrishnan et al.(2018), our cooperative game model is not formulated on the basis of ability of firms to abateindirect emissions. Rather, it arises from entirely different considerations, that is, to modelnew Canadian regulations that mandate factoring in upstream emissions while consideringthe environmental impact of energy projects.In operations management, cooperative game theory has been adopted to address prob-33lems of sharing the benefits of cooperation between independent entities. In this stream ofwork, various solution concepts are studied as potential mechanisms for sharing profits orcost savings from cooperation. For example, the core of a game is used in inventory sharingproblems, see, e.g., Hartman et al. (2000), and Anupindi et al. (2001), the Shapley alloca-tion is employed, for example, in transshipment games (see, e.g., Granot and Sosˇic´ 2003, andSosˇic´ 2006), and to allocate the excess profits of inventory pooling (Kemahliog˘lu-Ziya andBartholdi 2011), and the nucleolus was studied in the context of allocating cost savings fromsharing demand information in a three-level supply chain (Leng and Parlar 2009). Nagara-jan and Sosˇic´ (2008) provide a comprehensive overview of applications of cooperative gametheory in the supply chain management literature.Our work is also related to a branch of the cooperative game-theoretic literature concernedwith cost allocation problems on graphs, such as the minimum cost spanning tree (mcst)game, see, e.g., Granot and Huberman (1984). A special case of an mcst game is the treegame (Megiddo 1978, and Granot et al. 1996), and both models are extensions of the airportgame, e.g., Littlechild (1974). In the three models, the players1 are represented by nodes ina graph, the cost associated with the edges designate maintenance or construction costs, andthe objective is to allocate the total cost of construction or maintenance of the network ina fair manner. As is the case in this paper, the fair allocation method studied in the abovefour papers is the nucleolus of the respective cooperative games. Our cooperative gamemodel can also be shown to be a generalization of the airport game that is, however, distinctfrom the tree game model. Our algorithm to compute the nucleolus is distinct from thosedeveloped in Megiddo (1978) and Granot et al. (1996) for the tree game model. Moreover,in contrast with the above papers, we employ the non-cooperative game theory paradigm tofurther investigate implementation and stability properties of the nucleolus, as well as studyits ability, in our context, to incentivize the adoption of abatement technologies in fossil fuelsupply chains.From a methodological perspective, we also contribute to the Nash program, a researchagenda which seeks to provide a non-cooperative foundation for solution concepts of cooper-ative games. In particular, for recent implementations of the Shapley value, see, e.g., Ju andWettstein (2009), and Albizuri et al. (2015), and for implementations of the nucleolus, see,e.g., Serrano (1995), Dagan et al. (1997), and Albizuri et al. (2017).Plan of the PaperIn §3.2, we first develop a cooperative game model for the problem of allocating emissionresponsibility in fossil fuel supply chains while incorporating the principle of upstream emis-sion responsibility. We then formulate the regulator’s problem as an optimization model that1In the airport game, the players correspond to landings by airplanes of differing sizes.34maximizes the incentives offered by an allocation mechanism to firms for adopting potentiallyavailable emission abatement technologies, subject to some natural constraints, including aconsistency requirement that is important in the regulatory context of emissions allocation.In §3.3, we characterize (Theorem 3.1), in our setting, a commonly used cooperative game-theoretic solution concept, the nucleolus, demonstrate that it is a feasible solution to theregulator’s problem (Theorem 3.2), and develop a quadratic time algorithm (Theorem 3.3)for its computation. §3.4 provides an implementation framework for the nucleolus. Specif-ically, we construct a novel sequential non-cooperative alliance formation game, governedby two simple policies, which is shown (Theorem 3.4) to induce profit maximizing firms toadopt the nucleolus allocation. Further, we prove therein (Theorem 3.5) that the nucleo-lus allocation is the unique strong Nash-stable allocation subject to the two policies. Theself-implementing nature of the policy framework for the nucleolus, as well as its stabilityand consistency properties, make the nucleolus an attractive allocation scheme in fossil fuelsupply chains that, e.g., span multiple legal jurisdictions. In §3.5, we establish certain desir-able and insightful structural properties (Propositions 3.5 - 3.8) of the nucleolus mechanism.In §3.6, we provide (Theorem 3.6) lower-bound guarantees on the welfare gains it deliversto firms and the incentives it offers (Theorems 3.6 and 3.7) to adopt potentially availableemission abatement technologies. We further compare (Theorem 3.8), using these criteria,the performance of the nucleolus mechanism relative to the Shapley mechanism and the so-cially optimal allocation rule for certain specific supply chain configurations. Finally, in §3.7,we focus our attention on a proposed energy project in Canada, the extension of the TransMountain pipeline from the oil sands of Alberta to the ports of British Columbia. We performa well-to-wheel carbon footprinting analysis and evaluate the performance of the nucleolusallocation relative to other allocations in terms of the incentives it generates to adopt emis-sion reducing technologies and the social welfare it delivers. This helps us contextualize ourwork, which, hopefully, will also serve as a useful case study for policy makers and NGOs intheir evaluation of the environmental liability of similar energy projects in other regions.3.2. Model DevelopmentWe first briefly present some basic definitions and concepts of solution in cooperative gametheory that will guide our model development and analysis.3.2.1 PreliminariesA cost cooperative game is denoted by (N, c) where N is the set of players, and c is thecharacteristic cost function which assigns to each subset S of N , c(S), the cost of coalitionS, where c(φ) = 0. The game (N, c) is said to be monotone if the characteristic function c is35monotone, that is, c(S) ≤ c(T ) for S ⊂ T ⊆ N , and if c(S ∪ {i})− c(S) ≥ c(T ∪ {i})− c(T )for all S ⊆ T ⊆ N and i ∈ N , then (N, c) is said to be a concave game.A cost allocation vector x = (x1, ..., xn) which allocates to each player i a cost, xi, issaid to be a preimputation if∑i∈Nxi = c(N). It thus allocates the total cost of the grandcoalition, N , among all the players. A preimputation x for which xi ≤ c({i}), i ∈ N , isreferred to as an imputation. The core, C(N, c), consists of all vectors x = (x1, x2, . . . , xn)such that no subset of players, S, is allocated more than its associated cost, c(S). That is,C(N, c) = {x ∈ Rn : x(S) ≤ c(S), ∀S ⊂ N, x(N) = c(N)}, where x(S) ≡∑j∈S xj . The coreis thus the set of preimputations which are individually rational (i.e., xi ≤ c({i}) for each i)and coalitionally rational (i.e., x(S) ≤ c(S) for each S ⊆ N). But the core could be empty,and even if non-empty, it usually does not consist of a single allocation. For monotone gameswith a non-empty core, it can easily be shown that the core vectors are non-negative. Forconcave games, the core is non-empty (Shapley 1971).An important solution concept for cooperative games, introduced by Schmeidler (1969), isthe nucleolus. Intuitively, the nucleolus is based on the principle of minimizing the maximumdissatisfaction over all possible coalitions in a lexicographic manner. Formally, let eS(x) =c(S)−x(S) denote the excess of coalition S with respect to the allocation x. The smaller theexcess, the more dissatisfied the coalition S is with x. For each x, let e(x) = (eS(x))S∈2N\{N,∅}in which the excesses are arranged in an increasing order. The nucleolus z is the uniqueimputation that lexicographically maximizes the excesses of all coalitions. That is, e(z) le(x) for all other imputations x, where l denotes the lexicographic order. The nucleolus,by sequentially maximizing the welfare of the least well off coalitions, imports the Rawlsiannotion of fairness to cooperative games.The pre-kernel of (N, c), another solution concept for cooperative games, is based onbargaining power considerations. Introduced by Davis and Maschler (1965), it consists ofall allocations {x ∈ Rn : x(N) = c(N) and skl(x) = slk(x), for all k, l ∈ N, k 6= l}, whereskl(x) = min{c(S) − x(S) : k ∈ S, l /∈ S} denotes the maximum surplus of player k in theabsence of player l. The maximum surplus skl(x) is an intuitive measure of the bargainingpower of player k over player l with respect to x, and the pre-kernel balances the maximumsurplus for each pair of players. In concave games, the pre-kernel consists of a unique point inthe core and coincides with the nucleolus (Maschler et al. 1971), thus providing an alternateinterpretation of the nucleolus for the class of concave games.Despite the attractiveness of the nucleolus as a solution concept, its computation couldbe prohibitive. However, it can be efficiently computed in a variety of settings - including, forexample, three-player cooperative games (Leng and Parlar 2010), airport games (Littlechild1974), standard tree games (Meggido 1978 and Granot et al. 1996), and assignment games(Solymosi and Raghavan 1994). One of the contributions of this paper is the development36of a quadratic time algorithm to compute the nucleolus of a cooperative game which modelsthe allocation of upstream emission responsibilities in fossil fuel supply chains.3.2.2 A Cooperative Game ModelWe now introduce our cooperative game model that underpins the subsequent developmentof a mechanism to allocate upstream emission responsibilities in fossil fuel supply chains. Weconsider a supply chain enterprise, defined by SC = (V,E, a,N), where V and E are thevertex and edge sets, respectively, of the directed tree, T , with a root node denoted by 0.The vertex set, V = N ∪ {0}, where N designates the set of all the firms in the supply chainenterprise and n = |N | corresponds to the number of firms in the fossil fuel supply chain2.A firm (or project) i in the fossil fuel supply chain is associated with node i, i ∈ N , wherenode 1 represents the most downstream member of the supply chain, and we assume thata single arc emanating from node 1 enters node 0. Typically, node 1 could designate theend consumers or retailer in the fossil fuel supply chain. The leaf nodes represent the mostupstream firms, typically extractors of fossil fuels, and the other nodes represent intermediatefirms or distributors. Each edge e in E is associated with a process or an activity in the fossilfuel supply chain emitting a pollution, a(e).Following standard convention and Canadian guidelines (Canada 2016), the emissions,a(e), associated with the activity corresponding to the arc e, can be estimated by firstlyidentifying the throughput and its constituent distinct components flowing through the fossilfuel supply chain under consideration. Then, summing over the throughput of each individualcomponent, multiplied by its GHG emission factor, results with the activity’s emissions.The computations we perform for the Trans Mountain Pipeline case study are providedin Appendix II and serve as an illustration of this step. However, since the emissions ateach stage in the supply chain serve solely as inputs to our model, we refer the reader tocommunication by the Department of Environment and Climate Change (Canada 2016) forfurther details on the estimation methodology.Let ei denote the unique edge in T emanating from node i in the direction of the rootnode of T . Then, a(ei), the pollution associated with ei, represents the pollution directlycreated by firm i. Aside from the direct responsibility for the pollution a(ei), the regulatoryprinciple of assigning upstream emission responsibility implies that firm i is also indirectlyresponsible for emissions generated from all activities upstream to it. Accordingly, for eachfirm i, we denote by Ui the set of edges in the subtree of T rooted at node i, and including ei.Therefore, firm i is responsible for the pollution associated with the set of edges in Ui. Such aninterpretation of Ui is in line with the principle that each firm be held indirectly responsible2We note that the root node 0 is a pseudo-node that does not correspond to any entity in the supply chain.37for the pollution arising from all upstream activities from the point of resource extraction upto and including the direct operations of the firm or project under consideration. We thendefine the Upstream Responsibility cooperative game, (N, c), induced by an SC enterprise,whereby for each S in N , c(S) = a(∪i∈S Ui). The total pollution emitted by the supply chainis c(N) =∑e∈E a(e), and we seek to identify an apportionment of responsibilities, {xi}i∈N ,of the total emissions among the firms, such that,∑i∈Nxi = c(N). (3.1)Further, for i, j ∈ N , let i j denote that a firm i is downstream to another firm j.Then, an interpretation of the upstream responsibility principle implies that, since all thesupply chain processes upstream to firm j are also upstream to firm i,xi ≥ xj , ∀ i j. (3.2)Therefore, allocation mechanisms, {xi}i∈N , that satisfy the above property are said to beconcordant with respect to the principle of upstream responsibility.Figure 3.1: Illustrating the Upstream Responsibility game model for a simple fossilfuel supply chain.Example 3.1. As an illustrative example to clarify the above discussion, consider N ={1, 2, 3, 4, 5} as the set of firms in the fossil fuel supply chain depicted in Figure 3.1 andlet (N, c) denote the corresponding Upstream Responsibility game. The weights on the arcsrepresent the direct emissions (in some appropriate units) of the corresponding stage of thesupply chain, a1 = 1, a2 = 4, a3 = 1, a4 = 2 and a5 = 2. As the most downstream firmin the supply chain, firm 1 will be responsible for all the emissions in the supply chain,that is, c({1}) = 10, and indeed, for any subset of firms S, such that 1 ∈ S, c(S) = 10.Further, c({2}) = c({2, 3}) = c({2, 4}) = c({2, 3, 4}) = a2 + a3 + a4 = 7, and c({2, 5}) =c({2, 3, 5}) = c({2, 4, 5}) = c({2, 3, 4, 5}) = a2 + a3 + a4 + a5 = 9. Firms 3, 4, and 5 areindividually responsible only for their direct emissions as there are no upstream stages in the38supply chain. Therefore, c({3}) = 1, c({4}) = 2, and c({5}) = 2. Also, clearly c({3, 4}) = 3,c({3, 5}) = 3, c({4, 5}) = 4, and c({3, 4, 5}) = 5. Finally, c(N) = 10, corresponds to theemissions generated by the entire supply chain. An efficient solution of the cooperative gamewill be an allocation vector of responsibilities, {xi}i∈N , such that∑i∈Nxi = c(N) = 10. Incontrast, an application of the Canadian principle of upstream emission responsibility will holda project i in the fossil fuel supply chain responsible for its entire upstream emissions (Canada2016), that is, c({i}). For illustrative purposes, assume that the above fossil fuel supply chaincomprises of entirely new projects. Then, in the absence of an apportionment mechanism, theattributed responsibilities for projects {1, 2, 3, 4, 5} shall be given by [10, 7, 1, 2, 2], exemplifyingthe double-counting.3.2.3 ConsistencyApparently, the Davis-Maschler reduced game property (Davis and Maschler 1965), whichplays a prominent role in axiomatization of solution concepts in cooperative games, is anatural property to be desired from an emission responsibility allocation scheme in fossil fuelsupply chains. To explain, let us first introduce some definitions. Let (N, c) be a (cost)cooperative game, and assume, for simplicity of exposition, that the core, C(N, c), of (N, c)is not empty. Then, for a given non-empty coalition S and a core allocation x, the Davis-Maschler reduced game, (S, cˆxS) of (N, c) on S at x is given bycˆxS(T ) = min{c(T ∪Q)− x(Q) : Q ⊆ N \ S}, ∀ T ⊆ S.Note that the Davis-Maschler reduced game of an Upstream Responsibility game (N, c),on S at x, can be viewed as a cooperative game modeling of a generalized fossil fuel supplychain wherein the firms inN\S have committed to assume upstream pollution responsibilities,xi, i ∈ N \ S, and the remaining firms, S, are left to take advantage of these commitmentsas they attempt to allocate, among themselves, upstream responsibilities for the emissions ofthe entire supply chain.Definition 3.1. A solution concept φ is said to satisfy the reduced game property orconsistency if for every coalition S and every solution point x, the projection, xS ≡ (xi)i∈S,belongs to φ(S, cˆxS),x ∈ φ(N, c)⇒ ∀ S ⊆ N, xS ≡ (xi)i∈S ∈ φ(S, cˆxS). (3.3)A solution concept that satisfies the reduced game property, or consistency, satisfies in-ternal consistency which is a fundamental requirement of any allocation method, see, e.g.,39(Winter 2002). Indeed, consider (a single-point) solution concept, φ, which we would like touse as a cost allocation scheme, and suppose that we implement φ in two stages. In the firststage, φ is implemented to determine the cost allocations for members in a coalition N \ S.The environment subsequent to the first stage represents a different (reduced) game facingplayers in S, whose cost allocations are yet to be determined. It would be very natural,perhaps even obvious, to require that φ allocates the players in the reduced game exactlythe same cost shares as they would have been allocated in the original game, and a solutionconcept satisfying this requirement is referred to as being consistent.Note that, for example, in the context of emissions allocation in global fossil fuel supplychains, consistency of an allocation method is a natural requirement. Indeed, in such supplychains, different firms and projects often fall under the jurisdiction of different regulators. Inthese cases, it can be argued that the proposed allocation rule, implemented at a reducedsupply chain which is, e.g., under the jurisdiction of the same regulator, be invariant to pre-vious implementations of it in other jurisdictions. Consistency also contributes to simplicityof administration, one of the yardsticks identified by the Canadian government and discussedpreviously. Further, we note that a cross-jurisdictional review of energy regulators commis-sioned by the Natural Resources Canada (Stratos 2017) broadly recommends consistencyand coherence across regulatory systems while designing and implementing environmentalinitiatives.3.2.4 Welfare, Incentives and the Regulator’s ProblemThe attributed upstream responsibility, along with the manner in which it is integrated withinan existing environmental policy regime by the energy regulator, has economic implicationsfor the firms in the fossil fuel supply chain. Regulators could opt to utilize the attributed up-stream responsibility to qualitatively inform the impacts of an energy project. Alternatively,they could penalize firms by requiring them to offset or they could levy a carbon penaltyon the attributed emissions, either entirely, or on the part that exceeds some predeterminedthreshold. Carbon penalties, such as a carbon tax, are set, in principle, so as to reflectthe social cost of carbon emissions and to induce firms to internalize these costs (Plambeck2012). Similarly, offset requirements or emission thresholds are determined, in principle andin practice, by factoring in the available state-of-the art technologies, economy-wide emis-sion targets and so forth. The regulator designs these policies to be aligned with optimalsocial outcomes and by doing so, arguably, ensures that compliance with these policies is theonly relevant metric for the social objective. The apportionment mechanism chosen to at-tribute upstream emission responsibility, however, affects the incidence of the economic costsof compliance and consequently, firm-level welfare. In this paper, we consider the effects ofthe adopted apportionment mechanism on firm-level and supply chain welfare and on the40incentives offered to firms to adopt emission-reducing technologies. The analysis is carriedout in an environment where the firms are expected to pay a carbon penalty or offset theattributed emission responsibilities. That is, we assume the regulator implements a carbonpenalty levied at a price pt on the emissions attributed to each firm in the supply chain.Firm WelfareThe baseline allocation xi to a firm i in the fossil fuel supply chain, under the upstreamresponsibility principle, is given by xi = c({i}). The welfare gains for a firm i upon theadoption of the emission responsibility allocation vector x, is therefore obtained by comparingit against the baseline responsibility and is given by, θi(x) = pt (xi − xi). We also observe thatsince we assume, as is typical in the environmental operations literature (see, for example,Caro et al. 2013) that the emissions allocated to a firm and the resulting financial penalties donot impact the revenues from their core operations, the welfare gain, θi(x) can be interpretedas the firm’s cost savings or profit generated by the allocation mechanism x. A naturalwelfare requirement from a proposed emission responsibility allocation x is that it shouldresult in non-negative welfare gains for a firm in the fossil fuel supply chain with respect tothe baseline upstream responsibility policy,θi(x) = pt (xi − xi) ≥ 0, ∀ i ∈ N. (3.4)Environmental EffectivenessWe now outline here a general methodology to analyze the environmental effectiveness ofa policy, such as an upstream emission responsibility mechanism, by considering the incen-tives it provides to adopt potentially available emission reducing technologies. Consider atechnology t that has an associated abatement potential of e(t) beyond the baseline business-as-usual (BAU) emissions, at a cost c(t). Such technologies available to a specific firm canbe represented in an abatement cost plot, or the so-called “McKinsey curve” (Enkvist et al.2007). That is, a simple plot of available technologies to reduce emissions and their associ-ated costs, as sketched in the left panel of Figure 3.2. In the absence of any environmentalpolicy, it is still profitable to invest in those technologies that lie in the fourth quadrant, asthey provide environmental benefits at negative cost. If the social cost of carbon is denotedby pS and the carbon price pt is set at pS , then, in Figure 3.2 (left panel), any technologylying below the line c(t) = pSe(t) would be profitable. These technologies comprise the setof socially desirable investments, i.e., the cost of the technology is less than the social cost ofthe emission reduction from it.Apart from levying pecuniary penalties for pollution, environmental policies, in general,41aim to alter the cost structures to enlarge the set of potentially available and profitabletechnologies. Therefore, a natural measure of the environmental effectiveness of an allocationmechanism would be the area of the region of potentially available costly technologies that areprofitable given the specific mechanism. Formally, for a firm i with baseline BAU emissionsai, denote by ωi(x) the area of the space of costly emission-reduction technologies that wouldbe profitable under the allocation rule x, with a carbon price pt. In the right panel of Figure3.2, we sketch the technology adoption incentives offered to firm i by an allocation mechanismx, in relation to the baseline allocation, x.Figure 3.2: Abatement cost plot with a set of socially desirable emission reductiontechnologies under a carbon price pt = pS (left panel). Technology adoptionincentives for firm i by the mechanism x and the baseline allocation x (rightpanel).We can extend the preceding discussion to the entire supply chain. That is, assumethat each firm i in the fossil fuel supply chain has associated potentially available emissionreduction technologies, denoted by ti = {ei(ti), ci(ti)}, such that ti can potentially achievean emission reduction of ei(ti) at firm i at a cost ci(ti). For a firm i, denote the space ofall potentially available emission reduction technologies, ti, with ei(ti) ∈ (0, ai] and ci(ti) ∈(0,∞), by Ti. Then, the space of all emission reduction technology vectors, potentiallyavailable to the supply chain, is denoted by T = ⊕i∈NTi.A vector of technologies t = {ti}i∈N ∈ T , will be adopted by the supply chain in equilib-rium, under a carbon price pt and an apportionment mechanism x, if and only if the followingcondition is satisfied for each i ∈ N , ∆xi (t) = ptxi(ai; a−i − e−i(t−i))− ptxi(ai − ei(ti); a−i −e−i(t−i)) ≥ ci(ti) , where −i denotes the rest of the firms in the supply chain excluding i.Formally, denote by Ω(x) the volume of the n-dimensional space, T (x), of potentially avail-able costly technology vectors t = {ti}i∈N that would be adopted in equilibrium under the42allocation rule x and a carbon price pt. Then,Ω(x) =∫t∈T∆xi (t)≥ci(ti)dt =∫t∈T (x)dt . (3.5)Regulator’s ProblemThe regulator’s problem then involves identifying an allocation mechanism x that satisfiesthe constraints implicitly imposed by (3.1)-(3.4) while maximizing the social objective ofenvironmental effectiveness. The baseline allocation mechanism, x, being concordant withthe upstream responsibility principle, attributes each firm responsibility for its own directemission as well as all emissions upstream to it in the supply chain. As such, it shall maxi-mally incentivize the adoption of potentially available costly emission abatement technologies.Clearly, x is an inefficient allocation mechanism, i.e., it does not satisfy (3.1). Nevertheless,it can serve as a natural benchmark for an allocation mechanism in relation to its ability torender emission reduction technologies economically profitable. The regulator’s problem cantherefore be expressed as,maxx∈RnΩ(x)/Ω(x)subject to (3.1) - (3.4).In the next section, we will demonstrate that the nucleolus allocation mechanism is afeasible solution to the regulator’s problem as described above. In §3.6, we will relax certainregulatory constraints and compare the environmental incentives offered by the nucleolus withrespect to other feasible concordant mechanisms including the socially optimal mechanism.3.3. The Nucleolus AllocationSince the Upstream Responsibility game (N, c) is concave (all proofs and technical resultsare provided in Appendix B), we can conclude that it has a non-empty core, denoted C(N, c),containing the nucleolus. Therefore, the nucleolus is efficient and it induces non-negativewelfares to all firms. That is, it satisfies constraints, (3.1) and (3.4) of the regulator’s problem.Moreover, we note that while the Shapley value and the nucleolus both satisfy consistency,or the reduced game property, the reduced games associated with these two concepts aredifferent. In fact, both solution concepts are axiomatized by efficiency, symmetry and thereduced game property, see, e.g., (Sobolev 1975, Hart and Mas-Collel 1989, and Winter 2002).43The Davis-Maschler reduced game, described in §3.2.3, underlies the characterization of thenucleolus. And, as elaborated previously, in the context of allocating pollution responsibilitiesamong supply chain members, the environment representing the reduced situation for thenucleolus is very meaningful. By contrast, the reduced game underlying the characterizationof the Shapley value, due to Hart and Mas-Colell (1989), is quite different, and is meaninglessin the context of allocation of pollution responsibilities. In that sense, we suggest that, infossil fuel supply chains that are subject to the upstream responsibility principle, the nucleolusis the unique “natural” single-point consistent solution mechanism to apportion supply chainemissions.We now consider the Upstream Responsibility game (N, c), with an associated directedtree T = (V (T ), E(T )), as introduced in the previous section. If there is a directed arc fromi to j in T , we will say that the two firms, i and j, are adjacent in T , and that j is thesuccessor of i in T . For such firms i and j, we denote by Tij the subtree of T rooted at i awayfrom j, consisting of all the vertices whose unique path from them to the root node containsthe arc (i, j). Since each firm i has a unique successor firm j, for convenience, we sometimesalso denote Tij as simply Ti, and we denote the node cardinality of Ti by |Ti|. Further,let a(Tij) = a(Ti) ≡ a(ei) +∑(a(e) : e is an arc in Tij). The following theorem leveragesthe coincidence of the pre-kernel and the nucleolus in concave games to characterize thenucleolus of Upstream Responsibility games. It arises from applying the pre-kernel equations,skl(x) = slk(x), to pairs of adjacent players k and l in the tree.Theorem 3.1. A pre-imputation z in the Upstream Responsibility game (N, c) is the nucle-olus if and only if z satisfies the following set of equations for each pair of adjacent players(i, j) in T , where j is the successor of i,zi = a(Tij)− z(Tij), if zj ≥ a(Tij)− z(Tij),zi = zj if zj ≤ a(Tij)− z(Tij),z(N) = c(N).(3.7)While in general, the pre-kernel equations need to be satisfied for each pair of distinctplayers, Theorem 3.1 implies that in Upstream Responsibility games, if adjacent pairs ofplayers satisfy the pre-kernel equations, so do all the other pairs of players. Thus, it providesa characterization of the nucleolus based on local bargaining power considerations that onlyinvolve players that are immediate partners in the fossil fuel supply chain. That is, a pre-imputation z is the nucleolus of (N, c) if and only if skl(z) = slk(z) for all adjacent players kand l in T . Theorem 3.1 also ensures that a firm which is downstream to another firm in thesupply chain is necessarily assigned a larger share of the pollution responsibility by the nu-cleolus allocation implying that the nucleolus is concordant with the upstream responsibility44principle. Further, since the nucleolus is efficient, consistent and induces non-negative firmwelfares, as observed previously, we in fact have,Theorem 3.2. The nucleolus allocation mechanism z satisfies constraints (3.1)-(3.4) and istherefore, a feasible solution of the regulator’s problem.We next follow Granot et al. (1996) and modify (3.7) to derive a linear-time heuristicapproximation of the nucleolus, the proto-nucleolus, which under some conditions, as specifiedby Lemma 3.2 below, coincides with the nucleolus.Definition 3.2. The proto-nucleolus of the Upstream Responsibility game, (N, c), is a preim-putation x that satisfies xi = a(Tij) − x(Tij) for each pair of adjacent players i and j suchthat j is a successor of i.The following proposition characterizes the proto-nucleolus of Upstream Responsibilitygames and immediately lends itself to a linear-time computation of the proto-nucleolus.Proposition 3.1. The proto-nucleolus, x, of the Upstream Responsibility game (N, c) isunique and is the allocation given byxi =(ai +∑k∈Uixk)/2 : i 6= 1(a1 +∑k∈U1xk) : i = 1,(3.8)where Ui denotes the set of firms immediately upstream to i.The following proposition follows from (3.8) and the definition of the proto-nucleolus, andprovides conditions for the coincidence of the proto-nucleolus and nucleolus.Proposition 3.2. For an Upstream Responsibility game (N, c) with proto-nucleolus x andnucleolus z,i. xi ≤ xj for all adjacent players i and j, where j is the successor of i, if and only if x = z,ii. a(Tij) ≤ aj for all adjacent players i and j implies x = z.Proposition 3.2 clarifies that the proto-nucleolus coincides with the nucleolus mechanismif and only if the proto-nucleolus is itself a concordant allocation mechanism. Secondly, if thedirect emissions of downstream entities in the fossil fuel supply chain is sufficiently larger thantheir immediate upstream partners, then the proto-nucleolus will coincide with the nucleolus.We note that the proto-nucleolus is related to a pollution responsibility allocation methoddiscussed by Gallego and Lenzen (2005). Therein, the authors propose a non-game theoreticresponsibility sharing method where a fraction of the responsibility for pollution at a site isborne by the polluting firm, and a fraction is passed on to the downstream firms. Lenzen45et al. (2007) illustrate the method with an example where the fraction of pollution passedto downstream firms is half. In this case, the Gallego-Lenzen allocation coincides with theproto-nucleolus, where half of the pollution, ai, is allocated to firm i and the immediatelydownstream firm, in turn, is allocated a half of that and so on. Thus, the proto-nucleoluscaptures the intuition behind the Gallego-Lenzen method although it arises from entirelydifferent considerations, as an approximation to the nucleolus.The following lemma is the basis for a quadratic-time algorithm to compute the nucleolusallocation of upstream emission responsibilities in the fossil fuel supply chain. For j ∈ N ,j 6= 1, define cj = a(Tj)|Tj |+1 , and for j = 1, define cj =a(T )|T | .Lemma 3.1. Let z be the nucleolus of the Upstream Responsibility game, and let i denote aplayer for which cj, j ∈ N , attains the minimum. Then, zl = ci for all l ∈ Ti.Algorithm AStep 0. Initiate with T , the weighted directed supply chain tree.Step 1. Determine player i ∈ N for which cj as defined above is minimized with arbitrarybreaking of ties.Step 2. The nucleolus z allocates ci to all players in Ti.Step 3. Remove all nodes in Ti, that is, N is updated to N\V (Ti). If there are no moreplayers, terminate the algorithm.Step 4. Otherwise add ci to aj , the pollution at node j, where j is the node immediatelydownstream to i.Step 5. Return to Step 1.Lemma 3.1, coupled with the consistency property of the nucleolus, implies that AlgorithmA computes the nucleolus of Upstream Responsibility games in quadratic time.Theorem 3.3. Algorithm A computes the nucleolus allocation mechanism z of the UpstreamResponsibility game (N, c) in O(|N |2) operations.3.4. An Implementation Framework and Stability AnalysisThe polynomial-time algorithm constructed in §3.3 is useful from a computational pointof view, but necessitates central planners to use, as inputs, the direct emissions in orderto compute the allocated responsibilities to each firm in the fossil fuel supply chain fallingunder their jurisdiction. We now complement the algorithmic approach by providing a non-cooperative policy framework that supports the implementation of the nucleolus. That is,we describe in this section simple policies with easily verifiable compliance. When thesepolicies are imposed by the regulator on the firms in the supply chain, they ensure that46profit-maximizing3 firms, following a well-specified protocol, will uniquely organize themselvesto allocate upstream supply chain emissions in accordance with the nucleolus allocation.Specifically, we consider the following two policies.PolicyM: A firm or project in the supply chain is forbidden from bearing a smaller emissionresponsibility than its immediate upstream firms.Policy P: Each firm is permitted to collaborate with other firms in the fossil fuel supplychain to form an alliance, and all the firms in the alliance bear equal responsibility for, atthe minimum, the upstream emissions of the alliance that have not already been accountedfor by some other group. Moreover, in accordance with the notion of upstream responsibility,each alliance is permitted to transfer at most an equal upstream responsibility share to therest of the downstream supply chain members.Therefore, policyM imposes a monotonicity constraint on the implementation outcomesand naturally ensures that the emission responsibility shares that the firms are allocated inany outcome are concordant with the upstream responsibility principle. Policy P allows theformation of alliances in the supply chain and provides guidelines on how the firms in analliance can share upstream emission responsibility amongst themselves.Formally, an alliance is a subset of firms in the supply chain and an alliance structure isdefined as A = {A1, ..., Am}, wherem⋃k=1Ak = N and Ak ∩Al = φ for k 6= l. We observe thateach realization of Algorithm A to compute the nucleolus naturally defines a special alliancestructure An = {An1 , ..., Anm}, where each alliance in An corresponds to a specific subtree Tiobtained in some iteration of Algorithm A, and that the nucleolus allocation z complies withpolicies M and P. Since the algorithm may encounter ties in each iteration that are brokenarbitrarily, we note that the nucleolus alliance structure may not necessarily be unique for agiven fossil fuel supply chain.We next examine the space of feasible allocation vectors defined by policies M and P.We begin with some illustrative examples which clarify that the policies are well-defined,verifiable in linear-time and may sometimes yield inefficient allocations.Example 3.2. Consider the simple supply chain depicted in Figure 3.3a with arc-weightsdenoting the associated direct emissions, and the alliance structure A = {A1, A2, A3} whereA1 = {1, 5}, A2 = {2, 3}, A3 = {4}. Consider an allocation to each of the players underthe alliance structure A given by the vector x = [2.5, 2, 2, 1, 2.5]. It is easily seen that theallocation vector x satisfies M and P, which clarifies that policies M and P are well defined.However, in this example, the nucleolus alliance structure, An, is unique and can be shownto consist of independent alliances, i.e., all alliances therein are singletons, and is therefore3Since we assume that the emissions allocated to a firm and the resulting financial penalties do not impactthe revenues from their core operations, the profit of a firm given an allocation mechanism x is an affinefunction of its individual firm welfare, θi(x), and is maximized when θi(x) is maximized.47Figure 3.3: Illustrative examples with a simple supply chain and policy-compliantallocations.distinct from A. Further, it can be easily verified that the nucleolus allocation in this case,given by z = [4.75, 2.75, 0.5, 1, 1], also complies with policies M and P. Finally, note that, ingeneral, compliance with policies M and P is verifiable in linear time.Example 3.3. Consider the supply chain with modified arc-weights depicted in Figure 3.3b,and the alliance structure A = {A1, A2, A3, A4}, where A1 = {1, 5}, A2 = {2}, A3 = {3}and A4 = {4}. Consider the allocation vector x = [3, 3, 3, 0.5, 3]. x satisfies policies Mand P, but it is not an efficient allocation since it over-allocates the supply chain emissions.In fact, it is easily seen that for the alliance structure A, there does not exist an efficientallocation of the supply chain emissions that satisfies policies M and P. Similarly, considerthe alliance structure A′ = {A′1, A′2, A′3}, where A′1 = {1}, A′2 = {2, 5}, and A′3 = {3, 4}.Observe that A′ contains alliances that are non-contiguous. Then, the allocation vector x′ =[7/3, 7/3, 7/3, 7/3, 7/3] satisfies policies M and P but it is not efficient and it is easily seenthat there exists no efficient allocation vector satisfying the two policies.Formally, consider an alliance structure A and an allocation vector, x, of upstream emis-sion responsibilities in the fossil fuel supply chain that complies with the policies M and P.We now translate the two policies in terms of the constraints that they impose on x. For analliance A, denote the set of firms in N\A upstream to some firm in A by U(A). Policy Mimplies that for firms i and j such that i is upstream to j in the supply chain, xi ≤ xj . PolicyP then implies that for an alliance A ∈ A,x(A) ≥ c(A)− x(U(A))− x(A)|A| , 1 /∈ Ax(A) ≥ c(A)− x(U(A)), 1 ∈ Axi = xj if i, j ∈ A.(3.9)It is easily seen that policiesM and P are well-defined, in the sense that, given any alliance48structure A, there always exist allocations that comply with the two policies. For example,given any fossil fuel supply chain and an arbitrary alliance structure, the allocation x thatallocates c(N) to all the members in the supply chain trivially satisfies (3.9). Moreover, for thesame reason, given any alliance structure, in general, there will in fact exist infinite emissionresponsibility allocations that comply with policies M and P. However, in Propositions 3.3and 3.4 below, we establish that, assuming the firms in the fossil supply chain are rational,that is, profit maximizing, they will allocate responsibilities uniquely for a given alliancestructure A.We first consider the important special case of contiguous alliance structures. An alliancestructure, A = {A1, ..., Am}, is said to be contiguous if the subgraphs induced by the playersin each of its component alliances, Ai ∈ A, are connected in the supply chain graph. For thiscase, we provide an explicit characterization of the unique allocation vector xA induced bythe policies M and P, for a given alliance structure A.Proposition 3.3. Consider a supply chain consisting of rational firms compliant with policiesM and P, a contiguous alliance structure A, and players i and j such that j is the immediatedownstream firm to i. Then the allocation to player j, xAj , is given by,xAj = xAi , if i, j ∈ Ak ∈ A,xAj = max{xAi ,a(Ak)+a(Ti)−xA(Ti)|Ak|+1}if i /∈ Ak, j ∈ Ak, j 6= 1xAj = max{xAi ,a(Ak)+a(Ti)−xA(Ti)|Ak|}if i /∈ Ak, j ∈ Ak, j = 1.(3.10)We note that for the special case when the alliance structure arises from a situation whereall firms belong to singleton alliances, the corresponding allocation xA that complies withpolicies M and P coincides with the Gallego-Lenzen allocation discussed in §3.3.We now generalize the above proposition for the case of non-contiguous alliance struc-tures. That is, alliance structures that may contain alliances corresponding to disconnectedsubgraphs in the fossil fuel supply chain. First, we need to introduce some new definitions.A set of firms S is said to block another disjoint set of firms T if there exist possibly identicalfirms i, j ∈ S and u, v ∈ T , such that u is downstream to i and v is upstream to j. Forexample, if firm i is downstream to firm u and upstream to firm v, then S = {i} blocks theset of firms T = {i, j}.Given an alliance structure A of the set of firms N , let MA denote a set of firms which isa set-union of alliances in A. MA is a minimal non-blocking set of firms with respect to A if,(i) MA is neither blocked nor does it block any alliance in N\MA , and (ii) no subset of MAsatisfies (i). We define the minimal non-blocking set structure, M(A), M(A) = {M1, ...,Mk},with respect to A, as the set of minimal non-blocking sets of firms in N , such thatk⋃i=1Mi = N49and Mi∩Mj = φ for i 6= j. It can be shown that for an alliance structure, A, M(A) is unique.Further, note that any set in M(A) is either an original alliance in A or a union of alliancesin A, and that if A consists of non-blocking alliances, such as if A is a contiguous alliancestructure, then M(A) = A. In particular, for a nucleolus alliance structure An, M(An) = An.In Proposition 3.4 below, we show that the explicit characterization provided in (3.10)for contiguous alliance structures can be generalized to non-contiguous alliance structures.In this case, the minimal non-blocking sets of alliances comprising M(A) play the role thatthe individual alliances in A played in Proposition 3.3.Proposition 3.4. Consider a fossil fuel supply chain consisting of rational firms compliantwith policies M and P, an alliance structure A, and players i and j in alliances Au, Av ∈ A,respectively. Then, the unique allocation vector xA is given by,xAj = xAi , if i, j ∈Mk ∈M(A),xAj = max{xAi ,c(Mk)−xA(U(Mk))|Mk|+1}if j ∈Mk, i ∈ U(Mk), 1 /∈MkxAj = max{xAi ,c(Mk)−xA(U(Mk))|Mk|}if j ∈Mk, i ∈ U(Mk), 1 ∈Mk,(3.11)where U(Mk) denotes the set of firms upstream to Mk.From the above proposition, we immediately obtain the following corollary that if twodifferent alliance structures have identical associated minimal non-blocking set structures,then the allocations induced by the two alliance structures are also identical.Corollary 3.1. For alliance structures A1 and A2 such that M(A1) = M(A2), xA1 = xA2.Although, compliance with the two policies induces an infinite set of feasible allocationvectors, Propositions 3.3 and 3.4 establish a non-injective (many-to-one) mapping betweenthe alliance structure and its associated allocation vector for fossil fuel supply chains withrational firms. Thus, given an alliance structure A in a fossil fuel supply chain, we mayassume that xA is the unique allocation of responsibilities that will be induced by policiesMand P imposed by the regulator. Clearly, if the alliance structure coincides with a nucleolusalliance structure, i.e., A = An, then xA = z, where z is the nucleolus allocation.3.4.1 Endogenous Formation of AlliancesWe are now interested in the dynamics of how firms in a fossil fuel supply chain will organizethemselves subject to policies M and P being imposed by the regulator, and the alliancestructures that can be expected to be formed. We therefore analyze an endogenous processof alliance formation in a fossil fuel supply chain that is mandated to assume responsibility forthe total supply chain emissions. To this end, we consider a well-specified protocol, consisting50of a sequential procedure of alliance formation, whereby, downstream firms are permitted tooffer upstream firms to join them in their existing alliance, and in response, upstream firmscan choose to either accept or reject the offer, proceeding sequentially through all the firmsin the supply chain.Formally, the protocol mandates players to choose their actions in an order ρ, proceedingsequentially upstream through the supply chain from the most downstream entity to the mostupstream entities, with ties broken arbitrarily. Following the order ρ, each player j in thesupply chain chooses an action oji with respect to each of its immediate upstream partners i,oji ∈ {Offer, Do Not Offer}. That is, to either offer or not offer i to join the alliance that jis currently a member of, denoted by {O,D} in Figure 3.4. If player j chooses to offer playeri to join the alliance, then i can choose an action aij ∈ {Accept, Reject}. That is, to eitheraccept or reject j’s offer, denoted by {A,R}, respectively, in Figure 3.4. If j chooses to notoffer membership to i, then we vacuously allow i to reject j’s non-existent offer.For a given fossil fuel supply chain represented by the directed tree T , vector of arc-weightsa, and the order ρ, we can therefore define a sequential game with perfect information, thealliance formation game, Γ(T, a, ρ), which can be represented by a game tree H(Γ), as, forexample, depicted in Figure 3.4. For each node t in the game tree H, the subtree rooted at tcorresponds to a subgame Γt of the alliance formation game, Γ. The history of the game atnode t, denoted by Ht(Γ), consists of the players who have already played prior to t, N(Ht),their corresponding sequence of actions, A(Ht), and the player, n(Ht), who is to choose theimmediate next action.Figure 3.4: Game tree H(Γ) corresponding to an alliance formation game Γ in atypical fossil fuel supply chain.A strategy profile, σ = {σi}i∈N , is a mapping, for each player i, from all subgames Γtsuch that i = n(Ht), to a feasible action for i. Each strategy profile σ results in a unique51path of actions, pi(σ), from the root node to a leaf node of the game tree H, which is theoutcome of the alliance formation game Γ played with strategy profile σ, and pi(σ) generatesthe alliance structure, A(σ). The precise payoffs, that is, the allocation of responsibilitieswithin the alliance structure, A(σ), is governed by the policies M and P, which can bethought of as exogenous constraints on the allocations. As observed earlier, assuming thefirms in the fossil fuel supply chain are profit-maximizing, the resulting unique allocation ofresponsibilities is given by xA(σ), characterized in Proposition 3.3. Note that it is indeedpossible, as in Example 3.3, that the allocation may not always be efficient, in the sensethat, the formation of certain alliance structures may necessarily result in an allocation thatover-allocates the supply chain emissions.The central question of interest is, of the many possible alliance structures, which oneswould be formed by the firms. We expect the alliance structures that will form to be thosewhich are generated by equilibrium strategy profiles in the alliance formation game. Inthat respect, the following result provides a basis for the endogenous formation of thosealliance structures that yield the nucleolus allocation, thereby providing an implementationframework. In other words, the result below provides a non-cooperative implementation ofthe nucleolus mechanism to apportion upstream emission responsibility.Theorem 3.4. The alliance structure generated by any subgame perfect equilibrium strategyprofile σ˜ of the alliance formation game Γ(T, a, ρ) is a nucleolus alliance structure, A(σ˜) =An.3.4.2 Stability of Alliance StructuresWe now adopt a complementary perspective that allows us to analyze the stability of alliancestructures under the policies M and P. In order to do so, we employ an approach based onthe strong Nash equilibrium concept, according to which an individual player, or a group ofplayers, can withdraw from their current alliance and form a new alliance if the deviationmakes all players in the group strictly better off. We proceed to delineate the mechanics of adeviation. Formally, given an alliance structure A, and the corresponding allocation vectorxA, consider a set of firms S ⊂ N in the supply chain. A deviation by S from the alliancestructure A results in a new alliance structure containing the alliance comprising the firmsin S along with the previous alliances in A excluding those members now in S. We notethat, in general, the original alliance structure as well as the alliance structure arising froma deviation by S, may be non-contiguous. Therefore, this approach allows us to extend theimplicitly imposed sequential communication structure in Theorem 3.4 which permitted onlypartner firms to form alliances.52An alliance structure A is said to be strong Nash-stable if no set of firms S in the supplychain has a strictly profitable deviation. That is, there is no alliance structure B resultingfrom a deviation of S from A, for which xBi < xAi for all i ∈ S. In the case of the simple supplychain considered in Example 3.2, though the alliance structure A complies with policies Mand P, it is not strong Nash-stable because player 5, for example, can feasibly and profitablydeviate from the alliance {1, 5} to form the singleton alliance {5}, and reduce its allocationfrom 2.5 to 1. We are interested in identifying the allocations induced by alliance structuresthat are strong Nash-stable in a fossil fuel supply chain subject to the policies M and P.The following result allows us to restrict our attention to contiguous alliance structuressince for each non-contiguous alliance structure that is strong Nash-stable, there exists astrong Nash-stable contiguous alliance structure that yields an identical allocation of respon-sibilities.Lemma 3.2. Consider a non-contiguous strong Nash-stable alliance structure A. Then,there exists a contiguous strong Nash-stable alliance structure, A′, such that xA = xA′.The following theorem, in turn, shows that all contiguous strong Nash-stable alliancestructures correspond to a nucleolus alliance structure and therefore result in an identicalallocation of responsibilities that coincides with the nucleolus allocation.Theorem 3.5. A contiguous alliance structure A is strong Nash-stable under policies Mand P if and only if A = An. Then, xA = z, where z is the nucleolus allocation.The above theorem demonstrates that the only contiguous strong Nash-stable alliancestructures are nucleolus alliance structures. However, by Lemma 3.2 we immediately obtainthat all other alliance structures that are strong Nash-stable also result in identical allocationof emission responsibilities as in a nucleolus alliance structure.The stability analysis performed here complements the implementation framework devel-oped in §3.4.1. It speaks to the ability of the relatively straightforward and easily verifiablepolicies, M and P, to sustain the nucleolus mechanism to allocate upstream emissions in afossil fuel supply chain.3.5. Structural Properties and ImplicationsIn this section, we establish certain structural properties of the nucleolus alliance structure,and equivalently, of the nucleolus allocation mechanism to apportion upstream emission re-sponsibility in fossil fuel supply chains. These properties assume significant importance inpolicy-contextual modelling, such as ours, as it reaffirms the operational validity of the pro-posed approach (Gass 1983). Motivated by our theoretical results, we further highlight their53practical implications in terms of rationalizing the interpretability and applicability of thenucleolus mechanism.In §3.4, we prescribed policies that provide an implementation framework for the nucleolusallocation mechanism. In certain situations, the most downstream player in a fossil fuel supplychain corresponds to the consumers, and it may prove infeasible to include the consumers inan implementation mechanism such as the one described. However, Proposition 3.5 revealsthat the most downstream entity always forms a singleton alliance, as long as its activitiesgenerate a non-zero pollution. Therefore, in almost all realistic situations, this player can beremoved from the implementation procedure without any consequence.Proposition 3.5. For any fossil fuel supply chain with a1 > 0, a nucleolus alliance structure,An, contains the singleton alliance, {1}.We now proceed to investigate the effects of changes in emissions at some stage of thefossil fuel supply chain on the nucleolus allocation z. An allocation mechanism that is toosensitive to small changes in the emission outputs in various stages of the supply chain isundesirable practically. Transparent mechanisms that lend themselves to simple sensitivityanalyses are easier to implement from a regulatory perspective, and are likely to be viewedby the participating firms as being fairer. In general cooperative games, it is well-knownthat the nucleolus is piecewise linear in the characteristic cost function (e.g., Charnes andKortanek 1969). However, such a result is not directly applicable to our setting because weare interested in the effect of changes in the emissions at some stage in the supply chain,which is an underlying “primitive” of the derived cooperative game. Consider firms i and jin a fossil fuel supply chain (i and j may be identical), and let z be the nucleolus allocationof the associated upstream emission responsibility cooperative game.Proposition 3.6. The nucleolus allocation to firm i, zi, is continuous piecewise linear andnon-decreasing in the direct emissions of firm j, aj.Proposition 3.6 reveals that the effects of small changes in emissions at different stages onthe responsibilities allocated to the firms are linear, thereby emphasizing the transparency ofthe nucleolus allocation mechanism. We now study the effect of larger increases in emissionsof a particular project in the fossil fuel supply chain. Consider a project j whose emissionsincreases from aj to aj + ∆. For sufficiently large ∆, we are able to provide an explicitcharacterization of the nucleolus alliance structures.Specifically, let Pj denote the set of firms in the supply chain on the unique path fromfirm j to the root node 1, including j but excluding 1. Let L denote the set of firms thatare not in Pj but adjacent to a firm in Pj , again excluding the root node 1. It is easily seenthen that N = Pj⋃{1} ⋃k∈LV (Tk), where recall that Tk denotes the subtree of T rooted at54k. Given a subtree Tk, k ∈ L, let Ank denote a nucleolus alliance structure of the sub-supplychain restricted to the subtree spanned by V (Tk)∪k′, where k′ is the root node of sub-supplychain with k′ ∈ Pj and adjacent to k.Proposition 3.7. Consider a firm j in a fossil fuel supply chain with associated directemissions aj + ∆. Then, for sufficiently large ∆, any nucleolus alliance structure, An, isgiven by An = {{1}, Pj , {Ank}k∈L}, and further,∂zi∂∆= 0 where zi is the nucleolus allocationto i ∈ Tk, k ∈ L.Proposition 3.7 provides an explicit characterization of a nucleolus alliance structure whenthe increase in emissions, ∆, is sufficiently large. Moreover, it reveals that beyond somethreshold, the nucleolus allocation mechanism attributes responsibility for a large marginalincrease in the direct emissions associated with a particular project in the supply chain, suchas, for example, substantial capacity expansion, only to the firms directly downstream tothat particular project.Figure 3.5: Illustrating the structural properties of the nucleolus allocationmechanism (Example 3.4).Finally, we consider the effects of very general arbitrary structural changes in the supplychain network, for example, the addition of new projects such as extractors or refineries,disaggregation or closure of existing supply chain members and so forth. Formally, consider afossil fuel supply chain enterprise, SC = (V,E, a,N), and recall from §3.2.2 that V and E arethe vertex and edge sets of the directed tree representation, T , of the supply chain enterpriseSC. N denotes the set of firms in the supply chain, and a : E → R is an edge-weighting thatassociates the direct emissions corresponding to each stage of the fossil fuel supply chain. Asupply chain enterprise SC′ = (V ′, E′, a′, N ′) represented by a directed tree T ′, is said to beobtained by a structural change to SC at S ⊂ N , if N\S ⊆ N ′, and the weighted sub-trees55induced by the firms in N\S in T and T ′, respectively, are identical. As defined, a structuralchange therefore encompasses changes to the underlying graphical structure of the supplychain via either addition of new firms, removal of existing firms, or changes in the supplychain linkages, as well as changes to the direct emissions associated with particular stagesof the supply chain. Now, let us consider an alliance, Ank , belonging to a nucleolus alliancestructure, An, of the supply chain enterprise SC.Proposition 3.8. The nucleolus allocation to firms in the alliance Ank ∈ An does not increasedue to structural changes in the supply chain that are not upstream to any member of thatalliance.Proposition 3.8 notes that the nucleolus allocation to a firm can increase only as a conse-quence of structural changes that are upstream to some firms in the alliance that it belongsto. Changes to the supply chain network that are either downstream, or in other sub-supplychains that are not upstream to any firm in the alliance a firm belongs to, can only decrease orleave unaffected the emission responsibility allocated to that firm. Apart from ensuring easeof interpreting the effects of structural changes, Proposition 3.8 re-emphasizes the adherenceof the nucleolus allocation mechanism to the underlying principle of upstream responsibilitywhich mandates fossil fuel firms to bear responsibility only for upstream emissions.Example 3.4. Consider the supply chain depicted in the left panel of Figure 3.5. Proposi-tion 3.5 implies that a nucleolus alliance structure, An, contains the singleton alliance con-sisting of the most downstream entity in the supply chain, {1}. Proposition 3.7 demonstratesthat when the increase ∆ in the direct emissions of firm j, aj + ∆, is sufficiently large, thenj and firms that are intermediate to j and the downstream entity 1 all belong to the samealliance, Pj in An. Finally, consider the supply chain represented in the right panel of Figure3.5. For i ∈ Ank ∈ An, a structural change to the supply chain at S ⊂ N that is upstream tofirm j, such that j is not downstream to any firm in Ank , will not increase the allocation tofirms in V (Ti) according to Proposition 3.8.3.6. Fairness, Welfare and Incentive ConsiderationsIn this section, we consider a regulator implementing a carbon penalty levied at a price pt onthe emissions attributed to each firm in the supply chain as described in §3.2.4. The welfaregains for a firm i upon the adoption of the emission responsibility allocation vector x, is thengiven by, θi(x) = pt (xi − xi). Thus, the welfare of the overall supply chain given the allocationx, is Θ(x) =∑i∈Nθi(x), and therefore, for all efficient allocation mechanisms x, Θ(x) =pt(∑i∈Nc({i}) − c(N)) ≡ W , a constant. Thus, under an emission penalties policy regime,56every efficient emission responsibility mechanism including the nucleolus, not surprisingly,attains identical supply chain welfare4.However, different responsibility apportionment mechanisms distribute the net welfaredifferently across the supply chain. A report commissioned by the Natural Resources Canadato review energy regulators within Canada and internationally (Stratos 2017) observes that afair distribution of costs across the economy engenders trust and fosters participatory decisionmaking. Further, as noted previously, fairness is one of the five yardsticks recommendedby the Canadian government to evaluate environmental policy proposals. This, therefore,calls for a formal conceptualization that can evaluate the fairness of the distribution of theregulatory burden.Lexicographic Fairness We consider a criterion, briefly introduced in §3.2, based onthe Rawlsian notion of distributive fairness. For a set of firms S in the fossil fuel supplychain, consider the vector of welfares across subsets of firms in S induced by the allocation ofresponsibilities x, Θ(S, x) = (θ(T, x))T∈2S , in which the welfares are arranged in an increasingorder. Lexicographic fairness is achieved by maximizing the welfare of the least well-off setof firms, and then subsequently, maximizing the welfare of the second least well-off set, andso forth. This embodies the Rawlsian approach to fairness and has been previously employedin the operations literature (see, for example, Singh and Scheller-Wolf 2018). More recently,lexicographic fairness rules have also been adopted in the machine learning and mechanismdesign literature (e.g., McElfresh and Dickerson 2017).Proposition 3.9. The nucleolus allocation is the unique efficient emission responsibilityallocation mechanism that induces non-negative welfares and distributes the regulatory costsborne by the firms in N in a lexicographically fair manner.Welfare Gains and Abatement IncentivesBeyond the implications of the apportionment mechanism on the fairness of the distributionof the economic burden on the supply chain, it can also be analyzed via its effects on thewelfare gains delivered to each individual firm. To that end, in Theorem 3.6, we providelower bounds on the welfare gains, θi(z) = pt (xi − zi), provided by the nucleolus allocationmechanism, z, in relation to the baseline allocation mechanism x, xi = c({i}) that, as notedpreviously, attributes all upstream emission responsibility to each firm in the supply chain.4In this paper, we consider a regulator that collects a carbon penalty from each firm based on the attributedemissions. If instead, the upstream emissions attributed to a firm are compared against a threshold forrejection, or if the firms are expected to offset only the portion of emissions that exceeds the threshold,then the supply chain welfare will not be invariant across all efficient allocation mechanisms. The supplychain welfare will then depend on the allocation mechanism used as well as the thresholds determined by theregulator.57Since we further assume, as is typical in the environmental operations literature (see, forexample, Caro et al. 2013) that the emissions allocated to a firm and the resulting financialpenalties do not impact the revenues from their core operations, the bounds can thereforealso be interpreted as bounds on the costs savings delivered to firms due to our allocationmechanism z.Moreover, in Theorem 3.6, we also provide guarantees in terms of lower and upper boundson the ability of the nucleolus allocation to render potentially available emission reductiontechnologies profitable for a specific firm beyond the business-as-usual emissions. That is, webound the technology adoption incentive ratio for firm i, ωi(x)/ωi(x) between an allocationmechanism x, and the baseline allocation, x, as introduced in §3.2.4.Consider a fossil fuel supply chain with the set of firms N , and a corresponding emissionsprofile (ai; a−i). Let A(i) denote the alliance containing i that belongs to the nucleolus alliancestructure derived by Algorithm A. Now, we recall that for an alliance A, U(A) denotes theset of firms in N that are either in A or are upstream to some firm in A, and Ui denotes theset of firms immediately upstream to firm i. Finally, let Ii 6=1 represent the indicator functiondenoting whether i 6= 1.Theorem 3.6. Consider a firm i ∈ N in the fossil fuel supply chain, and let z denote thenucleolus allocation. Then,θi(z) ≥ ptxi(1− 1|A(i) ∩ Ti|+ Ii6=1)θ1(z) ≥ pt(x1 − a12)θi(z) ≥ ptIi 6=1(3xi − ai4− maxj∈Ui aj12),and1|U(A(i))|+ 1 ≤ωi(z)ωi(x){≤ 12 if i 6= 1,= 1 if i = 1.Theorem 3.6 provides lower bounds on the welfare gains, or equivalently cost savings,delivered to firm i by adopting the nucleolus mechanism to apportion upstream emissionresponsibility in relation to the baseline attribution mechanism. In particular, it providestwo distinct approaches to compute the lower bounds, one in terms of the nucleolus alliancestructure, and the other that is independent of it. Qualitatively, we immediately obtain,for example, that in supply chains where the most upstream emissions are relatively largerthan the other direct emissions, the lower bound on the welfare delivered to firm 1 by thenucleolus mechanism, compared to the penalty imposed on it by the baseline mechanism,ptx1, is approximately 1/2. Similarly, from the third inequality, for any firm i 6= 1 that issufficiently downstream, the lower bound on the welfare delivered by the nucleolus, comparedto the baseline penalty, is approximately 3/4. Further, in these supply chains, since thenucleolus alliance containing i, A(i), will include all firms in the subtree rooted at i, Ti, thefirst inequality implies that the lower bound on the welfare delivered by the nucleolus canbe strengthened to |Ti|/(|Ti| + 1) of ptxi. Moreover, Theorem 3.6 also provides guaranteesin terms of lower and upper bounds on the ability of the nucleolus allocation to render58potentially available emission reduction technologies profitable for a specific firm in the supplychain. For i = 1, the nucleolus mechanism captures the incentives offered by the baselinemechanism fully, while for firms i 6= 1, it incentivizes the adoption of at most half the spaceof potentially available technologies as compared to the baseline mechanism. We note thatthese upper bounds obtained in Theorem 3.6 are for general situations where we have noa priori information on the available set of technologies and hence they are assumed to lieanywhere arbitrarily on the abatement cost plot.Recall that Ω(x) denotes the volume of the space, T (x), of potentially available costlytechnology vectors t = {ti}i∈N that would be adopted in equilibrium under the allocationrule x. Since, all efficient allocation rules yield identical supply chain welfare in an emissionspenalty regime, then, if pt is set at the social cost of carbon pS , the socially optimal allocationrule concordant with the upstream emission responsibility principle maximizes Ω(x). Thatis, x∗ = arg maxx∈CΩ(x), where C denotes the space of efficient and concordant allocation rules,and we note that herein we relax the consistency constraint in the regulator’s optimizationproblem as formulated in §3.2.4. Unfortunately, the socially optimal allocation mechanism,x∗, is difficult to characterize. Computing the socially optimal allocation for a given emissionsprofile, {ai : i ∈ N}, in fact, involves jointly identifying x∗ for all emission profiles, {bi : bi ≤ai, i ∈ N}. This renders the computation of x∗ intractable even for small instances andconsequently, impractical to implement in practice.Similarly, the non-separability of the nucleolus allocation to firms in the profile of emis-sions across the supply chain, renders the characterization of the space of profitable technolo-gies for the entire supply chain under the nucleolus allocation challenging. We are neverthelessable to leverage a decomposition property to once again provide reasonable bounds on theperformance of the nucleolus mechanism in relation to the incentives provided by the baselineallocation mechanism.Consider the supply chain tree T with k (≥ 1) firms that are immediately upstream tofirm 1, which we recall, is the most downstream firm in the supply chain. Then, the nodescorresponding to the firms in the supply chain can be partitioned as V (T ) = {1} ⋃i∈U1V (Ti).Theorem 3.7. Consider a fossil fuel supply chain represented by the directed tree T and letz denote the nucleolus allocation mechanism. Then,Ω(z)Ω(x)≥ 11 + maxi∈U1|Ti| .We note that for given specific supply chain configurations, the bounds derived abovecan be tightened by exploiting their structural features. Now, in order to further clarify theenvironmental outcomes offered by the nucleolus allocation mechanism z from the regulator’sperspective, we analyze its relative performance as compared to two other salient allocation59mechanisms for certain limit supply chain configurations. First, we consider the sociallyoptimal efficient and concordant mechanism x∗ described previously. Second, we consideran emission allocation mechanism studied in Gopalakrishnan et al. (2018), the Shapleymechanism, denoted by xS , which attributes an equal share of the direct emissions ai of anentity i to all firms downstream to i. We note that x∗ and xS will, in general, not satisfythe notion of consistency and are therefore feasible solutions of the regulator’s optimizationproblem only upon relaxing this constraint.Consider a fossil fuel supply chain, SC = (V,E, a,N), where V = N ∪ {0} and E arethe vertex and edge sets, respectively, of the directed tree T representing the supply chain.Let Sk denote the star tree structure for a supply chain with k + 1 firms with directed arcsleading from k upstream nodes to a single downstream node 1. Further, consider a potentiallyavailable technology vector t = {ti}i∈N ∈ T (x), where recall that T (x) corresponds to then-dimensional space of potentially available costly technology vectors that would be adoptedin equilibrium under the allocation rule x and a carbon price pt. To clarify, Ω(x) denotesthe volume of T (x). Then, let a(t) = ∑i∈N(ai − ei(ti)) correspond to the entire supply chain’semissions upon adoption of the technology vector t.Theorem 3.8. Consider a fossil fuel supply chain represented by the weighted directed treeT . Let x∗, xS, and z, denote the socially optimal concordant mechanism, Shapley mechanismand the nucleolus mechanism respectively.(i) Suppose T = Sk, then Ω(xS) = Ω(z) ≤ Ω(x∗),(ii) Suppose a(Tij) ≤ aj for all adjacent players i, j ∈ N , then Ω(xS) ≤ Ω(z) < Ω(x∗),(iii) Suppose that for some i ∈ N , ai →∞, then for each t∗ ∈ T (x∗), there exist tS ∈ T (xS)and tz ∈ T (z) such that limai→∞a(tS)/a(t∗) = limai→∞a(tz)/a(t∗) = 1.Theorem 3.8 demonstrates that for supply chains in a star configuration, the volumeof the space of technology vectors incentivized for adoption by the nucleolus and Shapleymechanisms coincide. For supply chains where the direct emissions are sufficiently increasingdownstream, the nucleolus outperforms the Shapley mechanism. Naturally, in both cases,these two allocations are outperformed by the socially optimal concordant mechanism. Fi-nally, in supply chains, where the direct emissions of some entity is sufficiently large, then foreach technology vector supported in equilibrium by the socially optimal mechanism, thereexists equivalent technology vectors that will be supported in equilibrium by the nucleolusand Shapley mechanism achieving identical net supply chain emissions.603.7. Case Study – Trans Mountain Pipeline SystemThe Trans Mountain Pipeline (TMPL) is an oil pipeline network in Western Canada from Ed-monton to Burnaby that provides Alberta’s oil sands access to Pacific shipping routes via theports of the province of British Columbia. A recent controversial proposal to nearly triple itsnominal capacity from the current capacity of 300,000 barrels/day to 890,000 barrels/day hasrun into significant opposition primarily on the basis of its environmental impacts. Canada’sextensive oil sands account for 14% of global oil reserves (O&GJ 2004) and an expansionof the TMPL opens up economically lucrative shipping routes for the crude oil extractedfrom Alberta’s oil sands. However, oil sands have often been the target of environmentalgroups since the life-cycle carbon emissions associated with oil sands is higher than fromconventional crude oil, largely arising from higher emissions in the extraction, transportationand refining stages. In the following emissions accounting study, we focus on seven in-situ5oil sands and heavy oil projects that are expected to contribute around 224,500 bbl/day ofcapacity between 2016 and 2019 (ECCC 2016). Transported via the TMPL, the bitumen isthen to be shipped via the Westridge Marine Terminal in Burnaby, British Columbia, andexported to refineries in the Asia-Pacific region.As previously discussed, the Canadian federal government, since 2016, has a stated ob-jective of factoring in upstream emissions associated with a project during its environmentalimpact assessment and in setting emission reduction targets for individual energy projects.In this section, based on available data and estimates, we provide a well-to-wheel (WTW)accounting of the emissions associated with the different stages of the fossil fuel supply chaincorresponding to the TMPL expansion project. We then illustrate a practical application ofour proposed nucleolus mechanism to attribute upstream emission responsibilities to individ-ual entities in the supply chain and discuss its implications in this particular context.The map6 and a schematic of the fossil fuel supply chain associated with the TMPL aredepicted in Figure 3.6. The direct emissions associated with each stage in the above supplychain, represented as arc weights in our game-theoretic model, are provided in Table 3.1.The assumptions and approximations that went into the carbon footprint computations aredescribed in Appendix C and are largely based on data and estimates provided in ECCC(2016) and Charpentier et al. (2009). From our carbon footprinting analysis (Table 3.1), wefind that the supply chain associated with the oil sands and the TMPL has a carbon footprintof 105.54 kiloton (kt) CO2Eq/day, and we observe that the extraction emissions accountsfor around 17% of the total supply chain emissions, which is in line with estimations from5In-situ mining is one of two main methods of recovering the deposits, the other being surface mining forshallower mines. Dyer and Huot (2010) estimate that 80% of Alberta’s oil sands necessitate in-situ miningand is associated with two and half times as much emissions per barrel of bitumen as surface mining.6Trans Mountain Jet Fuel and Trans Mountain Puget Sound are two further re-routings of the TMPLwhich we omit from our case study.61Figure 3.6: A map of the Trans Mountain pipeline expansion project and a schematicof the supply chain associated with the pipeline.other similar sources (Charpentier et al. 2009). Further, the largest share of greenhouse gasemissions in the supply chain, around 66%, expectedly arises from the eventual downstreamcombustion of the extracted fossil fuel. The direct emissions associated with the intermediateprojects, the TMPL expansion and the Westridge Terminal, account only for a minor portionof the total supply chain emissions.The responsibility allocations to the entities in the fossil fuel supply chain in accordancewith the nucleolus mechanism can now be computed using the algorithm presented in §3.3,both in absolute terms and as a percentage of the total emissions associated with the sup-ply chain, and are also provided in Table 3.1. Responsibility allocations corresponding tothree alternative mechanisms that are also concordant with the upstream responsibility prin-ciple are considered. The first is the baseline, or the total upstream responsibility (TUR)mechanism, x, discussed in §3.2, that double counts and holds each entity responsible for allassociated upstream emissions. Secondly, since the total upstream responsibility mechanismis inefficient, we consider a natural adjustment to the TUR mechanism, the adjusted totalupstream responsibility (Adjusted TUR) mechanism, xµ, that identifies a scaling factor µrendering the mechanism efficient. That is, xµi = x/µ, where,µ =∑i∈N xic(N). (3.12)Third, we compute the Shapley mechanism discussed in §3.6. Comparing the four differentallocations, we qualitatively observe some salient features. The TUR mechanism, as well asthe Adjusted TUR mechanism, attribute a relatively much larger responsibility to the TMPL,the main entity of interest in the supply chain. This explains the environmental NGOs’preference for the TUR method. However, the nucleolus allocation, which incorporates theprinciple of upstream responsibility across the supply chain and was shown to be consistent62in a well-defined sense and to fairly distribute the regulatory burden across the supply chain,only allocates TMPL responsibility for 2.79% of the total supply chain emissions.Supply Chain Member Direct Emissions TUR (Baseline) Adjusted TUR Nucleolus Mechanism Shapley MechanismConsumers 69.914 105.537 54.86% 57.898 54.86% 80.562 76.34% 82.580 78.25%Refineries 18.350 35.623 18.52% 19.543 18.52% 10.648 10.09% 12.666 12.00%Westridge Terminal 0.186 17.273 8.98% 9.476 8.98% 2.947 2.79% 3.491 3.31%TMPL 0.227 17.087 8.88% 9.374 8.88% 2.947 2.79% 3.429 3.25%West Ells 0.533 0.533 0.28% 0.292 0.28% 0.266 0.25% 0.107 0.10%Vawn 0.751 0.751 0.39% 0.412 0.39% 0.375 0.36% 0.150 0.14%Edam East & West 1.089 1.089 0.57% 0.598 0.57% 0.545 0.52% 0.218 0.21%Hangingstone Expansion 2.148 2.148 1.12% 1.179 1.12% 1.074 1.02% 0.430 0.41%Christina Lake Phase F 5.362 5.362 2.79% 2.942 2.79% 2.681 2.54% 1.072 1.01%Foster Creek Phase G 3.222 3.222 1.67% 1.768 1.67% 1.611 1.53% 0.644 0.61%Mackay River Phase I 3.755 3.755 1.95% 2.060 1.95% 1.877 1.78% 0.751 0.71%Table 3.1: GHG emissions estimation for each stage in the fossil fuel supply chain andthe comparison of four alternative concordant allocation mechanisms (unit: ktCO2Eq/day). The emissions estimation only accounts for seven in-situ oil sandsand heavy oil projects that are expected to contribute around 224,500 bbl/day ofcapacity between 2016 and 2019.Further, all mechanisms based on the upstream emission responsibility principle shift asignificant portion of the responsibility for upstream emissions downstream, leaving the up-stream oil sands projects to bear a lower responsibility relative to other entities. In fact, theoil sands are nearly allocated identical relative responsibilities by three of the mechanisms.Environmental activists and regulators must take note that pushing for extended upstreamemission responsibility across the supply chain might result in certain key entities in thesupply chain, such as the upstream oil sands projects, being accorded a smaller relative re-sponsibility. This is particularly acute when the Shapley mechanism is employed to correctdouble counting. The nucleolus allocates to the TMPL, the Westridge Terminal and the endconsumers a larger responsibility than their own direct emissions, while the refineries and theoil sands are allocated smaller responsibilities. Further, the nucleolus, in fact, allocates equalresponsibility to both the TMPL and the Westridge Terminal entities, thereby providing somebasis for recent efforts by NGOs and activists to also focus on bringing intermediate supplychain entities such as shipping terminals used to transport fossil fuels into the discussionon climate change (Harrison 2015). We note that since mechanisms concordant with the up-stream responsibility principle shift the economic burden downstream towards end-consumersand other entities possibly situated in different jurisdictions, the distributional ramificationsof these mechanisms warrant more in-depth attention in future work.63Numerical AnalysisWe now proceed, as part of the case study, to numerically analyze the environmental andeconomic consequences of adopting the nucleolus mechanism to apportion upstream emissionsunder a flat carbon penalty pt, i.e., a carbon tax policy regime, at varying levels of the penalty,pt, from $20 to $50 per tonne CO2. The range of carbon penalties was chosen based on aninitiative to price carbon at the federal level in Canada which starts at $20 per tonne of CO2in 2019 and expected to ratchet up to $50 per tonne by 2022. We perform the analysis for akey entity in the pipeline supply chain, the TMPL, henceforth denoted as firm f .The additional economic costs imposed on the firms in the supply chain by the variousallocation schemes can be computed from their allocations provided in Table 1. In particular,at the baseline emission profile, f is allocated 17.087, 9.374, 2.947, and 3.429 kt CO2eq/dayby the TUR, adjusted TUR, nucleolus, and Shapley mechanisms, respectively. Firm welfareθf (x) (measured in 1000$/day) delivered by an allocation x (expressed in kt CO2eq/day)is obtained by comparing it with the economic costs associated with the baseline allocationmechanism, x, θf (x) = pt[xf−xf ]. Therefore, while the TUR mechanism delivers the baselinefirm welfare of zero, θf (x) = 0, the adjusted TUR mechanism has an associated firm welfare,θf (xµ) = 7.713pt. The nucleolus mechanism provides θf (z) = 14.14pt, and the Shapleymechanism delivers θf (xS) = 13.658pt.Figure 3.7: Region of potentially available technologies rendered profitable by thefour allocation mechanisms (left panel). The social environmental welfare andfirm welfare generated by the four mechanisms as a function of the carbonprice, pt (right panel).To analyze the environmental effectiveness of each allocation mechanism, as discussed in§3.6, we evaluate ωf (x), the area of the space of all potentially available costly emission-reduction technologies rendered profitable by each allocation mechanism. Recall that 0.22764is the direct emissions of f , and consider all potentially available technologies t with anassociated emission reduction 0 < e(t) ≤ 0.227 at a cost 0 ≤ c(t) < ∞. Upon adopt-ing technology t, the TUR allocation is given by, xf (af − e(t); a−f ) = 17.087 − e(t), andthe adjusted TUR by, xµf (af − e(t); a−f ) = (c(N) − e(t))(xf − e(t))/((∑i∈N xi) − 4e(t)) =(105.537− e(t))(17.087− e(t))/(192.38− 4e(t)). It can also be easily seen that the nucleolusalliance structure of the supply chain does not change by the adoption of emission reducingtechnologies by firm f , and therefore, zf (af − e(t); a−f ) = 2.947 − e(t)/3. Further, sincethe Shapley mechanism attributes an equal share of the emissions af to each entity down-stream to f , we have, xSf (af − e(t); a−f ) = 3.429 − e(t)/4. For an allocation x, we recallthat ωf (x) is the area of the region (denoted by Rf (x)), defined by 0 < e(t) ≤ 0.227 and0 ≤ c(t) < pt[xf (af ; a−f )−xf (af − e(t); a−f )]. In Figure 3.7 (left panel), we depict ωf (x) forthe four allocation mechanisms considered.Further, we note that the social environmental welfare derived from the adoption of a tech-nology t would be pte(t) − c(t). Therefore, we denote by SEWf (x) =∫Rf (x)(pte(t) − c(t))dt,the total social environmental welfare associated with the incentives offered by an allocationmechanism x to adopt potentially available emission abatement technologies. We numericallyevaluate the integral for the four different allocation mechanisms, and obtain the relative per-formances of the nucleolus allocation, SEWf (z)/SEWf (xµ) = 0.801, SEWf (z)/SEWf (x) =0.554, and SEWf (z)/SEWf (xS) = 1.270.A comprehensive comparison of the allocation mechanisms would also incorporate thewelfares delivered to the firm along with the social environmental welfare from incentiviz-ing potentially available emission abatement technologies. Therefore, in Figure 3.7 (rightpanel), we plot SEWf + θf as a function of the carbon price, pt. We observe that the nucle-olus mechanism outperforms the other three allocation mechanisms in terms of SEWf + θfacross pt. In our example, this is driven by the substantially lower economic costs leviedon the pipeline under the nucleolus mechanism resulting in higher firm-level welfare, θf (z).The nucleolus mechanism unambiguously outperforms the Shapley mechanism and generateshigher firm-level welfare as well as incentivizes a larger set of potentially available emissionabatement technologies. The nucleolus mechanism also performs fairly well in capturing theenvironmental benefits relative to the TUR, that allocates all upstream emissions to eachindividual firm, as reflected in our numerical estimates. We further note that while the ineffi-cient baseline allocation mechanism, x, shall always perform better than the nucleolus, z, atincentivizing potentially available emission abatement technologies, it is done at the expenseof significantly lower supply chain and firm-level welfare.In our example, the adjusted TUR mechanism performs marginally better than the nucleo-lus in terms of incentives offered, however, it delivers substantially lower firm welfare. Furthernumerical experiments, discussed in Appendix D, confirm that in supply chains where the65baseline mechanism suffers from excessive double counting, that is, when µ is sufficiently large,the adjusted TUR mechanism performs worse than the nucleolus at incentivizing emissionabatement technologies.3.8. DiscussionThe problem of assigning responsibility for emissions among the different members in ex-tended supply chains has recently received attention in the environmental and life-cycle as-sessment literature (for example, Kander et al. 2015). Motivated by the Canadian federalgovernment’s guideline of factoring in upstream emissions during the environmental assess-ment of proposed energy projects, we adopt a natural cooperative game theoretic approachand propose the nucleolus of an associated cooperative game as a mechanism to apportionemission responsibilities while being concordant with the principle of upstream emission re-sponsibility. Our contributions include (i) the development of a quadratic time algorithm tocompute the nucleolus of the associated cooperative game, (ii) the clarification that in thecontext of fossil fuel supply chains, the nucleolus is the unique single-point game theoreticallocation mechanism with a natural consistency property. Such a property makes the nu-cleolus an especially desirable allocation method since fossil fuel supply chains typically spanmultiple legal jurisdictions. Further, and quite importantly, (iii) we provide a self-enforcingimplementation framework consisting of easily-stated and compliance-verifiable policies, anda well-specified protocol, that are sufficient for the regulator to enforce the nucleolus mech-anism to allocate upstream emissions in supply chains with profit-maximizing firms. Wealso, (iv) prove certain structural results that highlight the interpretability of the proposednucleolus mechanism, (v) demonstrate that the nucleolus is the unique allocation mechanismthat distributes the regulatory burden across the supply chain in a formalizably fair manner,and (vi) provide bounds on the welfare the nucleolus delivers to firms and its performance interms of incentivizing firms to adopt potentially available emission reducing technologies.Finally, we contextualize our results by analyzing a proposed pipeline project in WesternCanada, the Trans Mountain pipeline expansion, that transports bitumen extracted fromoil sands in Alberta to the ports of British Columbia. Our results illustrate the benefitsand insights of the upstream responsibility principle, and more particularly, in adopting thenucleolus allocation mechanism in fossil fuel supply chains. We hope that they will serve as auseful case study for policy makers and environmental activists to analyze similar fossil fuelsupply chains in other regions.To assess the relative merits of our proposed nucleolus allocation mechanism, we couldalso consider the five evaluation criteria recommended by the Government of Canada, in2005, to assess environmental tax proposals: (i) environmental effectiveness, (ii) fiscal impact,66(iii) economic efficiency, (iv) fairness, and (v) simplicity of administration. Adopting theseas measuring sticks, we observe that the consistency property of the nucleolus mechanism,and its equilibrium properties subject to the easily stated and verifiable policies we provide,speak to the simplicity of administration and fairness. Fairness is also enshrined by thelexicographic distribution of welfares by the nucleolus allocation transposing the Rawlsiantheory of justice to allocation problems as elaborated in §3.6. We also observe that thenucleolus allocation, by virtue of its footprint balancedness, is economically efficient under acarbon tax policy regime, as are all other footprint-balanced mechanisms. The fiscal impactof the nucleolus apportionment mechanism as well as its environmental effectiveness dependon the precise manner in which it is integrated with broader environmental policy regimessuch as a carbon penalty. These are analyzed in §3.6, and in particular, in Theorems 3.6, 3.7,and 3.8, as well as in the case study.Our results provide managerial implications for energy regulators. Indeed, they implythat a mandated, centrally determined and binding emission responsibility allocation schemecan be replaced, in some sense, by a decentralized scheme. That is, regulators can providesome degree of freedom to entities in fossil fuel supply chains to collectively arrive at anapportionment of pollution responsibilities that is beneficial from the entire supply chain’sperspective. In that respect, it should be noted that a decentralized policy framework, thatcalls upon supply chain entities to collaborate with their partners, may catalyze additionalancillary environmental benefits.67Chapter 4Bike-Sharing Systems: An Analysis ofOperational Strategies4.1. IntroductionBicycle sharing is a transportation system in which bike stations are distributed across aregion and users rent a bike for a short duration with the option of returning it at anyother station. Bike sharing is fast emerging as a sustainable and environmentally friendlyalternative, that complements the traditional modes of transportation to meet growing urbantransport needs.From an operational standpoint, bike sharing presents several unique challenges. Mostnotably, spatial asymmetries in the underlying demand, over time, results in certain stationswith no bicycles to rent and some stations with no empty docks to return bikes. Thisnecessitates rebalancing the stations periodically whereby bikes are relocated from stationsthat are full, to stations with zero or too few bikes. Efficient and frequent rebalancing has beenobserved to be crucial to the success of a bike-sharing program as it improves its reliabilityand has thus been the subject of extensive studies recently, for example, by Freund et al.(2019) and Raviv et al. (2013). Despite the growing popularity of bike sharing, systems inseveral major cities, such as Seattle’s Pronto and Bixi in Montreal have run into financialdifficulties. High operational costs arising from system rebalancing, theft and vandalism,coupled with lower than projected levels of ridership are commonly identified as the majorcontributing factors.On the other hand, the environmental benefits of a bike-sharing program, as a consequenceof reduced vehicular emissions from individuals substituting away from personal automobiles,might be less substantial than presumed. For example, the 2014 survey report of the CapitalBike Share Program in Washington D.C. notes that - “40% percent of respondents would68have ridden a bus or train if Capital Bikeshare had not been available for the most recenttrip, another 37% would have walked to their destination, only 12% of respondents wouldhave driven or ridden in a car.” Another survey of bike-share users in Portland (PBOT 2016)estimated that only up to a quarter of the users had substituted away from cars. Further,typically the rebalancing operations are carried out with trucks which results in significantcarbon emissions. Efficient rebalancing can therefore not only be economically desirable butcould also potentially result in lower emissions from the rebalancing phase. Both these factorsleads us to suggest that in certain cases, the environmental benefits of bike-sharing programsmight be overstated. Lending further evidence, Fishman et al. (2014), using surveys andbike trip data, study the environmental impact of bike share programs across four citiesworld-wide, and find that the London bike-share system had a net negative environmentalimpact.This motivates our work where we consider three key strategic and operational decisionsfaced by bike share operators - the coverage and density of the system, the pricing model andthe frequency of rebalancing. Our objective is to develop a framework that can be employedby planners to design bike-sharing systems that are financially viable with high ridership andlow operational costs which maximize environmental benefits.Related LiteratureIn this work, we contribute and draw from three distinct strands of literature - the emergingoperations literature on bike sharing programs, the growing field of sustainable operationsmanagement and the mature body of work pertaining to continuous approximation modellingof distribution problems.Bike Sharing Programs. The sharing economy, and specifically, vehicle sharing businessmodels, raise several challenging operational problems. Much of the existing literature onbike-sharing systems focuses on developing and solving optimization models to address spe-cific operational problems during the management of these systems. Vehicle routing modelsfor rebalancing bike stations efficiently have attracted much attention (see, for example, Ra-viv and Kolka 2013, Raviv et al. 2013, Shu et al. 2013, O’Mahony 2015, Freund et al. 2019,Schuijbroek et al. 2017). Another question of interest that has been studied pertains to theoptimal allocation of docks across stations (O’Mahony 2015, Freund et al. 2017). In con-trast, we adopt a holistic modelling approach that addresses the impacts of key operationalstrategic decisions undertaken by city planners while incorporating the role of existing modesof transport. In related work, Kabra et al. (2019) perform an empirical study to estimatethe effects of accessibility and availability of bikes on ridership.Continuous Approximation Modelling. Methodologically, we build on the continuousapproximation (CA) modelling literature that develops analytical models to obtain qualitative69insights on trade-offs in transportation systems. CA models, introduced by Newell (1973),provide an alternative to mathematical programming, i.e., discrete optimization models inthe analysis of logistic systems. Unlike discrete optimization models that attempt to captureand model the system of interest as accurately as possible, CA models make approximateassumptions that replace discrete variables with continuous ones, in the interest of obtainingclosed-form solutions. Along with analytical tractability, CA models also therefore allow thederivation of managerial insights. We refer the reader to Daganzo (2005) and Langevin etal. (1996) for a comprehensive discussion of the CA method and its application to logisticssystem analysis. Ansari et al. (2018) provide a more recent survey of CA applications. Inthe operations literature, CA models have also recently found applications in studies thatprovide high-level policy insights into the economic and environmental impacts of operationaldecisions in several settings such as retail location (Cachon 2014) and online grocery retail(Belavina et al. 2017). Our paper is most closely related to this line of literature.Sustainable Business Models. More broadly, we also contribute to a growing sustainablebusiness model innovation (Girotra and Netessine 2013) literature that studies the interac-tions between operational strategies and the economic and environmental performance of newbusiness models, for example, shared logistics (Qi et al. 2018), online grocery retail (Belavinaet al. 2016), and car sharing programs (Bellos et al. 2017).4.2. Model SetupWe consider a region R, such as a metropolitan area or a city, which either operates oris considering the adoption of a bike-sharing system. Unlike a majority of the operationsliterature on bike-share systems which assume an exogenous demand for each station, wemodel the underlying demand in the region R and assume an origin-destination transportdemand function. The travel demand between any two locations u and v in the region, with ageographic distance between them denoted by d(u, v) is given by D(u, v). In this section, wedescribe the framework we adopt to model the operational and strategic decisions faced bythe bike-share system operator, and the consumer utility model that governs the transportmode choice for different individuals.4.2.1 Bike Share System OperatorWe consider a transportation planner or an operator O who is planning to operate a bikesharing system in the region R. The bike share system operator O faces several designconsiderations and operational decisions.i. Coverage and Density. We assume that the operator O chooses a radius of coverage, Rin which to locate the N bike share stations. By choosing a coverage radius, R, and given70the number of stations, N , the operator consequently decides the density of stations per unitarea, ρ = N/piR2. This captures a fundamental strategic choice faced by bike-share operatorsof deciding between a sparse but widely spread system versus a smaller but denser system.We also note that in practice, as assumed in our model, typically the number of stations Nis either an exogenous constraint on the operator or is a more stringent resource constraint.We assume a fixed bike-sharing system wherein users rent bikes from stations at definedlocations and return to any other station upon completion of the ride. This is a popular modelin operation across many cities including Paris, New York and Vancouver. Alternately, Ocould also choose to operate a free-floating bike share system in which users find the closestbike to them via a mobile application and then could leave it at their destination. Thiseliminates the need for stations in the bike share system. Some bike share programs in Chinahave adopted a free-floating model. We propose this as a potential extension of our model.ii. Rebalancing Service Level. Spatial asymmetries in the underlying demand, over time,results in certain stations with no bicycles to rent and some stations with no empty docksto return bikes. This necessitates rebalancing the stations such that bikes are moved fromstations with a more than optimal number of bikes to stations with zero or too few bikes. Theoperator O also chooses a rebalancing plan with an intent to maintain a specific service level,i.e., a specified probability ν of finding a bike (an empty dock) at a station. For exampleν = 0.95 would correspond to a situation wherein the probability of finding a bike (an emptydock) at a station is 0.95. Such service level requirements are routinely imposed on bike-shareoperators by the city and they, in turn, determine the extent of rebalancing that the operatorwill have to carry out.iii. Pricing Model. A large majority of bike share systems adopt a subscription-based pricingmodel with an annual, monthly or a daily pass (or a combination of the three) with a farewhich entitles pass holders to unlimited rides of a fixed duration TB. Let the amortized fareaveraged over the expected number of trips be denoted by KB. Further, the user will incura usage fee fB per unit distance for rides exceeding the specified duration. A few bike sharesystems in Europe such as in Germany charge only the marginal usage fee. In this paper, weconsider a unified framework for both pricing models by considering the marginal fee modelas a case where KB = TB = 0 and model the subscription fee and the free-ride durationand the usage fee as set by the bike share operator O. However, we recognize that in manyinstances the fare structure is also influenced by other considerations that are not necessarilyrevenue or welfare-maximizing, such as for example, to avoid competition with existing bikerentals.714.2.2 Consumer’s Mode Choice ModelWe consider three distinct transport options - a private car (C), public transit (P) andbike-sharing (B). Further, we also consider the option of a bimodal transport option - thatcombines bike-sharing and public transit (BP). While we ignore other forms of transportationsuch as taxis and other emerging modes such as ride-sharing services for parsimony, our modelcan be extended to include these alternate modes of transportation without foregoing the keyinsights derived from our model and we leave this for future extensions of our model. Weassociate a utility function Ump for each mode of transport m ∈ {C,P,B,BP} for everyindividual p in the population P. We consider three drivers of mode choice behaviour.i. Accessibility. Access time for mode m, τma is determined by the time to get from theindividual’s origin to the starting location of the service and getting from the end locationof the service to the individual’s destination. The access time for a privately owned vehicleis assumed to be zero.ii. Service Level. Waiting time τmw corresponds to the time spent in waiting to receive theservice and is a measure of the service level of the system. For a privately owned vehicle,this is again reasonably assumed to be zero, while for a public transit option, it is tied tothe frequency of the service. For bike sharing systems, while it is true that stations canbe full or empty rendering them unavailable, most modern bike-sharing systems rely onmobile applications which convey the information on the availability of bikes and docks inneighbouring stations, thus essentially nulling the waiting time. However, it is to be notedthat even in such systems with informative mobile applications, unavailability of bikes anddocks in the closest station increases the access time of the system.iii. Generalized Travel Cost. Generalized travel cost incorporates the travel fare τmg for bike-share programs and public transit are determined by the monetary costs associated with thetrip such as the fare or fuel cost, and the monetary equivalent of the in-vehicle travel time.Note that we extend Kabra et al. (2016, 2019) who consider two main drivers of consumerdemand in bike-share programs - availability and accessibility which correspond to our accesstime and waiting time. Traditionally, transportation models also incorporate factors suchas income and age as explanatory variables in travel mode choice. We ignore these socio-economic factors in our model for mathematical tractability. However, we also note thatthese factors can be ignored by suitably choosing the population under consideration P asthe set of individuals which are potential users of a bike sharing system. Indeed, severalempirical studies have noted that users of bike share program typically are homogeneous insocio-economic characteristics.The utility of a travel mode m for individual p with an origin-destination pair (u, v),72consists of the utility that the individual derives from the trip, along with the disutilityassociated with the mode of transport associated with the drivers discussed previously,Um(p) = θ(p)− θaτma (p)− θwτmw (p)− τmg (p). (4.1)θ(p) denotes the intrinsic utility derived from the trip for an individual p with an originu and a destination v. Note that equivalently, the utility function could alternatively bedefined over trips with a given origin-destination pair (u, v), instead of over individuals. Theutility derived for a trip with origin-destination given by (u, v) would be given by Um(u, v) =θ(u, v)−θaτma (u, v)−θwτmw (u, v)−τmg (u, v), where individuals have possibly different utilitiesfor the trip, θ(u, v), drawn from a distribution Fuv.Figure 4.1: Timeline of EventsTimeline of EventsThe bike share program operator O initially chooses the radius of coverage. Subsequently,the operator decides on the pricing model of the program. Then, in each time period T ,individuals of the population P evaluate the available modes of travel - private automobile,public transit, bike-share or a bimodal choice combining public transit and bike-share, andchoose the utility-maximizing option considering travel time, accessibility, service level andtravel fare. Also, periodically, during T , O rebalances the bikes in the system at a chosenfrequency. The frequency of rebalancing operations, in turn, determines the service levelof the bike-share system and therefore the usage of the system. The timeline of events isillustrated in Figure 4.1.4.3. Operational Decisions and Bike-Sharing DemandThe operational decisions of the bike-share operator - the coverage of the system or equiva-lently, the density of stations and the rebalancing service level evidently affect the ridership73in the system via their effects on the three drivers of mode choice. We thus begin our analysisby considering the impacts of these decisions on accessibility, service levels and generalizedtravel cost of the different travel mode options.4.3.1 Drivers of Mode ChoiceThe access time of an individual to the bike-sharing program depends on the density ofstations and the availability of working stations, that is, those that are neither empty norfull.Theorem 4.1. (Accessibility) The average access time 〈τBa 〉 for an individual using thebike-sharing system is given by,〈τBa 〉 ∼=4Rγ (N, ν)vW.Theorem 4.1 provides an expression for the average access time for an individual usingthe bike-sharing system, where γ is a function of N and ν and further details are providedin the proof of Theorem 4.1. The access time for a private car is assumed to be zero, thatis, τCa = 0, while the access time for public transit τPa is exogenous to our model and reflectsthe density of existing public transit infrastructure in the city. For the bimodal option ofusing bike sharing and public transit for a trip, we have the access time τBPa = τBa . This isbecause, in the bimodal option, the individual uses bike-sharing to get to the public transitand therefore, the accessibility of the combined mode of travel corresponds to the accessibilityof the first and last modes of transport which is bike-sharing.The second driver of consumer travel mode choice relates to service levels of the corre-sponding modes, as measured by the time spent waiting to receive service, the waiting time.The waiting time for a private car is again assumed to be zero, that is, τCw = 0. The waitingtime for a bike in a bike-sharing system is again zero because we have factored in the waitingtime in the accessibility of the system. Indeed, recall that we defined the access time for anindividual using bike-sharing as the time to the nearest available bike, and thus τBw = 0. Thewaiting time for public transit τPw is exogenous to our model and corresponds to the frequencyof existing transit operations in the region. For the bimodal option combining bike-sharingand public transit, the waiting time arises in the public transit phase of the option, andtherefore, τBPw = τPw .Now, we consider the third driver of mode choice - generalized travel cost. Generalizedcost of travel comprises of both the fixed and variable monetary costs and the money-valuecorresponding to the travel time.74Automobile Public Transit Bike Sharing Bike Sharing – TransitAccess Time τCa = 0 τPa τBa (Theorem 4.1) τBPa = τBaWaiting Time τCw = 0 τPw τBw = 0 τBPw = τPwGeneralized Travel Cost τCg (Remark 4.1) τPg (Remark 4.1) τBg (Remark 4.1) τBPg (Remark 4.2)Table 4.1: Drivers of mode choice for the different modes of transportRemark 4.1. For an individual with origin u and destination v travelling by mode m ∈{C,P,B}, the generalized cost of travel τmg is given by τmg =[d(u, v)vm]θg + Km + d(u, v)fmwhere vm, Km, fm correspond to the travel speed, fixed cost and marginal cost of mode mrespectively.The fixed cost KC for a trip with a private car corresponds to costs such as parking fees,while the variable cost fC is the per-mile fuel cost. As mentioned earlier, KB is the amortizedfare averaged over the expected number of trips while fB is the usage fee per unit distancefor a bike-sharing program. While a large number of public-transit systems in North Americaoperate on a flat rate or a zone-based fee structure, certain public transport systems haveadopted a variable rate fare structure. Thus, we assume that KP is the flat-rate for publictransport in the region averaged over the expected number of trips while fP denotes thevariable fare rate. Further, let vW denote the average walking speed of an individual.Remark 4.2. For an individual adopting the bimodal bike sharing and public transport op-tion,τBPg =[d(u, v)vP+τPa vWvB]θg +KP +KB + τPa vW fB + d(u, v)fP .This is because, the in-vehicle travel time comprises of the time spent on the bike tocover the distances from the origin and destination to the nearest transit points, τPa vW , inaddition to the time spent in the public transit to travel the distance between the two transitpoints, which is on average d(u, v). The public transit leg of the journey has a fixed costKP while the third term corresponds to the cost of using the bike-sharing program fee to getto and from the locations served by public transit. For individuals travelling from origin uto destination v, the costs corresponding to the three drivers of mode choice for each travelmode are summarized in Table 4.1 and the utility of using mode m of transport can thus becomputed.754.3.2 Transportation Mode ChoiceNow, we are in a position to characterize the equilibrium transportation mode choices forindividuals with different origin-destination pairs across the region and consequently, theequilibrium demand for the different modes of transport. We say that an individual p withan origin-destination pair (u, v) prefers mode a to mode b if p derives a larger utility fromadopting mode a as opposed to mode b. For parsimony, we assume a deterministic modechoice model1.We assume that the speeds of the three modes of transport, vC , vP and vB, are orderedsuch that vC > vP > vB and further that vC is sufficiently greater than vP which in turn issufficiently greater than vB2. Firstly, we consider the base situation when bike-sharing is notoffered in the region. Then, in our model, a simple threshold exists to determine the choicebetween a private car and public transport.Proposition 4.1. An individual with origin-destination (u, v), prefers a car to public trans-port if and only if d(u, v) > d˜CP where,d˜CP =KC −KP − θaτPa − θwτPwθg[1vP− 1vC]+ fP − fC.We now consider the introduction of bike-sharing services in the region but without thepossibility of the bimodal transport option. In Proposition 4.2, we identify threshold condi-tions on when the users prefer a car and public transport to using bike-sharing.Proposition 4.2. An individual with origin-destination (u, v), prefers a car to bike-sharing(respectively, public transit to bike-sharing) if and only if d(u, v) > d˜CB (respectively, d(u, v) >d˜PB), where,d˜CB =KC −KB − 4Rθaγ(N,ν)vWθg[1vB− 1vC]+ fB − fC, (4.2)d˜PB =KP −KB + θwτPw + θa[τPa − 4Rγ(N,ν)vW ]θg[1vB− 1vP]+ fB − fP. (4.3)Further, we note that since bike-sharing systems have a finite radius of coverage, therewill exist users who might prefer to adopt bike-sharing but are unable to do so because theirorigin or destination falls outside the coverage area. A continuous approximation lets usidentify, given a coverage radius R, an upper bound for the travel distance d(u, v) beyond1The qualitative insights remain similar with other choice models such as a multinomial logit model andwe leave this for an extension of our base model.2The formal necessary condition is introduced in Appendix E.76which bike-sharing is not a viable mode of transport. We also refer the reader to Vaughan(1984) and Stone (1991) for similar results.Lemma 4.1. For a bike-sharing system with radius of coverage R, an individual with origin-destination (u, v) will not adopt bike-sharing if d(u, v) ≥ R˜, where R˜ ∼= 32R9pi .Finally, we now consider the bimodal option of bike-sharing with public transit. In Propo-sition 4.3, we provide conditions for when an individual prefers the bimodal option to eachof the three other modes of transport, a car, public transit and bike-sharing.Proposition 4.3. Consider an individual p with origin-destination (u, v),i. p prefers the bimodal option to bike-sharing if and only if,d(u, v) >θwτPw + τPa vW[θgvB+ fB]+KPθg[1vB− 1vP]+ fB − fP= d˜MB, (4.4)ii. p prefers the bimodal option to public transit if and only if,θa(τPa − τBa ) > τPa vW(θgvB+ fB)+KB, (4.5)iii. p prefers the bimodal option to a car if and only if,d(u, v) <KC −KB −KP − θaτBa − θwτPw − τPa vW[θgvB+ fB]θg[1vP− 1vC]+ fP − fC= d˜MC . (4.6)In Figure 4.2, we obtain schematic plots to illustrate Propositions 4.1-4.3. The parametervalues assumed for the schematic plots approximately reflect realistic estimates. We refer thereader to Appendix E for further details. Figure 4.2 identifies the mode choice of individualsfor varying trip distances. Broadly, our model implies individuals choose a car for largerdistances while preferring public transport or bike sharing for trips of shorter distances. Thishighlights the importance of studying the substitution patterns between public transport andbike-sharing. Moreover, the bi-modal option bears relevance on the environmental impacts aswell as the revenue from both bike-sharing and public transport. We provide below analyticalexpressions for the economic and environmental impacts of introducing bike-sharing in theregion.From Propositions 4.1-4.3, given an individual with an origin u and a destination v,the mode of transport with the least disutility, i.e. the most preferred mode, is uniquelydetermined. Let us denote the chosen mode of transport for an origin u and destination v bym(u, v).77Figure 4.2: Disutilities of the various modes of transport and mode choice as afunction of travel distance (units: km).First, we quantify the economic impacts of bike-sharing. The revenue of the bike-sharingsystem, denoted by RB, is given by,RB =∫m(u,v)=B(d(u, v)fB +KB)D(u, v)dudv +∫m(u,v)=BP(τPa vW fB +KB)D(u, v)dudv. (4.7)That is, the revenue from bike-sharing arises from the per-unit distance fee and trip-averaged subscription fee paid by the individuals using bike-sharing for the entire trip as wellas from individuals using bike-sharing as a mode of first and last-mile transport. Since it isimportant to also study the economic impacts of bike-sharing in the city on the public transitsystem, we need to compare the revenue of public transit with the revenue of public transitprior to the introduction of bike-sharing, denoted by RP .78RP =∫m(u,v)∈{P,BP}(d(u, v)fP +KP )D(u, v)dudv −∫UP (u,v)>UC(u,v)(d(u, v)fP +KP )D(u, v)dudv. (4.8)The change in revenue from public transit arises from individuals who earlier preferred acar over public transit but prefer to use the bi-modal option after the introduction of bike-sharing. In order to quantify the environmental impacts of bike-sharing, we need to analyzethe patterns of mode substitution post the introduction of bike sharing in the region. Weassume that public transit and bike-sharing are both non-polluting modes of transport, inthat, they both generate zero usage emissions. We further assume that a car generates carbonemissions eC per km and let pS($/unit of emissions) denote the social cost of carbon. Then,the environmental benefits due to bike sharing in monetary terms is given by,∆(E) =∫UC(u,v)>UP (u,v)m(u,v)∈{P,BP}eCd(u, v)D(u, v)dudv − eT r(ν). (4.9)In (4.9), r(ν) denotes the distance travelled by trucks during rebalancing operations tomaintain a service level of ν. eT denotes the carbon emissions generated by the trucks per km.In the next section, we provide a closed-form analytical expression for r(ν), thereby allowingus to perform numerical analyses to determine the economic and environmental impacts ofvarious operational decisions undertaken by the bike-share operator.4.4. Continuous Approximation for Bike RebalancingDistanceA key logistical challenge for bike-share operators arises from spatial demand imbalances,that over time, result in some stations with too few or no bikes, and other stations which arefull with no available docks to return bikes. Operators typically employ a fleet of trucks torebalance the system periodically by moving bikes from surplus stations to deficit stations.The operational costs involved can be significant and finding optimal truck routes to performthe rebalancing operations aids in reducing these operational costs considerably. Efficientvehicle routing can also be beneficial from an environmental standpoint by helping achievea lower carbon footprint. De Maio (2009) notes that rebalancing bikes from areas of highsupply and low demand to areas with high demand and low supply is currently economicallyand environmentally expensive and flags this as an area for improvement in next-generationbike sharing systems.79The associated vehicle routing problem for bike-rebalancing is computationally hard (Er-dogan et al. 2015) and has thus been a subject of extensive study. Herna´ndez-Pe´rez et al.(2003) appear to be the first to consider the associated vehicle routing problem - the one-commodity pick-up and delivery travelling salesman problem. Exact algorithms (Erdogan etal. 2015), approximation algorithms with provable guarantees (O’Mahony et al. 2015) andheuristic approaches (Schuijbroek et al. 2017) have all been proposed to solve this problem.In this section, we eschew the numerical optimization approaches followed in the literatureand instead adopt a continuous approximation method that allows us to obtain simple anduseful guidelines for the associated truck routing problem and an estimate of the operationalcost.As before, we consider a bike-sharing system with N stations distributed over a coverageradius of R with a station density of ρ = N/piR2. We assume the average spatial demandimbalance in the system to be distributed according to a Poisson distribution and denotethe average spatial demand imbalance per unit time by λ. Therefore, λ denotes the averageabsolute difference between the in-flow and out-flow at each bike-sharing station. Further,suppose that the average capacity at each station is K bikes and K empty docks. Thefollowing result provides an expression for the average rebalancing distance covered by atruck to maintain a service level of ν across the bike-sharing system.Theorem 4.2. The average distance traveled to rebalance bikes across N stations, each withcapacity K, distributed over a region with radius R and an average spatial demand imbalancerate of λ, is given byr(ν,N,R,K, λ) ∼= kTSP f(ν,K, λ)R√piN, (4.10)where f(ν, k, λ) is the rebalancing frequency required to maintain a service level of ν and isthe solution to Q (K + 1, λ/f(ν,K, λ)) = ν, where Q is the regularized gamma function3.The above expression for the rebalancing distance, r(ν,N,R,K, λ) comprises of two com-ponents. The first, f(ν,K, λ) refers to the number of rebalancing operations necessary tosustain a service level of ν. The second component, kTSPR√piN , corresponds to the averagedistance traveled in each rebalancing stage. kTSP is a scalar constant that is determined bythe shape of the geographic region served, as well as the distance metric norm (i.e., L1 or L2norms) employed4.In Figure 4.3, we provide a partial numerical confirmation of Theorem 4.2. Therein, we3Q(x, y) = Γ(x,y)Γ(x), where Γ(x, y) =∫∞ytx−1e−tdx and Γ(x) =∫∞0tx−1e−tdx.4We leave studying the effects of different geographic shapes and distance norms for an extension of ourbase model considered here.80Figure 4.3: Comparison between approximation for r(ν,N,R,K, λ) from Theorem 4.2and numerical estimates of rebalancing distance for simulated bike-sharingnetworks of different sizes N distributed over a region of unit-distance radius.present the average rebalancing distance (with f(ν,K, λ) set to 1) for various simulated5bike-sharing networks of different sizes of N and compare it with the expression derived inTheorem 4.2. Figure 4.3 confirms that the rebalancing distance scales as√N .4.5. Qualitative Implications and ExtensionsFrom the numerical computations depicted in Figure 4.2, we obtain three salient observa-tions. In the absence of the bi-modal (public transport and bike-sharing) option, bike-sharingsubstitutes exclusively away from public transport, thereby yielding no additional environ-mental benefits. This remains true for a wide range of parameter values. Thus, our modelmodel findings are consistent with empirical reports from earlier studies such as Fishmanet al. (2014) which observe high modal substitution to bike sharing from public transit (orsimply walking). However, when we allow for the bi-modal option, the presence of a bike-5All the simulations were carried out in Python 3.7. We generated 200 instances of N bike-sharing stations uniformly and randomly distributed over a region of radius 1 unit distance (for N =10, 20, 30, 40, 50, 60, 70, 80, 100, 120, 140, 160, 180, 200). We then randomly initialized surplus and deficit sta-tions (i.e stations with excess and fewer bikes, respectively, than the target level). The rebalancing distancefor each instance was computed by employing a cluster-first and route-second heuristic to solve the associatedTSP problem. A variation of the cluster-first route-second heuristic has been employed for the bike-rebalancingproblem previously and shown to outperform other approaches (Schuijbroek et al. 2017).81sharing system generates positive environmental benefits by substituting certain car usersto the bi-modal option. Further, it increases ridership, and equivalently revenues, of bothbike-sharing and public transit. Finally, we also find in our numerical examples that theradius of coverage limits the uptake of bike-sharing, that is, d˜MC > R˜. Individuals travellingbetween an origin-destination pair, (u, v), such that R˜ < d(u, v) ≤ d˜MC would have preferredto opt for the bi-modal option but are limited by the coverage of bike-sharing. Therefore,in certain situations, increasing the radius of coverage, even though it would result in lowerdensity of bike-sharing stations, it might still result in higher net environmental benefits andgreater revenues for bike-sharing and public transit. That is, the higher disutility due to anincrease in the access time of bike-sharing is potentially outweighed by the increase in bi-modal demand from individuals who were previously unable to use the option due to limitedbike-sharing coverage.We suggest that the analytical expressions for the economic and environmental impactsof bike-sharing provided in equations (4.7)-(4.9) along with the expression for rebalancingdistance developed in Theorem 4.2, can be employed to provide a theoretical confirmation ofthe preceding qualitative insights obtained via numerical analysis. Two other directions forfuture research are as follows. First, the robustness of our qualitative predictions can be testedby moving from the deterministic choice model described here to a stochastic mode-choicemodel (such as a multinomial logit model). This would allow us to empirically estimate andcalibrate model parameters to real-world data. Finally, on that note, with the availability ofbike-sharing data along with public transit and aggregate travel demand data, an empiricalestimation and calibration of our model parameters will allow for more accurate and tailoredqualitative recommendations.To summarize, in this work, we have developed a transport modelling framework thatincorporates key strategic and operational decisions faced by bike-sharing operators and cityplanners while introducing bike-sharing system to a city. It provides a pathway for the mod-elling framework developed herein to be employed by city planners to design bike-sharingsystems that are financially viable with high ridership and low operational costs which max-imize environmental benefits.82BibliographyAgrawal V. V., Atasu A., Van Wassenhove L. N. 2019. OM Forum – New oppor-tunities for operations management research in sustainability, Manufacturing & ServiceOperations Management 21(1), 1-12.Albizuri, M. J., Echarri, J. M., and J. M. Zarzuelo. 2015. A non-cooperativemechanism for the Shapley value of airport problems, Annals of Operations Research235(1), 1-11.Albizuri, M. J., Echarri, J. M., and J. M. Zarzuelo. 2017. A non-cooperativemechanism yielding the nucleolus of airport problems, Group Decision and Negotiation,27(1), 153-163.Ansari, S., Basdere, M., Li, X., Ouyang, Y., Smilowitz, K. 2018. Advancementsin continuous approximation models for logistics and transportation systems: 1996-2016,Transportation Research: Part B 107, 229-252.Anupindi, R., Bassok, Y., and E. Zemel. 2001. A General Framework for the Studyof Decentralized Distribution Systems, Manufacturing & Service Operations Management3(4), 349-368.Atasu, A., Corbett, C. J., Huang, X., Toktay, L. B. 2020. Sustainable OperationsManagement Through the Perspective of Manufacturing & Service Operations Manage-ment, Manufacturing & Service Operations Management 22(1), 146-157.Battaglini, M. 2006. Joint production in teams, Journal of Economic Theory 130(1),138-167.Belavina, E., Girotra, K., Kabra, A. 2017. Online grocery retail: revenue models andenvironmental impact, Management Science 63(6), 1781-1799.Bellos I., Ferguson M., Toktay L. B. 2017. The car sharing economy: Interactionof business model choice and product line design, Manufacturing & Service OperationsManagement 19(2), 185-201.Benjaafar, S., Y. Li, M. Daskin. 2013. Carbon footprint and the management of supplychains: Insights from simple models, IEEE Trans. Automation Sci. Engrg. 10(1),99-116.83Bhattacharya, P., Chakrabarti, B.K. 2008. The mean distance to the nth neighbour ina uniform distribution of random points: an application of probability theory, EuropeanJournal of Physics 29(3), 639-646.Bhattacharya, S., Lafontaine, F. 1995. Double-sided moral hazard and the nature ofshare contracts, RAND Journal of Economics 26(4), 761-781.Bo¨hringer, C., Mu¨ller, A. and Schneider, J. 2015. Carbon tariffs revisited, Journalof the Association of Environmental and Resource Economists 2(4), 629-672.Cachon, G. P. 2014. Retail store density and the cost of greenhouse gas emissions, Man-agement Science 60(8), 1907-1925.Cai, H., Brandt, A. R., Yeh, S., Englander, J. G., Han, J., Elgowainy, A., andM. Q. Wang. 2015. Well-to-Wheels Greenhouse Gas Emissions of Canadian Oil SandsProducts: Implications for U.S. Petroleum Fuels, Environmental Science & Technology49(13), 8219-8227.Canada 2005. Annex 4: A Framework for Evaluation of Environmental Tax Proposals,Department of Finance Canada, The Budget Plan 2005.Canada 2016. Estimating Upstream GHG emissions, Canada Gazette. Accessed April 19,2019, http://www.gazette.gc.ca/rp-pr/p1/2016/2016-03-19/html/notice-avis-eng.htmlCarbon Disclosure Project: Supply Chain Report 2011, 2019. https://www.cdp.net/Caro, F., C.J. Corbett, T. Tan, R. Zuidwijk. 2013. Double counting in supply chaincarbon footprinting, Manufacturing & Service Operations Management 15(4), 545-558.Charnes, A. and K. O. Kortanek. 1969. On asymptotic behavior of some nuclei of n-person games and the piecewise linearity of the nucleolus, Management Science ResearchRep. 170, Carnegie Mellon University, Pittsburgh.Charpentier, A. D., Bergerson, J. A., H.L. Maclean. 2009. Understanding theCanadian oil sands industry’s greenhouse gas emissions, Environmental Research Letters4(1), 014005.Chen X., Benjaafar, S., A. Elomri 2019. On the Effectiveness of Emission Penalties inDecentralized Supply Chains, European Journal of Operational Research. 274(3), 1155-1167.C¸ifc¸y, B., Borm, P., H. Hamers. 2010. Highway games on weakly cyclic graphs, EuropeanJournal of Operational Research 204, 117-124Corbett, C.J., G.A. DeCroix. 2001. Shared-savings contracts for indirect materials insupply chains: Channel profits and environmental impacts, Management Science 47(7),881-893.Corbett, C.J., G.A. DeCroix, A.Y. Ha. 2005. Optimal shared-savings contracts in84supply chains: linear contracts and double moral hazard, European Journal of OperationalResearch 163, 653-667.Dagan, N., Serrano, R., O. Volij. 1997. A non-cooperative view of consistent bankruptcyrules, Games and Economic Behavior 18, 55-72.Daganzo, C. 2005. Logistic System Analysis, Springer Berlin, Germany.Davis, M. and M. Maschler. 1965. The kernel of a cooperative game, Naval ResearchLogistics Quarterly 12, 223-259.De Maio, P. 2009. Bike-sharing: History, impacts, models of provision, and future, Journalof Public Transportation 12(4), 41-56.Dickey, J. 1983. Metropolitan Transportation Planning, New York - McGraw Hill, 2nd ed.Domingos, T., Zafrilla, J. E., L. A. Lo´pez. 2016. Consistency of technology-adjustedconsumption-based accounting, Nature Climate Change 6 (8), 729-730.Drake, D. F. 2018. Carbon tariffs: Effects in settings with technology choice and foreignproduction cost advantage, Manufacturing & Service Operations Management 20(4), 667-686.Dubey, P. 1982. The Shapley value as aircraft landing fees—revisited, Management Science28(8), 869-874.Dyer, S. and M. Huot. 2010. Mining vs. In Situ, Pembina Institute, Accessed November5, 2017, http://www.pembina.org/pub/2017Enkvist, P., Naucler, T. and J. Rosander. 2007. A Cost Curve for Greenhouse GasReduction, The McKinsey Quarterly, (1) 35-45.Environment and Climate Change Canada (ECCC). 2016. Trans Mountain Expan-sion Project Review of Related Upstream Greenhouse Gas Emissions Estimates, Novem-ber 2016.Environmental Protection Agency, United States (EPA) 2016. Sources of Green-house Gas Emissions, Accessed November 5, 2017, https://www.epa.gov/ghgemissions/sources-greenhouse-gas-emissionsErdogan, G., Battarra, M., Calvo, R.W. 2015. An exact algorithm for the staticrebalancing problem arising in bicycle sharing systems, European Journal of OperationalResearch 245(3), 667-679.Eyland, T. and Zaccour, G. 2014. Carbon tariffs and cooperative outcomes, EnergyPolicy 65, 718-728.Fishman, E., Washington, S., Haworth, N. 2014. Bike share’s impact on car use:evidence from the United States, Great Britain, and Australia, Transportation ResearchPart D: Transport and Environment 31, 13-20.85Freund D., Henderson S. G., Shmoys D. B. 2019. Bike sharing, Sharing Economy:Making Supply Meet Demand, Springer Switzerland, 435-459.Freund, D., Henderson S. G., Shmoys D. B. 2017. Minimizing multimodular functionsand allocating capacity in bike-sharing systems, Integer Programming and CombinatorialOptimization Proceedings (Lecture Notes in Computer Science), F. Eisenbrand and J.Koenemann (eds.), 10328 Springer, 186-198.Gallego, B., M. Lenzen. 2005. A consistent input-output formulation of shared consumerand producer responsibility, Economic Systems Research 17(4), 365-391.Gass, S. I. 1983. Decision-Aiding Models: Validation, Assessment and Related Issues forPolicy Analysis, Operations Research 31(4), 603-631.Girotra K., Netessine S. 2013. OM forum – Business model innovation for sustainability,Manufacturing & Service Operations Management 15(4), 537-544.Gkatzelis, V., Kollias, K., T. Roughgarden. 2016. Optimal Cost-Sharing in GeneralResource Selection Games, Operations Research, 64 (6), 1230-1238.Gopalakrishnan, S., Granot, D., Granot, F., Sosˇic´, G. and H. Cui. 2018. Incen-tives and Emission Responsibility Allocation in Supply Chains, Working Paper, Univer-sity of British Columbia.Granot, D. and G. Huberman. 1984. On the core and nucleolus of minimum costspanning tree games, Mathematical Programming 29, 323-347.Granot, D., Maschler, M., Owen, G., W. R. Zhu. 1996. The kernel/nucleolus of astandard tree game, International Journal of Game Theory 25, 219-244.Granot, D. and G. Sosˇic´. 2003. A Three-Stage Model for a Decentralized DistributionSystem of Retailers, Operations Research 51(5), 771-784.Harrison, K. 2015. International Carbon Trade and Domestic Climate Politics, GlobalEnvironmental Politics 15, 27-48.Hart, S. and A. Mas-Colell. 1989. Potential, value and consistency, Econometrica 57,589-614.Hartman, B. C., Dror, M. and M. Shaked. 2000. Cores of Inventory CentralizationGames, Games and Economic Behavior 31(1), 26-49.Herman Miller: Environmental Record, 2016. http://www.smartfurniture.com/hermanmiller/environmental.htmlHernandez-Perez, H. and Salazar-Gonzalez, J.J. 2003. The one-commodity pickup-and-delivery travelling salesman problem, Combinatorial Optimization – Eureka, YouShrink!, Springer Berlin, 89-104.HP. 2014. Living Progress Report, http://www8.hp.com/h20195/v2/GetDocument.aspx?docname=86c04152740.Huang H., Narayanan S., Swaminathan J. (2019). Carrot or Stick? Supplier Diversityand its Impact on Carbon Emission Reduction Strategies. Working Paper, University ofNorth Carolina at Chapel Hill.International Council on Clean Transportation (ICCT). 2014. The Reduction ofUpstream Greenhouse Gas Emissions from Venting and Flaring, Report to the EuropeanCommission Directorate-General for Climate Action.IPCC. 2014. Climate Change 2014: Mitigation of Climate Change. Contribution of WorkingGroup III to the Fifth Assessment Report of the Intergovernmental Panel on ClimateChange (Edenhofer, O. et al. eds.), Cambridge University Press, Cambridge.Jensen, M. K. 2018. Distributional comparative statics, The Review of Economic Studies85(1), 581-610.Jira, C., M. Toffel. 2013. Engaging Supply Chains in Climate Change, Manufacturing& Service Operations Management 15(4), 559-577.Ju, Y. and D. Wettstein. 2009. Implementing Cooperative Solution Concepts: a Gener-alized Bidding Approach, Economic Theory 39, 307-330.Kabra, A., Belavina, E., Girotra, K. 2016. Bike-share systems, Environmentally Re-sponsible Supply Chains, Springer Cham., 127-142.Kabra A., Belavina E., Girotra K. 2019. Bike share systems: accessibility and avail-ability, Management Science, forthcoming, https://doi.org/10.1287/mnsc.2019.3407.Kander, A., Jiborn, M., Moran, D.D. and T. O. Wiedmann. 2015. Nationalgreenhouse-gas accounting for effective climate policy on international trade., Nature Cli-mate Change 5, 431-435.Kemahliog˘lu-Ziya, E., and Bartholdi, J. J. III. 2011. Centralizing inventory in supplychains by using Shapley value to allocate the profits. Manufacturing & Service OperationsManagement 13(2), 146-162.Kortum, S. and Weisbach, D. 2017. The design of border adjustments for carbon prices,National Tax Journal 70(2), 421-446.Lange, A. 2006. The impact of equity-preferences on the stability of heterogeneous inter-national agreements, Environmental and Resource Economics 34, 247-267.Langevin, A., Mbaraga, P., Campbell, J. 1996. Continuous approximation models infreight distribution: an overview, Transportation Research: Part B 30, 163-188.Larch, M. and Wanner, J. 2017. Carbon tariffs: An analysis of the trade, welfare, andemission effects, Journal of International Economics, 109, 195-213.Leng, M., and M. Parlar. 2009. Allocation of cost savings in a three-level supply chain87with demand information sharing: A cooperative-game approach, Operations Research57(1), 200-213.Leng, M., and M. Parlar. 2010. Analytic solution for the nucleolus of a three-playercooperative game, Naval Research Logistics 57(7), 667-672.Lenzen, M., Murray, J., Sack, F., T. Wiedmann. 2007. Shared producer and consumerresponsibility - theory and practice, Ecological Economics 61(1), 27-42.Levi Strauss & Co. 2015. The Lifecycle of a Pair of Levis 501 R©jeans. http://levistrauss.com/wp-content/uploads/2015/03/Full-LCA-Results-Deck-FINAL.pdfLevi Strauss & Co. 2017. Annual Report. https://www.levistrauss.com/wp-content/uploads/2018/03/Levi-Strauss-Annual-Report-2017.pdfLittlechild, S.C. 1974. A simple expression for the nucleolus in a special case, Interna-tional Journal of Game Theory 3 (1), 21-29.Littlechild, S.C., G. Owen. 1973. A simple expression for the Shapley value in a specialcase, Management Science 20 (3), 370-372.Luchs, M.G., Kumar, M. 2017. “Yes, but this other one looks better/works better”: howdo consumers respond to trade-offs between sustainability and other valued attributes?Journal of Business Ethics 140(3), 567-584.Matthews, H.S., C.T. Hendrickson, C.L. Weber. 2008. The importance of carbonfootprint estimation boundaries, Environmental Science & Technology 42, 5839-5842.Maschler, M., Peleg, B., Shapley, L. S. 1971. The kernel and bargaining set of convexgames, International Journal of Game Theory 1(1), 73-93.Maschler, M., Peleg, B., Shapley, L. S. 1979. Geometric Properties of the Kernel,Nucleolus and related solution concepts, Mathematics of Operations Research 4(4), 303-338.McElfresh, D.C. and Dickerson, J.P. 2018. Balancing lexicographic fairness and autilitarian objective with application to kidney exchange, Thirty-Second AAAI Conferenceon Artificial Intelligence.Megiddo, N. 1978. Computational complexity of the game theory approach to cost alloca-tion for a tree, Mathematics of Operations Research 3(3), 189-196.Milgrom, P., Roberts, J. 1990. Rationalizability, learning, and equilibrium in games withstrategic complementarities. Econometrica 58(6), 1255-1277.Monbiot, G. 2015. Keep fossil fuels in the ground to stop climate change, The Guardian.Accessed August 8, 2015, http://www.theguardian.com/environment/2015/mar/10/keep-fossil-fuels-in-the-ground-to-stop-climate-changeNagarajan, M. and Sosˇic´, G. 2008. Game-theoretic analysis of cooperation among supply88chain agents: Review and Extensions, European Journal of Operational Research 187,719-745.Newell, G. 1973. Scheduling, location, transportation and continuum mechanics: somesimple approximations to optimization problems, SIAM Journal on Applied Mathematics25, 346-360.Newman, P. 2009. Transport and Energy, Transportation Engineering Plannning Vol. II,ed. Tschango John Kim, EOLSS-UNESCO.Newman, P. and Kenworthy, J. 1999. Sustainability and Cities: Overcoming AutomobileDependence, Washington, DC: Island Press.Nielsen. 2018. Unpacking the Sustainability Landscape Report.Obama, B. 2009. Executive Order 13514 – Focused on Federal Leadership in Environmental,Energy, and Economic Performance, The White House, Washington, DC, https://www.whitehouse.gov/the-press-office/president-obama-signs-executive-order-focused-federal-leadership-environmental-ener.Oh, I., Yeo, Y., Lee, J. D. 2015. Efficiency versus Equality: Comparing design optionsfor indirect emissions accounting in the Korean Emissions Trading Scheme, Sustainability7(11), 14982-15002.Oil and Gas Journal (O&GJ) 2004. Worldwide look at reserves and production, 102(22)-3Oil Sands Magazine (OSM) 2017. Bitumen Upgrading Explained, Accessed November 5,2017, http://www.oilsandsmagazine.com/technical/bitumen-upgradingOil Sands Magazine (OSM) 2019. Air Emissions (Environment), Accessed December 18,2018, https://www.oilsandsmagazine.com/technical/environment/air-emissionsO’ Mahony, E. 2015. Smarter Tools For (Citi) Bike Sharing, PhD Thesis, Cornell Univer-sity.Orsdemir A., Deshpande V., Parlaktuurk A. K. 2019. Is servicization a win-winstrategy? Profitability and environmental implications of servicization, Manufacturing &Service Operations Management 21(3), 674-691.Oshita, Y. 2011. Identifying critical supply chain paths that drive changes in CO2 emissions,Energy Economics 34(4), 1041-1050.Paris Agreement. 2015. 2015 United Nations Climate Change Conference, Paris, France,https://treaties.un.org/pages/ViewDetails.aspx?src=TREATY&mtdsg no=XXVII-7-d&chapter=27&lang=en.Parry, I. W. H., M. Toman. 2002. Early emissions reduction programs: an applicationto CO2 policy, The Energy Journal 23(1), 73-95.89Plambeck, E.L. 2012. Reducing greenhouse gas emissions through operations and supplychain management, Energy Economics, 34, 64-74.Plambeck E. L., Taylor T. A. 2013. On the value of input efficiency, capacity efficiency,and the flexibility to rebalance them, Manufacturing & Service Operations Management15(4), 630-639.Porter, E. 2013. Rethinking How to Split the Costs of Carbon, New York Times. Ac-cessed May 12, 2014, http://www.nytimes.com/2013/12/25/business/economy/what-if-consumers-not-producers-paid-for-emissions.htmlPortland Bureau of Transportation (PBOT). 2017. BIKETOWN by the Numbers,https://content.govdelivery.com/accounts/ORPORTLAND/bulletins/1804f13, Accessed May9, 2020.Qi W., Li L., Liu S., Shen Z. J. M. 2018. Shared mobility for last-mile delivery: Design,operational prescriptions, and environmental impact, Manufacturing & Service Opera-tions Management 20(4), 737-751.Raviv, T., Kolka O. 2013. Optimal inventory management of a bike-sharing station, IIETransactions 45(10), 1077-1093.Raviv, T., Tzur, M. Forma, I.A. 2013. Static repositioning in a bike-sharing system:models and solution approaches, EURO Journal on Transportation and Logistics 2(3),187-229.Rodrigues, J., T. Domingos. 2008. Consumer and producer environmental responsibility:comparing two approaches, Ecological Economics 66, 533-546.Rodrigues, J., Domingos, T., Giljum, S., F. Schneider. 2006. Designing an indicatorof environmental responsibility, Ecological Economics 59, 256-266.Rosenthal, E. C. 2017. A Cooperative Game Approach to Cost Allocation in a Rapid-Transit Network, Transportation Research Part B 97, 64-77.Schaufele, B. 2016. An Economic Analysis of New Upstream Emissions Requirements forPipeline Approvals, Policy Brief, Ivey Energy Policy and Management Centre, WesternUniversity.Schmeidler, D. 1969. The Nucleolus of a Characteristic Function Game, SIAM Journal onApplied Mathematics 17, 1163-1170.Schmitz, A. (Ed.). 2011. The Economics of Alternative Energy Sources and Globalization,Bentham Science Publishers.Schneider, L., Kollmuss, A., Lazarus, M. 2014. Addressing the risk of double countingemission reductions under the UNFCCC, SEI Working Paper No. 2014-02.Schuijbroek, J., Hampshire, R.C., Van Hoeve, W.J. 2017. Inventory rebalancing and90vehicle routing in bike sharing systems, European Journal of Operational Research 257(3),992-1004.Serrano, R. 1995. Strategic bargaining, surplus sharing problems and the nucleolus, Jour-nal of Mathematical Economics 24(4), 319-329.Shapley, L. S. 1953. A Value for N-Person Games, Contribution to the Theory of GamesVol.2, Princeton University Press, Princeton, N.J. 307-317.Shapley, L. S. 1971. Cores of convex games, International Journal of Game Theory 1,11-26.Shu, J., Chou, M.C., Liu, Q., Teo, C.P., Wang, I.L. 2013. Models for effective de-ployment and redistribution of bicycles within public bicycle-sharing systems, OperationsResearch 61(6), 1346-1359.Singh, S., and A. Scheller-Wolf 2018. That’s not fair: Tariff structures for electricitymarkets with rooftop solar, Working Paper, Carnegie Mellon University.Sobolev, A. 1975. The characterization of optimality principles in cooperative games byfunctional equations, Mathematical Methods in the Social Sciences 6, 95-151, in Russian.Solymosi, T., Raghavan, T. E. S. 1994. An algorithm for finding the nucleolus of assign-ment games, International Journal of Game Theory 23, 119 - 143.G. Sosˇic´. 2006. Transshipment of Inventories Among Retailers: Myopic vs. FarsightedStability, Management Science 52(10), 1493-1508.Steer Davies Gleave. 2016. TransLink Transit Fare Review, Prepared for TransLink,Canada.Steimetz, S.S. 2008. Defensive driving and the external costs of accidents and travel delays,Transportation Research Part B: Methodological 42(9), 703-724.Stone, R.E. 1991. Some average distance results, Transportation Science 25(1), 83-90.Stratos. 2017. Cross-Jurisdictional Review of Energy Regulators, Submitted to NaturalResources Canada.Subramanian, R., Gupta, S., Talbot, B. 2007. Compliance strategies under permits foremissions, Production and Operations Management 16 (6), 763-779.Sudho¨lter, P., Zarzuelo, J. M. 2017. Characterizations of highway toll pricing methods,European Journal of Operational Research 260, 161-170.Sunar, N. 2016. Emissions Allocation Problems in Climate Change Policies, in Environ-mentally Responsible Supply Chains, A. Atasu (ed.), Springer Series in Supply ChainManagement, 261-282.Sunar, N., and Plambeck, E. 2016. Allocating Emissions Among Co-Products: Implica-tions for Procurement and Climate Policy, Manufacturing & Service Operations Manage-91ment 18(3), 414-428.Topkis, D.M. 1978. Minimizing a submodular function on a lattice. Operations Research26(2), 305-321.Topkis, D.M. 1998. Supermodularity and Complementarity. Princeton University Press.United Nations Environment Programme (UNEP). 2019. Emissions Gap Report 2019– Global progress report on climate action, https://www.unenvironment.org/interactive/emissions-gap-report/2019/, Accessed May 9, 2020.van Hoek, R., B. Fugate, M. Davletshin, M.A. Waller. 2019. Integrating Blockchaininto Supply Chain Management: A Toolkit for Practical Implementation, Kogan Page,London.Vaughan, R. 1984. Approximate formulas for average distances associated with zones,Transportation Science 18(3), 231-244.Wiedmann, T., M. Lenzen. 2006. Sharing Responsibility along Supply Chains – A NewLife-Cycle Approach and Software Tool for Triple-Bottom-Line Accounting, The Corpo-rate Responsibility Research Conference 2006, Trinity College Dublin, Ireland.Winter, E. 2002. The Shapley Value, in The Handbook of Game Theory, R. J. Aumannand S. Hart, North-Holland, 2002.Winters, M., Hosford, K. and Javaheri, S. 2019. Who are the ’super-users’ of publicbike share? An analysis of public bike share members in Vancouver, BC, PreventiveMedicine Reports 15, 100946.Young, H. P. 1985. Monotonic solutions of cooperative games, International Journal ofGame Theory 14(2), 65-72.Zeller H., Zah R., Gioacchini M., Faist M. 2017. Second Edition of the EnvironmentalImpact Valuation as base for a Sustainable Fashion Strategy. HUGO BOSS.92Appendix AChapter 2 – Proofs and Technical ResultsProof of Proposition 2.1. Note that for i ∈ N and S ⊆ N ,cG(S ∪ {i})− cG(S) =∑(fj : for all j ∈M such that i ∈ N j , S ∩N j = ∅).Clearly, for Q ⊆ S and j ∈ M , if S ∩ N j = ∅ then Q ∩ N j = ∅. Therefore, for i ∈ N andQ ⊆ S ⊆ N , cG(S ∪ {i}) − cG(S) ≤ cG(Q ∪ {i}) − cG(Q), which implies the concavity of(N, cG). Proof of Theorem 2.1. For each j ∈M and S ⊆ N , let(N, cjG)denote the game wherecjG(S) ={0, if S ∩N j = ∅,aj , otherwise.One can easily verify that for each S ⊆ N , cG(S) =∑j∈McjG(S). By its symmetry property,the Shapley value for the game(N, cjG)isΦji ={fj|Nj | , if i ∈ N j ,0, otherwise,and by its additivity property, Φi(cG) =∑j∈MΦji . Thus, the Shapley value of the GREENgame (N, cG) allocates the cost of the pollution fj equally among all players who can jointlyinfluence the emissions at j. That is, for each process j, the Shapley value allocates fj equallyamong all the firms in N j . Proof of Theorem 2.2. The set of maximizers of (2.4), G(t), is a correspondence (a multi-valued function) from T to 2X . A correspondence G : T 7→ 2X is said to be a concave93correspondence if for all t1, t2 in T , x1 ∈ G(t1), x2 ∈ G(t2), and λ ∈ [0, 1], there existsx ∈ G(λt1 +(1−λ)t2) with x ≥ λx1 +(1−λ)x2. From Theorem 5 of Jensen (2018), it followsthat G(t) is a concave correspondence in t. Finally, Lemma 2 of Jensen (2018) implies thatthe greatest selection of G(t), g(t) = sup G(t), is also concave in t. Proof of Theorem 2.3. Let BRi(x, t) denote the greatest best response for player i towardsx−i for parameter value t ∈ T . Then, BRi(x, t) = maxxi∈Xiui(xi, x−i, t) where Xi ⊂ R. DenoteT̂i = X−i × T and since T̂ is the product of two convex sets, it is also convex. Further,ui(xi, x−i, t) : Xi × T̂ 7→ R satisfies the quasi-concave differences property, that is, for allδ > 0 in the neighbourhood of 0, ui(xi, x−i, t)− ui(xi − δ, x−i, t) = ui(xi, tˆ)− ui(xi − δ, tˆ) isquasi-concave in (xi, x−i, t) = (xi, tˆ). Therefore, from Theorem 2.2, it follows that BRi(x, t)is concave in tˆ = (x−i, t) ∈ T̂ . Therefore, for t1, t2 ∈ T , and α ∈ [0, 1],BRi(αx˜(t1) + (1− α)x˜(t2), αt1 + (1− α)t2) ≥ αBRi(x˜(t1), t1) + (1− α)BRi(x˜(t2), t2)= αx˜(t1) + (1− α)x˜(t2),where the equality holds since x˜(t1) and x˜(t2), by virtue of being equilibrium action vectors,are fixed points of the best-response function BRi at t1 and t2, respectively. Further, sinceΓ(t) is a supermodular game, Lemma 4.2.2 in Topkis (1998) implies that the best responseBRi(x, t) is increasing in the actions of the other players, x−i ∈ Xi. Therefore, for x >αx˜(t1) + (1− α)x˜(t2),BRi(x, αt1 + (1− α)t2) ≥ BRi(αx˜(t1) + (1− α)x˜(t2), αt1 + (1− α)t2)≥ αx˜(t1) + (1− α)x˜(t2).Denote 1 = supX, where X ⊆ Rn is a convex and compact set of all possible actionvectors, with n = |N | being the number of players in Γ. We obtain that, BRi(·, αt1 +(1 − α)t2) maps [αx˜(t1) + (1 − α)x˜(t2),1] into itself. From Brouwer’s fixed point theorem,it then follows that BRi(·, αt1 + (1 − α)t2) has a fixed point in the domain restricted to[αx˜(t1) + (1−α)x˜(t2),1]. This fixed point, which will be an equilibrium of Γ(αt1 + (1−α)t2)is greater than αx˜(t1) + (1− α)x˜(t2) completing the proof of concavity of x˜(t) in t. We now clarify the following technical lemma involving the composition of multi-dimensionalconcave functions, which we will subsequently employ in the proof of Theorem 2.4.Lemma A.1. Consider a sequence of functions, {hi(x)}ki=1, where x ∈ Rn, such that forall 1 ≤ i ≤ k, hi : Rn 7→ R is concave in x. Let g : Rk 7→ R be a component-wise convexdecreasing function. Then, g˜(x) = g({hi(x)}ki=1) is convex in x.94Proof of Lemma A.1. Consider x1, x2 ∈ Rn and α ∈ [0, 1]. For all 1 ≤ i ≤ k, the concavityof hi implies,hi(αx1 + (1− α)x2) ≥ αhi(x1) + (1− α)hi(x2).Since g is decreasing, we haveg˜(αx1 + (1− α)x2) = g({hi(αx1 + (1− α)x2)}ki=1)≤ g({αhi(x1) + (1− α)hi(x2)}ki=1).From the component-wise convexity of g, we obtain,g({αhi(x1) + (1− α)hi(x2)}ki=1) ≤ αg({hi(x1)}ki=1) + (1− α)g({hi(x2)}ki=1).This implies that,g˜(αx1 + (1− α)x2) ≤ αg˜(x1) + (1− α)g˜(x2).Therefore, g˜(x) = g({hi(x)}ki=1) is convex in x. Lemma A.2. The equilibrium emission abatement effort vector, eφj , for the decentralizedfirst-stage game G(φ), is concave in φ.Proof of Lemma A.2. From (2.5), the payoff function ui for player i in G(φ) is given by,ui = −∑j∈Piaij(eij)−∑j∈PipSλijfj(ej) =∑j∈Pi(−aij(eij)− pSλijfj(ej)) = ∑j∈Piuji . This allowsus to decompose the game G(φ) into a set of independent non-cooperative games, one foreach process, j ∈ M , Gj(φ). Gj(φ) is supermodular since fj(ej) is submodular. Further,the convexity of ∂fj/∂eij and ∂aij/∂eij implies that uji is concave in (ej , λij). Then, fromLemma 1 of Jensen (2018), it follows that uji exhibits quasi-concave differences. Therefore,the game Gj(φ) is supermodular with the payoff function exhibiting quasi-concave differences,and a single-dimensional action set for each player. Therefore, Theorem 2.3 implies that the(greatest) equilibrium emission abatement vector eφj , for the decentralized first-stage gameG(φ), is concave in φ. Proof of Theorem 2.4. Consider any linear emission allocation rule φ, such that for agiven firm i and process j, φ allocates the emissions λijfj to firm i. Suppose that for thevector of cost functions a ∈ A, φ performs strictly better than the Shapley allocation rule,Φ, with respect to the equilibrium supply chain emissions. That is, fφ(a) < fΦ(a). We willshow that there exists some permutation, a′ ∈ A, of the functions in the cost function vectora, at which fΦ(a) ≤ fφ(a′). Note that this will complete the proof because it will contradict95the existence of an allocation rule with a corresponding worst-case loss of efficiency beingstrictly smaller than the worst-case loss of efficiency corresponding to the Shapley value.For each j ∈ M , consider an arbitrary permutation, pi, of the vector of cost functionsaj = {aij : i ∈ N j}, resulting with the vector of cost functions a′j . That is, for any firmi ∈ N j , a′ij = api(i)j for some pi(i) ∈ N j . The symmetry in efforts of the emission, fj , ofprocess j, implies that the effect of a permutation of the abatement cost functions on theequilibrium level of emissions is equivalent to the corresponding permutation of the sharevector, from λ to λ′, such that player pi(i), who originally was allocated the share λpi(i)j , isnow allocated λ′pi(i)j = λij .Note that for the Shapley allocation, the symmetry of the share vector implies that forany permutation of the cost functions, the equilibrium emission level remains the same,fΦj (aj) = fΦj (a′j). For any other linear emission allocation φ, different from Φ, and for thepermuted vector of cost functions, a′j , let fj(λ′) be the equilibrium emission level with λ′being the equivalent corresponding permutation of the share vector as described above.From Lemma A.2, we have that equilibrium vector of abatement efforts, eφj , is concavein φ. Further, from Lemma A.1, it follows that fj(eφj (λ′)) = fj(λ′) is convex in λ′. Consider1|Nj |!∑λ′∈pi(λ)fj(λ′), where pi(λ) denotes all possible permutations of the share vector associatedwith fj . The convexity of fj in λ′ and footprint balancedness,∑i∈Njλ′ij = 1, implies that1|Nj |!∑λ′∈pi(λ)fj(λ′) ≥ fj(1|Nj | ,1|Nj | , ...,1|Nj |)= fΦj . Thus, there exists some permutation λ′ ofthe share vector λ such that the equilibrium emission level fj(λ′) ≥ fΦj .Let the permutation λ′ of the share vectors correspond to the permutation, a′j , of theabatement cost functions as described before. Then, equivalently, the equilibrium emissionlevel with the vector of abatement costs given by a′j at the allocation φ is given by fφj (a′j) =fj(λ′) ≥ fΦj . Repeating the same argument over all the processes proves that, in equilibrium,the allocation of 1|Nj | of the pollution fj to each firm in Nj , which is precisely the Shapleyallocation, minimizes the worst-case loss of efficiency. We now present an alternate proof for a special case of Theorem 2.4. This alternate proofinvolves the repeated application of the implicit function theorem and therefore necessitatesmore restrictive assumptions on the footprint and abatement cost functions. This illustratesthe usefulness of the generalized comparative statics tools developed in Section 2.4.1.For each process j, the emission fj , is assumed to be a symmetric decreasing convexfunction of the emission reduction efforts and, in addition, to be additive separable in theefforts by all firms, N j , which are held responsible for the carbon footprint of process j. Theadditive separability assumption of carbon reduction efforts is made to perform the implicitfunction theorem analysis, and it is valid in several settings. For example, the design of a more96efficient component by one supplier may not affect the emissions due to another componentin the same product sourced from a different supplier. Further, several commonly assumedpollution abatement models in the literature satisfy the additive separable assumption.The abatement cost functions aij(eij) : [0, 1] → [0, A] are assumed to be convex andstrictly increasing. For a process j, let aj denote the vector of cost functions aij over all thefirms i ∈ N j and let a denote the collective vector of cost functions over all the processes.Similarly, let ej denote the vector of carbon reduction efforts by the firms in Nj and let ebe the collective effort vector for all firms over all the processes. We also assume that fj andcij have non-negative third derivatives for all firms i and processes j.Alternate Proof of Theorem 2.4. Consider any linear emission allocation rule φ, suchthat for a given firm i and process j, φ allocates the emissions λijfj to firm i. As before,suppose that for the vector of cost functions aj , φ performs strictly better than the Shapleyallocation rule, Φ, with respect to the emissions at process j in equilibrium. We will showthat there exists some permutation, a′j , of the functions in the cost function vector aj , atwhich fΦj (aj) ≤ fφj (a′j). This will complete the proof because it will contradict the existenceof an allocation rule with a corresponding worst-case loss of efficiency.The first-order condition for some player i who can influence the pollution at process j isgiven by∂aij(eij)∂eij+ pSλij∂fij∂eij= 0, where fij is the separable part of fj due to the effortsof i. Applying the implicit function theorem, we obtain that(pSλij∂2fij∂e2ij+∂2aij∂e2ij)∂(eφij)∂λij+pS∂fij∂eij= 0. Note that∂fij∂eij< 0 since fij is decreasing in eij . Also,∂2fij∂e2ij≥ 0 and ∂2aij∂e2ij≥ 0since fij and aij are convex in eij . Thus,∂(eφij)∂λij> 0 and therefore, we have that theequilibrium effort of i towards its pollution at process j, eφij(λij), is monotonically increasingin λij (its allocated responsibility towards process j). Implicitly differentiating the first ordercondition a second time, we have,(pSλij∂2fij∂e2ij+∂2aij∂e2ij)∂2(eφij)∂λ2ij+ 2pS∂2fij∂e2ij∂eφij∂λij+(pSλij∂3fij∂e3ij+∂3aij∂e3ij)( ∂eφij∂λij)2= 0.Further, noting the non-negativity of the third derivatives of fij and aij with respect to eij ,and the convexity of fij and aij and that eφij is monotonically increasing in λij , we concludethat,97∂2(eφij)∂λ2ij= −[2pS∂2fij∂e2ij∂eφij∂λij+(pSλij∂3fij∂e3ij+∂3aij∂e3ij)( ∂eφij∂λij)2](pSλij∂2fij∂e2ij+∂2aij∂e2ij) < 0.Thus, we have that eφij(λij) is concave in λij . The rest of the proof proceeds as before withappropriate notational modifications. Proof of Theorem 2.5. Consider process j ∈ M . From Lemma A.1 and Lemma A.2, asalso observed previously, the equilibrium emissions at j, fj(eφj ) = fj(φ), is convex in theallocation vector, φ = {λij : i ∈ N j}. Therefore, for the Shapley allocation vector, φ = Φ,fΦj = fj([1|N j |])≤ 1|N j |fj({1}) +(1− 1|N j |)fj({0}),where 0 and 1 denote the allocation vectors that assign to each firm in N j zero and fullresponsibility for fj respectively. Clearly, fj({1}) ≤ f∗j and fj({0}) = f0j . Thus, fΦj ≤f∗j|Nj | +(1− 1|Nj |)f0j . Rearranging,fΦj − f∗j ≤(1|N j | − 1)f∗j +(1− 1|N j |)f0j =(1− 1|N j |)(f0j − f∗j ).Summing over all j ∈M ,fΦ − f∗ ≤(1− 1max |N j |)(f0 − f∗).Thus, we have,δ(Φ,a)f0 − f∗ =fΦ − f∗f0 − f∗ ≤(1− 1max |N j |).This completes the proof. Proof of Theorem 2.6. Part i. The Shapley allocation rule is easily seen to satisfy the threeproperties. The proof of uniqueness is via induction. Consider the total pollution footprintf = [f1, f2, ..., fm] associated with the m processes, and let f0, f1, ..., fm be defined such thatf0 = [0, 0, ..., 0], f1 = [f1, 0, ..., 0] and so forth until fm = [f1, f2, ..., fm] = f . The proofis by induction. Clearly, any pollution allocation rule φ shall naturally allocate [0, 0, ..., 0]to the firms in f0 when all the processes have zero pollution. So, for f0, φ(f0) = Φ(f0),where Φ is the Shapley allocation rule. Let us assume that φ(f j−1) = Φ(f j−1), and we willprove that φ(f j) = Φ(f j). For process j, let |N j | = nj . Define f˜ j = (0, ..., 0, fj , 0, ..., 0).For the footprint set f˜ j , by firm nullity any firm not in N j must be allocated zero. By firm98equivalence and efficiency, each firm in N j is allocatedfjnjwhen the pollution footprint setis f˜ j . Now, the pollution of process j alone increases by fj in the footprint sets f0 andf j−1 to yield f˜ j and f j , while the pollution of the other processes remains the same. Forany firm i ∈ N\N j , φi(f˜ j) − φi(f0) = 0 and for i ∈ N j , φi(f˜ j) − φi(f0) = fjnj . Processhistory independence implies, φi(fj) = φi(fj−1) for i ∈ N\N j and φi(f j) = φi(f j−1) + fjnjfor i ∈ N j . Thus, if φ(f j−1) = Φ(f j−1), φ(f j) also has to be Φ(f j), the Shapley allocation,and by induction, we conclude that φ = Φ.We complete the proof by showing the independence of the three properties.1. Consider the pollution allocation rule φ defined previously, that allocates to each firmthe average pollution of all the processes, φi(f) =m∑j=1fjn . φ satisfies firm equivalence andprocess history independence but not firm nullity.2. Consider a pollution allocation rule φ that allocates zero to each null firm, and sharesequally the pollution among all the other firms. Such a rule naturally satisfies firm nullityand firm equivalence but in general it does not satisfy process history independence.3. Consider again the pollution allocation rule that allocates the entire responsibility foreach process to just one of the possibly many firms associated with it. It satisfies firm nullityand process history independence, but not firm equivalence.Part ii. Again, it is easy to see that the Shapley allocation rule satisfies the threeproperties. Now, recall that firm i can influence the pollution at the set of processes, Pi,and let |Pi| = mi. Consider a fully disaggregated supply chain derived as a result of eachfirm i in N disaggregating into mi firms, each responsible for a distinct process in Pi. Inthe fully disaggregated supply chain, each firm can now influence the pollution of at mostone process. Following an argument similar to the one used in the proof for part (i), wehave that firm-equivalence and no free riding imply that each firm in N j is responsible forfjnj. Invariance to disaggregation asserts that in the aggregated supply chain, each firm isresponsible for the cumulative responsibilities of its disaggregated firms. This implies thatagain, the responsibility of each process is shared equally among the firms responsible for it,which is the Shapley allocation. We complete the proof by showing the independence of thethree properties.1. Consider a pollution allocation rule φ which allocates the pollution responsibilityproportional to the individual responsibilities, φi(f) =f(Pi)n∑k=1f(Pk)m∑j=1fj . This is similar to theresponsibility allocation suggested by Lenzen et al. (2007) in order to obtain a disaggregationinvariant allocation rule. While φ is disaggregation invariant and firm equivalent, it does notprevent free riding.2. Let φ be a pollution allocation rule that allocates the pollution of each process equally99among some firms responsible for it and all other firms equivalent to it. φ is firm equivalentby definition, satisfies the no free riding property, but is not disaggregation invariant.3. In the disaggregated supply chain, consider again the pollution allocation rule thatallocates the entire responsibility for each process j to just one of the possibly many firmsassociated with it. In any aggregated supply chain, continue to allocate the responsibility offj to the possibly aggregated firm corresponding to the firm i that bears responsibility for jin the disaggregated supply chain. Such a pollution allocation rule is disaggregation invariantand prevents free riding. However, it is not firm equivalent. 100Appendix BChapter 3 – Proofs and Technical ResultsIn this appendix, we develop technical results and subsequently employ them to provideproofs for results provided in the main text of the paper.A. Preliminaries and Algorithmic DevelopmentConsider the Upstream Responsibility game (N, c), with an associated directed tree T =(V (T ), E(T )), as described in §3.2. Clearly, (N, c) is monotone.Proposition B.1. The Upstream Responsibility game (N, c) is concave.Proof of Proposition B.1. Note that for i ∈ N and S ⊆ N ,c(S ∪ {i})− c(S) =∑(ek : ek ∈ Ui\(∪j∈S Uj)) .For i ∈ N and Q ⊆ S ⊆ N , clearly if ek ∈ Ui\(∪j∈S Uj), then, ek ∈ Ui\(∪j∈Q Uj). Therefore,c(S ∪ {i})− c(S) ≤ c(Q ∪ {i})− c(Q), which implies the concavity of (N, c). The concavity of the Upstream Responsibility game implies that it has a non-emptycore (Shapley, 1971), the nucleolus allocation lies in the core (Schmeidler, 1969) and thenucleolus and pre-kernel coincide (Maschler et al., 1971). The monotonicity of the UpstreamResponsibility game implies that all core solutions are non-negative.Definition B.1. A minimum excess coalition, S, S 6= N , with respect to an imputation x,which contains player i satisfies c(S)− x(S) ≤ c(T )− x(T ), for all T containing i.Lemma B.1. For a player i and a non-negative imputation x in the Upstream Responsibilitygame (N, c), there exists a minimum excess coalition containing i that includes all players inTi.Proof of Lemma B.1. Let S be a coalition of minimum excess containing i and includingthe maximal number of players from Ti. Suppose there exists a j ∈ Ti such that j /∈ S.101Then, by definition of the characteristic function c, c(S ∪ {j}) = c(S). However, since x isnon-negative, x(S ∪ {j}) = x(S) + xj ≥ x(S). Thus, c(S ∪ {j})− x(S ∪ {j}) ≤ c(S)− x(S),contradicting the maximality of S. Thus, by Lemma B.1, we can assume that a minimum excess coalition S containing playeri also contains all players upstream to i.Lemma B.2. For players i and j in the Upstream Responsibility game (N, c), such that jis downstream to i, and a non-negative imputation x, sji(x) = min{c(R) − x(R), j ∈ R, i /∈R} = xi, and is achieved at N\{i}.Proof of Lemma B.2. For such players i and j and S ⊂ N , i /∈ S and j ∈ S, c(S) =c(S∪{i}) ≥ x(S∪{i}) = x(S)+xi, implying c(S)−x(S) ≥ xi. Since c(N\{i})−x(N\{i}) =c(N)− x(N) + xi = xi, the proof follows. Lemma B.3. Consider a pre-imputation z of the Upstream Responsibility game (N, c), thatsatisfies the following set of equations for each pair of adjacent players (i, j) in T , where j isthe successor of i, zi = a(Tij)− z(Tij), if zj ≥ a(Tij)− z(Tij),zi = zj if zj ≤ a(Tij)− z(Tij),z(N) = c(N).(B.1)Then,(I) For each pair of adjacent players i and j in T , zj ≥ zi.(II) The pre-imputation z is non-negative.Proof of Lemma B.3. (I) follows trivially from the equations defining z. Consider (II); ifz1 < 0, then it follows from (I) that z(N) < 0, and since c(N) ≥ 0, we obtained a contradictionto the assumption that z is a pre-imputation. Now, suppose that there exists some pair ofadjacent players i and j such that zi < 0 and zj ≥ 0. Then, by (I), zi = a(Tij) − z(Tij).Now, from (I), zi ≥ zk for all k ∈ Tij , and since zi < 0, z(Tij) < 0 as well. Therefore,zi = a(Tij)− z(Tij) > 0, contradicting the assumption that zi < 0, and we conclude that thepre-imputation z allocates non-negative cost shares to all players. 102Proof of Theorem 3.1First, we assume that z is the nucleolus of (N, c) and we will show that it satisfies (3.7). Sincethe nucleolus coincides with the pre-kernel in concave games, sij(z) = sji(z) for adjacentplayers i and j, and since z is in the core, z ≥ 0. Since j is a successor of i, it followsfrom Lemma B.2 that sji(z) = zi. Now, suppose sij(z) = min{c(S)− x(S) : i ∈ S, j /∈ S} isattained at S∗, that is, sij(z) = c(S∗)−x(S∗). If S∗ contains a player on the path from j to theroot, then S∗ = N\{j}. If S∗ does not contain any player on the path from j to the root, thenby Lemma B.1, S∗ consists of all the nodes in Tij . Thus, zi = sij(z) = min{a(Tij)−z(Tij), zj},and we conclude that if z is the nucleolus, then it satisfies the set of equations in (3.7).Now, suppose z is an allocation satisfying (3.7). For any two nodes k and l in the tree T ,consider the unique paths from k and l to the root node, and let m be the first node in thepaths common to both. By assumption, since only node 1 is adjacent to the root node, m isnot the root node. Consider the sub-path, P , from k to m. Since z satisfies (3.7), it followsfrom Lemma B.3 that the allocation z is non-decreasing along P . Let r be the farthest nodefrom k on P such that zr = zk. Note that since a(Tr) − z(Tr) = zr ≤ zi ≤ a(Ti) − z(Ti),over all players i ∈ P , a(Ti) − z(Ti) is minimized at i = r. Suppose sk,l(z) attains theminimum, c(S) − z(S), at S∗, where k ∈ S∗ and l /∈ S∗. Now, if S∗ contains any firmdownstream to l then, using the same proof technique as in Lemma B.2, we conclude thatsk,l(z) = zl. If not, then sk,l(z) = a(Tr) − z(Tr) = zr = zk. So, sk,l(z) = min(zk, zl).Similarly, sl,k(z) = min(zl, zk), and therefore sk,l(z) = sl,k(z) for all pairs of players k andl. Thus, z is the pre-kernel and hence, since the Upstream Responsibility game (N, c) isconcave, it coincides with the nucleolus. Proof of Proposition 3.1If player i resides in a leaf node, then by definition of the proto-nucleolus, xi = ai−xi, implyingthat, xi =ai2 . We proceed via induction. Suppose (3.8) holds for all nodes which are upstreamto player i. For adjacent players i and j with j being a successor of i, xi = a(Tij)− x(Tij) =ai+∑k∈Ui(a(Tk)−x(Tk))−xi = ai+∑k∈Uixk−xi, implying that xi = (ai+∑k∈Uixk)/2. For player1 who has no successor player, since x is a preimputation, we have that x1 = a1 +∑k∈U1xk. Proof of Proposition 3.2Part i. If xi ≤ xj for all adjacent players i and j, then clearly the set of equations (3.8)characterizing the proto-nucleolus also satisfy the set of equations (3.7) in Theorem 3.1 thatcharacterize the nucleolus. Therefore, the proto-nucleolus coincides with the nucleolus. Theother direction is trivially true.Part ii. Suppose a(Tij) ≤ aj for adjacent players i and j in the supply chain. Then, we claimthat for all adjacent players i and j in the supply chain such that j is the immediate successorof i, xi ≤ xj . If j = 1, from Proposition 3.1, xj = x1 = a1+∑i∈U1xi. Therefore, clearly, xj ≥ xi103for j = 1 and i ∈ U1. Suppose j 6= 1. Then, again from Proposition 3.1, xj = (aj +∑i∈Ujxi)/2.Consider a firm i ∈ Uj immediately upstream to j. Then, xj ≥ (aj+xi)/2 = (a(Tij)+xi)/2 ≥(xi + xi)/2 = xi. The last inequality follows from the observation that the proto-nucleolus xis also a core allocation. Therefore, for all adjacent players i and j in the supply chain suchthat j is the immediate successor of i, xi ≤ xj . Then, it follows from the proof of part (i)that the proto-nucleolus x coincides with the nucleolus z. Proof of Lemma 3.1By Theorem 3.2, zj ≤ z1 for each j. Therefore, since z(N) = a(T ), z1 ≥ c1. Assume on thecontrary, that there exists a player l, l 6= 1, for which zl < ci, and let k be a most downstreamplayer for which zk < ci. By minimality of ci, zk < ck. Thus, by Theorem 3.2, for all j ∈ Tk,zj ≤ zk < ck. Now,∑j∈Tkzj + (a(Tk) − z(Tk)) = a(Tk) and therefore, a(Tk) − z(Tk) >a(Tk) − ck|Tk| = a(Tk) − |Tk|a(Tk)/(|Tk| + 1) = a(Tk)/(|Tk| + 1) = ck > zk. Let k′ be theplayer immediately downstream to k. Then, sk′k(z) = zk = skk′(z) = min(zk′ , a(Tk)−z(Tk)),implying that, zk = zk′ < ci, which contradicts the assumption that k is a most downstreamfirm for which zk < ci. Thus, for all j ∈ N , zj ≥ ci. Suppose now, on the contrary, that forsome j ∈ Ti, zj > ci. Then, zi ≥ zj > ci. Since∑k∈Tizk + (a(Ti) − z(Ti)) = a(Ti), it followsthat, a(Ti)− z(Ti) < a(Ti)/(|Ti|+ 1) = ci. Let i′ denote the player immediately downstreamto i. Then si′i(z) = zi = sii′(z) ≤ a(Ti) − z(Ti) < ci, contradicting our previous conclusionthat zi > ci. Thus, for all l ∈ Ti, zl = ci. Proof of Theorem 3.3From Lemma 3.1, the nucleolus z allocates ci to all players, Ni, in Ti, the first subtreegenerated in Step 1 of Algorithm A. Consider the reduced game (N¯i, cˆzN¯i) on N¯i = N\Niat z. The characteristic cost function cˆzN¯i(Q), Q ⊆ N¯i, of the reduced game (N¯i, cˆzN¯i) of theUpstream Responsibility game (N, c) is given by cˆzN¯i(Q) = min{c(Q∪R)−z(R) : R ⊆ (N¯i)c}.Denote by (N¯i, c˜zN¯i) the upstream responsibility game induced by the subtree of T spannedby the set of vertices N¯i. That is, (N¯i, c˜zN¯i) is induced by the original tree graph wherefromTi and arc (i, j) were removed, where j is the immediate successor of i, and aj was increasedby ci = zi =a(Ti)|Ti|+1 . We will show that the reduced game (N¯i, cˆzN¯i) coincides with (N¯i, c˜zN¯i).Consider a coalition Q, Q ⊆ N¯i. If Q does not contain a node downstream to i (in theoriginal tree T ), then cˆzN¯i(Q) = min{c(Q∪R)−z(R) : R ⊆ (N¯i)c} = min{c(Q)+c(R)−z(R) :R ⊆ (N¯i)c}, and since c(R) ≥ z(R) for all R ⊆ (N¯i)c, we conclude that cˆzN¯i(Q) = c(Q) =c˜zN¯i(Q). If on the other hand, Q contains a firm downstream to i, then c(Q ∪ R) = c(Q) forall R ⊆ (N¯i)c, and thus, since z is a non-negative vector, cˆzN¯i(Q) = min{c(Q ∪ R) − z(R) :R ⊆ (N¯i)c} = c(Q) − z(N¯ ci ) = c(Q) − |Ti| · a(Ti)|Ti|+1 = c(Q) +a(Ti)|Ti|+1 − a(Ti) = c˜zN¯i(Q), andwe conclude that the games (N¯i, cˆzN¯i) and (N¯i, c˜zN¯i) coincide. However, since the nucleolusis consistent, that is, it has the reduced game property, the nucleolus allocations to players104in (N¯i, c˜zN¯i) coincide with the nucleolus allocations to these players in the original UpstreamResponsibility game and the correctness of the algorithm follows by induction. Since eachstep in the algorithm takes linear time in |N |, and they repeat at most |N | times beforetermination, we conclude that Algorithm A runs in quadratic time. B. Implementation Framework and Stability AnalysisProof of Proposition 3.3Suppose i and j belong to the same alliance Ak ∈ A, then policy P implies that i and j shouldbear equal responsibility. If i /∈ Ak and j ∈ Ak, then the remnant upstream responsibility forthe players in alliance Ak is a(Ti)−xA(Ti) and their direct responsibility is a(Ak). Accordingto policy P, players in Ak should bear equal responsibility and are permitted to leave an equalshare to a downstream alliance if one exists. Further, according to policy M, monotonicityof responsibilities must be maintained. This implies that xAj ≥ max{xAi ,a(Ak)+a(Ti)−xA(Ti)|Ak|+1}if j 6= 1 and xAj ≥ max{xAi ,a(Ak)+a(Ti)−xA(Ti)|Ak|}if j = 1. The proposition now follows fromthe assumption that all the players in the supply chain are rational. Proof of Proposition 3.4Suppose, on the contrary, that not all the firms in Mk are allocated identical responsibilities.Choose Q ∈ Mk as a largest subset of firms in Mk that are all allocated identical respon-sibilities. The minimality of Mk implies that Q is not a minimal non-blocking set of firms.Therefore, by definition, there exists some alliance Q′ in A, whose members are in N\Q, thateither blocks Q or is blocked by Q. If Q′ blocks Q, then, there exists firms u1, u2 ∈ Q andu′1, u′2 ∈ Q′ such that u′1 is upstream to u1 and u′2 is downstream to u2. Policies M and Pthen imply that x(u′1) ≤ x(u1) = x(u2) ≤ x(u′2). Therefore, the firms in Q′ are also allocatedthe same responsibilities as the firms in Q. Since Mk is a minimal non-blocking set of firmsand Q belongs to Mk, Q′ must also belong to Mk, thereby contradicting the maximality ofQ. Therefore, for all firms i and j in Mk, xi = xj .Now, analogous to the set of equations (3.9), it follows from policy P that the playersin Mk should bear responsibility for at least the remnant upstream emissions transferred tothem by an upstream alliance, if such an alliance exists, which is equal to the allocation ofany member in such an upstream alliance. Further, according to policy M, monotonicity ofresponsibilities must be maintained. Therefore, for j ∈ Mk and for any upstream firm i ∈U(Mk), xAj ≥ max{xAi ,c(Mk)−xA(U(Mk))|Mk|+1}if 1 /∈ Mk, and xAj ≥ max{xAi ,c(Mk)−xA(U(Mk))|Mk|}if 1 ∈ Mk. The equalities in (3.11) follow from the assumption that all the players in thesupply chain are rational. Proof of Theorem 3.4Consider the following requirements we place on the strategies of the players in Γ. For a105nucleolus alliance structure An, (i) player j offers an upstream player i to join j’s existingalliance if i and j belong to the same alliance in An, (ii) player j can either offer or not offerplayer i to join j’s existing alliance if i and j do not belong to the same alliance in An, (iii)player i accepts j’s offer if and only if i and j belong to the same alliance in An and rejectsotherwise. We claim that the above requirements, (i)-(iii), characterize the equilibrium pathactions, pi(σ˜), of the firms in any subgame perfect equilibrium (SPE) strategy profile σ˜ of thealliance formation game Γ. Clearly, any strategy profile σ that satisfies (i)-(iii) will generatethe nucleolus alliance structure, An. That is, A(σ) = An = {An1 , ..., Anm}, and let zi denotethe nucleolus allocation to player i.Now, let us assume, without loss of generality, that the alliance Ank corresponding tosubtree Tnk was obtained in the kth iteration of Algorithm A. The proof proceeds with abi-level induction, firstly on the subtrees obtained in each iteration of the algorithm, andsecondly, a backward induction on the players in the corresponding subtrees. Let σ˜ be anarbitrary SPE of Γ generating the corresponding alliance structure, A(σ˜).Base Case: Tn1 is the subtree obtained in the first iteration of Algorithm A. For each playeri ∈ Tn1 , consider the subgame Γt with history Ht such that the player to take the next actionis i = n(Ht), and all preceding actions in A(Ht) by players in Tn1 satisfy (i)-(iii). Note thatwe make no assumption on the actions of players not in Tn1 . Suppose i is the last leaf nodein Tn1 that did not take any action. Then, we can assume that the immediate precedingmove in Γt was the one where its downstream partner j offered i to join its alliance. If iaccepts the offer, the alliance An1 is formed. If, according to σ˜, i rejects the offer, then iforms an independent alliance, {i}, and receives the allocation xA(σ˜)i . By the minimality ofTn1 , xA(σ˜)i > zi. Therefore, it is optimal for i to accept j’s offer and thus, i chooses an actionthat satisfies (i)-(iii). This case corresponds to the base case of the backward induction onthe players in the subtree Tn1 . Now, suppose player i corresponds to a branch node in Tn1 ,and suppose that in the preceding action, its downstream partner, j, offered i to join itsalliance. If i accepts, then, since players in Tn1 satisfy (i)-(iii) in all preceding actions to i’saction, it follows by the backward induction hypothesis that the succeeding players will alsoact in accordance with (i)-(iii), and the eventual alliance formed will be An1 . If, on the otherhand, i rejects j’s offer, then An1 will not form. Instead, an alliance A corresponding to somesubtree of Tn1 will form such that either i ∈ A, or i is upstream to A. Again, M impliesthat the allocation i receives is at least as large as the allocation to a firm in A, and by theminimality of Tn1 , i will be worse off. Therefore, i will accept j’s offer. Suppose now thatby (i) - (iii), firm i should offer an upstream firm u to join its alliance. Then, if i offers u tojoin, by the backward induction hypothesis, u will accept the offer, and further the allianceAn1 will form. If i does not offer u, then again, an upstream alliance A corresponding to somesubtree of Tn1 will form, such that i is downstream to A, and similarly, i will receive a larger106responsibility allocation by the minimality of Tn1 andM. Finally, suppose i is the root nodeof Tn1 , and according to (i) - (iii), the current decision corresponds to i choosing to eitheraccept or reject an offer by its downstream player j, j /∈ An1 . Suppose player i accepts theoffer, then i will either be part of, or downstream to an alliance that corresponds to a subtreeof T distinct from Tn1 . Again, i will obtain a higher responsibility allocation and therefore, ishould reject j’s offer. Therefore, in any SPE σ˜, we have that all players in Tn1 will chooseactions that satisfy (i)-(iii).Induction Hypothesis: In any SPE strategy profile, σ˜, all players in alliances Anl , for l =1, ..., k−1, created in the first k−1 iterations of Algorithm A will choose actions in accordancewith (i)-(iii).Inductive Step: We need to show that players belonging to alliance Ank will also choose actionsin accordance with (i)-(iii). From the induction hypothesis, it is seen that irrespective of theactions of the players in Ank , the players in alliances Anl , for l = 1, ..., k−1, will choose actionsthat ensure the formation of their respective alliances. The proof for the inductive step thenfollows identically the proof for the base case, except that now the minimality of Tnk in thekth step of the iteration ensures that no player violates (i)-(iii) in a SPE, thus completing theinduction.Therefore, all players’ actions in the supply chain will satisfy (i)-(iii), and thus, the cor-responding alliance structure generated by σ˜, A(σ˜) = An. The following technical result will be subsequently employed in the proof of Lemma 3.2.Assertion B.1. Consider a strong Nash-stable alliance structure A. Then, there exists astrong Nash-stable alliance structure, A′, satisfying the property that for Mu,Mv ∈ M(A′),and i ∈Mu, j ∈Mv, if Mu is upstream to Mv, then xA′j > xA′i , and further, xA = xA′.Proof of Assertion B.1. Clearly, if A itself satisfies the above property, then A′ = A.Suppose that A does not satisfy the property. This implies that there exists a minimal non-blocking set Mk such that for a minimal non-blocking set Ml that is immediately upstreamto Mk, xAj = xAi for j ∈ Mk and i ∈ Ml. Consider Mk to be such a minimal non-blockingset that is most upstream. From Proposition 3.4, we therefore obtain that xAj = xAi ≥c(Mk)−xA(U(Mk))|Mk|+1 . Consider the alliance structure A′ such that the alliances comprising Mland the alliances comprising Mk are combined yielding Mk∪Ml as a minimal non-blocking setin A′. Then, c(Mk∪Ml) = c(Mk), and xA′(U(Mk∪Ml)) = xA(U(Mk))−xA(U(Ml)). Now, inA′, i, j ∈Mk ∪Ml, and xA′j = xA′i =c(Mk∪Ml)−xA′ (U(Mk∪Ml))|Mk∪Ml|+1 =c(Mk)−xA(U(Mk))+xA(U(Ml))|Mk∪Ml|+1 =c(Mk)−xA(U(Mk))+xAj |Ml||Mk|+|Ml|+1 ≤ xAj . The last inequality follows from the prior observation thatxAj ≥ c(Mk)−xA(U(Mk))|Mk|+1 . The strong Nash-stability of A therefore implies that xA′j = xAj andtherefore, xA′ = xA preserving the strong Nash-stability. The above union operation can be107repeated successively until the above property is satisfied for all pairs of minimal non-blockingsets and at each step, the strong Nash-stability shall be preserved as shown. This completesthe proof. Proof of Lemma 3.2Consider the minimal non-blocking set structure of A, M(A). Suppose that M(A) containsonly contiguous sets of firms. We can then define an alliance structure A′ such that eachalliance in A′ corresponds to some set Mk ∈M(A). That is, we consider the alliance structureA′ = M(A). Clearly, A′ is a contiguous alliance structure. Therefore, M(A′) = A′ = M(A),which in turn implies, due to Corollary 3.1, that xA = xA′ . Therefore, for the non-contiguousalliance structure A, we have identified a contiguous alliance structure that results in anidentical allocation of responsibilities and is therefore also strong Nash stable.Moreover, we can assume that the alliance structure A satisfies the property described inAssertion B.1, since otherwise, as demonstrated in Assertion B.1, we can always transformA to satisfy the said property while yielding an identical allocation of responsibilities. Now,suppose that for some Mk ∈M(A), Mk is a non-contiguous set of firms in the supply chain.Let Mk =⋃pi=1 Si, where each Si is a maximally contiguous set of firms in Mk. Assume, forbrevity, that 1 /∈Mk, since the same proof, with some natural modifications, can be appliedfor the case 1 ∈Mk. From Proposition 3.3, and since A is assumed to satisfy the property inAssertion B.1, for j ∈ Mk and i ∈ U(Mk), xAj = c(Mk)−xA(U(Mk))|Mk|+1 > xAi . Choose l such thatl = arg minic(Si)−xA(U(Si))|Si|+1 . Consider an alliance structure A′ formed by a deviation by thefirms in Sl to form a separate alliance. Then, the allocations to all the firms upstream to Slremain identical and therefore, xAj > xA′i for j ∈ Sl and i ∈ U(Sl).Further, suppose, on the contrary, that c(Sl)−xA′ (U(Sl))|Sl|+1 ≥ xAj . Then,c(Sl)−xA′ (U(Sl))|Sl|+1 =c(Sl)−xA(U(Sl))|Sl|+1 ≥ xAj =c(Mk)−xA(U(Mk))|Mk|+1 =p∑i=1c(Si)−p∑i=1xA(U(Si))p∑i=1|Si|+1.From the first and last terms in the inequality chain, we obtain,c(Sl)−xA′ (U(Sl))|Sl|+1 ≥p∑i=1i 6=lc(Si)−p∑i=1i 6=lxA(U(Si))p∑i=1i 6=l|Si|,which implies that,c(Sl)−xA′ (U(Sl))|Sl|+1 ≥ minj 6=lc(Sj)−xA(U(Sj))|Sj | > minj 6=lc(Sj)−xA(U(Sj))|Sj |+1 ,violating the minimality of Sl. Therefore,c(Sl)−xA′ (U(Sl))|Sl|+1 < xAj . However,108xA′j = max{xA′i ,c(Sl)−xA′ (U(Sl))|Sl|+1},and both terms in the curly brackets were shown to be strictly smaller than xAj . Therefore,if the firms in Sl deviate to form a separate alliance, resulting in the alliance structure A′,they would be strictly better off. This violates the strong Nash-stability of A. Therefore,there exists no such Mk that is non-contiguous in A, which completes our proof. Proof of Theorem 3.5Consider the nucleolus alliance structure, An = {Ank}mk=1, where each alliance, Ank , in Ancorresponds to the subtree Tk obtained in the kth iteration of Algorithm A. Further, considera contiguous alliance structure A such that A 6= An. We now show that A is not strong Nashstable. Let 1 ≤ i ≤ m be the smallest index for which the alliance Ani /∈ A. Consider the setof firms S = Ani . Since, all alliances Ank such that 1 ≤ k < i are in A, and A is contiguous, weobtain from Proposition 3.3, that the remnant upstream responsibility for S in the alliancestructure A is identical as in the nucleolus alliance structure. Then, by the minimality of thesubtree Ti, the set of firms S can profitably deviate to form the alliance Ani . Therefore, thealliance A is not strong Nash stable.Now, we prove the strong Nash stability of An. Suppose there exists a set of firms Sthat can profitably deviate from their existing coalitions. Let A be the alliance structurearising from the deviation of S from An. Since the deviation is strictly profitable for S, itfollows from Corollary 3.1 that M(A) 6= An. Further, from the proof of Lemma 3.2, weknow that if S is a non-contiguous set of firms, then there exists a smaller contiguous setof firms S′ ⊂ S that could form a separate alliance and be strictly better off. Therefore,we can assume that S is itself contiguous. And since, S is contiguous and A is obtainedby the deviation of S from An, all the minimal non-blocking sets in M(A) should also becontiguous. Let 1 ≤ i ≤ m denote the smallest index for which S ∩ Ani 6= φ. Consider thesubgraph of T , Gi = T\⋃i−1j=1Anj . There exists some k′ such that Ani = Tk′ , a subtree ofGi rooted at k′. Consider Ml ∈ M(A) such that the alliance S ⊂ Ml. Clearly, Ml 6= Ani ,because then S would have had to be a subset of Ani and then S would receive an identicalallocation after the deviation contradicting the strict profitability of the deviation. Further,Ml is also a subgraph of Gi and either corresponds to a subtree Tl′ 6= Tk′ rooted at l′ or thereexists some Mp that corresponds to the subtree Tl′ and is upstream to Ml. By the minimalityof Ani′ = Tk′ , the allocation to the firms in Tl′ is greater than the allocation to the firms inAni′ , and further, therefore by policy M, the firms in Ml (that includes the firms in S) arealso all allocated an allocation greater than the allocation to the firms in Ani′ . This impliesthat a deviation by S from the nucleolus alliance structure is not profitable for the firms inS ∩ Ani′ 6= φ. This contradicts the assumption that S is a set of firms that can profitablydeviate from their current coalitions.109Further, if M(A) = An, then M(A) = M(An) since An is a contiguous alliance structure.The second part of the result then follows from Corollary 3.1 since if two alliance structureshave identical minimal non-blocking set structures, then the induced responsibility alloca-tions, xA and xAn = z, should also be identical. C. Structural PropertiesProof of Proposition 3.5Suppose, on the contrary, that there exists an alliance A1 ∈ An such that 1 ∈ A1, butA1 6= {1}. Note that from Theorem 3.3, A1 corresponds to a sub-tree T ′1 obtained at thelast iteration of Algorithm A. Let L denote the set of firms adjacent to player 1 in A1, andconsider k ∈ L such that k = arg minl∈La(T ′l )/(|T ′l | + 1), where T ′l is the subtree of T1 rootedat l. By definition, c1 = a(T′1)/|T ′1| = (a1 +∑l∈La(T ′l ))/(∑l∈L|T ′l | + 1) >∑l∈La(T ′l )/(∑l∈L|T ′l | +1) ≥ ∑l∈La(T ′l )/∑l∈L(|T ′l | + 1) ≥ a(T ′k)/(|T ′k| + 1). This contradicts the minimality of c1,and correspondingly, the existence of such a subtree T ′1. Therefore, there exists no suchalliance A1. This implies that a nucleolus alliance structure, An, always contains the singletonalliance, {1}. Proof of Proposition 3.6Let (N, c) denote the corresponding Upstream Responsibility game and suppose that thedirect emissions aj of firm j increases by δ to aj + δ. Let us denote the correspondingmodified cooperative game by (N, c′). Then, the characteristic cost function c′(S) = c(S) + δfor all S ⊆ N such that there exists a firm in S downstream to j, and c′(S) = c(S) if nosuch firm is present in S. We show that there exists ∆ > 0 such that for all 0 < δ ≤ ∆ andfor all i, zi is linear and non-decreasing in δ. This will complete the proof that the nucleolusallocation is piecewise linear and non-decreasing in the direct emissions of each firm in thesupply chain.For any subtree S of T , define κ(S) = a(S)/(|S|+ 1). Further, define∆ = minR,S⊆T,κ(S)6=κ(R)|κ(S)− κ(R)| > 0.Denote by Ai the subtree obtained in the ith iteration of Algorithm A applied to (N, c).Suppose there exists some index k such that for all 1 ≤ i < k, player j /∈ Ai. Then, AlgorithmA applied to (N, c′) shall proceed as it does when applied to (N, c), until iteration k− 1, andtherefore the nucleolus allocation z′ in the modified cooperative game (N, c′) allocates anidentical responsibility to the firms ink−1⋃i=1Ai as it does in (N, c). Therefore, without loss ofgenerality, we assume that j ∈ A1. We first observe that given our choice of ∆, for all δ ≤ ∆,110the subtrees obtained from each iteration of the algorithm applied to (N, c) and (N, c′) remainidentical. This follows because, if ci = a(Ti)/(|Ti|+1) < cj = a(Tj)/(|Tj |+1) where Ti and Tjare some sub-trees of T generated by Algorithm A to produce the nucleolus of (N, c). Then,in (N, c′), c′i ≤ (a(Ti) + δ)/(|Ti| + 1) ≤ (a(Ti) + ∆)/(|Ti| + 1) < a(Tj)/(|Tj | + 1) ≤ c′j . Forfirm i ∈ A1, z′i = zi + δ/(|A1|+ 1) implying that zi is linear and non-decreasing in δ.Now, consider the upstream responsibility game induced by the subtree of T spanned bythe set of vertices N¯1 = N\A1. That is, the game subsequent to the removal, by AlgorithmA, of the players in A1, wherein the pollution associated with arc (u, v), av, was increased byδ′ ≡ δ/(|A1|+1) ≡ αδ, u is the most downstream player in A1 and v is its immediate successorin the original supply chain graph. Note that this reduced setting can be interpreted as anupstream responsibility game wherein the weight of an arc increases by 0 < δ′ = αδ < ∆.Thus, we can proceed inductively to show that all players either receive an identical allocationas in (N, c) or an allocation linearly increasing in δ′, and therefore equivalently, linearlyincreasing in δ. Therefore, zi is continuous piecewise linear and non-decreasing in the directemissions of firm j, aj . Proof of Proposition 3.7Consider the direct emissions associated with firm j in the fossil fuel supply chain given byaj + ∆. Choose ∆ > (|N | + 1)(maxi∈Nc(Ti)). Clearly, Algorithm A will ensure that none ofthe firms in Tk, k ∈ L, will form an alliance with any of the firms in Pj , because such analliance will also be responsible for ∆, and clearly c(Tk)/(|Tk|+ 1) < c(Tk) < ∆/(|N |+ 1) <c(A)/(|A|+1), where A is any alliance containing some firm in Pj . Therefore, for each k ∈ L,Algorithm A can be run independently on the subtrees Tk ∪ k′, where k′, as defined above, isthe root node of the sub-supply chain with k′ ∈ Pj and adjacent to k. Further, the nucleolusallocation to the players in these sub-trees shall clearly not depend on ∆. Therefore, forsufficiently large ∆,∂zi∂∆= 0 where zi is the nucleolus allocation to i ∈ Tk, k ∈ L.Now, consider the remaining nodes in the supply chain. They correspond to the reducedsupply chain consisting only of the firms in Pj and the root node, 1. We claim that Pj ∈ An.Suppose, on the contrary, that upon applying Algorithm A on the reduced supply chainspanned by Pj ∪{1}, the alliance {Pj} cannot be formed. That is, a sub-tree, Pm of Pj ∪{1}is derived. By Proposition 3.5, {1} ∈ An. Therefore, Pm ( Pj . Let the root nodes ofPj and Pm be u and v, respectively. Note that, cu = (a(Pj) + ∆)/(|Pj | + 1) and cv =(a(Pm) + ∆)/(|Pm|+ 1), and by Algorithm A, since alliance {Pj} cannot be formed, cv < cu.Observe that, a(Pj)/(|Pj |+1)−a(Pm)/(|Pm|+1) ≤ a(Pj)/(|Pj |+1) ≤ ∆/((|N |+1)(|Pj |+1)) <∆/((|Pj |)(|Pj |+ 1)) = ∆(1/(|Pj |)− 1/(|Pj |+ 1)) ≤ ∆(1/(|Pm|+ 1)− 1/(|Pj |+ 1)). But thisthen implies that cu = (a(Pj) + ∆)/(|Pj | + 1) < cv = (a(Pm) + ∆)/(|Pm| + 1), yielding acontradiction. Therefore, upon applying Algorithm A to the reduced supply chain, we obtainPj as the minimal subtree in the subsequent iteration implying that Pj ∈ An. Finally, from111Proposition 3.5, {1} ∈ An. This completes our proof. Proof of Proposition 3.8Since Ank is an alliance belonging to a nucleolus alliance structure of the fossil fuel supplychain enterprise SC, it follows from Theorem 3.3 that it is obtained in some iteration t ofAlgorithm A applied to the supply chain tree T . Suppose that u is the most downstreamplayer in Ank . It also follows from Algorithm A, that each player in V (Tu)\Ank is in somealliance, in the alliance structure An, and that every firm in these alliances is upstream tosome members in Ank . Let us denote all these alliances of An, by Ani , for i ∈ U . Let SC′denote the supply chain enterprise resulting from structural changes to SC, none of whichbeing upstream to any member of Ank . Suppose that each such alliance Ani ∈ An, i ∈ U ,also belongs to a nucleolus alliance structure, A′n, of the supply chain enterprise SC′. Then,from Theorem 3.3, since any change is not upstream to some members of Ank , it follows thatall these alliances Ani , i ∈ U , could be recovered in some iteration of Algorithm A appliedto the supply chain tree T ′. Observe that Ank will be a sub-tree in the reduced supply chainenterprise obtained subsequent to all the iterations that recovered the alliances Ani , i ∈ U .Therefore, since Ank is a feasible sub-tree in the optimization step of Algorithm A, it followsthat the nucleolus allocation to the firms in Ank in the supply chain SC′ is no greater than theallocation they would receive by being part of the alliance Ank of An corresponding to SC.Alternately, suppose that there exists some alliance Anj ∈ An, j ∈ U , which is not part ofany nucleolus alliance structure in SC′. Note that the firms in Anj must be part of an allianceA′ in A′n corresponding to a connected subgraph of T ′ and further, this alliance should alsoinclude u. The latter follows from the observation that if the alliance does not include u, itwould violate the correctness of Algorithm A applied to T , in the iteration which yielded thesubtree corresponding to alliance Anj . Now, since the alliance A′ includes the firms in Anj , aswell as all the firms in Ank , the nucleolus allocation to the firms in Ank in T′ is no greater thanthe nucleolus allocation to the firms in Anj in T . From Theorem 3.2, since the alliance Anj isupstream to Ank , the nucleolus allocation to the firms in alliance Ank in SC′ is no greater thanthe nucleolus allocation to these firms in SC. This completes the proof. D. Fairness and Welfare PropertiesProof of Proposition 3.9The proposed nucleolus mechanism induces non-negative welfares, since it belongs to thecore of the game (N, c), and any core allocation x satisfies θ(S, x) = pt(c(S) − x(S)) ≥ 0.Further, we observe that the welfare vector, Θ(S, x), is a scaling by p of the vector of excesses,e(x), restricted to the set S ⊆ N . Therefore, the nucleolus mechanism also lexicographicallymaximizes Θ(S, x). Further, if the set S coincides with the set N , then it follows from the112definition of the nucleolus that it is the unique mechanism that lexicographically maximizesΘ(N, x). Proof of Theorem 3.6a. For a firm i and given the nucleolus allocation z, θi(z) = pt(xi−zi). Suppose that i belongsto the alliance A(i) in the nucleolus alliance structure derived by the application of AlgorithmA on the supply chain with a baseline emission profile. Then, by the optimality of A(i) in thecorresponding iteration of Algorithm A, it follows that the allocation i would receive for beingpart of the alliance A(i)∩Ti is at least zi. If i were part of the alliance A(i)∩Ti, then, i wouldreceive an allocation xi =∑j∈Ti\(A(i)∩Ti) αjaj + a(A(i) ∩ Ti)|A(i) ∩ Ti|+ Ii6=1 for some αj ≤ 1, j ∈ Ti. Therefore,zi ≤ xi ≤ c{i}|A(i) ∩ Ti|+ Ii6=1 =xi|A(i) ∩ Ti|+ Ii 6=1 . Therefore, θi(z) ≥ pt(xi − xi|A(i) ∩ Ti|+ Ii 6=1)yielding the first desired inequality.Now, we provide a second approach to obtain lower bounds on the welfare gains deliveredby the nucleolus allocation z. Suppose that i = 1, then 1 bears full responsibility for a1 andsince z must satisfy policy P, it follows that 1 can at most be responsible for half of theemissions from each of the firms upstream to it. Therefore, z1 ≤ a1 + c({1})− a12 , implyingthat, θi(z) = pt(x1 − z1) ≥ pt(xi − a12).If i 6= 1, then, it follows from above that, zi ≤ xi =∑j∈Ti\(A(i)∩Ti) αjaj + a(A(i) ∩ Ti)|A(i) ∩ Ti|+ 1 =∑j∈V (Ti)βjaj . Note that, in fact, αj ≤ 1/2, since each firm can pass on at most half of it’s directemissions downstream (which happens when it belongs to a singleton alliance). Therefore,for j ∈ Ti\(A(i)∩Ti), βj ≤ 1/4. Further, if |A(i)∩Ti| = 1, then i is the only firm in A(i)∩Ti.Therefore, βi ≤ 1/2 and βj ≤ 1/4 for j ∈ V (Ti) and j 6= i. If |A(i)∩ Ti| = 2, then, let firms iand j belong to A(i) ∩ Ti. Then, βi = βj = 1/3, and βk ≤ 1/4 for k ∈ V (Ti)\{i, j}. Finally,if |A(i)∩Ti| ≥ 3, then, βj ≤ 1/4, for all j ∈ V (Ti). It follows that, in all situations, βi ≤ 1/2,and for at most one j that must be an immediate upstream partner of i, βj ≤ 1/3, whileβk ≤ 1/4 for all other k ∈ V (Ti)\{i, j}. Therefore, zi ≤ ai2 +maxj∈Ui aj3+∑k∈V (Ti)\{i,j} ak4,implying that, θi(z) = pt(xi − zi) ≥ pt(3xi − ai4− maxj∈Ui aj12). This completes our proof forthe lower bounds on the welfare gains delivered by the nucleolus allocation mechanism.b. Let ai denote the associated BAU emissions for firm i. Consider a technology t, whichupon adoption, will yield an emission reduction of e from the BAU emissions at firm i.Then, given an allocation mechanism x, the associated cost savings for firm i is given bypt(x(ai; a−i)− x(ai − e; a−i)). Then, under x, technology t will be profitable to adopt if andonly if c(t) ≤ pte. We note that x allows firm i to recover fully the economic benefits oftechnology t. Observe that 0 < e ≤ ai, therefore, implying that ωi(x) = pta2i /2.Further, from Algorithm A, it follows that if firm i belongs to alliance A(i), then it receivesa share of at least 1/(|A(i)| + 1) of its own direct emissions according to the nucleolus113allocation zi. Upon adoption of technology t, zi = z(ai − e; a−i), it follows, again fromAlgorithm A, that when the emissions attributed to i, ai, reduces, the alliance that i is apart of in the nucleolus continues to lie within the set of firms in U(A(i)). Therefore, i shallbe attributed at least 1/(|U(A(i))|+ 1) of its own direct emissions upon adopting t, implyingthat c(t) ≤ pte/(|U(A(i))|+ 1) is a sufficient condition for the adoption of technology t to beprofitable under the nucleolus allocation. Thus, ωi(z) ≥ pta2i /2(|U(A(i))|+ 1), and we obtainthat 1/(|U(A(i))|+ 1) ≤ ωi(z)/ωi(x). Further, from Algorithm A, the nucleolus allocates atmost 1/2 the responsibility of ai to firm i 6= 1, that occurs when i belongs to a singletonalliance. For i = 1, the nucleolus always allocates the full responsibility of ai to i. Thus,ωi(z)/ωi(x) ≤ 1/2 for i 6= 1, and ωi(z)/ωi(x) = 1, for i = 1. This completes our proof for thelower and upper bounds on the ability of the nucleolus to incentivize adoption of potentiallyavailable emission reduction technologies. Proof of Theorem 3.7Consider the nucleolus alliance structure An for the fossil fuel supply chain represented bythe directed tree T . From Algorithm A, and specifically, the proof of Proposition B.2, itfollows that if V (T ) = {1} ⋃i∈U1V (Ti), then for any alliance An ∈ An, all the firms in Anbelong exclusively to one of the V (Ti)’s, for i ∈ U1. Indeed, such a decomposition impliesthat Algorithm A can be applied individually to each of the subtrees Ti to obtain the alliancesin An.Consider a vector of technologies t = {ti}i∈N ∈ T , where ti is a potentially availabletechnology that can achieve an emission reduction of ei(ti) ∈ (0, ai] at firm i at a costci(ti) ∈ [0,∞). Suppose that, in equilibrium, t will be adopted by the supply chain, undera carbon price pt and the baseline allocation mechanism x. Then, for each i ∈ N , ∆xi (t) =ptxi(ai; a−i − e−i(t−i))− ptxi(ai − ei(ti); a−i − e−i(t−i)) = ptei(ti) ≥ ci(ti). Therefore,Ω(x) =∫t∈Tci(ti)≤ptei(ti)dt , (B.2)Consider the nucleolus allocation z. From the decomposition property described above,when the direct emissions of firm i is reduced by ei(ti), firm i shall continue to be in an alliancethat lies exclusively in one of V (Ti) for i ∈ U1. Therefore, ∆zi (t) ≥ ptei(ti)/(1 + maxi∈U1|Ti|).Then,Ω(z) ≥∫t∈Tci(ti)≤ ptei(ti)(1+ maxi∈U1|Ti|)dt ,114Therefore,Ω(z) ≥ Ω(x)(1 + maxi∈U1|Ti|) .This completes the proof. Proof of Theorem 3.8Part i. Suppose T = Sk. Consider i to be one of the k upstream firms in N\{1}. Then,from Theorem 3.1 and the definition of the Shapley mechanism, it follows that xS and z bothallocate to firm i responsibility for half of its own direct emissions, ai/2. Since both mecha-nisms are pre-imputations, it also follows that they also allocate identical responsibilities tofirm 1. Since the two allocation mechanisms coincide, it follows that Ω(xS) = Ω(z) ≤ Ω(x∗).The last inequality follows since x∗ is the socially optimal concordant mechanism.Part ii. Suppose a(Tij) ≤ aj for all adjacent players i, j ∈ N . Then, from Proposition 3.2,the nucleolus z coincides with the proto-nucleolus and is characterized by equation (3.8).Therefore, the nucleolus allocation mechanism z attributes to each firm i 6= 1 in the supplychain responsibility for exactly 1/2 of its own direct emissions, ai, as well as responsibilityfor a portion of upstream emissions. The Shapley mechanism, xS , allocates responsibility tofirm i for a fraction, 1/(|Pi| + 1) of its own emissions, ai, where recall Pi denotes the set offirms in the fossil fuel supply chain lying on the unique path from firm i to the root node1 including i but excluding 1. Consider a vector of technologies t = {ti}i∈N ∈ T , where tiis a potentially available technology that can achieve an emission reduction of ei(ti) ∈ (0, ai]at firm i at a cost ci(ti) ∈ [0,∞). Suppose that, in equilibrium, t will be adopted by thesupply chain, under a carbon price pt and the Shapley mechanism xS . Then, for each i ∈ N ,∆xSi (t) = ptxSi (ai; a−i−e−i(t−i))−ptxSi (ai−ei(ti); a−i−e−i(t−i)) = ptei(ti)/(|Pi|+1) ≥ ci(ti).Therefore,Ω(xS) =∫t∈Tci(ti)≤ ptei(ti)|Pi|+1dt . (B.3)For the nucleolus allocation z, ∆zi (t) ≥ ptei(ti)/2.Then,Ω(z) ≥∫t∈Tci(ti)≤ ptei(ti)2dt ,Therefore,Ω(z) ≥ (|Pi|+ 1)Ω(xS)2≥ Ω(xS).115The socially optimal concordant mechanism x∗ in this case will coincide with the total pro-ducer responsibility allocation which allocates to each firm responsibility for only its ownemissions ai. It then follows by similar arguments that Ω(x∗) ≥ Ω(z)2 . Therefore, if a(Tij) ≤ ajfor all adjacent players i, j ∈ N , then Ω(xS) ≤ Ω(z) < Ω(x∗).Part iii. From the proof of Proposition 3.7, it follows that for each i ∈ N , there exists asufficiently large M which is a function of {a−i}, such that if ai > M , the nucleolus allocationz allocates responsibility to firm i for a fraction, 1/(|Pi| + 1) of its own emissions. Further,since, x∗ should be concordant, it follows that for sufficiently large M , x∗ should also allocateresponsibility to firm i for a fraction, 1/(|Pi| + 1), of its own emissions. Since, otherwise,x∗ would not satisfy concordance along the path Pi. Finally, the Shapley mechanism, asobserved earlier, also allocates to firm i fraction, 1/(|Pi|+ 1), of its own emissions.Consider a technology, t∗ = {t∗j}j∈N ∈ T (x∗). Then, ∆x∗i (t∗) = ptx∗i (ai; a−i− e−i(t∗−i))−ptx∗i (ai− ei(t∗i ); a−i− e−i(t∗−i)) = ptei(t∗i )/(|Pi|+ 1) ≥ ci(t∗i ). Consider tS = tz = {t∗i ; t0j : j 6=i ∈ N} where t0j denotes a null technology which yields zero emissions reduction at zero cost.As ai →∞, ai− ei(t∗i ) > M , and since the three allocations allocate identical responsibilitiesto firm i for its own emissions, ∆zi (tz) = ∆xSi (tS) = ptei(t∗i )/(|Pi| + 1) ≥ ci(t∗i ). Further forj 6= i, clearly, the equilibrium condition is satisfied. Therefore, tS ∈ T (xS) and tz ∈ T (z).Moreover, a(t∗) =∑j∈N(aj−ej(t∗j )) = ai−ei(t∗i )+ and a(tS) = a(tz) = ai−ei(t∗i )+∑j∈N,j 6=iaj =ai − ei(t∗i ) + ′. Therefore, it follows, that limai→∞ a(tS)/a(t∗) = limai→∞a(tz)/a(t∗) = 1. 116Appendix CChapter 3 – Carbon FootprintingComputationsOil sands are deposits of bitumen, a dense oil that needs to be typically diluted with diluentsto form diluted bitumen (dilbit) before transportation and refining. The planned dilbitcapacity for the seven in-situ (IS) projects under consideration is 224,500 bbl/day (ECCC,2016). A part of the diluted bitumen is also usually upgraded to synthetic crude oil (SCO), alower density product variety, before transportation via pipelines. Due to the economic costsimposed by upgrading bitumen, and the increasing capability of refineries to refine dilbit, thegrowth in Canadian oil sands projection and the subsequent transportation via the pipelineis expected to largely consist of dilbit rather than SCO (OSM, 2017). Therefore, we restrictthe scope of our analysis to the in-situ and diluted bitumen pathway (IS+B) rather thanin-situ and upgrading (IS+Up).We next compute the emissions associated with each stage of the fossil fuel supply chainassociated with the Trans Mountain pipeline extension depicted in Figure 6.A. Oil Sands Projects – Extraction EmissionsThe seven mines under consideration were all found to extract bitumen using the steam-assisted gravity drainage (SAGD) method. ECCC (2016) provides the GHG emission fac-tors during extraction and dilution phase of bitumen using the SAGD method as 75.1 kgCO2eq/bbl for the year 2019 with minor variations moving ahead.i. West Ells (Sunshine Oil)The planned dilbit capacity for the West Ells mine operated by Sunshine Oil is 7,100 bbl/day.Assuming an emission factor of 75.1 kg CO2eq/bbl, we obtain 0.533 kt CO2eq/day.117ii. Vawn (Husky Energy)The planned dilbit capacity for the Vawn mine operated by Husky Energy is 10,000 bbl/day.Multiplying with the appropriate emissions factor, we obtain a daily emissions of 0.751 ktCO2eq/day.iii. Edam East & West (Husky Energy)The planned dilbit capacity for the West Ells mine operated by Husky Energy is 14,500bbl/day. Multiplying with the appropriate emissions factor, we obtain 1.089 kt CO2eq/day.iv. Hangingstone Expansion (Japan Canada)The planned dilbit capacity for the West Ells mine operated by Japan Canada is 28,600bbl/day. Multiplying with the appropriate emissions factor, we obtain 2.148 kt CO2eq/day.v. Christina Lake Phase F (Cenovocus/ConocoPhillips)The planned dilbit capacity for the West Ells mine operated by Cenovocus/ConocoPhillipsis 71,400 bbl/day. Multiplying with the appropriate emissions factor, we obtain 5.362 ktCO2eq/day.vi. Foster Creek Phase G (Cenovocus/ConocoPhillips)The planned dilbit capacity for the West Ells mine operated by Cenovocus/ConocoPhillipsis 42,900 bbl/day. Multiplying with the appropriate emissions factor, we obtain 3.222 ktCO2eq/day.vii. Mackay River Phase I (Brion Energy)The planned dilbit capacity for the West Ells mine operated by Brion Energy is 50,000bbl/day. Multiplying with the appropriate emissions factor, we obtain 3.755 kt CO2eq/day.B. TMPL – Pipeline EmissionsFrom ECCC estimates, we obtain that the emission intensity of the pipeline is 6.0 kgCO2eq/1000 tonne kilometres. This includes emissions associated with the pumping sta-tions to transport the fuel as well as leakage emissions. The pipeline extends for a length of1150 kilometres. Further, it transports 224,500 bbl/day of diluted bitumen from the sevenprojects. We need the density of the dilbit in order to estimate its tonnage. From the histor-ical information about the density of Canadian dilbit blends obtained from Crude Monitor(http://www.crudemonitor.ca), we assume a density of 923.2 kg/m3. A barrel corresponds118to 158.98 litres, that is, 0.159 cubic metre. Thus, a barrel of dilbit weighs 146.79 kg, that is,0.147 tonnes.The associated pipeline emissions for TMPL becomes 0.147× 6× 224, 500× 1150/109 ktCO2eq/day = 0.227 kt CO2eq/day.C. Westridge Terminal – Shipping EmissionsFrom ECCC (2016), the marine emissions associated with the pipeline expansion project isestimated to be 68 kt CO2eq/year. Or, (68/365) kt CO2eq/day = 0.186 kt CO2eq/day.D. Refining EmissionsCai et al. (2015) provide an estimate of the greenhouse emissions of refineries in the UnitedStates processing bitumen from Canadian oil sands. We work with the assumption that theseestimates are also reflective of the processing efficiency of refineries in the Asia-Pacific withan average associated GHG emissions of 13.4 g CO2eq/MJ. A barrel of crude oil has anenergy content of 6.1 GJ (Schmitz, 2011). Therefore, the refining emissions is estimated tobe (224, 500× 6.1× 109 × 13.4) kt CO2eq/day/(106 × 109) = 18.350 kt CO2eq/day.E. Consumption EmissionsThe refining efficiency from dilbit to gasoline is 84.8% (Cai et al., 2015), and the GHG emis-sions from burning a litre of gasoline(http://sustainableanalytics.ca/2017/07/04/gasoline-carbon-tax/) is 2.31 kg. Consumption emissions from the net dilbit is then, 0.848× 158.98×224, 500× 2.31 kg CO2eq/day = 69.914 kt CO2eq/day.Scope of AnalysisIn this case study, we included those entities which are incorporated in the actual environmen-tal impact assessment report of the TMPL (ECCC 2016). The report does not incorporaterefineries or other stages downstream to the pipeline, but we have done so in order to provideas comprehensive an analysis as possible. We note that our cooperative game model and thesubsequent analysis makes no assumptions as to which entities can or cannot be included inthe supply chain under consideration. Further, typically, the scope of the evaluation processis clearly specified by the regulator. For example, the report specifies up front that the scopeof the review does not extend to “indirect” upstream emissions generated during the pro-duction of inputs such as electricity or fuels, or the emissions generated from the transportof products from the oil sands to the TMPL. So, while determining the scope of the processis indeed critical from the perspective of the regulator and the firms in the supply chain, itdoes not in any way limit the application of our model.119Appendix DChapter 3 – Further Numerical ResultsWe now consider the following simple supply chain depicted in Figure 8. The weights on thearcs represent the baseline direct emissions of the corresponding entities. The subsequentnumerical analysis is performed on firm 2 in the supply chain.Figure D.1: A simple fossil fuel supply chain.The TUR, adjusted TUR, nucleolus, and Shapley mechanisms for the supply chain canbe easily computed along similar lines as in the case study presented in §3.7. Therefore, firm2 is allocated 22, 7.5625, 6, and 7.6667 units by the TUR, adjusted TUR, nucleolus, and theShapley mechanisms, respectively. Firm welfare θ2(x) delivered by an allocation x is obtainedby comparing it with the economic costs associated with the baseline allocation mechanism,x, θ2(x) = pt[x2 − x2]. Therefore, while the TUR mechanism delivers the baseline firmwelfare of zero, θ2(x) = 0, the adjusted TUR mechanism has an associated firm welfare,θ2(xµ) = 14.4375pt. The nucleolus mechanism provides θ2(z) = 16pt, and the Shapleymechanism delivers θ2(xS) = 14.3334pt.To analyze the environmental effectiveness of each allocation mechanism, we evaluate120ω2(x), the area of the space of all potentially available costly emission-reduction technologiesto firm 2 rendered profitable by each allocation mechanism. Consider all potentially availabletechnologies t with an associated emission reduction 0 < e(t) ≤ 2 at a cost 0 ≤ c(t) < ∞.Upon adopting technology t, the TUR allocation is given by, x2(a2 − e(t); a−2) = 22 − e(t),and the adjusted TUR by, xµ2 (a2− e(t); a−2) = (22− e(t))2/(64− 2e(t)). It can also be easilyseen that the nucleolus alliance structure of the supply chain does not change by the adoptionof emission reducing technologies by firm 2, and therefore, z2(a2 − e(t); a−2) = 6 − e(t)/2.Further, since the Shapley mechanism attributes an equal share of the emissions a2 to eachentity downstream to 2, we have, xS2 (a2 − e(t); a−2) = 7.6667 − e(t)/2. For an allocationx, we recall that ω2(x) is the area of the region defined by 0 < e(t) ≤ 2 and 0 ≤ c(t) <pt[x2(a2; a−2) − x2(a2 − e(t); a−2)]. In Figure D.2 (left panel), we depict ω2(x) for the fourallocation mechanisms considered. In the right panel of Figure D.2, we plot SEW2 + θ2 as afunction of the carbon price, pt computed as in §3.7.Figure D.2: Region of potentially available technologies rendered profitable by thefour allocation mechanisms (left panel). The social environmental welfare andfirm welfare generated by the four mechanisms as a function of the carbonprice, pt (right panel).From Figure D.2 (left panel), we observe that, in this example, the nucleolus and theShapley mechanisms perform identically with respect to incentivizing the adoption of poten-tially available emission reduction technologies. Further, both mechanisms outperform theadjusted TUR mechanism in this respect. Recall that in the case study, the adjusted TURperformed better than the nucleolus along this dimension. We reconcile this by observingthat in the simple supply chain considered here, the extent of double counting, as measuredby µ ≈ 2.9, is considerably higher than that in the case study, where it was, µ ≈ 1.9. This121lends support to our observation that in supply chains with excessive double counting, thenucleolus mechanism will outperform the adjusted TUR with respect to incentivizing theadoption of potentially available emission reduction technologies.Further, in terms of cumulative firm and social environmental welfare, SEW2 + θ2, weobserve from the right panel of Figure D.2 that the nucleolus mechanism outperforms boththe Shapley and the adjusted TUR mechanism across varying levels of the carbon price,pt. This is driven by the fact that the nucleolus mechanism offers both greater firm welfareas well as higher incentives for adopting emission abatement technologies. The nucleolusmechanism also performs better than the baseline TUR mechanism at low and moderatelevels of the carbon price. This is because the nucleolus avoids double counting and as suchdelivers a higher level of welfare to firm 2. However, at higher levels of pt, this is offset by thegains in SEW2 by the baseline mechanism which offers superior incentives for the adoptionof emission abatement technologies.122Appendix EChapter 4 – Proofs and NumericalParametersProof of Theorem 4.1: Consider an arbitrary location u in the region R with N bike-sharing stations distributed uniformly across a region of radius R. We now obtain the averagedistance to the kth nearest station from u, 〈rk(N)〉. Let P (r)dr denote the probability thatthe kth nearest station is located at a distance between r and r+ dr from u. Equivalently, itis the probability that k − 1 of the other N − 1 stations lie within a radius of r and at leastone of the remaining N − k stations lies inside the ring of radii r and r + dr. Therefore,P (r)dr =(N − 1k − 1)(r2R2)k−1 [N−k∑i=1(N − ki)(2rdrR2)i]=(N − 1k − 1)(r2R2)k−1 [(N − k1)(2rdrR2)](ignoring higher order terms)=2(N − k)R(N − 1k − 1)( rR)2k−1dr.The average distance to the kth nearest station, 〈rk(N)〉, is then given by,〈rk(N)〉 =R∫r=0rP (r)dr=R∫r=02(N − k)(N − 1k − 1)( rR)2kdr123=2(N − k)R2k(N − 1k − 1) R∫r=0r2kdr=2(N − k)R2k(N − 1k − 1) R∫r=0r2kdr=2R(N − k)2k + 1(N − 1k − 1).In order to compute the average access time 〈τBa 〉 for an individual using the bike-sharingsystem, we need to compute the average distance to the nearest available bike, and the averagedistance from the nearest available dock after returning a bike. The symmetry ensures thatthe two distances are equal. Therefore, 〈τBa 〉 is then given by twice the time to walk to thekth nearest station conditioned on all the preceding k − 1 nearer stations being empty, foreach k. Further, the probability p of finding an available bike in some station is given by theservice level, p = ν.〈τBa 〉 = 2N−1∑k=1p(1− p)k−1〈rk(N)〉= 2N−1∑k=12p(1− p)k−1R(N − k)2k + 1(N − 1k − 1)= 4R[N−1∑k=1ν(1− ν)k−1(N − k)2k + 1(N − 1k − 1)](p = ν)= 4Rγ (N, ν) .Using hyper-geometric identities in Mathematica 12.1.0, we also obtained a closed-formexpression for γ (N, ν). However, for our present comparative static purposes, it suffices toderive the dependence of 〈τBa 〉 on R. The preceding analysis is also of independent interestin diverse applied settings, such as statistical physics, wherein similar computations may berequired (Bhattacharya and Chakrabarti 2008). Proof of Proposition 4.1: An individual with origin-destination (u, v) prefers a car topublic transport if and only if UC(p) > UP (p). Thus,θ(p)− θaτCa (p)− θwτCw (p)− τCg (p) > θ(p)− θaτPa (p)− θwτPw (p)− τPg (p).By comparing the disutilities of the two modes and substituting the expressions from Re-124mark 4.1, we have,θaτPa + θwτPw + θg(d(u, v)vP)+KP + d(u, v)fP > θg(d(u, v)vC)+Kc + d(u, v)fC .Rearranging the terms, and assuming that θg[1vP− 1vC]+ fP − fC > 0, we obtain that theabove inequality is equivalent to,d(u, v) >Kc − θaτPa − θwτPw −KPθg[1vP− 1vC]+ fP − fC= d˜CP .We note that the condition is satisfied so long as vC is sufficiently greater than vP as mentionedpreviously. Proof of Proposition 4.2: An individual with origin-destination (u, v) prefers a car tobike-sharing if and only if UC(p) > UB(p). Thus, by comparing the disutilities of the twomodes of transport and from Remark 4.1, we have,θaτBa + θg(d(u, v)vB)+KB + d(u, v)fB > θg(d(u, v)vC)+Kc + d(u, v)fC .From Theorem 4.1,4θaRγ (N, ν) + θg(d(u, v)vB)+KB + d(u, v)fB > θg(d(u, v)vC)+Kc + d(u, v)fC .Rearranging the terms, and assuming that vC is sufficiently greater than vB, we obtain thatthe above inequality is equivalent to,d(u, v) >KC −KB − 4Rθaγ (N, ν)θg[1vB− 1vC]+ fB − fC= d˜CB.Further, an individual with origin-destination (u, v) prefers public transit to bike-sharingif and only if UP (p) > UB(p). Thus, by comparing the disutilities of the two modes oftransport and from Remark 4.1 and Theorem 4.1, we similarly have,4θaRγ (N, ν) + θg(d(u, v)vB)+KB + d(u, v)fB > θaτPa + θwτPw + θg(d(u, v)vP)+KP + d(u, v)fP .Rearranging the terms, and assuming that vP is sufficiently greater than vB, we obtain that125the above inequality is equivalent to,d(u, v) >KP −KB + θwτPw + θa[τPa − 4Rγ (N, ν)]θg[1vB− 1vP]+ fB − fP= d˜PB.Proof of Lemma 4.1: The radius of coverage of bike-sharing is given by R. Let R˜ denote theaverage distance from any point in the interior of the region to a point in the circumferenceof the region. Then, clearly, on average, for an origin u in the interior of the region, if thedestination v is such that d(u, v) > R˜, then v shall lie outside the region of coverage. We nowcompute R˜ as a function of R. By radial symmetry, R˜ is the average distance of an arbitrarypoint on the circumference of the region to all points in the interior of the region.Consider a coordinate system with its origin lying on the circumference of the region andlet a diameter of the circular region correspond to one of the coordinate axes. As noted, theaverage distance of the origin from all points in the interior of the region corresponds to R˜.Employing polar coordinates, we have,R˜ =1piR2+pi/2∫−pi/22R cos θ∫0r2 dr dθ = 32R/9pi.Proof of Proposition 4.3:i. An individual p with origin-destination (u, v) prefers the bimodal option to bike-sharingif and only if UBP (p) > UB(p). Thus, by comparing the disutilities of the two modes oftransport and from Remarks 4.1 and 4.2, we have,θg(d(u, v)vB)+KB + d(u, v)fB > θwτPw +[d(u, v)vP+τPa vWvB]θg+KP +KB + τPa vW fB + d(u, v)fP .Rearranging the terms, and assuming, as before, that vP is sufficiently greater than vB, weobtain that the above inequality is equivalent to,d(u, v) >θwτPw + τPa vW[θgvB+ fB]+KPθg[1vB− 1vP]+ fB − fP= d˜MB.ii. An individual p with origin-destination (u, v) prefers the bimodal option to public transit126if and only if UBP (p) > UP (p). Thus, by comparing the disutilities of the two modes oftransport and from Remarks 4.1 and 4.2, we have,θaτPa + θwτPw + θg(d(u, v)vP)+KP + d(u, v)fP > θaτBa + θwτPw +[d(u, v)vP+τPa vWvB]θg+KP +KB + τPa vW fB + d(u, v)fP .Rearranging the terms, we obtain that the above inequality is equivalent to,θa(τPa − τBa ) > τPa vW(θgvB+ fB)+KB.iii. An individual p with origin-destination (u, v) prefers the bimodal option to a car if andonly if UBP (p) > UC(p). Thus, by comparing the disutilities of the two modes of transportand from Remarks 4.1 and 4.2, we have,θg(d(u, v)vC)+Kc + d(u, v)fC > θaτBa + θwτPw +[d(u, v)vP+τPa vWvB]θg+KP +KB + τPa vW fB + d(u, v)fP .Rearranging the terms, and assuming, as before, that vC is sufficiently greater than vP ,we obtain that the above inequality is equivalent to,d(u, v) <KC −KB −KP − θaτBa − θwτPw − τPa vW[θgvB+ fB]θg[1vP− 1vC]+ fP − fC= d˜MC .Proof of Theorem 4.2: First, we observe that each rebalancing stage corresponds to atraveling salesman problem (TSP) route that visits each station in the system exactly once.Asymptotic analysis (Daganzo 2005) of a TSP routing that visitsN sites randomly distributedin a region with a size A provides an approximate routing distance of kTSP√AN where kTSPis a scalar constant that is determined by the shape of the geographic region served, as wellas the distance metric norm (Ansari et al. 2018), and A is the size of the region. Therefore, itimmediately follows that the average distance during each rebalancing stage is kTSPR√piN .Further, f(ν, k, λ) denotes the rebalancing frequency, i.e. number of rebalancing stagesrequired per unit time, to maintain a service level of ν. Then, 1/f(ν, k, λ) corresponds tothe time interval between two successive rebalancing stages. K denotes the average capacityof each station, and let X denote the number of bikes/docks utilized in the time intervalbetween two successive rebalancing stages. To maintain a service level of ν, Pr(X ≤ K) = ν.Further, as mentioned, we assume that capacity of bikes and docks at each station is utilized127according to a Poisson arrival/departure process at a spatial demand imbalance rate of λper unit time. Then, it follows that X ∼ Poisson(λ/f(ν,K, λ)). Since the cumulativedistribution function for a Poisson-distributed random variable Y , Pr(Y ≤ m) with mean µand integer m, is equal to Q(m+ 1, µ), where Q is the regularized gamma function, it followsthat that, Pr(X ≤ K) = Q (K + 1, λ/f(ν,K, λ)) = ν. This completes the proof. 128Numerical parameters for Figure 4.2In Figure 4.2, we substitute realistic parameter values to generate schematic plots thatillustrate Propositions 4.1-4.3. θa, θw and θg refer to the disutility for an individual from thetime to access a mode of transport, from waiting for the mode of transport, and from thetravel time, respectively. Steimetz (2008) estimates the value of travel time to be $29.46/hr,and we therefore, set θg = $0.49/min. Further, based on Dickey (1983), we assume thatwaiting time is worth twice as much to individuals, and walking time 1.5 times as much.This leads to θa = $0.74/min and θw = $0.98/min.Based on the estimates of average speeds of cars and public transport options (bus, trains,light rails) across different cities, as in Newman and Kenworthy (1999) and Newman (2009),we set the average speed of cars, vC = 42 km/hr, and average speed of public transit, vP = 30km/hr. We then assume the speed of a bike-share user, vB = 13 km/hr.Based on estimates from a fare review of Vancouver’s public transportation system (SteerDavies Gleave 2016), we assume the average fare for public transit to be fP = $0.30/km1 andset KP = 0. Winters et al. (2019) analyze data from Vancouver’s Mobi bike sharing systemand find that the mean number of bike-share trips taken by a surveyed set of members is 10.5trips per month. Since the 3-month pass costs $75, we then estimate an average fixed costfor bike-sharing per trip of KB = $2.38/trip, and set fB = 0. This is in line with the farestructure for most public bike-sharing systems which operate on a subscription based pricingstructure. For a private car, we assume the fixed per-trip cost KC (which incorporates theaveraged cost of ownership and cost of parking and so forth) to be $12.34 and the marginalfuel cost per km, fC = $0.14/km based on estimates from https://carcosts.caa.ca/.We assume a headway of 6 minutes between buses/metro resulting in an average waitingtime for public transit, τPw = 3 minutes. We assume the time to reach the nearest publictransit point to be 4 minutes, thereby resulting in τPa = 8 minutes. These numbers are inline with typical access and wait times for public transport systems across cities. We assumethe radius of bike-sharing coverage to be 7.5 km resulting in R˜ = 8.49 km. Finally, notethat, in our model, the average access time to the nearest bike and dock, τBa , is derived fromthe density of the bike-sharing station using Theorem 4.1. However, for simplicity, in ournumerical computations, we directly assume the access time for bike-sharing, τBa = 2 minutes.1For simplicity, we consider a conversion of 1 USD = 1 CAD.129
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Essays on sustainable operations management
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Essays on sustainable operations management Gopalakrishnan, Sanjith 2020
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Essays on sustainable operations management |
Creator |
Gopalakrishnan, Sanjith |
Publisher | University of British Columbia |
Date Issued | 2020 |
Description | This dissertation comprises three independent essays on sustainable operations management. In the first essay, we consider supply chains with joint production of carbon emissions, operating under either a carbon tax or an internal carbon pricing regime. Supply chain leaders, such as Walmart, are assumed to be environmentally motivated to induce their suppliers to abate their emissions. We derive a footprint-balanced scheme for reapportioning the total carbon emissions amongst the firms in the supply chain. This allocation scheme, which is the Shapley value of an associated cooperative game, is shown to be transparent and easy to compute. Further, when the abatement cost functions of the firms are private information, it incentivizes suppliers to exert pollution abatement efforts that minimize the maximum deviation from the socially optimal pollution level. Finally, it is the unique allocation mechanism satisfying certain contextually desirable properties. The second essay analyzes a Canadian federal mandate to factor in upstream emissions during the environmental impact assessment of fossil fuel energy projects. We employ a cooperative game-theoretic model and propose the nucleolus mechanism to apportion upstream emission responsibilities. The nucleolus allocation avoids the distortionary effects of double counting and exhibits a certain contextually desirable consistency property. We develop a polynomial-time algorithm to compute the nucleolus and further provide an implementation framework in terms of two easily stated and verifiable policies. We also provide lower-bound guarantees on the welfare gains it delivers to firms and on the incentives it offers them to adopt emission abatement technologies. In the third essay, we consider the operations of bike-sharing systems. Despite their growing popularity as a sustainable urban transport option, bike-share programs in several cities such as Seattle and Montreal have run into financial difficulties due to low ridership and high operational costs. Further, their environmental benefits are ambiguous since a majority of users are observed to substitute from public transport or walking. We develop a consumer transport mode choice model to analyze the economic and environmental implications of three key operational levers: the pricing structure, station coverage and density, and frequency of rebalancing operations. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2020-07-27 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0392559 |
URI | http://hdl.handle.net/2429/75285 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration - Management Science |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
GraduationDate | 2020-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2020_november_gopalakrishnan_sanjith.pdf [ 3.39MB ]
- Metadata
- JSON: 24-1.0392559.json
- JSON-LD: 24-1.0392559-ld.json
- RDF/XML (Pretty): 24-1.0392559-rdf.xml
- RDF/JSON: 24-1.0392559-rdf.json
- Turtle: 24-1.0392559-turtle.txt
- N-Triples: 24-1.0392559-rdf-ntriples.txt
- Original Record: 24-1.0392559-source.json
- Full Text
- 24-1.0392559-fulltext.txt
- Citation
- 24-1.0392559.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0392559/manifest