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.
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.
Security: Foo -Class A Shares -Class B Shares -Class C Shares
John can only buy Class A and Class B (Wants to buy 500 at $1.50)
Sally can only buy Class B, and Class C (Wants to buy 300 at $1.52)
- Joel can buy any class. ((Wants to buy 200 @ 1.49)
Xavier owns 500 (200 Class A, 300 class B) and is selling 400 at $1.42
Jennifer owns 1000 shares (800 Class B, 200 class C) and is selling 650 at $1.50
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?