Mechanism Design for Double Auctions with Temporal Constraints

1 Introduction

A double auction market allows multiple buyers and sellers to trade commodities simultaneously. Most modern exchange markets, e.g. the New York Stock Exchange, use double auction mechanisms. In a typical double auction market, buyers submit bids (buy orders) to the auctioneer (the market maker) offering the highest prices they are willing to pay for a certain commodity, and sellers submit asks (sell orders) to set the lowest prices they can accept for selling the commodity. The auctioneer collects the orders and tries to match them using certain market clearing policies in order to make transactions.

Although price is the major concern of market clearing in most double auction markets, other factors, such as quantity, quality and temporal constraints, are equally important in some market situations. For instance, a futures contract normally specifics not only the price of the underlying commodity but also quantity, quality and settlement date. Nevertheless, most real-world exchange markets are purely pricedriven and most studies on double auctions are limited to a single-valued domain [Wilson, 1985; McAfee, 1992]. One reason is that some factors, e.g. quantity and quality, can be eliminated by standardising exchange commodities. However, those attributes with a continuous range or large number of varieties, are hard to standardise.

∗This research was supported by the Australian Research Council through Discovery Project DP0988750.

Laurent Perrussel 2 IRIT

University of Toulouse, France laurent.perrussel@univ-tlse1.fr

This paper considers an extension of the single-valued double auction model that allows traders to specify temporal constraints in their orders. Roughly speaking, an order is written in the form (p, t′ , t′′ ), where p stands for the order price and [t′ , t′′ ] represents the time period when the commodity can be exchanged (not for the order itself). In this extension, a bid and an ask is matchable if and only if the bid price is no lower than the ask price and the intersection of their time constraints is non-empty. We found that the market clearing problem under this extension can be transformed into a weighted bi-

niques in graph theory, such as augmentation, for the design and analysis of the mechanisms. We prove that an allocation for the double auction is efficient if and only if it corresponds to a maximum weighted bipartite matching of the graph encoding the incoming orders. Based on that, we develop an efficient and dominant-strategy incentive-compatible double auction mechanism, i.e. a VCG mechanism [Groves, 1973]. Remarkably, our payment can be implemented much faster than the classical VCG payment, known as Clarke pivot payment, while resulting in the same payments, because it directly uses the abridging and replacing paths generated during the allocation process rather than recall the allocation algorithm as Clarke pivot payment does.

It is worth mentioning that during the last decade many researchers started to look at the mechanism design problem for dynamic environments where traders are arriving and departing dynamically, referred to as online mechanism design [Parkes, 2007]. To model the dynamics, temporal information is also used. Although the meaning of the temporal information of a trader's type in the online setting is different from that in our setting, a trader's type is modelled in the same way in both settings [Blum et al., 2006; Bredin et al., 2007]. Therefore, the mechanism in our model also provides an optimal (offline) solution for a corresponding dynamic market. Such an optimal solution can be directly used for calculating the competitive ratio of an online marketclearing algorithm. Moreover, although orders arrive dynamically, the alternating paths are relatively stable and therefore can be used, for example, to identify potential good orders to find more efficient allocations in an online setting.

This paper is organised as follows. In Section 2 we briefly introduce our market model and related concepts. In Section 3, we introduce a graphic representation for market situations and transfer the market clearing problem into a weighted bipartite matching. In Section 4, we concentrate on the design of an allocation algorithm and a payment algorithm, and prove their desirable properties. We conclude in Section 5 with a brief discussion for the future work.

2 The Model

Consider a double auction market, in which a set B of buyers and a set S of sellers trade one commodity simultaneously. Buyers and sellers are traders. Let T = B ∪ S and assume that the traders are independent and B ∩ S = ∅. We also assume that each seller and each buyer supplies and demands a single unit of the commodity.

