Paging the patron GM(s) of the Auction House on Line 1!

[Yomo Kimyata]

I was hoping to use this a thread to ask GMs (if they can or will tell us) about some of the inner workings of how certain things really work.  But I'm not sure who the right person to ask is, so I'll start by pinging the wise and powerful @Jimmy in the hopes that they can steer us in the right direction.

 

And my first question is:  in the AH, the first tie breaker is price, but how are trades allocated if there are identical bids or offers?  If you put in block bids, some will partially fill and some will completely fill in no obvious order.  If two characters are offering an item at the same price, how does the AH choose one over another?

 

Inquiring minds want to know!  And thanks!

[Jimmy]

Ah yes, the auction house.

 

Here is an accurate depiction of the inner workings of the auction house:

 

 

(but really I have no idea, sorry)

[Yomo Kimyata]

Y'all should appoint GM Jude as the patron GM of lost causes...

 

[Yomo Kimyata]

@Jimmy is there any GM who can answer questions about this?

[seebs]

That would be devs, not GMs, and you know, the code is available...

[Yomo Kimyata]

1 hour ago, seebs said:

That would be devs, not GMs, and you know, the code is available...

 

Well, if you're volunteering, great, thanks!  I don't have the code skills myself.  I appreciate it!

[seebs]

Oh, I'm definitely not volunteering. Vague recollection: I saw nothing to indicate that there was any tie-breaking or ordering going on, so how it chooses is it doesn't, which means that it gets whatever order the results happened to come back in, which is sort of random-ish but without any actual attempt at being random, just also without any attempt to impose an order.

[Andreah]

5 hours ago, seebs said:

Oh, I'm definitely not volunteering. Vague recollection: I saw nothing to indicate that there was any tie-breaking or ordering going on, so how it chooses is it doesn't, which means that it gets whatever order the results happened to come back in, which is sort of random-ish but without any actual attempt at being random, just also without any attempt to impose an order.

This is my recollection and belief as well, but it would be great to see it be confirmed from code inspection.

[UberGuy]

We had this information given to us back pre-sunset by the Paragon devs, after some players experimented extensively and reported their findings.

 

The order ties are broken is based on purely internal implementation details of how the auctions are stored. That order is fixed until, IIRC, someone posts another of the same items at the same price. Then the tie resolution order shuffles again.

 

For practical purposes, yes, it's effectively random.

 

Edited April 21, 2021 by UberGuy

[UberGuy]

I just went digging in some of the public I26 code, which is a couple of years old now. I didn't study it in great detail, but here's what I got from it.

 

The list of bids and listings are stored in "binary heap" structures storing pointers to structures representing bids and sales, respectively. A processing loop iterates over both in parallel, popping items off of the "top" of the two heaps looking for matches where a bid fulfills a listing. "Skipped" bids and listings that don't line up are stuffed into temporary heaps during processed and all of them are shoved back into the main bid/sale heaps before moving on to the next loop iteration.

 

Sort order of items with different values in binary heaps is stable, meaning the sort order of unchanged entries will be the same after an insertion or removal of an item to/from the heap. However, the sort order of items with equal values (ties) is not guaranteed to be stable. The auction item listings stored in the heaps are sorted by item name and the bid/sale price, without reference to who is bidding on or selling the item, or when the bid/sale was posted. This means changes to the structures can re-order the ties on each heap change.

 

Edited April 21, 2021 by UberGuy

[Yomo Kimyata]

Thanks @UberGuy.  Now I have to make a tanker named Heap Change.

 

Next question:  when converting an IO by rarity, how does the algorithm work?  Does it choose any (in rarity) (not in set) from a list?  Does it select completely randomly and if the same set is chosen, re-roll?  Does it choose a different set (in rarity) first and then select within set randomly?  I hope to have another data project done soonish, but it would be nice to verify!

[UberGuy]

Conversions using any of the "out-of-set" categories are done at the whole set level. A non "in-set" conversion will always give you a piece of a different set than the original piece. A list of valid target sets (based on conversion group and a few things like the original enhancement's level) is constructed first and then a random set is chosen from that list. Pieces within the resulting set are chosen randomly from the pieces listed as part of that set. There are no rerolls.

Edited April 21, 2021 by UberGuy

[Yomo Kimyata]

On 4/21/2021 at 12:15 PM, UberGuy said:

I just went digging in some of the public I26 code, which is a couple of years old now. I didn't study it in great detail, but here's what I got from it.

 

The list of bids and listings are stored in "binary heap" structures storing pointers to structures representing bids and sales, respectively. A processing loop iterates over both in parallel, popping items off of the "top" of the two heaps looking for matches where a bid fulfills a listing. "Skipped" bids and listings that don't line up are stuffed into temporary heaps during processed and all of them are shoved back into the main bid/sale heaps before moving on to the next loop iteration.

 

Sort order of items with different values in binary heaps is stable, meaning the sort order of unchanged entries will be the same after an insertion or removal of an item to/from the heap. However, the sort order of items with equal values (ties) is not guaranteed to be stable. The auction item listings stored in the heaps are sorted by item name and the bid/sale price, without reference to who is bidding on or selling the item, or when the bid/sale was posted. This means changes to the structures can re-order the ties on each heap change.

 

 

I'm guessing that this was just an easier programming job, but boy, it smarts at the thought that someone else can come in after you at the same price and buy or sell first.

 

Almost makes you want to spend time on developing pricing strategy...

[Yomo Kimyata]

On 4/21/2021 at 2:06 PM, UberGuy said:

. A list of valid target sets (based on conversion group and a few things like the original enhancement's level) is constructed first and then a random set is chosen from that list. Pieces within the resulting set are chosen randomly from the pieces listed as part of that set. There are no rerolls.

 

I assume that these are equal weighted, both in terms of selecting a new set and then within the set?

 

And thanks again @UberGuy you're my patron saint!

[UberGuy]

24 minutes ago, Yomo Kimyata said:

 

I assume that these are equal weighted, both in terms of selecting a new set and then within the set?

 

And thanks again @UberGuy you're my patron saint!

 

Yep. It picks a random integer in the range 0 - (LIST_SIZE-1) and indexes into the array using that.

 

And very welcome!

Edited April 23, 2021 by UberGuy

[Andreah]

On 4/22/2021 at 9:41 PM, Yomo Kimyata said:

Almost makes you want to spend time on developing pricing strategy...

😄

[tidge]

On 4/21/2021 at 12:15 PM, UberGuy said:

Sort order of items with different values in binary heaps is stable, meaning the sort order of unchanged entries will be the same after an insertion or removal of an item to/from the heap. However, the sort order of items with equal values (ties) is not guaranteed to be stable. 

 

In my day job (the one I don't get Patrol XP for) I find myself on both sides of issues like this: explaining why we just can't write requirements around specific implementations and motivating testers to demonstrate that any invocation of the "80-20" rule had better be thorough enough to show me that such an issue (caused by a specific immutable implementation) happens less than 20% of the time.

 

I think it was Genghis Khan that said "There will always be one software engineer willing to walk alone into the blizzard just to scream at the Dzud."