# budget_feasible_mechanisms_over_graphs__ca4fa7b8.pdf

Budget Feasible Mechanisms Over Graphs

Xiang Liu1, , Weiwei Wu1, , Minming Li2,3, Wanyuan Wang1,

1 Southeast University, Nanjing, P.R. China 2 City University of Hong Kong, Hongkong, P.R. China 3 City University of Hong Kong Shenzhen Research Institute, Shenzhen, P.R. China {xiangliu,weiweiwu}@seu.edu.cn, minming.li@cityu.edu.hk, wywang@seu.edu.cn

This paper studies the budget-feasible mechanism design over graphs, where a buyer wishes to procure items from sellers, and all participants (the buyer and sellers) can only directly interact with their neighbors during the auction campaign. The problem for the buyer is to use the limited budget to incentivize sellers to propagate auction information to their neighbors, thereby more sellers will be informed of the auction and more item value will be procured. An impossibility result shows that the large-market assumption is necessary. We propose efﬁcient budget-feasible diffusion mechanisms for large markets that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentivecompatibility to report private costs and diffuse auction information. Moreover, the proposed mechanisms achieve logarithmic approximation that the total procured value is within a logarithmic factor of the optimal solution. Compared to most related budget-feasible mechanisms, which do not take the individual interactions among sellers into account, our mechanisms can incentivize sellers to further propagate auction information to other potential sellers. Meanwhile, existing related diffusion mechanisms only focus on seller-centric auctions and fail to satisfy the budget-feasibility of the buyer.

Introduction Auction theory, as a common paradigm for multi-agent resource allocation (Krishna 2009), has enabled a wide range of applications, e.g., wireless spectrum auctions (Huang, Berry, and Honig 2006) and mobile crowdsourcing markets (Feng et al. 2014). Much effort over past decades focused on designing mechanisms to regulate trading behaviors in markets, e.g., seller-centric auction when a seller sells items to buyers, or buyer-centric/reverse auction when a buyer procures items from sellers. Among the extraordinary progresses, the budget-feasible mechanism design in reverse auctions was initially studied in (Singer 2010), where payments used to regulate behaviors should satisfy the budget constraint. Many following works invest efforts to design budget-feasible mechanisms (Chen, Gravin, and Lu 2011; Dobzinski, Papadimitriou, and Singer 2011; Bei et al. 2012; Singer 2012; Singer and Mittal 2013; Zhao, Li, and Ma

These two authors contributed equally to this work. Corresponding author Copyright c 2021, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

2014; Anari, Goel, and Nikzad 2018). All these works assume that sellers are reachable to the buyer and ready to join the auction campaign. However, in reality, many potential sellers will be unaware of the auction information if none of their acquaintances propagates information to them. In order to propagate auction information to more potential sellers, the buyer can adopt the traditional advertising mechanisms. However, the high agency fee charged by the third party platform might degrade the net revenue of the buyer (Mehta 2000). Against this background, this paper studies the social diffusion mechanisms over a graph. The connections modeled in the graph might represent positive individual interactions, which have been widely adopted for information diffusion (Kempe, Kleinberg, and Tardos 2003), information acquisition (Cebrian et al. 2012), and information search (Watts, Dodds, and Newman 2002). With the local positive interactions, social diffusion mechanisms can bring a volume of potential sellers without any extra cost. Taking the buyer s budget constraint into account, the following natural question arises: Can we design a budgetfeasible mechanism which guarantees desirable economic properties and stimulates involved sellers to propagate auction information to her neighbors over graphs, while guaranteeing a bounded total payment from the buyer? For example, considering the questionnaire, a classic research instrument for the organizer to gather information from respondents especially in the social networks (Sarason et al. 1983), a critical requirement is to get sufﬁcient respondents. However, it is inefﬁcient and costly for the organizer to notify all respondents by herself. A promising way is to incentivize participated respondents to invite potential people, e.g., their followers and friends. There may be costs associated with ﬁnishing questionnaires, e.g., participants time and privacy. It is common to give participants monetary rewards to motivate the population. Moreover, the organizer usually has a budget and cannot afford unlimited monetary rewards. Therefore, such scenario calls for viable budget feasible diffusion mechanisms. In the budget-feasible mechanism design literature, although there exists a general rule characterizing the truthful bidding behavior in single-parameter domains (Myerson 1981), there is no general rule on how to incentivize sellers to bid truthfully while at the same time to propagate auction information to their neighbors. On the other hand, the

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

