{"paper_id":"2410.18751","title":"Double Auctions: Formalization and Automated Checkers","authors":["Mohit Garg","N. Raja","Suneel Sarswat","Abhishek Kr Singh"],"paper_date":"2024-10-24","paper_type":"theoretical","paper_url":"https://arxiv.org/pdf/2410.18751v1","page_url":"https://thequant.space/flowcharts/double-auctions-formalization-and-automated-checkers/","scores":{"empirical_rigor":7,"math_complexity":8,"quadrant":"Holy Grail"},"proposes":{"status":"available","statement":"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.","quote":"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.","summary":"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…","strategy":null},"assumptions":{"status":"available","items":[{"assumption":"Orders are represented as an admissible order‑domain (B, A) with unique ids and timestamps.","type":"model","stated":"explicit","quote":"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.","support":"full"},{"assumption":"All sets of bids and asks are finite; the Coq formalization uses lists to represent them.","type":"model","stated":"explicit","quote":"Our presentation leverages set notation for clarity, with the understanding that all sets discussed are ﬁnite. It is worth noting that our Coq formalization employs lists rather than sets.","support":"full"},{"assumption":"The input lists of bids and asks are sorted by decreasing competitiveness before matching.","type":"execution","stated":"explicit","quote":"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.","support":"full"}]},"datasets":{"status":"available","items":[{"name":"real market data from an exchange","provider":null,"kind":"order-book","access":"unknown","period":null,"universe":null,"quote":"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.","support":"full"}],"known":[],"sample":{"start":null,"end":null,"market":null,"asset_class":null,"frequency":null},"data_resolution":"l2-book"},"transaction_costs":{"status":"not_applicable","modeled":"n/a","headline_net_of_costs":null,"detail":null,"quote":null,"source":"front_matter","rule":"R3","candidates":{"front_matter":"n/a","evidence_card":"n/a","evidence_card_quoted":false},"meaning":"the paper reports no trading or execution result"},"results":{"status":"available","evaluation_type":"none","findings":[{"finding":"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.","kind":"theoretical","quote":"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 deﬁne total supply. Theorem Bound p M B A: admissible B A /\\ Matching M","support":"full"},{"finding":"The Fair procedure converts any matching into a fair matching without changing total trade volume (Theorem 2).","kind":"theoretical","quote":"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 ′).","support":"full"},{"finding":"The UM algorithm outputs a fair and optimal‑uniform matching, achieving the maximum possible volume among uniform matchings (Theorem 3).","kind":"theoretical","quote":"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).","support":"full"},{"finding":"A practical checker based on the verified program can automatically detect violations in an exchange’s matching algorithm when run on real market data.","kind":"performance","quote":"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.","support":"full"}],"reported_performance":null,"out_of_sample":{"method":"none","headline_out_of_sample":null}},"independent_evidence":{"status":"none_found","supports":[],"contradicts":[],"qualifies":[],"compared_with":13,"citations":{"cited_by_in_corpus":0,"by_independent_authors":0,"how_cited":{"used_as_baseline":0,"uses_method_or_data":0,"extends":0,"discusses_findings":0,"mentions":0,"unclassified":0},"independent_papers":[],"scope":"Citations between papers in this corpus only; citations from outside it are not counted."}},"implementation":{"status":"available","public":false,"code_url":null,"note":"No repository presented by the authors as their own was found in the paper. Absence here is not proof that no code exists."},"replication":{"status":"none_found","card":null,"note":"No replication of this paper has been run by thequant.space yet."},"extraction":{"text_source":"fulltext","model":"openai/gpt-oss-120b","version":2,"extracted_at":"2026-11-14T19:54:23Z"},"provenance":{"claims":"Everything here is what the authors state in the paper. Nothing was re-run or reproduced by the platform.","quotes":"Assumptions, datasets, cost detail and findings were extracted by a language model. Every quote is verbatim paper text. Where an item has `support`, \"full\" means every figure in it appears in the quoted sentences and \"partial\" means a figure is stated elsewhere in the paper; items with a figure found nowhere in the paper were discarded.","datasets_known":"datasets.known lists well-known vendors and public datasets by a stable id, found by a dictionary over the full text where the sentence says the data is used; it is independent of the model and covers only names in the dictionary.","flags":"transaction_costs.modeled, results.evaluation_type and results.out_of_sample.method are platform classifications (structured-decision models); see https://thequant.space/score-guide/#penalty-flags","comparisons":"supports / contradicts / qualifies are a language model's reading of two papers' quoted findings, restricted to closely related papers that share no author. They are pointers to read, not verified replications, and coverage is partial.","implementation":"code_url is a repository the paper itself presents as its own (rule-scored, ambiguous cases judged by a model), checked for liveness when it was recorded."},"docs":"https://thequant.space/agents/"}