Each trader i ∈ T has a privately observed type θi = (vi, si, ei), where vi, si and ei are non-negative real numbers, vi is the trader's valuation of a single unit of the commodity, and si and ei are the starting point and the ending point of the time constraint [si, ei]. If trader i is a buyer, i obtains utility vi - p if i receives a unit of the commodity within the time interval [si, ei] and pays p; i obtains zero utility if i pays nothing and does not receive the commodity within the time period. Similarly, if i is a seller, i obtains utility p - vi if i successfully sells a unit of the commodity within the time period [si, ei] and receives payment p; i obtains zero utility if i fails to sell the commodity within the time period and no payment is made.

Let θ = (θi)i∈T denote the type profile where θi is the type of trader i. θ-i means the type profile of all traders except trader i. Note that we treat a type profile as a vector of types rather than a set of types. Let Θi be the set of all possible types of trader i, and we write Θ = (Θi)i∈T .

Since we will focus on direct-revelation mechanisms, we assume that traders directly report their types to the auctioneer as their orders [Myerson, 2008]. Traders do not necessarily truthfully report their types but no early-start and no lateend misreports are permitted. Formally, let θi = (vi, si, ei) be trader i's type and ˆ θi = ( ˆ vi, ˆ si, ˆ ei) be the trader's report. We assume that [ ˆ si, ˆ ei] ⊆ [si, ei]. The intuition behind the assumption is that no trader would report a temporal constraint that might give him negative utility. Let R(θi) be the set of all permitted reports from trader i given his type θi, R(Θi) = ⋃θi∈Θi R(θi) be the set of all possible reports from i, and R(Θ) = (R(Θi))i∈T .

Given traders' reports θ ∈ R(Θ), an ask θi = (vi, si, ei) (means i ∈ S) and a bid θj = (vj, sj, ej) (means i ∈ B) are matchable if and only if vi ≤ vj and [si, ei] ∩ [sj, ej] ̸= ∅. That is, the bid's valuation is no less than the ask's valuation, and the intersection of their time constraints is not empty.

An allocation policy π = (πi)i∈T is a function that assigns 0 or 1 to each trader, given traders' reports ˆ θ ∈ R(Θ). For a trader i, if πi( ˆ θ) = 1 we say i wins; otherwise i loses. An allocation determines whose order is granted for a transaction.

A payment policy x = (xi)i∈T is a function that assigns a real number to each trader given an input of traders' reports ˆ θ ∈ R(Θ), i.e. xi( ˆ θ) ∈ R for all i ∈ T .

Definition 1. A double auction mechanism on Θ is a pair

(π, x), where π is an allocation policy and x is a payment policy.

Following the standard definition, we say that an auction mechanism (π, x) is efficient if π maximizes

for any type profile θ = ((vi, si, ei))i∈T .

We say that an auction mechanism is dominant-strategy incentive-compatible, i.e. truthful, if for each trader, reporting his true type is his dominant strategy.

There are a number of alternatives to characterise truthfulness in an auction mechanism. We will use one of them in this paper based on [Parkes, 2007; Nisan, 2007]. To describe it, we need the following two auxiliary concepts [Parkes, 2007].

For each trader i, we define a partial order ⪯i on R(Θi):

i i i i We say that an allocation policy π is monotonic if, for each i ∈ T, πi( ˆ θi, ˆ θ-i) = 1 implies πi( ˆ θ′i , ˆ θ-i) = 1 whenever ˆ θi ⪯i ˆ θ′i .

Definition 2. Given a monotonic policy π and traders' reports ˆ θ ∈ R(Θ), the critical value of trader i of type θi = (vi, si, ei) is defined as

It is undefined if no such v′i exists.

Now we are ready to describe a characterisation of truthfulness, which will be used in Section 4. Theorem 1 is based on Theorem 9.36 in [Nisan, 2007] for a single-valued domain and on [Parkes, 2007] for a single-valued online domain. The proof is omitted here as it is similar to the above mentioned theorems.

Theorem 1. A double auction mechanism (π, x) is dominantstrategy incentive-compatible if and only if:

• π is monotonic.
• every winning seller (buyer) is paid (pays) his critical value, and the payment is 0 for losing traders.

3 Graph Representation