well-known VCG mechanism (Vickrey 1961; Clarke 1971; Groves 1973) fails in budget-feasible mechanisms as an unlimited payment may be incurred. Last but not least, the VCG mechanism aims to maximize the total procured value with a budget, which is NP-hard. In the information diffusion mechanism design literature, all critical participants whose invitations increase social welfare will be rewarded (Li et al. 2017; Zhao et al. 2018; Li et al. 2019; Kawasaki et al. 2020; Zhang, Zhao, and Chen 2020). Existing diffusion mechanisms mainly focus on seller-centric auctions where the seller incentivizes buyers to diffuse the information and decides the ﬁnal winners. While in budget-feasible mechanism design, as a fundamental difference from the seller-centric auction, the payment used to elicit truthful behaviour should satisfy the buyer s budget constraint. The payment scheme used to elicit truthfulness or propagate the auction information in seller-centric auctions cannot meet the budget-feasibility requirement in reversed auctions as an unbounded payment may be incurred1. Recently, (Shi et al. 2019) consider the budget constraint in information diffusion mechanisms, but they only focus on rewarding agents to spread information via social connections, not on auction problem of procuring items from sellers. Our contributions can be summarized as follows.

We ﬁrst model a budget-feasible diffusion mechanism over graphs where the buyer with a budget wants sellers to propagate auction information to their neighbors, which builds the bridge between budget-feasible mechanisms and information diffusion mechanisms.

We show that without the large market assumption, no budget-feasible diffusion mechanisms can achieve an approximation ratio better than n (the number of sellers).

By incorporating the large market assumption, we overcome the non-approximability and design budget-feasible diffusion mechanisms that guarantee desirable theoretical properties including budget feasibility, computational efﬁciency, individual rationality, truthfulness, strong budget-balance, and logarithmic approximation.

Preliminaries The Model

We consider an undirected graph consisting of a buyer a and a set of n sellers S = {s1, s2, ..., sn} where buyer a wants to procure items with a budget B and each seller has a single item to sell. Seller si has a cost ci and a value vi when selling her item to the buyer. In this paper, we consider the incomplete information case where each seller s cost ci is privately known by herself. Following previous budget-feasible mechanisms (Singer 2010; Dobzinski, Papadimitriou, and Singer 2011), we assume that each item s value vj is common knowledge to the buyer ranging in [1, V ]. The objective is for the buyer to maximize the total value of items procured within the budget. Let A = {a, s1, ..., sn} denote the set of all participants including the buyer and all sellers. Each

1A detailed comparison to existing mechanisms can be found in Section: The Inefﬁciency of Existing Mechanisms.

seller si S has a set of neighbors ni A\{si} with whom si can exchange information directly. Speciﬁcally, the buyer a s neighbors are na(na = ). A seller can participate in the auction if and only if one of her neighbors is informed of the auction information and further propagates the information to her. Initially, only na know that the buyer a wants to procure items. According to the types of items, we mainly consider two cases: the homogeneous item setting where sellers hold identical items, and the heterogeneous item setting where sellers hold diverse items with different values. We focus on the strategic scenario where sellers behave strategically to maximize their own utilities. Each seller reports cost c i of her item that may be different from the real cost ci. Additionally, seller si may reject to further propagate the auction information to her neighbors or report false neighbor set n i ni. Let ti = (ci, ni) denote the truthful bid that si truthfully declares her cost and propagates the auction information to all her neighbors, while bi = (c i, n i) denotes the bid when si participates in the auction. Let b = {b1, ..., bn} denote the bid proﬁle of all sellers and b i denote the bid proﬁle of all sellers except the seller si. The bid proﬁle b can also be represented by b = (bi, b i). Large Market Assumption: Informally speaking, a market is large if the cost of a single item is very small compared to the buyer s budget B, i.e., ci B. This assumption is used in other large-market problems (Anari, Goel, and Nikzad 2014) with application in crowdsourcing markets, where there is a requester who has a limited budget (e.g., $500). The requester publishes a large quantity of microtasks, like image labeling, content generation, and validating recommendation engines. After ﬁnishing a micro-task, the worker will get a tiny reward ($0.2) for cost compensation. To improve the efﬁciency of crowdsourcing, the requester can estimate the quantity of workers for better micro-task pricing. Therefore, this paper also assumes that there is an upper bound on the market size, i.e., |S| Nmax, which is known by the buyer. We will show that the large market assumption is necessary by proposing an impossibility result at the beginning of Section . The Mechanism: An auction mechanism M = (X, P) consists of an allocation policy X = {xi}i S deciding winners and a payment policy P = {pi}i S deciding how much payment is paid to each seller. If si is selected as a winner, xi(b) = 1, otherwise, xi(b) = 0. Let Sw denote the set of winners. Given si s bid bi, bid proﬁle b and mechanism M = (X, P), we deﬁne si s utility as the difference between the payment she receives and her real cost, i.e., ui(bi, b, M) = pi xi ci. The utility of the buyer is the total value of items procured, i.e., ua(b, M) = P 1 i n xi vi. If no ambiguity arises, ui(bi, b, M) and ua(b, M) will be written as ui(bi) and ua, respectively. A mechanism M is individual rational if the utility of each seller is non-negative when she truthfully reports her private information.

Deﬁnition 1. A mechanism M = (X, P) is individual rational (IR) if ui(ti, (ti, b i), M) 0, si S.

We also consider the incentive compatibility or truthfulness property. Different from traditional graph-ignorant

