Double Auctions: Formalization and Automated Checkers

ArXiv ID: 2410.18751 “View on arXiv”

Authors: Unknown

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.

Keywords: Double Auctions, Market Microstructure, Formal Verification, Matching Algorithms, Market Design, Multi-Asset

Complexity vs Empirical Score

• Math Complexity: 8.0/10
• Empirical Rigor: 7.0/10
• Quadrant: Holy Grail
• Why: 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.

  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"]