Transcript Seminarium odbiorcze za rok 2005

Artificial intelligence methods in the CO2
permission market simulation
Jarosław Stańczak*, Piotr Pałka**, Zbigniew Nahorski*
*Systems
Research Institute, Polish Academy of Sciences
**Institute of Control and Computation Engineering, Warsaw University of
Technology
Introduction
• Observations of climate change indicate that global climate
warming is becoming a real threat for human civilization.
• Many researchers claim that emission of CO2 and other
greenhouse gases is responsible for this.
• Thus, great efforts are being made to reduce these emissions. An
accepted method to make this burden lighter is to implement a
system of emission limits and tradable emission permits.
The Kyoto Protocol and the market of CO2
emission permits
• This approach to emission reduction has been accepted by many
countries of the world under the Kyoto Protocol.
• Countries participating in an emission permits system have
limitations imposed on their emissions.
• If the limitations are too low for some countries, they can buy
permits from other countries, or reduce their emissions by applying
new technologies to produce „clean” energy.
• An accepted solution should depend on their decisions, based on
thorough economic optimization.
• This economic optimization is in general quite difficult problem,
thus artificial intelligence methods like evolutionary algorithms or
multi-agent systems are applied to solve it.
• To make an efficient optimization it is necessary to build a proper
model of the emission permits market.
A standard static model of the permission trade
- central planner
n
F  m in  Ci ( xi )
xi i 1
xi  K i  yi
n
y
i
0
i 1
Ci(xi) – the costs of decreasing emission from an initial value x0i down to xi;
yi – the number of acquired permits;
Ki – Kyoto target for participant i;
xi – emission of participant i ;
n – the number of participants.
Limitations of the central planner model
• Standard model does not allow free transactions between
participants;
• Calculated quantities of permits and money should be compulsory
trade
• Standard model does not calculate prices and quantities of
conducted transactions;
• Price negotiations are not considered in standard model;
• Preferences of participants are not considered in standard model.
•The central planner may not know all parameters of cost functions
with high accuracy.
New dynamic model
• Introduces transactions between participants;
• Introduces negotiations of transaction prices and amounts of traded
permits;
• Participants independently make decisions to make contracts on the
basis of negotiated prices;
•Participants do not know their optimal price level, but probably
better know their cost functions than a central planner;
• The number of transactions is not known in advance;
• Profitable transactions move market toward equilibrium;
• It is possible to apply agent-based methods to simulate such a
market model.
Dynamic model for multi-agent system
T


Gi   m ax C i ( x j 1, i )  C i ( x ji )  s ji  
j 1 s ji  ji
T
xTi  K i   s ji
j 1
0  s ji  s max

0 for parties not trading in transaction j
for parties trading in transaction j
 ji  

  ji
ji

n T
  s ji  0
i 1 j 1
 0 for partiesnot tradingin transaction j

for thepartyselling in transaction j
s ji   s ji
s ji
for thepartybuying in transaction j

Gi – maximum reduction in the total costs of decreasing emissions resulting from trading;
T – number of transactions conducted;
Cji(xji) – the costs of decreasing emissions in region i from initial value x0i to value xji after j
transactions;
Ki – Kyoto target for country i; n – number of participants;
xji – emissions of participant i after j transactions;
sji – the number of units of emissions acquired by participant i in transaction j;
smax – the maximum number of units allowed to be traded in one transaction;
pji – price of permits bought/sold by participant i in transaction j.
Applied AI methods of permission market
analysis and simulation
- specialized evolutionary algorithm
- multi-agent system
AI methods of permission market simulation
- specialized evolutionary algorithm
1. Random initialization of the population of solutions.
2. Reproduction and modification of solutions using genetic
operators.
3. Evaluation of the solutions obtained.
4. Selection of individuals for the next generation.
5. If a stop condition is not satisfied, go to 2.
Algorithm 1. Standard evolutionary algorithm.
1. Initialization of individuals (agents).
2. Modification of individuals’ states using specialized
operators.
3. Evaluation of new individuals’ states.
4. If a stop condition is not satisfied, go to 2.
Algorithm 2. Specialized evolutionary method for market simulation.
AI methods of permission market simulation
- multi-agent system
•
•
•
•
System composed of two or more autonomous software agents;
Agents communicate with each other and striving for their own purposes;
Multi-agent system should achieve some overarching objectives;
The multi-agent system does not implement these objectives directly, but
through individual objectives of each of the agents and their interactions;
• Each agent represents single party, guided by its own interests;
• Agent comes to interact with others;
• Agent’s motivation is the desire to achieve certain gains from the exchange
of permits;
Problem encoding – information required by
agents/individuals
• The marginal cost associated with a given number of permits
possessed by the country (shadow price);
• The real current price of a permit for sale/purchase;
• The real current value of a permit for sale/purchase;
• Current number of units for sale/purchase;
• The net number of units sold/purchased;
• Current emissions level;
• Previous emissions level (before the present transaction);
• Present and previous value of the objective function.
Genetic operators – models of trade methods
• Bilateral trade - two randomly chosen countries
conduct negotiations and if they agree, the transaction
is done;
• Tender - the country considered offers a number of
permits for sale, other countries offer to buy, the best
option is chosen and the contract is done.
Multi-agent platform – roles and behaviors of
agents applied
• Roles of negotiating agent and the Morris Column agent;
• Bilateral trades and tender behaviors implemented;
• The bilateral trade and tender were performed using
specialized roles and behaviors.
The data applied in computer simulations
Cost functions
Shadow price functions
a  ( x0i  xi ) 2 for xi  x0i
Ci ( x)   i
0 for xi  x0i
m ax 2 * ai * ( x0i  xi ) , min_p  for xi  x0i
ci ( x)  
min _ p for xi  x0i
Country
(region)
USA
EU
Japan
CANZ
EEFSU
Initial
emissions
(x0i)
MtC/y
1 820.3
1 038.0
350.0
312.7
898.6
Cost function
parameter
(ai)
MUSD/(MtC/y)2
0.2755
0.9065
2.4665
1.1080
0.7845
Kyoto
Limit
(Ki)
MtC/y
1 251
860
258
215
1 314
CANZ – Canada, Australia, New Zealand;
EEFSU – East Europe and Former Soviet Union.
The central planner results
Country
(region)
USA
EU
Japan
CANZ
EEFSU
Total
Final
emissions
[MtC/y]
1561.6
959.4
321.1
248.4
807.8
3988.3
Final price Number of Expenditure
permit
on permits
units
acquired
[USD/t]C
[Mt/y]
[MUSD/y]
142.5
310.8
44289.0
142.5
99.1
14121.75
142.5
63.5
9048.75
142.5
32.9
4688.25
142.5
-506.3
-72147.75
0

