The Exchange Problem

We now formally describe call auctions which are slight generalizations of the tasks introduced above.

We first briefly summarize the past results that were obtained for Problems 1 and 2. In the following, $n$ represents the number of orders in the input, i.e., $n=|A|+|B|$.

• $\mathrm{■}$

  First, in [12] it was shown that Problem 2 can be solved in $O(n\log n)$ time.

• $\mathrm{■}$

  Next, in [13] it was shown that Problem 1 can be solved in $O(n^2)$ time under the assumption that all orders have unit quantity. The authors mention that for multi-unit orders, one can simply break an order into multiple single-unit orders and use their algorithm. But, this would then result in overall complexity $O(Q^2)$, where $Q$ is the sum of the total demand and total supply, i.e., $Q=\mathrm{𝖵𝗈𝗅}(A)+\mathrm{𝖵𝗈𝗅}(B)$.

• $\mathrm{■}$

  This was improved in [10] where it was shown that Problem 1 can be solved in $O(n\log n)$ time for single-unit orders.

• $\mathrm{■}$

  Finally, inspired from previous works, in [9, 4] algorithms for both Problems 1 and 2 were presented that run in $O(n\log n)$ time each for arbitrary multi-unit orders. However, the authors did not analyze the time complexity of their algorithms, as they were more focused on formalizing these algorithms in a theorem prover. Their algorithms are general versions of the two algorithms we saw on page 1, where instead of sorting the lists of bids and asks by their prices, they are sorted by their competitiveness. After this modification, the first algorithm yields a maximum volume matching (note that Problem 1 requires the output matching to be also fair), whereas the second algorithm yields a uniform and fair matching with maximum volume (precisely solving Problem 2). For solving Problem 1, in addition to the above algorithm, they use an $O(n\log n)$ time algorithm that takes an arbitrary matching and outputs a fair matching of the same volume (this is always possible, see Theorem 3). It is straightforward to see that their algorithms indeed run in $O(n\log n)$ time.

Now we describe the results obtained in this work.

Call auctions are ubiquitous in financial markets. Major stock exchanges – including the New York Stock Exchange (NYSE), NASDAQ, and various global exchanges – often rely on uniform-price call auctions at market open and market close to establish a single clearing price. The main advantage is its simplicity and impartiality: every matched trader pays/receives the same price. Similar rules govern IPO allocations and some commodity trading platforms. Our work thus not only answers fundamental complexity questions – shedding light on the intrinsic difficulty of maximum-volume matching – but also yields a more efficient uniform-price procedure. In high-frequency or large-volume trading environments, any reduction in algorithmic overhead can be consequential.

Moreover, these results highlight an intellectually appealing paradox: while dynamic-price matching intrinsically requires sorting (or an equivalent $O(n\log n)$ process) under the comparison model, uniform-price matching admits a more efficient linear-time solution. This dichotomy had never been formally established, despite the centrality of call auctions in marketplace design.

This work offers a fundamental yet previously unexamined algorithmic advance for widely used exchange procedures, and we believe these insights will be of significant interest to researchers and practitioners in auction theory, matching markets, operations research, and financial engineering alike.

In [5, 6], continuous auctions were studied, that form a class of double auctions that complement the call auctions. The authors presented an algorithm that implements the continuous auction and runs in $O(n\log n)$ time for processing $n$ instructions (requests/orders). They also showed that their algorithm is time-optimal by reducing the task of sorting to continuous auctions.

Theorems 6 and 1 are proved in Section 2. Next, in Section 3, Theorem 7 is proved. Finally, we conclude the paper in Section 4 with some concluding remarks.

We now show a lower bound on the number of comparisons needed to solve the element distinctness problem on a small domain. This is a known result, but the proof that we could find has gaps, so we decided to include a complete proof.

In this subsection, we prove Theorem 9.

We describe the algorithm in [9, 4], which we denote by $\mathrm{𝖴𝖬}$. The transaction prices that are set by $\mathrm{𝖴𝖬}$ are not guaranteed to be uniform initially. After the matching is produced, a linear time algorithm is employed to put a uniform transaction price for all the transactions. For example, the maximum of the limit prices of the asks that participate in the output matching can be set as the transaction price of all the transactions in the output matching. Consequently, in the algorithms presented below, we will not worry about putting a transaction price in the transactions.