budget-feasible mechanism problems in (Singer 2010) where truthfulness means that for each seller, truthfully reporting her cost is a dominant strategy. In our model, we also need to consider sellers incentives to propagate the auction information to their neighbors. Thus, we also require the designed mechanism to guarantee that for each seller, reporting her real cost and diffusing the auction information to all her neighbors is a dominant strategy. Deﬁnition 2. A mechanism M = (X, P) is incentive compatible (IC) or truthful if ui(ti, (ti, b i), M) ui(bi, (bi, b i), M).

Note that b i is replaced by b i on the right side of the inequality. The reason is that if bid bi does not propagate the auction information to all her neighbors, then some sellers, who can get the information under bid ti, may not receive the information under bid bi. Thus, under bi, the feasible bid proﬁle of sellers except si is changed from b i to b i. Given the payment policy, we deﬁne the budget feasibility and strong budget-balance. Deﬁnition 3. A mechanism M = (X, P) is budget-feasible if the total payment paid to sellers does not exceed the budget, i.e., P

1 i n pi B.

Deﬁnition 4. A mechanism M = (X, P) is strong budgetbalanced if the total payment charged from the buyer equals the total payment paid to sellers. The objective is to maximize the utility of the auctioneer/buyer, i.e., max ua(b, M). Deﬁnition 5. A mechanism M = (X, P) is αapproximation if the ratio between the optimal solution where mechanism knows sellers true private information and the solution by mechanism M is no greater than α.

The Inefﬁciency of Existing Mechanisms There are two main directions for the truthful auction design problem. One is to apply Vickrey-Clarke-Groves (VCG) mechanisms. The other is to design truthful mechanisms via Myerson s theorem (Myerson 1981) to guarantee two properties, the monotonicity and the threshold payment. Next, we show the inefﬁciencies of these two existing classes of mechanisms in the budget-feasible diffusion problem. The inefﬁciency of VCG mechanisms: (Li et al. 2017) show that the classical VCG mechanism can incentivize auction information diffusion in seller-centric auctions and further improve upon VCG mechanism on the revenue efﬁciency. However, such kind of methods totally ignore the budget-feasibility requirement and thus cannot be applied to deal with the key challenge in budget-feasible mechanism design2, as an unbounded payment may be incurred. For instance, given the graph in Fig. 1, we consider a linear graph with n > 2 sellers and a buyer a located at the left endpoint of the line. The cost of seller sn 1 is 5ϵ while the costs of the remaining sellers are ϵ. All sellers have identical value vi = 1. In addition, the budget of the buyer is B = (n+2)ϵ. The VCG mechanism will choose all sellers except sn 1 as

2Actually, VCG would also fail in the computational efﬁciency as computing the optimal item allocation is NP-hard (Singer 2010).

𝑠!"# 𝑠$ 𝑠% 𝑠# 𝑎

Figure 1: An example showing the inefﬁciency of existing mechanisms.

!! !!"# !% !# "

-#= - - - - -

If !# does not spread the auction information

Figure 2: An example for the proof of Theorem 1.

winners since the total cost is within budget B, and pay each winner 4ϵ, which exceeds the budget B = (n + 2)ϵ. The inefﬁciency of graph-ignorant budget-feasible mechanisms: In the traditional budget-feasible mechanisms (Singer 2010; Chen, Gravin, and Lu 2011), which are based on Myerson s theorem, the proportional share allocation rule is widely used to generate budget-feasible allocations and elicit the truthfulness.

Proportional share allocation rule

Sort sellers according to their non-decreasing costs relative to their values.

Allocate seller si to winner set Sw if ci vi B P

Assume that the last winner is sk, then the payment for each winner si Sw will be vi min{ ck+1

1 h k vh }. Applying the mechanism in (Singer 2010) to the graph in Fig. 1, all sellers with cost ϵ will be selected as winners and the payment for each winner is min{5ϵ, B n 1} = B n 1. Seller s3 can reject to propagate the auction information to her neighbors and then her payment now is B

3 which implies that she can get more utility by manipulating the diffusion strategy. Thus, such kind of mechanisms cannot incentivize sellers to propagate the auction information to their neighbors.

Mechanism Design In this section, we investigate budget-feasible diffusion mechanisms. We start from the homogeneous item setting, where sellers items have identical values, and then extend it to the heterogeneous item setting. Before introducing our mechanisms, we ﬁrst show an impossibility result without the large market assumption as follows, Theorem 1. Without the large market assumption, no truthful budget-feasible diffusion mechanisms can achieve an approximation ratio better than n.

Proof. Assume that there exists a budget-feasible diffusion mechanism M which can achieve (n ε)-approximation ratio, for any ε > 0. Suppose that sellers have identical values vi = 1. As shown in Fig. 2, we consider an example where there are n+1 sellers each with cost c = B

n in the linear network. We have 0 < c1 = c B. It is clear that the optimal solution can procure n items from sellers and each winner is paid B

