Budget-feasible Procurement Mechanisms in Two-sided Markets

1 Introduction

For one-sided markets, either with a single-seller and multiple buyers or with a single-buyer and multiple sellers, much research effort in the past decades has been invested to design auction mechanisms to regulate the trading ([Vickrey, 1961; Clarke, 1971; Groves, 1973]). While for two-sided markets with both buyers and sellers being strategic, most of the works fall into the research line of double auction mechanism design ([Myerson and Satterthwaite, 1983; McAfee, 1992] ), which assumes that the sellers can bid their costs and the buyers can bid their values for the items and the mechanism needs to determine the trading/payment rules that guarantee some desirable properties, such as truthfulness of the bidding behavior. In such scenarios, buyers' behavior and sellers' behavior are somehow symmetric, one with item value and one with item cost. Accordingly, the seminal work in [McAfee, 1992] provides algorithms to match buyers to sellers by natural ordering of their values until a breakeven index; [D¨utting et al., 2014] further consider the situation that there are restrictions on which buyers and sellers can trade with one another. [Colini-Baldeschi et al., 2016] and [Segal-Halevi et al., 2016] extend their work by designing mechanisms satisfying strong budget balance, i.e., the amount of money paid by the buyers is totally and exclusively transferred to the sellers.

∗Corresponding author

These works, however, did not provide truthful mechanisms for a natural procurement scenario in two-sided markets where multiple strategic buyers come into the market with their private budgets and want to procure as much value of items as possible from the sellers with private costs. A mechanism in such scenario needs to guarantee that the total payment paid by each buyer does not exceed its own budget. In such scenario, the behaviours of buyers and sellers are asymmetric, and the main challenge in designing such mechanisms differs much from the traditional double auctions that does not consider payment budgets. A natural question then arises in such scenarios.

Can we design an efficient mechanism in two-sided markets that stimulates the desired economic interactions among buyers and sellers without any buyer's payment exceeding its budget?

In the procurement mechanism design problem above, multiple buyers compete with each other for procuring more value of items with diverse procurement budgets/abilities and the sellers compete with each other to sell their items with more payment rewarded. The designed mechanism should determine an allocation and a payment scheme to guarantee various desired theoretical properties like, individual rationality that the payment to each seller covers at least (but not necessarily equals) its private cost, budget feasibility that the total payment of each buyer does not exceed its budget, sellers' truthfulness that no sellers have incentive to bid a false cost, buyers' truthfulness that no buyers have incentive to claim a false budget, and approximation that the total value procured by buyers is close to the optimal solution that would be achievable had the mechanism known the bidders' true private information.