As assumed in the previous section, each trader has only one unit of a commodity to sell or buy. Transaction must be made in pairs: a seller can only sell his good to a unique buyer, assuming their orders are matchable. This means that to allocate the goods in a double auction is to find matchings between buy orders and sell orders. In such a case we can transform the allocation problem into a matching problem in graph theory. As a result an efficient allocation corresponds to a maximum-weighted bipartite matching. We will first review some concepts related to bipartite matching [West, 2000], encode incoming orders in a bipartite graph, and then show some special properties related to the encoding.

Definition 3. A graph G = (V, E) is a bipartite graph if the vertex set V consists of two disjoint subsets X and Y , and no edge has both end points in the same subset. For explicitness, we denote the graph as G = ((X, Y ), E).

Definition 4. Given a traders' report θ ∈ R(Θ), we call Gθ = ((Sθ , Bθ ), E) a bipartite graph generated from θ if

• Sθ = {θi : i ∈ S} and Bθ = {θi : i ∈ B},
• E = {(θi, θj) : θi and θj is matchable}.

Definition 5. Given a graph G, a matching M in G is a set of pair-wise non-adjacent edges, i.e. no two edges share a common vertex. The size of M is denoted by |M|. A vertex is matched if it is incident to an edge in the matching. Otherwise the vertex is free.

Given a matching M,

• an M-alternating path is a path in which the edges belong alternatively to M and not to M.
• anM-augmenting path is anM-alternating pathwhose endpoints are free.
• an M-abridging path is an M-alternating path whose first edge and last edge are in M.
• anM-replacement path is anM-alternating pathwhere one of the endpoints is free and one of the ending edges is inM.

A path is simple if it has no repeated vertices. In the rest of this paper, we will only consider simple paths.

Figure 1 shows an example of bipartite representation of eight different type reports. Lines and dashed lines indicate matched edges and free edges respectively, and dots and circles denote matched vertices and free vertices respectively. The value beside each vertex is its valuation. Temporal information is not shown in the graph. It is clear that path (3,10,2,9) is an augmenting path, path (2,10,4,7) is an abridging path, and path (2,10,4,7,5) is a replacement path.

Given a matching M, we can use an M-augmenting path p to augment M by changing all matched edges in p to be free and all the free edges to be matched. By contrast an Mabridging path can be used in the same way to abridge M. Consequently, |M| will increase (decrease) by one with one augmenting (abridging) process. An M-replacement path can be used to replace a bid or an ask in M without changing the status of the other vertices.

Definition 6. An allocation policy π is feasible if for any traders' reports θ ∈ R(Θ), there is a matching M in the bipartite graph generated from θ such that M exactly covers {θi : πi(θ) = 1}.

It follows that any matching in a bipartite graph generated from traders' reports uniquely determines a feasible allocation. In the rest of this paper, we will only consider feasible allocation policies.

Definition 7. Given bipartite graph Gθ, an edge e between θi = (vi, si, ei) and θj = (vj, sj, ej), where i ∈ S and j ∈ B, we define the weight of e as w(e) = vj - vi. For any set of edges E′ ⊆ E, the weight of E′ is defined as

The weight increase of an M-alternating path p is the total weight of free edges in p minus that of matched edges in p:

where P is the set of all edges in p.

If p is an M-augmenting, M-abridging, or M-replacement path, then Δ(p) is the net change in the weight of the matching after augmenting, abridging, or replacing by p: w(M ⊕ p) = w(M) + Δ(p), where M ⊕ p ≡ M ⊕ P , P is the set of all edges in p, and ⊕ is the symmetric difference operator on sets: A ⊕ B = (A ∪ B) \ (A ∩ B).

Lemma 1. Given Gθ, a matching M in Gθ, and an Malternating path p, Δ(p) is equal to

• the valuation of the bid minus that of the ask of the endpoints of p, if p is an augmenting path.
• the valuation of the ask minus that of the bid of the endpoints of p, if p is an abridging path.
• the valuation of the free (matched) endpoint minus that of the matched (free) endpoint of p when the endpoints are bids (asks), if p is a replacement path.