Given the list of bids B and asks A, $\mathrm{𝖴𝖬}$ first sorts the lists based on their respective competitiveness with the most competitive order on the top. It then invokes $\mathrm{𝖬𝖺𝗍𝖼𝗁}$ on the sorted lists $B$, $A$, and an empty matching $M$. Throughout the algorithm, $M$ can only grow, and at the end of the algorithm, $M$ will contain a desired uniform-price matching.

$\mathrm{𝖬𝖺𝗍𝖼𝗁}$ on $(B,A,M)$ picks the most competitive bid $b$ and the most competitive ask $a$ from $B$ and $A$ respectively, and checks if they are tradable. If they are not tradable, it returns $M$, and the algorithm terminates.

Otherwise, if they are tradable, it adds a transaction between $b$ and $a$ with transaction quantity $q=\min \{\mathrm{𝗊𝗍𝗒}(a),\mathrm{𝗊𝗍𝗒}(b)\}$ to $M$, reduces the quantity of $a$ and $b$ by $q$ in the lists $B$ and $A$. Note that at least one of $b$ or $a$ must be fully exhausted and removed completely from $B$ or $A$. It then recursively calls $\mathrm{𝖬𝖺𝗍𝖼𝗁}$ on $(B,A,M)$.

Clearly UM takes $O(n\log n)$ time, whereas $\mathrm{𝖬𝖺𝗍𝖼𝗁}$ takes $O(n)$ time, where $n=|A|+|B|$.

The algorithm can be simply described as first sorting the lists $B$ and $A$ based on competitiveness, and then doing a top-down greedy matching as long as the current bid and ask are tradable.

The following result states that the above result is correct.

We give a brief intuition of the proof of the above result. Let $M=\text{UM}(B,A)$. To see that $M$ is a fair matching is trivial, as it starts matching the bids and asks in the decreasing order of competitiveness. Similarly, it is easy to convince oneself that $M$ has a uniform price; any price between the limit prices of the last paired bid and ask is acceptable to all orders that participate in the matching; this again follows from the fact that matching is done top down in the order of decreasing competitiveness. Finally, to see that $M$ has maximum volume needs some work: fix an optimal matching $\mathrm{𝖮𝖯𝖳}$. We can gradually transform $\mathrm{𝖮𝖯𝖳}$ into $M$ without altering its volume. The illuminating case to consider is when the most competitive orders $b$ and $a$ are fully traded in $M$. Note that the transaction quantity between $b$ and $a$ in $M$ is $q=\min \{\mathrm{𝗊𝗍𝗒}(b),\mathrm{𝗊𝗍𝗒}(a)\}$. Since $\mathrm{𝖮𝖯𝖳}$ is fair, $b$ and $a$ must also be fully traded in $\mathrm{𝖮𝖯𝖳}$. In particular $\mathrm{𝖰𝗍𝗒}(b,\mathrm{𝖮𝖯𝖳})\ge q$ and $\mathrm{𝖰𝗍𝗒}(a,\mathrm{𝖮𝖯𝖳})\ge q$. Now, if the transaction quantity between $b$ and $a$ in $\mathrm{𝖮𝖯𝖳}$ is strictly less than $q$, then $\mathrm{𝖮𝖯𝖳}$ can be modified by making the transaction quantity between $b$ and $a$ equal to $q$. Let us say $b$ is matched with $a^{\prime }$ and $a$ is matched with $b^{\prime }$ in $\mathrm{𝖮𝖯𝖳}$, then we can reduce the quantity of these transactions by a unit quantity, increase the transaction quantity between $b$ and $a$ by unit quantity, and increase the transaction quantity between $b^{\prime }$ and $a^{\prime }$ by a unit quantity (this is possible since every matched bid is tradable with every matched ask as all the transaction prices are identical). Note that in the end, $\mathrm{𝖵𝗈𝗅}(\mathrm{𝖮𝖯𝖳})$ remains the same. We can repeat this surgery over and over again till the matched quantity between $b$ and $a$ in $\mathrm{𝖮𝖯𝖳}$ becomes equal to $q$. We remove this transaction from both $\mathrm{𝖮𝖯𝖳}$ and $M$ and apply the same argument repeatedly till $M=\mathrm{𝖮𝖯𝖳}$.

Before we proceed to describe our improved algorithm, we establish certain lemmas and subroutines that will be useful in describing our algorithm and proving its correctness.

We first need some definitions.

