Author Topic: any document for the maching algorithm?  (Read 3966 times)

0 Members and 1 Guest are viewing this topic.

Offline biophil

  • Hero Member
  • *****
  • Posts: 880
  • Professor of Computer Science
    • View Profile
    • My Academic Website
  • BitShares: biophil
Excellent. The more I look into all this, the more impressed I am with how well thought-out things seem to be. And the happier I am that I discovered it now instead of 3 months from now.

And bytemaster, I really appreciate your unflagging interest and patience in answering everybody's questions! Thanks for not turning up your nose at a newbie's criticism!
Support our research efforts to improve BitAsset price-pegging! Vote for worker 1.14.204 "201907-uccs-research-project."

Offline bytemaster

Yep, I see. I think you've answered to my satisfaction... I guess the incentive to under-represent your willingness to trade still exists in traditional market matching, in a way that it doesn't necessarily in a 1-sided auction.

Obviously, 100% transparency will help a lot too.

So will it be possible for someone to create a client that automatically walks the book an order at a time? One that does traditional market-matching on the client side? I guess it will depend on how the network prioritizes orders - if it does something like "process high bids and low asks first" then client-side market matching would be quite a bit harder.

I do process high bids and low asks first which means that you couldn't dump 20 orders at different prices at once because your high bid would be matched against the lowest ask and you would pay a higher fee.  This forces the book-walkers to place 1 bid per block.   By slowing the book walkers down you prevent manipulation.
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline biophil

  • Hero Member
  • *****
  • Posts: 880
  • Professor of Computer Science
    • View Profile
    • My Academic Website
  • BitShares: biophil
Yep, I see. I think you've answered to my satisfaction... I guess the incentive to under-represent your willingness to trade still exists in traditional market matching, in a way that it doesn't necessarily in a 1-sided auction.

Obviously, 100% transparency will help a lot too.

So will it be possible for someone to create a client that automatically walks the book an order at a time? One that does traditional market-matching on the client side? I guess it will depend on how the network prioritizes orders - if it does something like "process high bids and low asks first" then client-side market matching would be quite a bit harder.
Support our research efforts to improve BitAsset price-pegging! Vote for worker 1.14.204 "201907-uccs-research-project."

Offline bytemaster

I think I've figured out my misgivings:

In your example, B has an incentive to raise his ask price; A has an incentive to lower his bid price. That's all well and good, but here's the the problem: B's ask price no longer accurately reflects his true willingness to sell, and A's bid price no longer accurately reflects his true willingness to buy. Since they don't know each others' willingness to exchange, B could raise his ask price above A's bid price and make the market illiquid.

So there's the dangerous perverse incentive: giving people exactly the exchange rate on their order incentivizes them to act like they're less willing to exchange than they really are, and market liquidity suffers.

This is why eBay doesn't charge winning bidders their bid; it charges them the bid of the second-highest bidder, because then bidders do not have an incentive to under-represent their willingness to buy. eBay's goals are essentially the same as BitShares'; i.e., they both want to facilitate the highest possible number of exchanges.

I can't speak to your last point; it could be that the technical aspect of validating transactions wins in the end.

Everyone wants to lower their bid or raise their ask to maximize their return even with traditional market matching.    It isn't the people who don't want to buy or sell that facilitate trades, it is those that DO want to buy and sell.  With my matching algorithm if you want to buy *NOW* then you have 2 choices:

1) Place 1 order at a price that will be matched with enough volume to be filled immediately.  In this case every ask is filled at the price they requested and YOU pay a fee proportional to how much of the order book you consumed in a single go.   If you were willing to pay Price X for 80% of your order then paying .01X more than necessary for the other 20% of your order should be irrelevant.   In other words, the algorithm penalizes people for walking the book in a single go.  The more of the book you walk the higher your effective fees become.  This is good for preventing manipulation.

2) Place N orders sequentially higher so that you can minimize your fees.  Thus you gradually walk the book one trade at a time and get the same result as placing a single large order in a traditional matching algorithm.  You minimize your fees and get everything at the best price possible.

The benefit of forcing people to do #2 is that it gives the market a chance to respond to attempts to walk the book.  Price manipulation becomes harder because everyone sees you walking the book and thus has time to throw new orders your way.