n . If s1 rejects to propagate the auction information to her neighbor s2, no sellers after s1 can get the auction information. Thus, seller s1 must be a winner with payment B to ensure truthfulness (as s1 can bid any false cost no greater than B without the large market assumption). The utility of s1 now is u1 = B c1. Recall that a seller obtains the maximum utility when she reports real cost and propagates the auction information to her neighbors in budget-feasible diffusion mechanism M . Thus, s1 should achieve at least B c1 utility to incentivize her to propagate the auction information to her neighbors. On one hand, if s1 is selected as a winner when she propagates the auction information, her payment should be B to obtain at least B c1 utility. M cannot procure one more item from other sellers due to the budget constraint. On the other hand, if s1 is a loser, her payment should be no smaller than the utility when she propagates the information, which is B c1. Thus, M can procure at most one item from other sellers. For both cases, Mechanism M can only procure at most one item from sellers, which contradicts with the assumption that M achieves (n ϵ)-approximation.

Mechanism for the Homogeneous Item Setting

In this subsection, we introduce the budget-feasible diffusion mechanism for the homogeneous item setting, called Mechanism BDM-H. The high level idea is as follows. We ﬁrst generate a seller sequence from the graph according to each seller s distance to the buyer. Considering the budget constraint, we divide the mechanism into multiple phases, in each of which we set a target number of winners and a ﬁxed payment for each winner. In addition, to achieve better utility on the buyer s side, we aim to ﬁnd more winners with lower costs in the later phase by setting a larger target number of winners and a lower ﬁxed payment. The detailed design is presented as follows. Generate seller sequence: We ﬁrst construct a seller sequence according to bid proﬁle b. We calculate each seller s shortest distance to the buyer and sort sellers in the nondecreasing order of the shortest distance with arbitrary tiebreaking rule, denoted as a sequence O = s1, s2, ..., sn . Fig. 3 shows an example of seller sequence generation over a graph. We use circles to represent sellers and the rectangle to represent the buyer. The number in each circle is her cost, and the pair consisting of a capital letter and a number indicates her index and the shortest distance. The number in the rectangle is the buyer s budget. By sorting all sellers shortest distances, we can get the seller sequence O = B, C, E, D, F, G, I, J, L, H, M, K . Phase Division: We divide the winner selection process into L = log2 Nmax phases, each of which is allocated with a partial budget ˆB = B

L . In the l-th phase, we set a ﬁxed

/, 2 0, 2 1, 3

Figure 3: An example of a graph. We have B, C, E with distance 1, D, F, G, I, J, L with distance 2, H, M with distance 3 and K with distance 4.

payment τ l p and a target number of winners τ l w. Speciﬁcally, we have τ l p τ l w = ˆB which can ensure that the partial budget in each phase is not exceeded. Winner selection and payment scheme: Now, we start from the ﬁrst phase, i.e., l = 1, by setting τ l p = ˆ B 2l 1 and τ l w = 2l 1. In addition, we use τ c w to count the number of sellers with costs no greater than τ l p in this phase, which is initialized to be zero. Assume that we are now considering seller si in the l-th phase. If c i > τ l p, we continue to test the next seller si+1. If c i τ l p and τ c w < τ l w 1, the value of τ c w increases by one and we go to the next seller si+1. If c i τ l p and τ c w = τ l w 1, the number of sellers with costs no greater than τ l p in the l-th phase reaches 2l 1 after considering seller si. This seller is also denoted as key seller Hl. We use H and I(Hl) to denote the set of all key sellers and Hl s position in the seller sequence O, respectively. Once the value of τ l w reaches 2l 1, sellers with costs no greater than τ l p in the l-th phase will all be selected as winners and added into winner set Sw, i.e., si Sw if i (I(Hk 1), I(Hk)] and c i τ l p. In addition, the payment to each of these winners in the l-th phase is set with pi = τ l p = ˆ B 2l 1 . Then, we move to the (l + 1)-th phase where the ﬁxed payment will be reduced to half of the ﬁxed payment of the previous phase, i.e., τ l+1 p = 1

2τ l p = ˆ B 2l , and we will try to select twice as many winners as in the previous phase, i.e., τ l+1 w = 2τ l w = 2l. In addition, we set the value of τ c w to be zero and continue to test the next seller si+1. We repeat this process until no sufﬁcient winners can be selected, that is, after k phases, we cannot further ﬁnd τ k+1 w = 2k winners whose bids are no greater than τ k+1 p = ˆ B 2k , i.e.,

|{h|c h τ k+1 p , h > I(Hk)}| < τ k+1 w . (1)

Then, sellers after Hk are all losers. The payments for all losers are zero, i.e., pi = 0 if si / Sw. Note that we have at least one key seller, i.e., k 1 because we can ﬁnd at

Algorithm 1: Mechanism BDM-H(B, b , S, Nmax)

Input: B, b , S, Nmax. Output: P, Sw 1 P 0, X 0, Sw , H ;

2 L log Nmax 2 , ˆB B

3 Calculate the shortest distance for each seller and sort all sellers in the non-decreasing order of the distance, i.e., O = s1, s2, ..., sn ;

4 i 1, l 1;

5 while l L do

6 τ l p ˆ B 2l 1 , τ l w 2l 1, τ c w 0;