We will not provide the proof of Lemma 1 which follows the weight definition of the edges.

4 Efficient and Truthful Policy Design

In order to design a double auction that is both efficient and truthful, by Theorem 1, we need to find an efficient and monotonic allocation policy, and a payment policy that calculates the critical value of each winning trader. Inspired by the similarity between this allocation problem and the weighted matching in a bipartite graph, we first transform the model into a bipartite graph. Within this graph, we show how to efficiently use the well established methods from bipartite matching in the allocation policy, and how to calculate critical payment without running the allocation policy again.

4.1 Efficient &Monotonic Allocation Policy

With the above graph encoding of traders' reports, we designed an efficient allocation policy by adopting the maximum-weighted bipartite matching that constructs a maximum-weighted matching by beginning with the empty matching and repeatedly performing augmentations using augmenting paths of maximum weight increase until a maximum-weighted matching is achieved [Tarjan, 1983; Kozen, 1991]. The resulting allocation policy is called Maximum-weighted Bipartite Matching Allocation (MBM Allocation), which seeks an allocation that maximises social welfare of any reports θ, by first representing θ in a bipartite graph Gθ , and then applying modified maximum-weighted bipartite matching to get a maximum-weighted matching M which determines all winning reports.

We added a more detailed path selection rule in the maximum-weighted bipartite matching in order to achieve the monotonicity property. The rule is based on the order ≼p defined for augmenting paths. Let a sequence of vertices θ1 ◦ ... ◦ θn denote an augmenting path of length n, which starts from ask θ1 and ends in bid θn. We define ≼p on all augmenting paths based on their endpoints:

where ⩽s is the lexicographic order of two equal length sequences of real numbers: (r1 1 , ..., r1n ) ⩽s (r2 1 , ..., r2n ) iff ∃1≤j≤n(r1 j ≤ r2 j ∧ ∀1≤k<j (r1 k = r2 k )). We will use ≼p in MBM Allocation to distinguish augmenting paths that have the same weight increases.

Maximum-weighted Bipartite Matching Allocation:

Initialization:

• Encode reports θ in bipartite graph Gθ.
• Set the result matching M = ∅ for Gθ.

Recursion:

• AugPath = {p : Δ(p) > 0 and p is an Maugmenting path}.
• MaxAugP ath = arg maxp∈AugP ath Δ(p).
• If MaxAugPath = ∅, stop recursion.
• Otherwise, let ˆ p ∈ MaxAugPath s.t. p ≼p ˆ p for any p ∈ MaxAugPath, and M = M ⊕ ˆ p.

Output:

• All reports covered by M win and all the rest lose.

Theorem 2. Maximum-weighted Bipartite Matching Allocation is efficient.

We prove Theorem 2 in the Appendix. Here we show one essential lemma used in the proof. In the rest of this paper, π denotes MBM Allocation.

Lemma 2. Maximum-weighted Bipartite Matching Allocation is efficient if and only if the maximum-weighted bipartite matching maximizes the weight of the matching.

Proof. The weight of the matching is ∑πi(θ)=1∧i∈B vi - ∑πi(θ)=1∧i∈S vi, which is equal to (∑πi(θ)=1∧i∈B vi + ∑πi(θ)=0∧i∈S vi) - ∑i∈S vi . ∑i∈S vi is fixed, so if the weight of the matching is maximised, then ∑πi(θ)=1∧i∈B vi + ∑πi(θ)=0∧i∈S vi is also maximized, and vice versa.

Theorem 3. Maximum-weighted Bipartite Matching Allocation is monotonic.

Although we added a specific path selection rule based on ≼p to avoid randomisation of MBM Allocation in most cases, there is still one situation where ≼p cannot help. When two types are the same and two augmenting paths of maximum positive weight increase start from them and end in the same vertex, then ≼p cannot separate these two paths clearly, i.e. both of them have a chance of being selected but none of them are guaranteed. Thus we assume that all type reports of sellers (buyers) are different. Note that there might be more than one augmenting path with the same endpoints, but this does not affect the deterministic property of MBM Allocation. The proofs of all the theorems are given in the Appendix.