Note that the problem above falls into the field of budgetfeasible procurement mechanism design, in which the first budget-feasible truthful mechanism in single-buyer procurement auctions is developed in [Singer, 2010]. As shown in their work, the design challenge differs much from the traditional mechanisms since the budget constraints apply not to the costs but to the payments the mechanism uses to support truthfulness; Furthermore, the traditional VCG mechanism also fails due to the fact that computing the required optimal allocation is NP-hard, and even if computed, it may result in infinite/unbounded total payment. They successfully designed a novel mechanism that achieves the truthfulness (only sellers'), budget feasibility and constant approximation on maximizing the total procured value of the single-buyer. Related work. After the seminal work of [Singer, 2010], many research efforts have been invested to design budgetfeasible mechanisms. [Chen et al., 2011] further developed improved mechanisms with better approximation ratio. [Dobzinski et al., 2011] and [Bei et al., 2012] further consider general value functions where the buyer has a subadditive value function over procured items. While many works focus on the offline problem, [Badanidiyuru et al., 2012] and [Singer and Mittal, 2011] investigate the online procurement problem where agents arrive in sequential order and a budget feasible mechanism must make an irrevocable decision whether or not to procure the service as the agents arrive.

Note that the works above consider the one-sided auctions where there are multiple sellers with public values but private costs, and did not address the truthfulness of the singlebuyer. A series of works then investigate a reversed scenario with multiple budgeted buyers but a single seller with public cost, where buyers can bid their budgets and values over the item of the single-seller. However, for such budgeted agent setting, the traditional measure, the sum of buyers' procured values, is known to be very poorly approximatable under budget constraints, even when budgets are known to the auctioneer. To overcome this impossibility, [Dobzinski and Leme, 2014] propose a new assumption/measure by capping the procured value of a buyer by its budget (which is the minimum between its procured value and its budget), which admits incentive compatible mechanisms with logarithmic approximation to the sum of buyers' procured values, and even improved mechanisms with constant approximation ([Lu and Xiao, 2015]). Our work also considers budget-feasible auctions with multiple buyers, but in contrast, we address two-sided auctions with multiple sellers, and meanwhile the values of items are public while the budgets from buyers and costs from sellers are private. We want to design truthful mechanisms that could achieve constant approximation without resorting to the assumption of capped procured value of buyers. Our mechanism requires the buyers to submit their full amount of claimed budgets as deposit to verify the overbidding case, following the design of mechanisms with verification ([Penna and Ventre, 2014; Ferraioli et al., 2016]). Since no prior works have addressed the truthfulness on both sides simultaneously, our work takes a step forward towards designing mechanisms with truthfulness on both sides in two-sided auctions with budgets.

[Hirai and Sato, 2017] also study two-sided markets with buyers' budget constraints, but they only address buyers' truthfulness while sellers are assumed to be truthful, and meanwhile it considers divisible items. This paper conducts the first work on the budget-feasible mechanism design in two-sided auctions considering the truthfulness of the sellers and buyers simultaneously.

Our Results. In this work, we address the budget-feasible procurement problem in two-sided markets. We investigate the model where items have heterogeneous values. Our main contribution is a randomized mechanism that guarantees desired theoretical properties like the budget feasibility, individual rationality, truthfulness both on the sellers' side and the buyers' side, and constant approximation to the optimal total procured value of buyers.

2 Preliminaries

2.1 Two-sidedMarket Model

We consider a two-sided procurement market with a set of n sellers S = {s1, s2, ..., sn} and a set of m buyers A = {a1, a2, ..., am}. Each buyer ai has a budget Bi ∈ R+, which is privately known by the buyer itself. Each seller sj has an item with value vj ∈ R+ and cost cj ∈ R+ to sell. While the item's cost cj is privately known by the seller itself, we assume that the item's value vj is common knowledge, following the assumption in the traditional reverse-auctions ([Klemperer, 1999; Singer, 2010]). Let B = {B1,B2, ...,Bm} denote the budgets of the buyers, C = {c1, c2, ..., cn} be the costs of the sellers and V = {v1, v2, ..., vn} be the values of the items.

This paper addresses procurement mechanisms to model buyer-centric scenarios, e.g. crowdsoucing, microtask crowdsourcing ([Anari et al., 2014; Gao et al., 2015]). In such applications, the announced tasks usually cannot be finished by a single seller/worker and buyers can afford the costs of single-sellers. We assume that all buyers have a basic procurement ability Bi ≥ Bmin for all ai (where Bmin is a known minimum threshold of budget) and no items exceed any buyer's procurement ability, i.e., cj ≤ Bmin for all sj.

We focus on the strategic setting, in which the participants (buyers and sellers) may act strategically to maximize its own utility. Each seller bids a cost bj of its item that may be different from the real cost cj in order to maximize its own utility (or benefit). Let b = {b1, b2, ..., bn} denote all the bids of the sellers. Each buyer ai claims a budget ˆBi that may be different from its true budget Bi.

2.2 The Mechanism

Formally, a mechanism M = (f, P ) consists of an allocation function f specifying which buyer buys which seller's item and a payment function P specifying how much is paid. The allocation function f maps a set of bids to a set of winning sellers Sw ⊆ S. We use xij = {0, 1} to indicate whether the item of seller sj is allocated/sold to buyer ai and use pij to denote the payment paid by buyer ai to seller sj.

The utility of seller sj is pijxij-cj , the difference between the payment it receives and its true cost if sj is allocated (sj ∈ Sw), and 0 otherwise. The utility of buyer ai is ∑j∈Sw vjxij , the total value it procures from the market.

In this work, we design truthful budget-feasible procurement mechanisms in two-sided markets. The designed mechanism should guarantee the following properties,

Individual rationality. The utility of each winning seller sj is non-negative, i.e., ∑1≤i≤m pijxij-cj ≥ 0 for all sj ∈ Sw. Sellers' truthfulness. Each seller sj would truthfully bid its cost, i.e., its utility is maximized when it bids bj = cj.

Buyers' truthfulness. Each buyer would truthfully bid its budget, i.e., its utility is maximized when it bids ˆBi = Bi.

Following the design of mechanisms with verification, we require buyers to submit their full amount of claimed budgets as deposit at the beginning of the auction to verify the overbidding case. Since overbidding can be detected and forbidden 1 , we concentrate on showing buyers would not underbid.

Budget feasibility. The designed mechanism should meet the budget feasibility for all buyers. That is, the total payment of each buyer ai does not exceed its budget, i.e., ∑1≤j≤n pijxij ≤ Bi.

Approximation. The auctioneer wants to maximize the total value of buyers procured from the market, V (S,B) = ∑1≤i≤n ∑1≤j≤m vjxij. To measure the performance of the mechanism, we compare its solution with the optimal solution that is obtainable in the full-information scenario where all true private information is known. A mechanism is O(g(n, m))-approximation if the ratio between the optimal solution and the mechanism is O(g(n, m)).

In this paper, we consider agents' truthfulness in expectation and design randomized mechanisms to maximize the expected total procured value of buyers.

3 MechanismDesign

The proposed mechanism needs to guarantee the truthfulness of sellers in bidding their costs and the truthfulness of buyers in claiming their budgets. Since sellers' item values are heterogeneous, an efficient mechanism needs to adopt different payment to sellers. Moreover, buyers have heterogeneous budgets, and therefore diverse abilities to procure items from the sellers, which adds another challenge to design the mechanism.

To address the challenge above, we design a randomized mechanism, called GRM, by randomly combining two sub-mechanisms. In general, we try to divide the sellers into two groups and conquer them separately in two submechanisms. That is, sellers with small bids (no greater than Bmin 3 ) and sellers with large bids (greater than Bmin 3 ). The first sub-mechanism, namely, UNIFORMMECH or UM for short, tackles the sellers with small bids. While for the sellers with large bids, we design the second mechanism, namely, GREEDYMECH, that uses a greedy allocation. In detail, GRM returns the results of Mechanism UM with probability 7 12 and returns the results of GREEDYMECH with probability 5 12 . Note that to slightly improve the performance, we run GREEDYMECH over the original input with all n sellers.

The high level idea of Mechanism UM is as follows. Since sellers have small bids, we take into account a part of each buyer's budget, namely, Bi 3 , and just use the virtual total budget ∑1≤m Bi 3 . Then, we choose the sellers in the order of non-decreasing value bj vj successively until a certain threshold is violated. Once the winning sellers are determined, we introduce a notion based on the obtained threshold, namely, the quota of each buyer, to measure the diverse procurement

1 We do not allow buyers to borrow money from outside, and if a buyer borrows the money before it enters the market, then we consider this borrowed amount within its true budget. A buyer can be detected and punished with infinite cost when it overbids.

Mechanism 1 General Random Mechanism GRM(B, b, V)

• 1: Let ˜ S = {sj : bj ≤ Bmin 3 } be the sellers with bids no greater than Bmin 3 , and denote by ˜b the corresponding bids of the sellers and denote by ˜ V the values of their items.
• 2: With probability 7 12 , return UNIFORMMECH(B,˜b, ˜ V )
• 3: With probability 5 12 , return GREEDYMECH(B, b, V )

ability of buyers. After determining the winning sellers and the quota of each buyer, we generate a virtual allocation by assigning the items of winning sellers virtually to buyers, in which an item may be assigned to different buyers. Last, we design a random allocation rule and generate a real allocation based on the virtual allocation.

In detail, it works as follows. Since the sellers have bids no greater than Bmin 3 , we first use each buyer's one-third budget Bi 3 as a virtual budget, and denote by Bt = ∑1≤m Bi 3 the sum of each buyer's virtual budgets. Before selecting winning sellers, we sort the sellers with small bids in the order of non-decreasing price-per-value bj vj . We test each seller successively. If the j-th seller sj satisfies bj vj ≤ Bt ∑h≤j vh , then sj will be selected as a winning seller. Assume that sk is the last winning seller, then we have bk+1 vk+1 > Bt ∑h≤k+1 vh . Accordingly, we define q = min{ Bt ∑j≤k vj , bk+1 vk+1 } to be the virtual critical threshold. Then, in the virtual allocation, buyer ai is allowed to procure at most wi = Bi 3q total value , called quota of buyer ai, and the items of winning sellers will be allocated in non-decreasing order of value bj vj to the buyers according to their increasing index. According to such an allocation rule, buyers with smaller index would have higher priority to consume their quota. We denote by V (Bi, B-i, b) the amount of value buyer ai procured in the virtual allocation, which will be written as V (Bi) for short if no ambiguity arises. Note that ∑1≤i≤m wi = Bt q ≥ ∑1≤j≤k vj, which implies that the total value of items to be allocated is not greater than the total quota of buyers and thus some buyer with larger index may be allocated with V (Bi) < wi or even V (Bi) = 0.

Next, we generate a real allocation by designing a random allocation rule so that the expected total value procured by buyer ai is exactly equal to V (Bi), the total value obtained in the virtual allocation. The detailed implementation is as follows. We allocate the winning sellers in the increasing order of price-per-value to the buyers according to their increasing index. Knowing that the first i buyers can procure at most ∑i′≤i wi′ value, after allocating the first ∑j ′≤j-1 vj ′ virtual sellers, we check whether assigning all vj value of seller sj would exceed the limit ∑i′≤i wi′ . If it does not exceed the limit, we allocate seller sj to buyer ai with probability min{∑j′≤j vj′-∑i′≤i-1 wi′ ,vj} vj . If it exceeds the limit, we allocate seller sj to buyer ai with probability min{∑i′≤i wi′-∑j′≤j-1 vj′ ,wi} . This would use up the quota

Mechanism 2 Mechanism UNIFORMMECH(B,b,V)

Input: B, b with all bj ≤ Bmin 3 , V .

• 1: Let Bt = ∑i≤m Bi 3 .
• 2: Sort sellers in the order of non-decreasing value bj vj .
• 3: // Selecting winning sellers.
• 4: j ← 1
• 5: while bj vj ≤ Bt ∑j′≤j vj′ do
• 6: j ← j + 1, Sw ← Sw ∪ {sj}
• 7: Let sk be the last winning seller and q = min{ Bt ∑j≤k vj , bk+1 vk+1 }.
• 8: // Allocation and Payment scheme
• 9: Let the quota wi = Bi 3q .
• 10: Generate a virtual allocation by allocating the items from the first k sellers to buyers according to their increasing index without exceeding each buyer's quota. Accordingly, each buyer ai is allocated with at most Bi 3q value of items.
• 11: Set i = 1, j = 1 and generate a real allocation as follows.
• 12: while i ≤ m, j ≤ k do
• 13: if ∑j ′≤j vj ′ ≤ ∑i′≤i Ni′ then
• 14: with probability min{∑j′≤j vj′-∑i′≤i-1 wi′ ,vj} vj : allocate seller sj to buyer ai. 15: j ← j +1
• 16: else
• 17: with probability min{∑i′≤i wi′ -∑j′≤j-1 vj′ ,wi} vj : allocate seller sj to buyer ai.
• 18: i ← i + 1
• 19: The buyer allocated with seller sj pays min{vj · q, Bmin 3 }.

of buyer ai and we consider the next buyer ai+1. Moreover, the buyer who gets the allocation rewards seller sj with payment min{vj · q, Bmin 3 }, which is the key to guarantee the truthfulness. The process repeats until all the first k items are allocated. Note that the virtual budget is set with one-third of the original budget, which guarantees that even if a buyer is allocated with a seller exceeding the limit twice (when generating the real allocation), the buyer can use the remaining two-thirds of its budget to pay the seller without violating the budget feasibility.

Now, we design the second mechanism GREEDYMECH, which intends to avoid missing the possible high value items of sellers with large bids. Any seller who bids bj > Bmin would not be allocated. W.l.o.g., we assume bj ≤ Bmin for all sj, which is consistent with the assumption cj ≤ Bmin. The high level idea of GREEDYMECH is simple, i.e., select the high-value sellers and pay each selected seller a maximum payment Bmin (since all bj ≤ Bmin). In detail, it computes the total number ∑1≤i≤m⌊ Bi Bmin ⌋ of items that can be procured with payment Bmin. Then, it allocates the top K = min{∑1≤i≤m⌊ Bi Bmin ⌋, n} highest-value sellers to the buyers according to their increasing index, and accordingly gets a final allocation.

Mechanism 3 Mechanism GREEDYMECH(B, b, V)

• 1: Sort the sellers by non-increasing item values.
• 2: K ←min{∑1≤i≤m⌊ Bi Bmin ⌋, n}
• 3: Allocate the first K sellers in highest-value-first order to the buyers with increasing index, where buyer ai buys ⌊ Bi Bmin ⌋ items and each seller gets payment Bmin.

Finally, we have our general mechanism GRM by combining UNIFORMMECH and GREEDYMECH randomly.

4 Theoretical Guarantees of Performance

In this section, we analyze the performance of the mechanism. Firstly, we have the following basic property of Mechanism UM according to its allocation rule.

4.1 Budget-Feasibility, Individual-Rationality

First we show the budget feasibility. For GREEDYMECH, it is easy to see the budget feasibility. For UM, buyer ai pays min{vj · q, Bmin 3 } ≤ vj · q when a seller with value vj is allocated to it. Since the total value procured by buyer ai is at most Bi 3q , its total payment is at most Bi 3q ·q ≤ Bi 3 in the virtual allocation generated by Mechanism UM. Furthermore, when the real allocation is generated in the random allocation, buyer ai gets at most two extra sellers randomly allocated to it (respectively when the limit ∑i′≤i-1 wi′ and ∑i′≤i wi′ are exceeded). Thus, it only needs to reward at most two extra sellers (which have small bids and each should be paid at most Bmin 3 ) using the remaining two-third of its budget. Thus, the budget feasibility holds. Therefore, Mechanism GRM is budget feasible.

Next, we prove the individual rationality. For GREEDYMECH, it is easy to see its individual rationality since the payment for each winning seller is Bmin > bj. For Mechanism UM, if seller sj is not selected, its utility is zero. If seller sj is selected, its utility is pj - cj. Since sj is a winning seller, we have bj vj ≤ bk vk ≤ Bt ∑j≤k vj and bj vj ≤ bk+1 vk+1 .

Thus, bj vj ≤ q. Moreover, the seller has small bid bj ≤ Bmin 3 . Therefore pj = min{vj · q, Bmin 3 } ≥ bj. Thus, its utility is non-negative, implying individual rationality.

4.2 Sellers' Truthfulness

We will show that GRM is truthful. Since sellers with cost ci ≥ Bmin 3 would not underbid to participate in mechanism UM, it suffices to prove that the two sub-mechanisms are truthful, respectively. First, we analyze GREEDYMECH first. Clearly, each seller cannot get more payment by false bidding because we select sellers based on highest-value-first rule and the payment for each winning seller is constant Bmin. Thus, GREEDYMECH satisfies sellers' truthfulness.

Next we analyze the sellers' truthfulness in UM. We first introduce a theorem for verifying the truthfulness in the single parameter domain.

Theorem 1. (Monotone theorem, [Myerson, 1981]) In single parameter domains, if each agent's utility follows the form uj(bj) = pj - cj , a mechanism M = (f, p) is truthful iff:

• f is monotone: ∀si ∈ S, if c′i ≤ ci, then si ∈ f(ci, c-i) implies si ∈ f(c′i , c-i) for every c-i;
• winners are paid threshold payments: the payment to each winning bidder is the critical value inf{ci : i /∈ f (ci, c-i)}.

We prove the sellers' truthfulness of the mechanism by showing that it satisfies the theorem above.

Theorem 2. MechanismUM satisfies sellers' truthfulness. Proof. Monotonicity: Suppose bk is the last winning bid in mechanism UM, and we have bk vk ≤ Bt ∑j≤k vj . For any seller with j ≤ k, it is obvious that seller sj is selected, i.e., bj vj ≤ Bt ∑h≤j vh . If sj decreases its bid to be b′j ≤ bj, according to the allocation scheme of Mechanism UM, it is clear that b′j vj ≤ Bt ∑h≤j vh since bj vj ≤ Bt ∑h≤j vh . Thus, seller sj will still be selected as a winning seller. Therefore, Mechanism UM is monotonic.

Threshold payments: In MechanismUM, let bk denote the last winning seller. For any winning seller sj, the payment is pj = min{vj · q, Bmin 3 }, where q = min{ bk+1 vk+1 , Bt ∑j≤k vj }. Assume that seller sj increases its bid to b′j . Clearly, bidding bj > Bmin 3 would make the seller fail to be selected inMechanism UM. Thus, it remains to show that any seller bidding higher than vj · q will not be selected. We distinguish two cases of value q:

Case 1 ( bk+1 vk+1 ≤ Bt ∑j≤k vj ): In such case, q = bk+1 vk+1 and bk+1 vk+1 > Bt ∑j≤k+1 vj by Lemma 1. When seller sj with j ≤ k bids b′j > vj · q, we have b′j vj > q = bk+1 vk+1 > Bt ∑j≤k+1 vj . Assume that sj is ranked in the t-th place with t ≥ k + 1 after bidding. That is, bk+1 vk+1 ≤ ... ≤ b′j vj . Suppose on the contrary that sj is still selected in such case, which implies that b′j vj ≤ Bt ∑h≤j-1 vh+∑j+1≤h≤t vh+vj ≤ Bt ∑j≤k+1 vj . This leads to a contradiction. Thus, seller sj will not be selected as a winning seller. Therefore, the value vj · q is the critical value and the winning sellers are paid threshold payment.

Case 2 ( bk+1 vk+1 > Bt ∑j≤k vj ): We have q = Bt ∑j≤k vj . When seller sj with j ≤ k bids b′j > vj · q, we have b′j vj > q = Bt ∑j≤k vj . Assume that seller sj is ranked in the t-th place with t ≥ k after bidding, that is, bk vk ≤ ... ≤ b′j vj . Suppose on the contrary that sj is still selected in such case, which implies that b′j vj ≤ Bt ∑1≤h≤j-1 vh+∑j+1≤h≤t vh+vj ≤ Bt ∑j≤k vj . This leads to a contradiction. Thus, seller sj will not be selected as a winning seller. Therefore, the value vj · q is the critical value and the winning sellers are paid threshold payment.

Based on the analysis of two cases above, Mechanism UM guarantees sellers' truthfulness.

Therefore, we conclude that Mechanism GRM guarantees sellers' truthfulness.

4.3 Buyer's Truthfulness

We will show buyers' truthfulness of Mechanism UM first and then consider GREEDYMECH.

To prove buyers' truthfulness of Mechanism UM, we first show that the expected total value that buyer ai procured through the random allocation rule is equal to V (Bi) in the following lemma. The detailed proof is omitted here due to space limit.

Lemma 2. The expected total value that buyer ai procured through the random allocation rule is equal to V (Bi).

Then, we show that the expected procured value of any buyer ai would not increase, i.e., V (B′i ) ≤ V (Bi). Assume the one-third of buyers' total virtual budget is B′t and the virtual critical threshold is q′ when buyer ai underbids a lower budget B′i < Bi. We use V (B′i ) to denote the expected total value procured from sellers and assume the mechanism selects the first r sellers as winning sellers in such case. Let B = ∑i≤m Bi and ∆B = B - Bi = ∑h≤m,h̸=i Bh and V = ∑j≤k vj .

The total budget Bt would decrease when running mechanism UM if buyer ai underbids. Thus, the number of winning sellers cannot be increased, i.e., Sw = {sj : j ≤ r} where r ≤ k, which implies the total procured value does not increase. Otherwise, the mechanism could have more winning sellers when ai bids its true budget according to the allocation rule. According to the virtual allocation in Mechanism UM, the sellers are allocated to the buyers according to buyers' increasing index. Assume that al is the first buyer who has not used up its quota in the virtual allocation. That is, all buyers with i ≤ l-1 use up their quota and all buyers with i > l have not procured any value. Accordingly, let ˜ A = {ai : i ≥ l}. We prepare a basic lemma as follows.

Lemma 3. If q′ ≤ q when a buyer ai ∈ ˜ A underbids, we have V (B′i ) ≤ V (Bi).

Proof. Note that each buyer after al (whose index is larger than l) is not allocated any value in the true bidding. The total value of winning sellers that is used for allocation is not increased as r ≤ k in the false bidding. Since q′ ≤ q after false bidding, the quota for each buyer before al cannot be decreased. Thus, if al misreports, then buyers before it still have higher priority to be allocation, thus the value allocated to al would not increase. Moreover, if buyer ai ∈ ˜ A\{al} misreports, then ai is not allocated any value in the true bidding and the quota of buyers prior to ai does not decrease after false bidding. Thus, ai still does not procure any value. Therefore, we have V (B′i ) ≤ V (Bi).

Now we show that buyer ai cannot increase its utility. We discuss it by two cases of value q.

Case 1 (q = Bt V ≤ bk+1 vk+1 ): When buyer ai reports a lower budget B′i , the virtual critical threshold may change to q′ =min{ B′t ∑j≤r vj , br+1 vr+1 }. If ai /∈ ˜ A, the expected total value V (Bi) = Bi 3q = Bi Bi+∆B · V since its quota is used up. Next, we distinguish two cases of q′ :

Case 1.1 ( q′ = B′t ∑j≤r vj ≤ br+1 vr+1 ): We first consider the case of r = k. We have q′ = B′t V ≤ Bt V = q where the first equation follows by r = k and the inequality holds by B′t < Bt. If ai ∈ ˜ A, it is clear that V (B′i ) ≤ V (Bi) by Lemma 3. If ai /∈ ˜ A, then we have V (B′i ) ≤ B′i 3q′ = B′i B′i+∆B · V where the first inequality is true because each buyer's expected procured value from sellers is at most the quota computed in the virtual allocation. Since B′i B′i+∆B ≤ Bi Bi+∆B when B′i < Bi, we have V (B′i ) ≤ B′i B′i+∆B · V ≤ Bi Bi+∆B · V = V (Bi) .

Next, we consider the case of r < k. According to the precondition q′ = B′t ∑j≤r vj ≤ br+1 vr+1 , we have q′ ≤ br+1 vr+1 ≤ bk vk ≤ Bt V = q where the last inequality holds by Lemma 1. Thus, q′ ≤ q. If ai ∈ ˜ A, we have V (B′i ) ≤ V (Bi) by Lemma 3. If ai /∈ ˜ A, the expected value procured from sellers is V (B′i) ≤ B′i 3q′ = B′i B′i+∆B · ∑j≤r vj ≤ Bi Bi+∆B · V = V (Bi) where the second inequality is because B′i B′i+∆B ≤ Bi Bi+∆B when B′i < Bi and ∑j≤r vj ≤ V = ∑j≤k vj. That is, V (B′i ) ≤ V (Bi) .

Case 1.2 ( q′ = br+1 vr+1 < B′t ∑j≤r vj ): We first consider the case of r = k. We have q′ = bk+1 vk+1 < B′t ∑j≤k vj since r = k. Since B′t < Bt, we have bk+1 vk+1 < B′t ∑j≤k vj < Bt ∑j≤k vj which contradicts the condition Bt V ≤ bk+1 vk+1 . Thus, it is impossible that r = k.

Next, we consider the case of r < k. We have q′ = br+1 vr+1 ≤ bk vk ≤ Bt V = q where the second inequality holds by Lemma 1, thus q′ ≤ q. If ai ∈ ˜ A, we have V (B′i ) ≤ V (Bi) by Lemma 3. If ai /∈ ˜ A, we have V (B′i) ≤ B′i 3q′ = B′i 3· br+1 vr+1 . We also know

br+1 vr+1 > B′t ∑j≤r+1 vj because seller sr+1 is not selected as a winning seller. Thus, we have V (B′i) ≤ B′i 3· br+1 vr+1 < B′i B′i+∆B ·

Case 2 (q = bk+1 vk+1 < Bt V ): For this case, the technical proof is also involved but similar to Case 1, which is omitted here due to space limit.

Therefore, Mechanism UM satisfies buyers' truthfulness. Next, we prove buyers' truthfulness in GREEDYMECH. Buyer ai can procure at most ⌊ Bi Bmin ⌋ items since B′i < Bi. The expected procured value of buyer ai cannot increase because sellers are allocated in the order of highest-value-first to buyers according to their index. Therefore, GREEDYMECH satisfies buyers' truthfulness.

Therefore, Mechanism GRM satisfies buyers' truthfulness.

4.4 Approximation

Let Vu(S1) denote the total value procured in UM with the candidate sellers in set S1 and similarly let Vg(S2) denote the total value of items procured in GREEDYMECH with the candidate sellers in set S2 where S1 = {sj|bj ≤ Bmin 3 }, S2 = {sj|bj > Bmin 3 } and S = S1 ∪ S2. Correspondingly, we denote by OPT(S1) and OPT(S2) the optimal solution with input of S1 and S2, respectively.

Lemma 4. Mechanism UM achieves an approximation ratio of 4+ 3 m-1 ≤ 7 , where m is the number of buyers.

Proof. To analyze the approximation of Mechanism UM, we distinguish two kinds of bids, the ones with price-per-value less than q and the ones with price-per-value no less than q. First, we consider the bids with peice-per-value less than q. By the definition of q, we have bk+1 vk+1 ≥ q and all sellers with price-per-value less than q have at most a total value ∑j≤k vj. For the optimal solution, the best case is that it buys all ∑j≤k vj amount of value with total cost 0.

Next, we consider the bids with price-per-value no less than q. The best case is that all the bids in {bj|j ≥ k+1, bj ∈ b} are equal to q and the optimal solution pays each seller vj · q. In such case, we can procure at most Bt q value from these sellers given a total budget Bt. If q = Bt V , then Bt q = ∑j≤k vj. If q = bk+1 vk+1 , then Bt q = Bt bk+1 vk+1 ≤ Bt Bt ∑j≤k+1 vj =

∑j≤k+1 vj since Bt ∑j≤k+1 vj ≤ bk+1 vk+1 by Lemma 1. For both cases, we have Bt q ≤ ∑j≤k vj + vk+1. However, for the optimal solution, it has the full amount of each buyer's budget, which equals 3Bt. Thus, the optimal solution can get at most 3Bt q ≤ 3 ∑j≤k vj +3vk+1 value from sellers with price-pervalue no less than q.

Combining the two cases above, the optimal solution can procure at most 4 ∑j≤k vj + 3vk+1 value from all sellers. Therefore,

By Lemma 1, we have (∑j≤k+1 vj) · bk+1 vk+1 > Bt. Thus,

The reason for the second inequality is that each candidate seller's bid in Mechanism UM is at most Bmin 3 and the budget for any buyer is at least Bmin. Combining (1) and (2), we have OPT(S1) Vu(S1) ≤ 4+ 3vk+1 ∑j≤k vj ≤ 4+ 3 m-1 ≤ 7.

The following lemma further show that the simple greedy mechanism GREEDYMECH for large bids is 5approximation. The intuition is that the value procured from sellers with large bids in GREEDYMECH is close to the optimal solution (which should pay each seller with large bid at least Bmin 3 ). The detailed proof is omitted due to space limit.

Lemma 5. GREEDYMECH achieves a 5-approximation.

Finally, for Mechanism GRM, the total procured value is V (S) = 7 12 · Vu(S1) + 5 12 · Vg(S) ≥ 1 12 · (OPT(S1) + OPT(S2)) ≥ 1 12 · OPT(S).

Theorem 3. Mechanism GRM achieves an O(1)- approximation.

Acknowledgements

The work described in this paper was partially sponsored by National Key R&D Program of China 2017YFB1003000, and National Natural Science Foundation of China under Grants No. 11771365, No. 61672154, and partially sponsored by the Shenzhen Research Institute, City University of Hong Kong.