Observe the following fact about the previous algorithm UM.

This is trivial to see when all orders in $B\cup A$ have unit quantities since UM matches the $i^{\text{th}}$ most competitive bid with the $i^{\text{th}}$ most competitive ask for all $i\le \mathrm{𝖵𝗈𝗅}(M)$, where $M=\text{UM}(B,A)$, and the $\mathrm{𝖱𝖺𝗇𝗀𝖾}$ of the $i^{\text{th}}$ most competitive bid (and ask) is the singleton $\{i\}$. To see why the general statement is true observe that whenever $\text{Match}(\widehat{B},\widehat{A},\widehat{M})$ is called it potentially matches the most competitive bid $b\in \widehat{B}$ with the most competitive ask $a\in \widehat{A}$, and $\mathrm{𝖵𝗈𝗅}(\widehat{M})+1\in {\mathrm{𝖱𝖺𝗇𝗀𝖾}}_B(b)\cap {\mathrm{𝖱𝖺𝗇𝗀𝖾}}_A(a)$.

Our main workhorse is the $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍}$ subroutine which works in linear time by employing the classical algorithm of [1]. Given a list of orders (all bids or all asks) $\mathrm{\Omega }$ and a number $t\le |\mathrm{\Omega }|$, $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍}(\mathrm{\Omega },t)$ outputs the $t^{\text{th}}$ most competitive order in $\mathrm{\Omega }$.

We also use a weighted version of $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍}$ called $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍𝖰}$ which takes as input $\mathrm{\Omega }$ and a quantity $q\le \mathrm{𝖵𝗈𝗅}(\mathrm{\Omega })$ and outputs the unique element $\omega \in \mathrm{\Omega }$ such that $q\in {\mathrm{𝖱𝖺𝗇𝗀𝖾}}_{\mathrm{\Omega }}(\omega )$. $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍𝖰}$ can be implemented in linear time using the $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍}$ algorithm as subroutine as described below.

We get the following recurrence relationship on the running time of $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍𝖰}$: $T(n)\le T(\lceil n/2\rceil +1)+O(n)$, which yields $T(n)=O(n)$, where $n=|\mathrm{\Omega }|$.

The next subroutine we consider is $\mathrm{𝖲𝗉𝗅𝗂𝗍}(\mathrm{\Omega },\omega )$, which partitions $\mathrm{\Omega }$ into two parts consisting of orders in $\mathrm{\Omega }$ which are at least as competitive as $\omega$, and orders which are strictly less competitive than $\omega$. We now want to define a subroutine $\mathrm{𝖲𝗉𝗅𝗂𝗍𝖰}$ which takes as input a list of orders $\mathrm{\Omega }$ and a quantity $q\le \mathrm{𝖵𝗈𝗅}(\mathrm{\Omega })$. We want to “partition” $\mathrm{\Omega }$ into two parts so that the volume of the more competitive part is precisely $q$. For this, we first find the element $\omega \in \mathrm{\Omega }$ such that $q\in {\mathrm{𝖱𝖺𝗇𝗀𝖾}}_{\mathrm{\Omega }}(\omega )$. We then $\mathrm{𝖲𝗉𝗅𝗂𝗍}(\mathrm{\Omega },\omega )$ to obtain $({\mathrm{\Omega }}_{⪰},{\mathrm{\Omega }}_{\prec })$. If $\mathrm{𝖵𝗈𝗅}({\mathrm{\Omega }}_{⪰})=q$, then we are immediately done. Else $\mathrm{𝖵𝗈𝗅}({\mathrm{\Omega }}_{⪰})>q$ and . Thus we must break a part of $\omega$ and put it in ${\mathrm{\Omega }}_{\prec }$ so that $\mathrm{𝖵𝗈𝗅}({\mathrm{\Omega }}_{⪰})$ is precisely $q$. This can be achieved in linear time by the following subroutine $\mathrm{𝖲𝗉𝗅𝗂𝗍𝖰}(\mathrm{\Omega },q)$. Apart from outputting the partition as described above, it also returns the order $\omega$. $\mathrm{𝖲𝗉𝗅𝗂𝗍𝖰}$ clearly runs in linear time.

We are now ready to state another lemma regarding the previous algorithm UM.