7 while i n, τ c w < τ l w do

8 if c i τ l p then

9 τ c w τ c w + 1;

11 i i + 1;

13 if τ c w = τ l w then

14 Hl si 1, H H {Hl};

15 for I(Hl 1) < h I(Hl) and c h ˆ B 2l 1 do

16 ph ˆ B 2l 1 , xh 1, Sw Sw {sh};

23 return P, Sw

least one seller with cost no greater than ˆB in the ﬁrst phase according to the large market assumption. Running example: We now show a running example of Mechanism BDM-H using the graph in Fig. 3. Assume that all sellers report real private information. The buyer s budget is B = 32 and the maximum number of sellers is Nmax = 16. Thus, we have L = log2 16 = 4 and ˆB = 8. We select winners by the sequence O as shown in Fig. 4. We start from the ﬁrst phase which tries to ﬁnd τ 1 w = 20 sellers with costs no greater than τ 1 p = ˆ B 20 = 8. It is clear that the ﬁrst seller with cost 2.5 marked by red box is selected as a winner and her payment is τ 1 p = 8. In addition, she is also the ﬁrst key seller H1. Then, we consider the next phase to ﬁnd τ 2 w = 21 sellers with costs no greater than τ 2 p = ˆ B 21 = 4. In this phase, seller C and E marked by the blue box are winners each paid τ 2 p = 4. And seller E is the second key seller H2. Similarly, we can see sellers D, I, J, L are winners each with payment τ 3 p = 2 in the third phase. Last, in the fourth phase, we cannot ﬁnd τ 4 w = 8 sellers with costs no greater than τ 4 p = ˆ B 23 = 1. Thus, we ﬁnally have the winner set Sw = {B, C, E, D, I, J, L} and three key sellers H = {B, E, L}. Next, we analyze the theoretical performance of BDM-H.

Theorem 2. Mechanism BDM-H guarantees individual rationality, strong budget-balance, budget feasibility and com-

Seller . / 0 1 2 3 4 5 6 7 8 9 Cost *. ; < < < ; = <. *; < * < <. *; <. *

Figure 4: Running example of Mechanism BDM-H.

putational efﬁciency.

Before analyzing the truthfulness of Mechanism BDM-H, we ﬁrst introduce a useful lemma.

Lemma 1. The order of sellers before si (including si herself) in seller sequence O will not change if si misreports her neighbors n i ni.

Proof. Let ρ(si), d(si) denote the shortest path and the corresponding distance from the buyer to seller si, respectively. Note that the shortest distance of seller sj before si in seller sequence O is no greater than d(si), i.e., d(sj) d(si). We can ﬁnd that si cannot be on the path ρ(sj), otherwise, we can ﬁnd a path from the buyer to si shorter than ρ(sj), which leads to a contradiction. After si misreports her neighbors n i ni, the number of paths from the buyer to sj will not increase and the path ρ(sj) will still exist since si is not on path ρ(sj). Thus, seller sj shortest distance to the buyer is still d(sj). This implies that the order of sellers before si will not change. Furthermore, sellers on path ρ(si) are all before si and will still propagate the auction information to si which means the position of si will also not change after misreporting her neighbors. This ﬁnishes the proof.

Theorem 3. Mechanism BDM-H guarantees incentivecompatibility/truthfulness.

Proof. To achieve more utility, seller si may propagate auction information to a subset of her neighbors n i ni and report a false cost c i = ci. It is clear that seller si s position in sequence O will not change by Lemma 1 even when she chooses to propagate auction information to a subset of neighbors n i. Thus, si, regardless of which subset of neighbors she reports, will still be considered at the same phase as when she had reported the true set of neighbors. Assume that si is considered in the l-th phase. When she is being considered under reporting false neighbor set, the value of target seller number τ l w, the ﬁxed payment τ l p and the current number of speciﬁed sellers τ c w are the same as when she reports real cost and propagates auction information to all her neighbors. Thus, it is easy to ﬁnd that si cannot achieve more utility by diffusing information to a subset of neighbors. Thus, it remains to discuss the case that a seller bids a false cost when she propagates the information to all her neighbors. Based on the position of si in the sequence O, we consider the following cases: Case 1: Seller si where I(Hl 1) < i I(Hl) and l k: Recall that BDM-H selects 2l 1 winners with bids no greater than ˆ B 2l 1 from sellers between Hl 1 and Hl, and

pays each winner ˆ B 2l 1 . We further consider two sub-cases, whether si is a winner or not when she reports the true cost and propagates the information to all her neighbors. 1) Seller si is a winner, i.e., ci ˆ B 2l 1 and pi = ˆ B 2l 1 : Seller si would become a loser by bidding a higher cost c i > ˆ B 2l , leading to zero utility. If si bids a cost lower than ˆ B 2l 1 , she is still a winner with the same payment ˆ B 2l 1 which implies her utility will not increase. Thus, winners cannot get more utilities by bidding false costs. 2) Seller si is a loser, i.e., ci > ˆ B 2l 1 and pi = 0: Seller si is still a loser by bidding a higher cost c i > ˆ B 2l 1 . If she bids

