Say Alice asks for 100 for 5 stocks, Rob asks 101 for 5 stocks.
Bob really wants to buy the stocks, so he bids $101 for 10 stocks.
Does Bob actually pays 100 * 5 + 101 * 5 + fee, or 101 * 10 + fee?
This is complicated by the fact that Bob may not see Alice is asking 100 for 5 stocks if Alice's order arrives few milliseconds before Bob's order.
Or maybe all brokers eat it, but no exchange eats it?
What your describing is a simple limit-order book. Bob submits a limit order to buy 10 shares at \$101 so he will get filled for 5 @ 100 and 5 @ 101 and have a VWAP of \$100.5.
If a broker or exchange did that to you where you pay 101 for all it would be completely illegal. You’re entitled to receive shares at the best available price by law in most countries. When you submit orders either market or limit you fill against orders in this order: price, time, hidden.
This means that the first priority for filling against an order is the price. The second condition is time. So for example if two traders submitted orders to sell at 5@100 but trader A submitted his ask 10 minutes before trader B, trader A would have priority for selling his shares — if you only bought 5 shares then only trader A would sell and B would still have an ask waiting at 100. The last condition is hidden status which can vary across exchanges...
For hidden status this is what we refer to as an iceberg order in the case of Canadian markets. The rule is you have to display part of the order but you can have as many shares that will re-queue on fill. The upside is you can hide part of your order, downside is you lose priority if other traders match your price. This is done so that somebody with a huge position trying to offload can in many respects hide their intentions. For example if trader C has an iceberg order to sell 500@100 in chunks of 5 at a time.. then trader A and B submitted orders to sell 5@100 then what would happen if a market order to buy 20@100 was submitted C would sell 5 then A and B would sell 5 each then C would immediately re-queue and the last 5 would sell from C @ 100.
Hope that helps. This gets more convoluted when you add odd-lots, dark pools and dark orders into the mix... but we won’t get into that.
Bob pays 100 * 5 + 101 * 5. Each exchange has strict matching rules, it's called Matching Algorithm (MA). MA can be different for different markets and exchanges. But as far as I know, it's always available publicly (I doubt that traders would trade otherwise).
There is a large variety of how different MA set priority for orders at the same price. Suppose, there are more than 1 order at price=100. The most popular is FIFO, or Price-Time priority, meaning that the order that appeared first at price=100 will be matched first. But as far as I know, all MA have price priority. Which means Bob's BUY order would first be matched against price=100 and only then against price=101 and so on if necessary.
It doesn't matter whether Bob was aware of order(s) at price=100 or not.
Also, note that Matching Engine (ME) matches orders one by one. If both Bob and Donald sent equal orders and they arrived to ME even at the same nanoseconds, only the first among them will get execution at price=100. The other one will be matched against orders at higher price (if the order's limit price permits so).
Here is a video of market mechanics in action: https://twitter.com/bookmap_pro/status/963390817326063616
And here are two images demonstrating the "matching" process. The green and red lines are Best Bid and Best Ask accordingly. Green and red dots are executions of Buy and Sell orders accordingly. And the Heatmap represents the market depth (in your example - the resting orders of Alice and Rob) - see its colormap on the toolbar.