Different strategies will be required, but in a market with 100% transparency and relatively slow (30 seconds) order processing a different approach is required than a High Frequency Trading system. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline biophil

  • Hero Member
  • *****
  • Posts: 880
  • Professor of Computer Science
    • View Profile
    • My Academic Website
  • BitShares: biophil

Rather than present a "technical" justification I will simply present an analogy.  You have 3 players in the market, someone who wants to buy A, someone who wants to sell B, and someone who knows both A and B, C.   

If A and B do not know each other and C knows there is an opportunity to buy from B low, flip, and sell to A for a profit then he will make the market and keep the profit.   If A and B know that C will be doing this then they have incentive to minimize the spread.

Perverse incentives that could result... users must create many small bids/asks to get the best possible price.

Also the process of giving people exactly what they ask for makes validating transactions much easier because I can search for equality rather than >= and thus avoid ambiguous cases.


I think I've figured out my misgivings:

In your example, B has an incentive to raise his ask price; A has an incentive to lower his bid price. That's all well and good, but here's the the problem: B's ask price no longer accurately reflects his true willingness to sell, and A's bid price no longer accurately reflects his true willingness to buy. Since they don't know each others' willingness to exchange, B could raise his ask price above A's bid price and make the market illiquid.

So there's the dangerous perverse incentive: giving people exactly the exchange rate on their order incentivizes them to act like they're less willing to exchange than they really are, and market liquidity suffers.

This is why eBay doesn't charge winning bidders their bid; it charges them the bid of the second-highest bidder, because then bidders do not have an incentive to under-represent their willingness to buy. eBay's goals are essentially the same as BitShares'; i.e., they both want to facilitate the highest possible number of exchanges.

I can't speak to your last point; it could be that the technical aspect of validating transactions wins in the end.
Support our research efforts to improve BitAsset price-pegging! Vote for worker 1.14.204 "201907-uccs-research-project."

Offline bytemaster

Bytemaster, have you guys done a game-theoretic analysis of your matching? I haven't thought about it yet in enough detail to be sure, but from what I know of auction theory, it seems to me that giving people exactly what they ask for (instead of the best price available) could introduce some unexpected perverse incentives...

On the other hand, the fact that bidders/askers get the best price available if they bid the market price could essentially be an incentive to price stability, which is of huge concern.

Rather than present a "technical" justification I will simply present an analogy.  You have 3 players in the market, someone who wants to buy A, someone who wants to sell B, and someone who knows both A and B, C.   

If A and B do not know each other and C knows there is an opportunity to buy from B low, flip, and sell to A for a profit then he will make the market and keep the profit.   If A and B know that C will be doing this then they have incentive to minimize the spread.

Perverse incentives that could result... users must create many small bids/asks to get the best possible price.

Also the process of giving people exactly what they ask for makes validating transactions much easier because I can search for equality rather than >= and thus avoid ambiguous cases.
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline biophil

  • Hero Member
  • *****
  • Posts: 880
  • Professor of Computer Science
    • View Profile
    • My Academic Website
  • BitShares: biophil
Bytemaster, have you guys done a game-theoretic analysis of your matching? I haven't thought about it yet in enough detail to be sure, but from what I know of auction theory, it seems to me that giving people exactly what they ask for (instead of the best price available) could introduce some unexpected perverse incentives...

On the other hand, the fact that bidders/askers get the best price available if they bid the market price could essentially be an incentive to price stability, which is of huge concern.

Over the weekend I'll try to write up what I'm thinking a little more formally; till then I'd love to hear whatever technical justification of your matching algorithm you have.
Support our research efforts to improve BitAsset price-pegging! Vote for worker 1.14.204 "201907-uccs-research-project."

Offline alt

  • Hero Member
  • *****
  • Posts: 2821
    • View Profile
  • BitShares: baozi
It makes sense.
It's enough to know that you have carefully considered the algorithm.
I trust you guys.

Anyway I think the alpha test will be more effective if you can offer more documents about the details.
Thx.

Offline bytemaster

The way it is set up now everyone gets exactly what they ask for and nothing more.  The theory is that when you look at the order book, there is very little volume near the highest bid or lowest ask and therefore anyone looking to buy or sell in bulk would quickly walk the book and get the majority of their order filled at a much wider spread.   The difference in cost between placing 10 orders that exactly match and placing 1 order is how the market charges a trading fee.  If you place many bids in an attempt to optimize the purchases you will also pay more trx fees.

