Description
Strategy is also about attaining and maintaining a position of advantage over adversaries through the successive exploitation of known or emergent possibilities rather than committing to any specific fixed plan designed at the outset.
Classification of trading strategies of agents in a competitive market
CS 689 - Machine Learning Final Project presentation
Mark Gruman Manjunath Narayana
12/12/2007
Application
CAT tournament Objective
Facilitate transactions between buyers and sellers based on their expected profit margins Maximize our profit from transactional fees (static) and commission (based on transaction price)
Why perform classification?
Knowing which strategies are utilized can help us adjust our fees to maximize transactions and profit
Trading strategies used by agents
4 known strategies
Double Auction (Gjerstad-Dickhaut)
New bids depend on expectation of profit from bid Keeps track of what fraction of bids at a particular price were accepted
Extensive-Form game (Roth-Erev)
New bids based on profits from previous bids in the system Keeps track of how much profit resulted from each bid
ZI-C: Zero Information, Constrained (Gode-Sunder)
New random bids, below value (buyers) and above cost (sellers)
ZIP: Zero Information Plus (Dave Cliff)
New random bids, below value (buyers) and above cost (sellers) Keeps track of other bids and adjusts margins based on market
Data generation
Buyers - GD Buyers - GD Buyers - GD Buyers - GD
1,12,3,4,23,45,4,5,6
MARKET
21,2,4,3,45,7,2,4,33
Sellers - GD
Sellers - GD
Sellers - GD
Sellers - GD
Data Collection
Issues
4 strategies – multiclass problem Many traders use same strategy
We don’t know which trader uses which strategy Bids are masked before they reach the market
We don’t know which bid belongs to which trader If a bid is accepted, the string of bids terminates, and the same trader begins a new series of bids using a new bid ID
Bids are being shouted in no particular order
Some traders bid much more often than others
Bids are adjusted based on market response
A number of data conversion tools had to be developed
Illustration of data
Single seller example • Bids can be of any length
Seller_GD_1- 84.0, 90.4, 102.9 Seller_GD_1- 113.9 Seller_GD_1- 113.9 Seller_GD_1- 59.0, 85.2, 82.7, 81.3, 73.4,…can be a large number
• Depends on the price buyers are willing to buy at
Overall Market • Bid can be any length, any seller belonging to Seller_GD_1- 84.0, 90.4, 102.9 any strategy • Actual identities are hidden
Seller_RE_1- 93.6 Seller_GD_3- 153.9, 140.5, 75.6, 90.3 Seller_ZIP_1- 100.2, 98.7, 89.6, 77.6, 109.4 Seller_ZIP_4- 59.0, 85.2, 82.7, 81.3, 73.4 Seller_ZIC_3- 34.5,56.7,78.9 Seller_GD_3- 152.8, 132,6 … …
Classification
Generate data where the identities are not hidden Divide into classes (GD,RE,ZIP,ZIC) Break into training and testing sets Learn on training set Classify the testing set
K-means Results
Collected data did not fit the k-means model
Different number of bid sequences per strategy Variable size of bid sequences, had to limit to 1
Overall Result:
Pred->
GD 7 25 44 26
RE 56 56 44 46
ZIP 0 14 8 15
ZIC 72 40 39 48
GD RE ZIP ZIC
Accuracy = 22.04%
K-means Plot
SVM Results
SVM Polynomial kernel SVM Linear kernel
Pred->
Default gamma=1, coeff=0, degree=3
Pred->
GD 82 44 64 94
RE 0 7 0 8
ZIP 15 46 60 15
ZIC 95 38 46 78
GD 92 42 42 71
RE 0 27 8 9
ZIP 0 15 33 1
ZIC 100 51 87 114
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 32.8%
Accuracy = 38.4%
SVM Radial kernel
Default gamma=1
Pred->
SVM Sigmoid kernel
Default gamma=1, coeff=0
Pred->
GD 166 37 68 60
RE 2 39 10 15
ZIP 1 15 53 6
ZIC 23 44 39 114
GD 0 0 0 0
RE 0 0 0 0
ZIP 0 0 0 0
ZIC 192 135 170 195
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 53.8%
Accuracy = 28.2%
HMM
Q Hidden State M Mixture parameters HMM 10 States, 10 Mixtures
Pred->
GD 175 19 20 34
RE 3 49 17 15
ZIP 3 26 96 35
ZIC 11 41 37 111
GD RE ZIP ZIC
X Bid
Accuracy = 62.28%
The Model
Best result from multiple runs
HMM Results
HMM 4 States, 2 Mixtures
Pred->
HMM 100 States, 1 Mixture
Pred->
GD 158 21 25 26
RE 6 40 36 20
ZIP 10 35 64 49
ZIC 18 39 45 100
GD 163 26 32 33
RE 2 36 21 12
ZIP 3 27 62 45
ZIC 25 46 55 105
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 52.31%
Accuracy = 52.75%
HMM 4 States, 10 Mixtures
Pred->
HMM 4 States, 100 Mixtures
Pred->
GD 178 23 27 32
RE 2 34 20 17
ZIP 3 43 75 49
ZIC 9 35 48 97
GD 181 22 33 38
RE 1 45 9 9
ZIP 4 30 83 35
ZIC 6 38 45 113
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 55.49%
Accuracy = 60.98%
Feature reduction
Since there only some samples with large number of features (bids), what happens when we truncate the bids to smaller sequences? 2 features – Reduction in accuracy 10 features - Improvement (slight) in accuracy
HMM First 2 features only
Pred->
HMM First 10 features only
Pred->
GD 138 20 29 22
RE 0 13 0 0
ZIP 14 47 59 39
ZIC 40 55 82 134
GD 175 22 20 36
RE 1 50 9 5
ZIP 10 22 105 51
ZIC 6 41 36 103
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 49.71%
Accuracy = 62.57%
Other methods
Other classification techniques:
CRF SVM with user defined kernel
Fourier kernel Results
38-42% accuracy
Would like to try the pyramid kernel
Additional information may be obtained via CAT framework
More traders, longer training data collection intervals Information via “subscription” to other markets
Summary and Conclusion
Difficult dataset Best accuracy with HMM
Hidden variables (identity of traders, parameters) Time-series Thus, HMM is the best method
SVM also fairly successful (relative)
Time varying data Varying number of features
Most times 1 feature, sometimes as many as 200
Determining strategy employed by each trader may not be necessary
May be sufficient to rely on an “accurate” distribution
References
Dave Cliff. Minimal-intelligence agents for bargaining behaviours in market-based environments. Technical Report HP-97-91, HewlettPackard Research Laboratories, Bristol, England, 1997. S. Gjerstad and J. Dickhaut. Price formation in double auctions. Games and Economic Behaviour, 22:1-29, 1998. D. K. Gode and S. Sunder. Allocative efficiency of markets with zerointelligence traders: Markets as a partial substitute for individual rationality. The Journal of Political Economy, 101(1):119-137, February 1993. A. E. Roth and I. Erev. Learning in extensive-form games: Experimental data and simple dynamic models in the intermediate term. Games and Economic Behavior, 8:164-212, 1995.
Thank you!
More information on CAT can be found at:
http://www.marketbasedcontrol.com
Questions/comments? E-mail: [email protected] [email protected]
doc_918163122.pdf
Strategy is also about attaining and maintaining a position of advantage over adversaries through the successive exploitation of known or emergent possibilities rather than committing to any specific fixed plan designed at the outset.
Classification of trading strategies of agents in a competitive market
CS 689 - Machine Learning Final Project presentation
Mark Gruman Manjunath Narayana
12/12/2007
Application
CAT tournament Objective
Facilitate transactions between buyers and sellers based on their expected profit margins Maximize our profit from transactional fees (static) and commission (based on transaction price)
Why perform classification?
Knowing which strategies are utilized can help us adjust our fees to maximize transactions and profit
Trading strategies used by agents
4 known strategies
Double Auction (Gjerstad-Dickhaut)
New bids depend on expectation of profit from bid Keeps track of what fraction of bids at a particular price were accepted
Extensive-Form game (Roth-Erev)
New bids based on profits from previous bids in the system Keeps track of how much profit resulted from each bid
ZI-C: Zero Information, Constrained (Gode-Sunder)
New random bids, below value (buyers) and above cost (sellers)
ZIP: Zero Information Plus (Dave Cliff)
New random bids, below value (buyers) and above cost (sellers) Keeps track of other bids and adjusts margins based on market
Data generation
Buyers - GD Buyers - GD Buyers - GD Buyers - GD
1,12,3,4,23,45,4,5,6
MARKET
21,2,4,3,45,7,2,4,33
Sellers - GD
Sellers - GD
Sellers - GD
Sellers - GD
Data Collection
Issues
4 strategies – multiclass problem Many traders use same strategy
We don’t know which trader uses which strategy Bids are masked before they reach the market
We don’t know which bid belongs to which trader If a bid is accepted, the string of bids terminates, and the same trader begins a new series of bids using a new bid ID
Bids are being shouted in no particular order
Some traders bid much more often than others
Bids are adjusted based on market response
A number of data conversion tools had to be developed
Illustration of data
Single seller example • Bids can be of any length
Seller_GD_1- 84.0, 90.4, 102.9 Seller_GD_1- 113.9 Seller_GD_1- 113.9 Seller_GD_1- 59.0, 85.2, 82.7, 81.3, 73.4,…can be a large number
• Depends on the price buyers are willing to buy at
Overall Market • Bid can be any length, any seller belonging to Seller_GD_1- 84.0, 90.4, 102.9 any strategy • Actual identities are hidden
Seller_RE_1- 93.6 Seller_GD_3- 153.9, 140.5, 75.6, 90.3 Seller_ZIP_1- 100.2, 98.7, 89.6, 77.6, 109.4 Seller_ZIP_4- 59.0, 85.2, 82.7, 81.3, 73.4 Seller_ZIC_3- 34.5,56.7,78.9 Seller_GD_3- 152.8, 132,6 … …
Classification
Generate data where the identities are not hidden Divide into classes (GD,RE,ZIP,ZIC) Break into training and testing sets Learn on training set Classify the testing set
K-means Results
Collected data did not fit the k-means model
Different number of bid sequences per strategy Variable size of bid sequences, had to limit to 1
Overall Result:
Pred->
GD 7 25 44 26
RE 56 56 44 46
ZIP 0 14 8 15
ZIC 72 40 39 48
GD RE ZIP ZIC
Accuracy = 22.04%
K-means Plot
SVM Results
SVM Polynomial kernel SVM Linear kernel
Pred->
Default gamma=1, coeff=0, degree=3
Pred->
GD 82 44 64 94
RE 0 7 0 8
ZIP 15 46 60 15
ZIC 95 38 46 78
GD 92 42 42 71
RE 0 27 8 9
ZIP 0 15 33 1
ZIC 100 51 87 114
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 32.8%
Accuracy = 38.4%
SVM Radial kernel
Default gamma=1
Pred->
SVM Sigmoid kernel
Default gamma=1, coeff=0
Pred->
GD 166 37 68 60
RE 2 39 10 15
ZIP 1 15 53 6
ZIC 23 44 39 114
GD 0 0 0 0
RE 0 0 0 0
ZIP 0 0 0 0
ZIC 192 135 170 195
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 53.8%
Accuracy = 28.2%
HMM
Q Hidden State M Mixture parameters HMM 10 States, 10 Mixtures
Pred->
GD 175 19 20 34
RE 3 49 17 15
ZIP 3 26 96 35
ZIC 11 41 37 111
GD RE ZIP ZIC
X Bid
Accuracy = 62.28%
The Model
Best result from multiple runs
HMM Results
HMM 4 States, 2 Mixtures
Pred->
HMM 100 States, 1 Mixture
Pred->
GD 158 21 25 26
RE 6 40 36 20
ZIP 10 35 64 49
ZIC 18 39 45 100
GD 163 26 32 33
RE 2 36 21 12
ZIP 3 27 62 45
ZIC 25 46 55 105
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 52.31%
Accuracy = 52.75%
HMM 4 States, 10 Mixtures
Pred->
HMM 4 States, 100 Mixtures
Pred->
GD 178 23 27 32
RE 2 34 20 17
ZIP 3 43 75 49
ZIC 9 35 48 97
GD 181 22 33 38
RE 1 45 9 9
ZIP 4 30 83 35
ZIC 6 38 45 113
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 55.49%
Accuracy = 60.98%
Feature reduction
Since there only some samples with large number of features (bids), what happens when we truncate the bids to smaller sequences? 2 features – Reduction in accuracy 10 features - Improvement (slight) in accuracy
HMM First 2 features only
Pred->
HMM First 10 features only
Pred->
GD 138 20 29 22
RE 0 13 0 0
ZIP 14 47 59 39
ZIC 40 55 82 134
GD 175 22 20 36
RE 1 50 9 5
ZIP 10 22 105 51
ZIC 6 41 36 103
GD RE ZIP ZIC
GD RE ZIP ZIC
Accuracy = 49.71%
Accuracy = 62.57%
Other methods
Other classification techniques:
CRF SVM with user defined kernel
Fourier kernel Results
38-42% accuracy
Would like to try the pyramid kernel
Additional information may be obtained via CAT framework
More traders, longer training data collection intervals Information via “subscription” to other markets
Summary and Conclusion
Difficult dataset Best accuracy with HMM
Hidden variables (identity of traders, parameters) Time-series Thus, HMM is the best method
SVM also fairly successful (relative)
Time varying data Varying number of features
Most times 1 feature, sometimes as many as 200
Determining strategy employed by each trader may not be necessary
May be sufficient to rely on an “accurate” distribution
References
Dave Cliff. Minimal-intelligence agents for bargaining behaviours in market-based environments. Technical Report HP-97-91, HewlettPackard Research Laboratories, Bristol, England, 1997. S. Gjerstad and J. Dickhaut. Price formation in double auctions. Games and Economic Behaviour, 22:1-29, 1998. D. K. Gode and S. Sunder. Allocative efficiency of markets with zerointelligence traders: Markets as a partial substitute for individual rationality. The Journal of Political Economy, 101(1):119-137, February 1993. A. E. Roth and I. Erev. Learning in extensive-form games: Experimental data and simple dynamic models in the intermediate term. Games and Economic Behavior, 8:164-212, 1995.
Thank you!
More information on CAT can be found at:
http://www.marketbasedcontrol.com
Questions/comments? E-mail: [email protected] [email protected]
doc_918163122.pdf