Costs of
reducing
emissions
[MUSD/y]
18433.0
5602.0
2059.0
4583.0
6473.0

Bilateral trade results
Country
(region)
Final
emission
USA
EU
Japan
CANZ
EEFSU
Total
[MtC/y]
1 556.7
960.2
321.2
249.0
811.9
3 899.0
Last
transaction
price
[USD/tC]
143.58
129.52
123.81
142.30
141.68
-
Corresponding
marginal price
(shadow price)
[USD/tC]
145.24
141.05
142.07
141.16
137.60
-
No. of traded Permission
permissions
cost
[MtC/y]
305.7
100.2
63.2
34.0
-503.1
0
Reduction
cost
[MUSD/y]
48 472.42
14 025.68
10 539.84
2 001.36
-75 039.30
0
[MUSD/y]
19 147.46
5 487.95
2 049.17
4 497.47
6 040.79
37 222.84
Corresponding No. of traded Permission
marginal price permissions
cost
(shadow price)
[USD/tC]
[MtC/y]
[MUSD/y]
143.52
308.83
59 794.97
142.41
99.45
20 837.18
140.00
63.62
13 736.11
142.40
33.44
3 768.45
141.12
-505.34
-98 136.71
0
0
Reduction
cost
Results of simulation using evolutionary method.
Country
(region)
Final
emission
USA
EU
Japan
CANZ
EEFSU
Total
[MtC/y]
1 559.83
959.45
321.62
248.44
808.66
3 898.00
Last
transaction
price
[USD/tC]
142.09
142.47
138.89
141.91
141.72
-
Results of simulation using multi-agent system.
[MUSD/y]
18 692.00
5 593.85
1 987.87
4 575.90
6 346.66
37 466.28
Tender trade results
Country
(region)
USA
EU
Japan
CANZ
EEFSU
Total
Final
emission
[MtC/y]
Last
transaction
price
[USD/tC]
1 561.3
959.1
321.1
248.1
808.4
3 898.0
124.70
125.34
137.41
139.74
138.61
-
Corresponding
marginal price
(shadow price)
[USD/tC]
No. of traded Permission
permissions
cost
Reduction
cost
[MtC/y]
[MUSD/y]
[MUSD/y]
310.3
99.1
63.1
33.1
-505.6
0
34 901.88
11 074.08
7 169.72
3 588.02
-56 733.70
0
18 480.87
5643.23
2060.27
4623.96
6382.91
37191.24
Corresponding No. of traded Permission
marginal price permissions
cost
(shadow price)
[USD/tC]
[MtC/y]
[MUSD/y]
Reduction
cost
142.71
143.05
142.56
143.15
141.52
-
Results of simulation using evolutionary method.
Country
(region)
Final
emission
[MtC/y]
USA
EU
Japan
CANZ
EEFSU
Total
1 559.99
959.95
321.32
248.78
807.96
3 898.00
Last
transaction
price
[USD/tC]
143.05
141.27
141.89
141.94
142.72
-
143.43
141.50
141.48
141.65
141.21
-
308.99
99.95
63.32
33.78
-506.04
0
Results of simulation using multi-agent system.
51 955.74
6 742.33
4 966.81
-6 078.57
-57 586.31
0
[MUSD/y]
18 669.49
5 522.73
2 029.09
4 527.84
6 446.11
37195.26
Transaction prices in bilateral contracts
Results of simulation
using evolutionary
method.
Results of simulation
using multi-agent
system.
Conclusions
• Results of emission market simulation obtained using
considered AI methods are very similar;
• AI methods are able to deal with complicated economic
systems with many interactions between their elements
and participants;
• Economic systems can be quite easily modeled,
simulated and controlled using AI systems;
• Future work will concentrate on introducing different
kinds of transactions between participants and
uncertainty of reported emissions.