4.2 Truthful Payment Policy

We have found an efficient allocation policy, MBM Allocation, and proved its monotonicity property which is one of the two iff conditions to satisfy truthfulness. What is left is to calculate the critical value for each winning trader.

Obviously, it is not practical to calculate the critical value as it's defined in Definition 2. Here we propose another approach which is inspired by the reverse of MBM Allocation. A type θi is matched because there is an augmenting path of maximum positive weight increase ending with θi in some round of the matching procedure. Therefore, if a type does not satisfy the above condition, it will not be matched. This is the basis of our payment policy which is seeking the least violation condition for each winning type, i.e. the edge condition between winning and losing.

Given traders' reports θ, if πi(θ) = 1, the payment for trader i, xi(θ), is defined in terms of abridging and replacement paths starting from θi in the following, which is called Min-Max Payment (MM Payment). xi(θ) = 0 if πi(θ) = 0.

Min-Max Payment:

where

• D is a set of all abridging paths starting from θi,
• R is a set of all replacement paths starting from θi,
• and v(ending(p)) is the valuation of the ending vertex, the endpoint other than θi, of path p.

For each winning ask, MM Payment gives the minimum valuation such that, if the ask's valuation were greater than or equal to that minimum, it can be removed from the matching to (weakly) increase the weight of the matching, while for each winning bid, the payment is the corresponding maximum. The set D gives all possible ways to remove θi by abridging, while the set R gives all possible ways to substitute a free vertex for θi. Note that set D does not necessarily contain the path that was used to match θi, as the path can be changed with other augmentations after adding θi.

Theorem 4. Given bipartite graph Gθ and a winning type θi = (vi, si, ei) determined by MBM Allocation, Min-Max Payment xi(θ) is equal to critical value c(θi, θ-i).

Another appealing property of Min-Max payment is its independence from the allocation algorithm. We show that Min-Max payment results in the same payments as the most desirable VCG payment (Clarke pivot payment), but it does not require the recall of the allocation algorithm. Clarke pivot payment is defined as xi(θ) = V π (θ-i) - V π -i (θ), where V π (θ) is the social value given traders' report profile θ and the allocation policy π, and V π -i (θ) is the social value without counting trader i.

Lemma 3. Given traders' report θ and efficient and monotonic allocation policy π, for each trader i, Min-Max payment xMM i (θ) is equal to Clarke pivot payment xCi (θ).

Proof sketch. We need to prove that for each winning type θi if we remove θi from the maximum-weighted matching M of bipartite graph Gθ by using the path p that gives xMM i (θ), the result matching M ′ is also maximum-weighted in Gθ-i . By contradiction, assume that M ′ is not maximum-weighted, we will conclude either M is not maximum-weighted or path p contradicts the definition of Min-Max payment.

Corollary 1. Double auction mechanism (MBMAllocation,MMPayment) is efficient, dominantstrategy incentive-compatible and individual-rational, i.e. traders never get negative utility.

Figure 2 shows an example of the double auction we have defined, where the number beside each vertex is the valuation of the vertex and the value inside parentheses is the payment.

4.3 Computational Complexity

We further show that both our allocation policy and payment policy can be implemented in polynomial time and, more importantly, our payment can be implemented much faster than Clarke pivot payment.

Theorem 5. Let n be the number of traders' reports. MBM Allocation can be implemented in time O(n3 ), and Min-Max Payment can be implemented in time O(n3 ).

This result is significant because, to the best of our knowledge, the implementations of Clarke pivot payment cannot avoid the recall of the allocation algorithm [Nisan and Ronen, 1999; Sandholm, 2003]. In other words, for each winning report θi, π needs to search another allocation on the remaining reports θ-i. Therefore, it will take O(n) times of the allocation time in this model, i.e. O(n4 ) with MBM Allocation.

