Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching

Question

I'm having some difficulty with implementing a non-brute force algorithm for solving the following Problem. If I can get something even close to O(N^3) i'd be happy at this point.

Auction: https://www.investopedia.com/terms/a/auctionmarket.asp

I have an algorithm in place that can do a generic Auction (accumulating bids and offers over a fixed period of time, leading up to an event whereby bids and offers are matched to determine a reference price (the price securities are sold at in the auction)however we've just implemented a level of complexity that is throwing me for a loop.

We have a security with underlying shares that contain restrictions on who can own them. During an auction, we need to ensure that buyers can only buy shares they're allowed based on the underlying restriction.

Example:

Security: Foo -Class A Shares -Class B Shares -Class C Shares

Buy Orders

1. John can only buy Class A and Class B (Wants to buy 500 at $1.50)

2. Sally can only buy Class B, and Class C (Wants to buy 300 at $1.52)

3. Joel can buy any class. ((Wants to buy 200 @ 1.49)

Sell Orders

1. Xavier owns 500 (200 Class A, 300 class B) and is selling 400 at $1.42

2. Jennifer owns 1000 shares (800 Class B, 200 class C) and is selling 650 at $1.50

3. Martha owns 1500 shares (300 Class A, 1200 class C) and is selling 400 at $1.52

---

When a user puts in Buy / Sell auction order, they don't care what class of shares they're buying or selling, we can determine what they are buying or selling.

The goal is trying to find the price point where the most shares can be sold, while making sure that we're filling all orders that can be filled.

I've ran through multiple scenarios on calculating it from a price perspective, and the underlying class perspective, calculating the # of shares that can be sold at each price point, but I'm at a blank as each way I do it, i find I'm missing shares that could be traded.

Example: The following illustrates (when we have a correct price) that we also need to match buyer & seller using the most restricted / least tradable security so we match those who can't trade with much first, then go for those that are less restricted.

The above isn't hard to solve, it's getting to that point, to figure out the best price and tradeable amount.

Any thoughts or ideas on this?

Answer 1

I would do this iteratively going through buyers ready to pay the highest price. I assume you can have partial fills if buyer and seller quantity don't match?

Step 1. Sort the buyers with MAX price at the top.
Step 2. Sort the sellers with LEAST price at the top.
Step 3. Take the topmost buyer from step 1 and try to fill its order, taking into consideration any restrictions, with a matching seller from the top. This will be your reference price. To match the seller you would need to traverse from top, comparing one by one to see which seller matches.
Step 4. Update the seller and buyer quantities based on the match in step 3.
Step 5. Repeat from step 1.

Hope that helps. Have a wonderful day!