Paper: arXiv 2410.18751
Authors: Mohit Garg, N. Raja, Suneel Sarswat, Abhishek Kr Singh
Abstract
Double auctions are widely used in financial markets, such as those for stocks, derivatives, currencies, and commodities, to match demand and supply. Once all buyers and sellers have placed their trade requests, the exchange determines how these requests are to be matched. The two most common objectives for determining the matching are maximizing trade volume at a uniform price and maximizing trade volume through dynamic pricing. Prior research has primarily focused on single-quantity trade requests. In this work, we extend the framework to handle multiple-quantity trade requests and present fully formalized matching algorithms for double auctions, along with their correctness proofs. We establish new uniqueness theorems, enabling automatic detection of violations in exchange systems by comparing their output to that of a verified program. All proofs are formalized in the Coq Proof Assistant, and we extract verified OCaml and Haskell programs that could serve as a resource for exchanges and market regulators. We demonstrate the practical applicability of our work by running the verified program on real market data from an exchange to automatically check for violations in the exchange algorithm.
Complexity vs Empirical Score
- Math Complexity: 8.0/10
- Empirical Rigor: 7.0/10
- Quadrant: Holy Grail — high math complexity, high empirical rigor
Why this score: The paper employs advanced formal methods (Coq proof assistant, correctness proofs, extraction of verified OCaml/Haskell) and complex mathematical theorems, giving a high math score. It demonstrates practical applicability by testing the verified program on real market data from an exchange to check for violations, resulting in strong empirical rigor.
Research Flowchart
flowchart TD A["Research Goal: Verify<br>Double Auction Matching Algorithms"] --> B["Methodology: Formalization & Proof in Coq"] B --> C["Data Input: Real Market Data<br>from Exchange"] B --> D["Computational Process:<br>Verified OCaml/Haskell Extraction"] C --> E["Computational Process:<br>Automated Violation Checker"] D --> E E --> F["Key Finding 1:<br>Formal Proofs & Uniqueness Theorems"] E --> G["Key Finding 2:<br>Detection of Exchange Violations"]
Evidence Card
What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card
Proposes
The paper extends double auction theory to multiple‑quantity trade requests and provides fully formalized matching algorithms (Fair, Uniform‑matching, Maximum‑matching) with correctness and uniqueness proofs, extracted as verified OCaml and Haskell programs.
Source sentence
In this work, we extend the framework to handle multiple-quantity trade requests and present fully formalized matching algorithms for double auctions, along with their correctness proofs. We establish new uniqueness theorems, enabling automatic detection of violations in exchange systems by comparing their output to that of a verified program.
Assumes 3
- Orders are represented as an admissible order‑domain (B, A) with unique ids and timestamps. model
Source sentence
Here an admissible order-domain (B, A) refers to a set of bids B and a set of asks A with unique ids and unique timestamps.
- All sets of bids and asks are finite; the Coq formalization uses lists to represent them. model
Source sentence
Our presentation leverages set notation for clarity, with the understanding that all sets discussed are finite. It is worth noting that our Coq formalization employs lists rather than sets.
- The input lists of bids and asks are sorted by decreasing competitiveness before matching. execution
Source sentence
Algorithm 4 The UM Algorithm function UM(Bids B, Asks A) Sort the bids in B in decreasing order of competitiveness. Sort the asks in A in decreasing order of competitiveness.
Data
- real market data from an exchange order-book unknown
Source sentence
We demonstrate the practical applicability of our work by running the verified program on real market data from an exchange to automatically check for violations in the exchange algorithm.
Costs
Not applicable
Finds 4
- Theorem 1 (Demand‑Supply Inequality) shows that for any price p, no matching can exceed the sum of total demand and total supply at p. theoretical
Source sentence
For example, in Theorem 1, we prove a well-known result (Lemma 4 of [NP13]): for any price p, no matching can achieve a volume higher than the sum of the total demand and the total supply in the market at price p. Here the total demand at a price p is the sum of the quantities of the bids whose transaction price is at least p. Similarly, we can define total supply. Theorem Bound p M B A: admissible B A /\ Matching M
- The Fair procedure converts any matching into a fair matching without changing total trade volume (Theorem 2). theoretical
Source sentence
In Theorem 2, we show that the volume of M and M ′ are the same and M ′ is a fair matching. If M is a matching over an admissible order-domain (B, A), then the matching M ′ = Fair(M, B, A) over (B, A) is a fair matching such that Vol(M) = Vol(M ′).
- The UM algorithm outputs a fair and optimal‑uniform matching, achieving the maximum possible volume among uniform matchings (Theorem 3). theoretical
Source sentence
We design an algorithm, the UM procedure, that takes as input a collection of bids and asks and outputs a fair and uniform matching. Formally, Theorem 3 (Correctness of UM).
- A practical checker based on the verified program can automatically detect violations in an exchange’s matching algorithm when run on real market data. performance
Source sentence
We demonstrate the practical applicability of our work by running the verified program on real market data from an exchange to automatically check for violations in the exchange algorithm. A practical demonstration of such a checker is also included in Section 6.1.
Checked by others
No other paper in the archive has been found to support or contradict these findings (compared with 13 related papers). Coverage is partial, so this is neither replication nor refutation.
Code
No repository by the authors found in the paper.
Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.