5 Conclusion

We have developed an efficient and truthful double auction mechanism (i.e. a VCG mechanism) in a model where each trader's type consists of a valuation of a commodity and a time period that constrains when the commodity can be exchanged. This mechanism is characterised by an allocation policy and a payment policy. By encoding the model in a bipartite graph, we efficiently adapted the maximum-weighted bipartite matching to get an efficient and monotonic allocation policy. We also developed a truthful payment policy that can be implemented faster than Clarke pivot payment while resulting in the same payments as Clarke pivot payment.

Myerson et al. [1983] proved that there is no efficient, incentive-compatible and individual-rational bilateral trade without outside subsidies, i.e. a market with our mechanism will run in deficit. To avoid this deficit, we need to compromise between efficiency and truthfulness. There are two possible remedies: either relaxing efficiency, or giving up incentive compatibility, as investigated by McAfee [1992] and Wurman et al. [1998] in single-valued domains. Finding how these compromises can lead to a realistic mechanism under our model is worth further investigation.

Appendix: Proofs of Theorems

Proof of Theorem 2: In order to prove Theorem 2, by Lemma 2, we shall prove that the maximum-weighted bipartite matching indeed gives a maximum-weighted matching. To do that, we need the two verified properties of the maximum-weighted bipartite matching given in Claim 1 and 2 [Tarjan, 1983]. This is one of the advantages we gained by encoding the model in a graph. We will skip the proofs of the following two claims.

Claim 1. Given graph G, let M be a matching of size k of maximum weight among all matchings of size k in G. If we augment M by an augmenting path of maximal weight increase, then we obtain a matching of size k + 1 of maximum weight among all matchings of size k + 1 in G.

Claim 2. The maximum-weighted bipartite matching will augment along augmenting paths of successively nonincreasing weight increase.

By Claim 1, the maximum-weighted bipartite matching will give a matching Mk of size k of maximum weight among all matchings of size k after k augmentations. By Claim 2, Mk is also maximumweighted among all matchings of size at most k if the weight increase at the k-th augmentation is positive. Therefore, the matching it gives until there is no augmenting path of positive weight increase is maximum-weighted among all matchings.

Proof of Theorem 3: By contradiction, without loss of generality, assume that πi(θ) = 1 and πi(θ′i, θ-i) = 0 for some bids θi ⪯i θ′i. Let θi be matched in round k of π(θ), i.e some augmenting path ending with θi is of maximal weight increase in round k. Since θ and θ′i are both not matched before round k, so the matchings are the same in both π(θ) and π(θ′i, θ-i) after any round < k. Let θm ◦ ... ◦ θi be the augmenting path of maximal weight increase selected in round k of π(θ). Since θi ⪯i θ′i, θm ◦ ... ◦ θ′i is an augmenting path in round k of π(θ′i, θ-i) and θm ◦ ... ◦ θi ≼p θm ◦ ... ◦ θ′i. Moreover, in round k, all augmenting paths in π(θ′i, θ-i), except those that end with θ′i, are also augmenting paths in π(θ). Thus, in round k of π(θ′i, θ-i), for any augmenting path p that does not end with θ′i, p ≼p θm ◦ ... ◦ θ′i, and all the rest end with θ′i. Therefore, an augmenting path ending with θ′i should be selected in round k of π(θ′i, θ-i), which contradicts the assumption.

Proof of Theorem 4: The proof needs the following two claims which can be found in [Kozen, 1991; Blum et al., 2006].

Claim 3. Given two matchings M and M ′ , M ⊕M ′ consists of a collection of vertex-disjoint alternating paths and even length cycles.

Claim 4. Given two matchings M and M ′ , a vertex v is an endpoint of a path in M ⊕M ′ if and only if it is matched in either M or M ′ but not both.

Now we are ready to prove Theorem 4. Without loss of generality, assume θi = (vi, si, ei) is a winning ask, and let xi = xi(θ) and ci = c(θi, θ-i). To prove xi = ci , by the definition of ci , we need to show that for any θ′i = (v′i, si, ei):