a lower cost c i ˆ B 2l 1 , she will be selected as a winner and

the payment is ˆ B 2l 1 which leads to negative utility. Thus, losers also cannot get more utilities by bidding false costs. Case 2: Seller si where i > I(Hk): Recall that all these sellers are losers. Since Hk is the last key seller, there are no 2k sellers with bids no greater than ˆ B 2k . Given that seller

si reports real neighbor set ni, if ci ˆ B 2k , si cannot be a

winner whatever she bids. If ci > ˆ B 2k , she either is still a

loser or is a winner by bidding a lower cost c i ˆ B 2k with

payment ˆ B 2k which leads to negative utility. Thus, any seller si|i>I(Hk) cannot get more utility by bidding a false cost. Thus, sellers have no incentive to bid false costs. Therefore, Mechanism BDM-H guarantees the truthfulness.

Theorem 4. Mechanism BDM-H achieves 2( log2 Nmax + 1)-approximation.

Proof. Let S and S denote the set of sellers before Hk (including Hk herself) and sellers after Hk, respectively. Meanwhile, we use S k and S k to denote the set of sellers in S whose costs satisfy ci ˆ B 2k and ci > ˆ B 2k , respectively. Since Hk is the last key seller, there are at most 2k 1 sellers whose costs are no greater than ˆ B 2k , i.e., |S k| 2k 1, while the costs of the remaining sellers after Hk are greater than ˆ B 2k . Denote by OPTh and ALGh the optimal solution and the solution of Mechanism BDM-H for the homogeneous item setting, respectively. According to the sellers positions in the sequence O, we consider two cases: 1) Sellers in S = {si|i I(Hk)}: It is clear that the number of winners in S is

1 h k 2h 1 = 2k 1. (2)

For the optimal solution, the best case is that costs of winners in S are zero while losers costs are higher than ˆ B 2k 1 , i.e.,

ci = 0, i S Sw and ci > ˆ B 2k 1 , i S \ Sw. Thus, OPTh might procure all winners in S with payment zero. 2) Sellers in S = {si|i > I(Hk)}: For the best case, the costs of sellers in S k and S k are zero and ˆ B 2k , respectively. Within the budget B, the optimal solution OPTh can procure at most 2k 1 value from S k with cost zero and B/ ˆ B 2k = 2k L value from S k by paying each seller ˆ B 2k .

Winner C+, loser set C., , with costs

