Fair Combinatorial Batch Auction

CoW Protocol collects and aggregates intents off-chain and auctions them off to solvers. The auction is combinatorial because each solver can submit multiple bids. A solver can submit multiple bids on individual orders, in which case each "bid" represents the best price this solver can provide to an individual order. However, a solver can also submit "batched" bids, that is, bids on groups of orders.

The protocol filters out ``unfair'' batched bids, which are those delivering less to an order than some available "non-batched" bids. It then selects the combination of winning bids that maximizes the surplus received by the orders that are part of the auction (subject to some computational constraints due to the combinatorial nature of the problem).

The fair combinatorial auction provides several benefits:

• MEV Protection: Fair combinatorial auctions allow for Uniform Directed Clearing Prices (UDP), where a directed asset pair that appears multiple times across orders in the same auction settles for a consistent price. This makes transaction order irrelevant within the block, undermining the ability for MEV bots to extract value.
• Coincidence of Wants: When multiple orders trade the same assets within an auction, there may be an opportunity for a peer-to-peer swap that doesn't tap on-chain liquidity, which a solver could exploit by submitting a batched bid.
• Fairness: Ensuring that each order receives as much as it would have received had that order been auctioned off alone.