Let M be the matching of π(θ) and M ′ be that of π(θ′i, θ-i). We will prove these two conditions one by one blow.

Part I: By contradiction, assume that πi(θ′i, θ-i) = 1 and v′i > xi . Let AM (BM) be all the matched asks (bids) in M, and AM′ (BM′ ) be all the matched asks (bids) in M ′ . Since π is monotonic and M and M ′ are maximum-weighted, it follows that all matched asks in M except for θi must be matched in M ′ , i.e. AM \ {θi} ⊂ AM′ , and all the matched bids in M ′ must be matched in M, i.e. BM′ ⊆ BM. Thus inequalities |AM| - 1 < |AM′ | and |BM′ | ≤ |BM| hold. Moreover, |AM| = |BM| and |AM′ | = |BM′ |, so we get |M| = |M ′ |, BM = BM′ , and AM \{θi} = AM′ \{θ′i}. Therefore, by Claim 3 and 4, there is only one alternating path ponly = θi ◦ ... ◦ θ′i in M ⊕M ′ , and all the rest are cycles. If all vertices reachable from θi through M-abridging or M-replacement paths are also reachable from θ′i through M ′ - abridging or M ′ -replacement paths, then, since v′i > xi , there is at least one M ′ -abridging or M ′ -replacement path of positive weight increase by which we can remove θ′i to increase the weight of the matching, which contradicts the choice of M ′ .

Let us prove that the above reachability condition holds. (1). For any vertex v except for θi (θ′i) in ponly, the path between θi (θ′i) and v is either an abridging or a replacement path with respect to M (M ′ ). (2). Any vertex v′ not in ponly that is reachable from θi by an abridging or replacement path p is also reachable from θ′i through the same type of path p′ . Since p must be connected with ponly and for any edge e ∈ p and e ̸∈ ponly, if e ∈ M and e ̸∈ M ′ , there must be an even length cycle that contains e in M ⊕M ′ , and vice versa, i.e. if e connects vertices v1 and v2 in p, there is always a corresponding edge or path connecting v1 and v2 in p′ . For instance, Figure 3 shows one alternating path (a,b,c,d,e) and a cycle (h,i,j,k) of M ⊕M ′ : thin lines and thick lines belong to M and M ′ respectively, while the double line between f and g is in both matchings and dashed lines are free. It is easy to see that all vertices reachable from a through a M-augmenting or M-replacement path is also reachable from e by a corresponding path with respect to M ′ . Part II: To prove the second condition, we will prove πi(θ′i, θ-i) = 1 for any v′i < xi . By contradiction, assume that v′i < xi and πi(θ′i, θ-i) = 0. By Claim 4 there is a path pθi ∈ M ⊕M ′ starting from θi and ending with θn in either M or M ′ . Since xi ≤ vn by the definition of xi and v′i < xi as we assumed, we can substitute θ′i for θi in pθi to get an M ′ -alternating path pθ′i . If θn is matched inM, then pθ′i is anM ′ -augmenting path and by Lemma 1 Δ(pθ′i ) = vn - v′i > 0, which contradicts the choice of M ′ . Thus θn is a matched ask in M ′ , and pθ′i is an M ′ - replacement path. Since M ′ is a maximum-weighted, by Lemma 1 Δ(pθ′i ) = vn -v′i ≤ 0. Put all results together, we get contradiction vn ≤ v′i < xi ≤ vn.

Proof of Theorem 5: Bipartite graph representation of the reports takes at most n2 /4 time by checking each pair of ask and bid, so there will be at most m = n2 /4 edges. According to [Galil, 1986], finding an augmenting path of maximal weight increase can be solved by Dijkstra's algorithm taking O(m+n log n) time. There are at most n/2 rounds, so MBM Allocation can be implemented in time O(n3 ). For each winning type, MM Payment can be done by depth-first or breadth-first search which takes O(n +m) time. There are at most n winning types, so MM Payment can also be implemented in time O(n3 ).