The above statement is easy to check. Since $\widehat{b}$ gets completely traded in $M$, all orders in $B_{⪰}$ must get traded with the most competitive asks in $A$ whose total quantity is $q$, which is precisely the set $A_{⪰}$. Let $M_1$ consist of the transactions produced while matching orders in $B_{⪰}$. Then $M_2$ will be obtained by running the UM on $(B_{\prec },A_{⪯})$.

Note that a symmetric statement holds where we start with the assumption that the $t^{\text{th}}$ most competitive ask gets traded in $M$.

We are now ready to describe our improved algorithm.

Our improved algorithm $\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}$ takes as input a list of bids $B$ and a list of asks $A$. It immediately invokes ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ on $(B,A,M=\mathrm{\varnothing })$. $M$ will grow into the final matching output by the algorithm.

There are two main subroutines of our algorithm ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ and ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖺𝗌𝗄}}$ which are symmetric in nature and they alternatively call each other. This is done to ensure that in two successive return calls, the problem size, i.e., $|B|+|A|$, reduces by a factor of two, as ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ halves the number of the bids, whereas ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖺𝗌𝗄}}$ halves the number of the asks. So just understanding ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ will be sufficient for understanding our algorithm.

On receiving $(B,A,M)$, ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ first finds the median bid $b$ by invoking $\mathrm{𝖲𝖾𝗅𝖾𝖼𝗍}(B,\lceil \frac{B}{2}\rceil )$. It then splits $B$ into two halves $(B_{⪰},B_{\prec })$ based on the median bid $b$ by invoking $\mathrm{𝖲𝗉𝗅𝗂𝗍}(B,b)$. Let $q=\mathrm{𝖵𝗈𝗅}(B_{⪰})$. It then finds the element $a\in A$ such that $q\in {\mathrm{𝖱𝖺𝗇𝗀𝖾}}_A(a)$ by calling $\text{SplitQ}(A,q)$ and splits $A$ into its most competitive and least competitive asks $(A_{⪰},A_{⪯})$ such that $\mathrm{𝖵𝗈𝗅}(A_{⪰})=q$ by applying $\mathrm{𝖲𝗉𝗅𝗂𝗍𝖰}(A,q)$.

After that, the algorithm checks if $b$ and $a$ are tradable. Two cases arise. If $b$ and $a$ are tradable, then every order in $B_{⪰}$ and $A_{⪰}$ are tradable and they will exhaustively be matched to each other to produce a matching of volume $q$ in linear time using the Match subroutine. ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ adds this $\mathrm{𝖵𝗈𝗅}$ $q$ matching to $M$ and recursively calls ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖺𝗌𝗄}}$ on $(B_{\prec },A_{⪯},M)$. Intuitively, the previous algorithm would also match all orders in $B_{⪰}$ and $A_{⪰}$ exhaustively to each other to produce a matching of volume $q$ and proceed to matching orders in $B_{\prec }$ and $A_{⪯}$.

In the case $b$ and $a$ are not tradable, then ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$ discards $(B_{\prec },A_{⪯})$ and calls ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖺𝗌𝗄}}$ on $(B_{⪰},A_{⪰},M)$. Intuitively, the previous algorithm will halt (i.e., produce its last transaction) before it even comes down to examining orders in $B_{⪰}$ and $A_{⪰}$.

${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖺𝗌𝗄}}$ is similar to ${\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}}_{\mathrm{𝖻𝗂𝖽}}$. Observe that, as opposed to the earlier $O(n\log n)$-time algorithm, the Match subroutine is not being provided sorted lists of bids and asks, but instead it is given a list of bids and asks of equal volume where each bid and each ask are tradable, and consequently it produces an exhaustive matching. Having described our algorithm $\mathrm{𝖴𝗇𝗂𝖿𝗈𝗋𝗆}$, we now turn to prove its correctness. The main theorem that establishes the correctness is as follows.

Once we prove the above theorem, the correctness follows from the following proposition and Theorem 13.

The proposition is obvious: the volumes of $M_1$ and $M_2$ must be the same from the condition above. Also, since the same orders participate in both $M_1$ and $M_2$, transactions in $M_2$ can be assigned the same uniform price that is in $M_1$. Finally, fairness also follows immediately since the more competitive orders are fully traded in $M_1$, they must be fully traded in $M_2$ as $\mathrm{𝖰𝗍𝗒}(w,M_1)=\mathrm{𝖰𝗍𝗒}(w,M_2)$ for all orders $w$.

We now turn to proving Theorem 17.