(! and loser set C., , with costs >

Figure 5: Example of position of H k in the sequence O.

By combining these two cases, the optimal solution can procure at most OPTh 2(2k 1)+2k L = 2k+1 2+2k L. Thus, OP Th

ALGh 2 + 2k L

2k 1 2( log2 Nmax + 1).

Recall that we use the upper bound Nmax of the market size (denoted by N = |S|) as the input, where N Nmax. In the real scenario, an estimated upper bound may be inaccurate. We thus show that, even when Nmax is not that accurate, the outputs of the mechanism has a small gap when running over the input Nmax and real number N. Let ALGh and ALG h denote the solutions of BDM-H with the input number Nmax and N of participants, respectively.

Theorem 5. The gap between ALGh and ALG h is within (8α 1) where α = log2 Nmax

Proof. We have L = log2 N and ˆB = B L . It is easy to ﬁnd that L L and ˆB ˆB. Let S w denote the winner set in solution ALG h. Assume that there are k key sellers in solution ALGh. If L < k L, the number of key sellers of ALG h must be less than solution ALGh which implies that ALG h procures less value of items than solution ALGh. If k L , due to ˆB ˆB, there are at least k key sellers in ALG h and the k-th key seller H k must be on the left side of Hk, i.e., I(H k) I(Hk) as shown in Fig. 5. For ALGh, let Sl and Sw denote the loser and winner set, respectively. The costs of losers between Hl 1 and Hl are greater than ˆ B 2l 1 (l k). Thus, the costs of losers before

Hk are all greater than ˆ B 2k 1 . Note that all sellers after Hk are also losers. Among these losers, there are at most 2k 1 sellers with costs no greater than ˆ B 2k while the costs of the

remaining losers are greater than ˆ B 2k , since ALGh only has k key sellers. Then, losers in ALGh can be divided into two groups: losers with costs no greater than ˆ B 2k denoted by

Sl, k, and the remaining losers with costs greater than ˆ B 2k , denoted by Sl, k. All sellers consist of three groups: Sw, Sl, k, Sl, k, and we have |Sw| = 2k 1, |Sl, k| 2k 1. Now, we analyze the maximum value ALG h can procure from sellers after H k. Besides the sellers in Sw and Sl, k, ALG h can procure items from Sl, k when the ﬁxed payment is higher than ˆ B 2k . Assume that there are at most x

phases whose ﬁxed payments are higher than ˆ B 2k after the

k-th phase, i.e., x = argmaxh 1{ ˆ B

2k+h 1 ˆ B 2k } which implies x = log2 α + 1 where α = log2 Nmax / log2 N . Then, the ﬁxed payment in the (k + x + 1)-th phase will

Algorithm 2: Mechanism BDM-G(B, b , S, Nmax)

Input: B, b , S, Nmax. Output: P, Sw 1 β log2 V ;

2 Divide all sellers into β groups according to (3);

3 for each group Gj do

4 (Pj, Sj w) = BDM-H(B, b, Gj, Nmax);

6 With probability 1

β , return (Pj, Sj w);

be lower than ˆ B 2k , and no sellers in Sl, k can be selected as winners in ALG h after the (k + x)-th phase. Thus, the only possible sellers to be selected as winners in ALG h after the (k+x)-th phase are from Sw Sl, k. Since the target number of winners after the (k + x)-th phase is at least 2k+x 2k, sellers in Sw Sl, k can only make the number of phases increase by at most one since they contain at most 2(2k 1) sellers. Thus, there are at most k + x + 1 phases in ALG h, and we have ALG h P l k+x+1 2l 1 = 2k+x+1 1.

Therefore, we have ALG h ALGh 2k+x+1 1

Mechanism for the Heterogeneous Item Setting Now we extend the result to the general setting where sellers hold heterogeneous items. The main challenge is that sellers with valuable items should get higher payments which makes it more difﬁcult to ensure budget-feasibility. We design a budget-feasible diffusion mechanism BDMG for the heterogeneous item setting. The idea is that we try to transform the heterogeneous item setting problem into multiple homogeneous item setting problems. Intuitively, we divide all sellers into multiple groups so that each group of sellers have similar values, and thus we can consider each group of sellers as owning items of homogeneous value. The mechanism proposed in the homogeneous item setting can then be used to deal with each group of sellers. We ﬁrst divide all the sellers into β groups, denoted by G = {G1, G2, ..., Gβ}, by their values of items where β = log2 V as follows,

G(si) = Gj, if vi (2j 1, 2j], 1 j β G1, otherwise (3)

where G(si) is the group seller si allocated to. Then, we view that each seller in the same group owns the same value. Thus, we call Mechanism BDM-H for the homogeneous setting to deal with the sellers in the same group. Denote by Sj w and Pj the output winners and the corresponding payment returned by Mechanism BDM-H on group Gj, i.e., (Pj, Sj w) = BDM-H(B, b, Gj, Nmax). Last, we sample one of the outputs from all groups with probability 1

β as the ﬁnal solution. Next we analyze the theoretical performance of BDM-G.

Theorem 6. Mechanism BDM-G guarantees individual rationality, computational efﬁciency, strong budget balance, budget feasibility and incentive compatibility.

Theorem 7. Mechanism BDM-G achieves (3 + 4L)βapproximation in expectation where L = log2 Nmax and β = log2 V .

Proof. Denote by OPTg and ALGg the optimal solution and the solution of Mechanism BDM-G, respectively. In group Gl, assume that there are kl key sellers. Thus, we have 2kl 1 winners in group Gl similar as in Equation (2). After the last key seller, we have at most 2kl 1 items with costs no greater than ˆ B 2kl and the remaining sellers are with costs

greater than ˆ B 2kl according to Equation (1). The expected total value procured by Mechanism BDM-G is

l β 2l 1 (2kl 1). (4)

Thus, we have

l β 2l (2kl 1). (5)

On one hand, in group Gl, OPTg can procure 2kl 1 items from winners in ALGg with cost zero, and 2kl 1 items whose costs are no greater than ˆ B 2kl . On the other hand,

with budget B, OPTg can procure at most B/ ˆ B 2kl = 2kl L

items from sellers whose costs are greater than ˆ B 2kl in Gl. Then, OPTg can procure at most 2l 2kl L value from Gl with budget B. Thus, OPTg can procure at most

l β 2l(2kl 1) + X

l β 2l 2kl L

3βALGg + Lβ

= 3βALGg + Lβ

l β(2l 2kl 2l) + 2l

= (3β + 2Lβ) ALGg + L X

(3β + 2Lβ)ALGg + 2LβALGg = (3 + 4L)β ALGg. where the second and third inequalities are due to (5). Therefore, we have OP Tg

ALGg (3 + 4L)β.

Conclusion In this paper, we consider the budget-feasible diffusion mechanisms over graphs that can incentivize sellers to further propagate auction information to the potential sellers and satisfy the buyer s budget constraint, simultaneously. For the homogeneous item setting, we propose Mechanism BDM-H, which selects winners by phases based on a generated seller sequence and controls the total payment at each phase by setting a target number of winners and a ﬁxed payment for each winner. We then extend the result to the heterogeneous item setting by proposing Mechanism BDM-G, which transforms the heterogeneous item setting into multiple homogeneous item setting problems by putting sellers with similar values into the same group. The designed mechanisms can guarantee desirable properties like individual rationality, budget-feasibility, strong budget-balance, incentive-compatibility and logarithmic approximation.

Acknowledgements The work described in this paper was partially sponsored by the National Key Research and Development Program of China under grant No. 2019YFB2102200, Natural Science Foundation of China under Grant No. 61632008, 61902062, 61672154, 61972086, 61932007, 61806053, 61807008, the Project 11771365 supported by NSFC, the Natural Science Foundation of Jiangsu Province of China (BK20180356 and BK20180369), the Postgraduate Research & Practice Innovation Program of Jiangsu Province of China (KYCX19 0089), and partially sponsored by the Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education.

References Anari, N.; Goel, G.; and Nikzad, A. 2014. Mechanism design for crowdsourcing: An optimal 1-1/e competitive budget-feasible mechanism for large markets. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 266 275. IEEE. Anari, N.; Goel, G.; and Nikzad, A. 2018. Budget Feasible Procurement Auctions. Operations Research 66(3): 637 652. Bei, X.; Chen, N.; Gravin, N.; and Lu, P. 2012. Budget feasible mechanism design: from prior-free to bayesian. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 449 458. Cebrian, M.; Coviello, L.; Vattani, A.; and Voulgaris, P. 2012. Finding Red Balloons with Split Contracts: Robustness to Individuals Selﬁshness. In Proceedings of the Forty Fourth Annual ACM Symposium on Theory of Computing, STOC 12, 775 788. Chen, N.; Gravin, N.; and Lu, P. 2011. On the approximability of budget feasible mechanisms. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, 685 699. SIAM. Clarke, E. H. 1971. Multipart pricing of public goods. Public choice 11(1): 17 33. Dobzinski, S.; Papadimitriou, C. H.; and Singer, Y. 2011. Mechanisms for complement-free procurement. In Proceedings of the 12th ACM conference on Electronic commerce, 273 282. Feng, Z.; Zhu, Y.; Zhang, Q.; Ni, L. M.; and Vasilakos, A. V. 2014. TRAC: Truthful auction for location-aware collaborative sensing in mobile crowdsourcing. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, 1231 1239. IEEE. Groves, T. 1973. Incentives in teams. Econometrica: Journal of the Econometric Society 617 631. Huang, J.; Berry, R. A.; and Honig, M. L. 2006. Auctionbased spectrum sharing. Mobile Networks and Applications 11(3): 405 408. Kawasaki, T.; Barrot, N.; Takanashi, S.; Todo, T.; Yokoo, M.; et al. 2020. Strategy-Proof and Non-Wasteful Multi Unit Auction via Social Network. In AAAI, 2062 2069.

Kempe, D.; Kleinberg, J.; and Tardos, E. 2003. Maximizing the spread of inﬂuence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 137 146. Krishna, V. 2009. Auction theory. Academic press. Li, B.; Hao, D.; Zhao, D.; and Yokoo, M. 2019. Diffusion and auction on graphs. In Proceedings of the 28th International Joint Conference on Artiﬁcial Intelligence, 435 441. AAAI Press. Li, B.; Hao, D.; Zhao, D.; and Zhou, T. 2017. Mechanism design in social networks. In Thirty-First AAAI Conference on Artiﬁcial Intelligence. Mehta, A. 2000. Advertising attitudes and advertising effectiveness. Journal of advertising research 40(3): 67 72. Myerson, R. B. 1981. Optimal auction design. Mathematics of operations research 6(1): 58 73. Sarason, I. G.; Levine, H. M.; Basham, R. B.; and Sarason, B. R. 1983. Assessing social support: the social support questionnaire. Journal of personality and social psychology 44(1): 127. Shi, H.; Zhang, Y.; Si, Z.; Zhao, D.; et al. 2019. Maximal Information Propagation with Budgets. ar Xiv preprint ar Xiv:1912.04056 . Singer, Y. 2010. Budget feasible mechanisms. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 765 774. IEEE. Singer, Y. 2012. How to win friends and inﬂuence people, truthfully: inﬂuence maximization mechanisms for social networks. In Proceedings of the ﬁfth ACM international conference on Web search and data mining, 733 742. Singer, Y.; and Mittal, M. 2013. Pricing mechanisms for crowdsourcing markets. In Proceedings of the 22nd international conference on World Wide Web, 1157 1166. Vickrey, W. 1961. Counterspeculation, auctions, and competitive sealed tenders. The Journal of ﬁnance 16(1): 8 37. Watts, D. J.; Dodds, P. S.; and Newman, M. E. J. 2002. Identity and Search in Social Networks. Science 296(5571): 1302 1305. Zhang, W.; Zhao, D.; and Chen, H. 2020. Redistribution Mechanism on Networks. In Proceedings of the 19th International Conference on Autonomous Agents and Multi Agent Systems, 1620 1628. Zhao, D.; Li, B.; Xu, J.; Hao, D.; and Jennings, N. R. 2018. Selling Multiple Items via Social Networks. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, 68 76. Zhao, D.; Li, X.-Y.; and Ma, H. 2014. How to crowdsource tasks truthfully without sacriﬁcing utility: Online incentive mechanisms with budget constraint. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications, 1213 1221. IEEE.