New York Sock Exchange
- 3 minsSummary
An intelligent trading system, written in Java, that trades socks. Yes. Socks.
Links
A full report on the project can be found here.
The Github repo.
The Problem
The New York Sock exchange is a turn based simulation of a hypothetical scenario involving traders trying to trade socks, in order to get socks that match in color as much as possible.
Each player inherits a collection of ‘2n’ socks, and each sock has a color determined by an (R,G,B) triple. Here, R, G, and B are integers between 0 and 255 and the collection of (R,G,B) values is random. A player will likely be ‘embarrassed’ to wear two socks of different colors, hence the aim of the game is to pair up socks of similar colors.
The ‘sock exchange’ has been developed with players in a similar situation. In the exchange, players publicly post two socks they would like to trade, ranked as first and second. The auction house then exchanges socks between players based on compatibility and rank, and the game proceeds.
The project was a part of the Programming and Problem Solving(COMS 4444) course taught at Columbia University in Fall 2017.
Our Strategy: An Overview
Our strategy is broken into two phases:
The Matching phase
In this phase, we employed a combination of Edmond’s Blossom algorithm to come up with an optimal matching for the socks we had. The Blossom algorithm converts the sock set into a weighted graph, before finding an optimal perfect matching on the graph. To read more about the algorithm refer to Blossom Algorithm.
The Trading phase
For our trading strategy, we deployed a strategy that involved two facets.
First, we built a knowledge graph, that estimated the market value of all the socks on the market, giving our trader a good idea of what socks were “hot” on the market.
Second, we had an estimator for which socks were best for us to request i.e the socks that would decrease our embarrassment the most.
Finally, we combined both facets using a hyper-parameter tuning algorithm that found the optimal balance between these two strategies.
How we built it
Our bot is written in Java. All strategies were implemented from scratch by us.
Accomplishments that we’re proud of
Apart from doing excellently in the tournaments run in class, we are also extremely proud of the fact that our bot is efficient and our unique approach to building the knowledge graph.
What we learned
In the process of developing our strategy, we learned about matching algorithms, where they are used in practice, and how to approximate matching algorithms efficiently.
In addition, we also learned about different real world market strategies and came up with some on our own. We learned how difficult it is to predict the market value even in a toy setting such as ours.
Real World Inspiration
While the problem seems abstract at first, it manifests itself in numerous real world situations.
The sock matching problem can be abstracted to finding a minimum weight perfect matching in a graph. This is a problem that comes up in a lot of applications, including protein matching simulations in biology, traffic routes in cities etc.
Our market value knowledge graph aims to solve the online version of an important problem in machine learning, about learning from sparse partial information.
What’s next for New York Sock Exchange
While we believe we made significant strides towards developing a fully functional and optimal trader, we do believe there is scope for improvements that we plan to incorporate in the near future.
Maintaining Trade Histories
Using this information, we could sophisticate our offer strategy, catering our offers to players whom we know possess certain socks that could improve our embarrassment.
Player Specific Market Value
This could definitely provide an improved market value strategy since different players could be demanding different socks and this would allow us to discern those requests.
Links
A full report on the project can be found here.
The Github repo.
Ananth Narayan
Graduate Student, Columbia University