Bottom line is that the inefficiencies in the order matching force people to place bids and asks based upon value rather than technicals and the process makes it more expensive to attempt to manipulate the market.   

Those that want the ultimate efficiency can create many bids and asks client side. 

Ultimately the matching algorithm choice will be driven by market forces as anyone can fork the code and launch a chain with a different matching algorithm.   

I took the perspective that the blockchain is a 'market maker' which makes trades it can and profits from anyone who bids too high or asks too low.

If you want to buy in bulk, I recommend placing a large order slightly above the highest bid price and letting the asks sell into it. 

Remember, this market will not be geared toward high frequency trading.

If Alt can post an alternative variation of his algorithm below that also charges a transaction fee... that would be great.   Also Alt's algorithm fails if x, z and y are all equal. 

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline alt

  • Hero Member
  • *****
  • Posts: 2821
    • View Profile
  • BitShares: baozi
the highest bid price is x, lowest ask price is y, last trasaction price is z.

Code: [Select]
if x < y
    can't deal
else
     if x > z > y
          this transaction price is z
     else if z > x >  y
          this transaction price is x
     else if x > y > z
          this transaction price is y
   


I test agian, yes, you are right. C will buy from B
I should make it more clear:
1.  short 1000 usd with price 100usd/bts
2.  short  1000 usd with price 100.1usd/bts
3.  short 1000 usd with price 100.2 usd/bts
   ......
10.  short 1000 usd with price 100.9 usd/bts
   
     If someone want to buy 10000 usd, how should he give the order?
     For the algorithm now, he had to give 10 orders with price 100, 100.1, 100.2, 100.3 ......
     It's not good
no, according to the existing market order matching algorithm, C will buy 1000 usd from B with price 1 usd/bts.

btw, why C place the order with the price 1 usd/bts if market has already offerred price 100 usd/bts :-X

i agree with you that this is a problem. the market order was always executed at the ask price if the ask price is lower than the bid price.

Offline crazybit

I test agian, yes, you are right. C will buy from B
I should make it more clear:
1.  short 1000 usd with price 100usd/bts
2.  short  1000 usd with price 100.1usd/bts
3.  short 1000 usd with price 100.2 usd/bts
   ......
10.  short 1000 usd with price 100.9 usd/bts
   
     If someone want to buy 10000 usd, how should he give the order?
     For the algorithm now, he had to give 10 orders with price 100, 100.1, 100.2, 100.3 ......
     It's not good
no, according to the existing market order matching algorithm, C will buy 1000 usd from B with price 1 usd/bts.

btw, why C place the order with the price 1 usd/bts if market has already offerred price 100 usd/bts :-X

i agree with you that this is a problem. the market order was always executed at the ask price if the ask price is lower than the bid price.

Offline alt

  • Hero Member
  • *****
  • Posts: 2821
    • View Profile
  • BitShares: baozi
I test agian, yes, you are right. C will buy from B
I should make it more clear:
1.  short 1000 usd with price 100usd/bts
2.  short  1000 usd with price 100.1usd/bts
3.  short 1000 usd with price 100.2 usd/bts
   ......
10.  short 1000 usd with price 100.9 usd/bts
   
     If someone want to buy 10000 usd, how should he give the order?
     For the algorithm now, he had to give 10 orders with price 100, 100.1, 100.2, 100.3 ......
     It's not good
no, according to the existing market order matching algorithm, C will buy 1000 usd from B with price 1 usd/bts.

btw, why C place the order with the price 1 usd/bts if market has already offerred price 100 usd/bts :-X

Offline crazybit

no, according to the existing market order matching algorithm, C will buy 1000 usd from B with price 1 usd/bts.

btw, why C place the order with the price 1 usd/bts if market has already offerred price 100 usd/bts :-X

Offline alt

  • Hero Member
  • *****
  • Posts: 2821
    • View Profile
  • BitShares: baozi
I have some question about the maching algorithm:
1. how about the maker-taker ?
    http://www.marketswiki.com/mwiki/Maker-taker
   
2. A short 1000 usd with price 10usd/bts
    B short  1000 usd with price 100usd/bts
    C buy 1000 usd with price 1usd/bts
I think the result is C buy 1000 usd from B, with  price 100usd/bts.
but now, the result is C buy 1000 usd from A, with price 1 usd/bts.

Sorry for my poor Englist.