Warm tip: This article is reproduced from serverfault.com, please click

Optimization Algorithm for Trading Items

发布于 2021-02-02 14:30:41

When you have something that you want to sell or something you want to buy there's basically two options: to use money or to trade it with another item. This happens in real life and also in games where you have a trading system in place (an open market).

My question is: is there an optimal algorithm capable of receiving all of the available deals on the market and returning the best, optimal sequence of trades to get to item x that minimizes the overall cost?

I'll give you an example: Lets say that on the market we have this two tables, one for the people that want to trade/sell something, and one for the people that want to buy something:

Sellers:

Item I Have Items I Want (or) Price I Want
Item A - 140
Item A - 160
Item B - 50
Item C Item A + Item B 220
Item D Item C 240
Item E Item A + Item D 360
Item X Item E 360

Buyers:

Item I Want Price I'll Pay
Item A 150
Item B 70

It has to take into consideration some of the following scenarios:

  • Get to Item x only using money;
  • Get to Item x using money and trades;
  • Get to Item x using only trades;
  • Consider several small trades before getting the final trade;
  • The market is dynamic and the prices are not really "fixed". Meaning that some sellers/buyers are definitely buying/selling at prices bellow or up the average. The algorithm should thrive on this "misplaced" deals.

I don't know if I was able to make myself clear. I have a background in engineering and programming, and tried to find something that would tackle this problem but couldn't find much. I imagine that there's something to do with Greedy Algorithms, but I honestly don't know it there's something already proven to be good for this problem or if neural networks could do something for me here.

I know that this problem isn't trivial at all. In fact, there's a lot of people that make a living buying/selling items for profit like that. But they rely mostly on their knowhow and mining of opportunities that appear on the market.


I initially thought that I could transform this problem into a "traveling salesman" type of problem, where the cities are the items, and the distance between the cities is the price, and I would use some of the already established algorithms for this problem on it. But I don't know if it will work (if someone else already tried it).

Questioner
Thomas Marcelo
Viewed
0
kaya3 2021-02-02 23:41:19

You can solve this with a single source shortest path algorithm for weighted directed graphs which allows negative-weight edges, such as the Bellman–Ford algorithm.

The nodes in the graph are sets of items, the source node is the set of items you start with (possibly the empty set), the edges are either buying an item (the edge weight is the purchase price), selling an item (the edge weight is the negative sale price), or trading a set of items (the edge weight is zero).

The Bellman–Ford algorithm will find paths minimising the cost (i.e. maximising the amount of money you have remaining) to each possible set of items you can end up with. Then you can simply take the minimum cost of a path to any set containing the item you wish to acquire.

It's possible that your economy allows arbitrage, i.e. some sequence of trades, purchases and sales by which you can end up with the same items you started with but with more money. (In your example, you can buy item A for 140 and sell it for 150.) In this case the graph contains a negative-weight cycle, so there is no "best" price for any item because you can exploit the arbitrage opportunity for unbounded profit. If there is a negative-weight cycle, the Bellman–Ford algorithm will detect and report it instead of finding shortest paths.