# diffusion_and_auction_on_graphs__58d31ca6.pdf

Diffusion and Auction on Graphs

Bin Li1 , Dong Hao1 , Dengji Zhao2 and Makoto Yokoo3

1University of Electronic Science and Technology of China, Chengdu, China 2Shanghai Tech University, Shanghai, China 3Kyushu University, Fukuoka, Japan

Auction is the common paradigm for resource allocation which is a fundamental problem in human society. Existing research indicates that the two primary objectives, the seller s revenue and the allocation efﬁciency, are generally conﬂicting in auction design. For the ﬁrst time, we expand the domain of the classic auction to a social graph and formally identify a new class of auction mechanisms on graphs. All mechanisms in this class are incentivecompatible and also promote all buyers to diffuse the auction information to others, whereby both the seller s revenue and the allocation efﬁciency are signiﬁcantly improved comparing with the Vickrey auction. It is found that the recently proposed information diffusion mechanism is an extreme case with the lowest revenue in this new class. Our work could potentially inspire a new perspective for the efﬁcient and optimal auction design and could be applied into the prevalent online social and economic networks.

1 Introduction

Auction has been a common paradigm for allocating resources [Krishna, 2009], its applications vary from assigning the sponsored links to advertisers [Edelman et al., 2007] to allocating the wireless spectrum worldwide [Cramton, 2013]. Auctions ask and answer this question: who should get the goods and at what prices? Typically, there are two goals in auction design. One is to design auctions that maximize social welfare, i.e., allocating the goods in a way that maximizes the total utilities of all participants. Another line focuses on the seller s revenue. Traditionally, there are two ways to improve the revenue: use the classic optimal auction [Myerson, 1981] or gather more people to join the auction. The former method requires prior knowledge of buyers valuations to compute a reserve price. The buyer set needs to be ﬁxed in advance, and the mechanism will be invalid if a seller can

Dong Hao is the corresponding author. Email address: libin@std.uestc.edu.cn, haodong@uestc.edu.cn, zhaodj@shanghaitech.edu.cn, yokoo@inf.kyushu-u.ac.jp

hardly have a panorama (value distribution) of all the underlying bidders. As a comparison, the latter method seems to be more effective and adaptive comparing with optimal auctions. A classic result in [Bulow and Klemperer, 1996] shows that when the buyers valuations draw i.i.d from a regular distribution, then the expected revenue of a second price auction with one additional bidder is no less than that given by the optimal auction. However, except using costly advertising, where these additional buyers could come from? The natural way is to ask the current bidders to help to diffuse the sale information to the outsiders. However, the selﬁsh bidders have no incentives to do so. From the point of view of the whole economic network, this information blocking not only decreases the seller s revenue, but also reduces the allocation efﬁciency of goods. Here are two examples. On online selling websites like e Bay, the ﬁnal price of an item depends on the population of interested buyers. Normally, the buyers have no incentives to invite other competitors and the information are limited to people who see this sale. One activity on online social networks that is frequently seen is people sharing clicking links (such as a new product) to their friends. This is actually an informal way to use information diffusion to recruit more people to a sale. Essentially, the above prevalent problems are about how to design a good market for the sale of products or services where the participants are encouraged to invite more people to the mechanism. The problem can be seen as auctions constrained with (negative) externalities [Bhattacharya et al., 2011; Haghpanah et al., 2013; Belloni et al., 2017]. However, for our problem, the underlying social connections of all participants gives the externality constrains in a very complicate way, where previous common techniques on externalities can hardly help. The most related works are from [Li et al., 2017; 2018; Zhao et al., 2018]. [Li et al., 2017] initiates this problem and proposes one mechanism which incentivizes buyers to diffuse seller s sale information to their neighbors. [Zhao et al., 2018] extends this to a multi-unit setting where the seller has multiple homogeneous items for sale and each buyer wants at most one of them. [Li et al., 2018] further investigates this problem in constrained economic networks where both the allocation efﬁciency and revenue can be obtained. We study the problem of auction on graphs from a more general point of view. In the ﬁrst part of this paper, we propose a class of mechanisms named critical diffusion mech-

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

anism (CDM) on unweighted graphs. We shows that the method proposed in [Li et al., 2017] is a special case of this class and is the one with the lowest revenue. In the second part, we further study this problem on weighted graphs which has never been tackled in the literature. We propose the very ﬁrst solution called weighted diffusion mechanism (WDM). In both CDM and WDM, each buyer s optimal choice is to report her valuation truthfully and diffuse the sale information to all her neighbors. Our theoretical results can be applied to the research and application ﬁelds such as crowdsourcing, sharing economics and viral marketing. By using our mechanisms, the buyers on e Bay are happy to do the invitations, the diffusion of an innovation will be maximized as well.

2 Preliminaries Consider a seller selling an item in a digraph G = (V, E) where V is the node set with |V | = n and E is the edge set. Besides the seller s, each node i V owns a private type ti = (vi, ri), where vi is her valuation on the item and ri is the set of her neighboring nodes. Node i can only communicate with j through existing link (i, j) E, and a node could participate in the auction only if someone of her neighbors has joined in the auction and further informs her of the sale. Initially, only the seller s neighbors are informed of the sale. Let w(i, j) be the weight on edge (i, j), for instance in a distribution network w(i, j) can be represented as the freight of transporting the item from i to j. We assume graph G contains no negative cycles and w(i, j) is known once i and j join in the auction. In Figure 1, node s owns one item for sale and only node A and B are informed of the sale at ﬁrst. Node C cannot join in the auction if B does not inform her of the sale. The values in each circle are nodes private valuations and the red numbers represent for the resided weights. We model the selling problem as an auction. Formally, denote ti = (vi, ri) by node i s private type and t = (t1, , tn) by the type proﬁle of all nodes. Let t i = {t1, t2, , ti 1, ti+1, , tn} be the type proﬁle of all other nodes except i, i.e., t = (ti, t i). Let Ti = R 0 P(V ) be the type space of i where P(V ) is the power set of V and T = Ti V \{s} be the type proﬁle space of all nodes. As usual, let t i = (v i, r i) Ti be the reported type of node i where r i ri means that i diffuses the sale information to nodes in r i. The set r i is limited to P(ri) as node i is not aware of other nodes who are not her neighbors. Denote t = (t 1, , t n) by the reported type proﬁle of all nodes where t i = nil when i has never been informed of the sale or i has no interest in the auction. Deﬁnition 1. Given a reported type proﬁle t and a node i with t i = nil, deﬁne a trading path from seller s to i as an ordered sequence of nodes (a1, a2, , al, al+1 = i) such that a1 rs and for 1 < j l + 1, aj r aj 1. Among all trading paths from the seller to node i, denote L i (t ) by the shortest one, i.e., L i (t ) = arg min L Li(t ) P (i,j) L w(i, j) where Li(t ) is the set of all possible trading paths of node i. Since G contains no negative cycles, then L i (t ) is a simple path from s to i. Deﬁnition 2. A diffusion auction M = (π, x) deﬁned on G consists of two components: an allocation rule π : T L

Figure 1: An example of weighted graphs where C G(t) = {B, F, G} and L F (t) = {B, E, F}.

which determines a single trading path π(t), where L is the set of all possible trading paths in G and π(t) is a selected path whose terminal node will be allocated with the item; and a payment rule x = {xi}i V \{s} which is the amount that each node pays, where xi : T R is the payment rule for i.

Given an allocation π(t), the social welfare in diffusion auctions is deﬁned as v(π(t)) P (i,j) π(t) w(i, j) where v(π(t)) is winner s true valuation. Here the total weights P (i,j) π (t) w(i, j) is perceived as the externalities incurred when passing an item from the seller to the winner. An allocation π is efﬁcient if it maximizes the social welfare for every t T, i.e., π arg maxπ Πv(π (t)) P (i,j) π (t) w(i, j) where Π is the feasible allocation set. Denote W (t) by the social welfare under efﬁcient allocation π . In our model, each node has quasilinear utility function, meaning that given i s type ti and an allocation π(t ), i s utility is deﬁned as: ui(ti, t , (π, x)) = vizi(t ) xi(t ) where zi(t ) is an indicator variable which is 1 if i wins the item and 0 otherwise. A diffusion mechanism is individually rational if for each node, her utility is non-negative when she reports her valuation truthfully regardless of her diffusion strategies, i.e., ui(ti, ((vi, r i), t i), (π, x)) 0. And it is incentivecompatible (IC) if reporting true types is a dominant strategy for every node in the auction, that is ui(ti, (ti, t i), (π, x)) ui(ti, (t i, t i), (π, x)) for all i V \ {s}. Note that on the right side of the inequality, we use t i to replace t i because the set of nil type nodes may change when i s report becomes t i. Given a reported type proﬁle t and a mechanism M = (π, x), the seller s revenue generated by M is deﬁned by Rev M(t ) = P i V \{s} xi(t ) P (i,j) π(t ) w(i, j).

The VCG mechanism [Vickrey, 1961; Clarke, 1971; Groves, 1973] is a generic truthful mechanism for achieving an efﬁcient allocation. However, it has many serious practical problems [Rothkopf, 2007]. Under our framework, it can lead to a high deﬁcit for the seller [Li et al., 2017]. Instead, we use the outcomes of the Vickrey auction [Vickrey, 1961], a special case of the VCG mechanism, as the benchmark and design good diffusion auctions that outperform them. In the Vickrey auction, the item is allocated to the highest bidder who is charged with the second highest bid. Since every node in the auction has no incentives to share the sale information, then the allocation efﬁciency and the seller s revenue equal the highest and second highest bid in {ti}i rs respectively.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

3 Auction Mechanism on Unweighted Graph

This section investigates diffusion mechanisms in unweighted graphs where each edge s weight is zero. In an unweighted graph, for any determined node i V \ {s}, there would be multiple simple paths from s to i. Moreover, there are several cut nodes which are shared by all these paths. These nodes are called critical diffusion nodes of i since without any of them, node i cannot receive the sale information and cannot join in the auction.

Deﬁnition 3. Given a reported type proﬁle t and a node i with non-nil reported type, deﬁne Ci(t ) = {T L}L Li(t ) as the set of i s critical diffusion nodes where Li(t ) is the set of all feasible trading paths from the seller s to node i.

Notice that for any pair j, k Ci(t ), we have that either j Ck(t ) or k Cj(t ). Therefore there is an unique fully ordered set C i (t ) = {s1, s2, , sk, sk+1, , i} for all nodes in Ci(t ) such that sj is a critical diffusion node of sj+1. This unique sequence is named as the critical diffusion sequence of i. In addition, for any j C i (t ), it is clear that C j (t ) = {s1, s2, , j}. For example, there are four simple paths from the seller to node G in Figure 1, any of which has to pass node B and F, and therefore node G s critical diffusion nodes are {B, F, G}. Then, we have C G = {B, F, G} and C F = {B, F}. Let di be the set of nodes whose critical diffusion nodes include i, e.g., d F = {F, G, H}. Clearly, if i is removed from the graph, the nodes in di cannot join in the sale. Denote t x by the partially reported types from set x and t x = t \ t x as the reported type proﬁle when set x is removed from the graph, where x could be a set of edges, vertices or a mixture. For an edge (i, j), t {(i,j)} means that node j is removed from i s diffusion strategy r i with respect to t . For example, we have t {F } = {ti}i V \d F and t {(B,D),(B,E)} = {ti}i {A,B,C}.

Deﬁnition 4. Given a reported type proﬁle t , assume that the highest bidder is m and her critical diffusion sequence is C m(t ) = {1, 2, , k, k + 1, , m}. Deﬁne αm = and for an arbitrary i C m(t ) \ m, predeﬁne an edge set αi = {(j, l) E}j di which has the following properties:

1. Information blocking: node i + 1 / t αi, meaning that the nodes in di+1 cannot join in the auction if αi is removed from the graph.

2. Node independence: for any two reported type proﬁles t 1 and t 2 which only differ in t di+1, α1 i = α2 i . This property ensures that αi is independent of the strategies of nodes in di+1.

3. Diffusion monotonicity: if r i r i , then t α i t α i . That is, the set of non-nil type in t αi is monotonically increasing with r i.

The ﬁrst property requires the set should be a cut. The second property says when the mechanism designer chooses αi, her choice should not be affected by what happened in di+1. The third property further requires the choice of αi should not ruin the monotonicity of information diffusion. Based on αi, we now give a class of new mechanisms named critical diffusion mechanisms (CDM) in Alg. 1. In

Algorithm 1: Critical Diffusion Mechanism (CDM)

1 initialize π(t ) = and {xi(t ) = 0}i V \{s}; 2 locate the highest bidder m, break tie arbitrarily; 3 compute C m(t ) and denote it by {1, 2, , m}; 4 for i 1 to m do 5 compute αi; 6 if vi = W (t αi) then 7 set π(t ) to be any trading path of i and xi(t ) = W (t i); 8 break;

9 else 10 set xi(t ) = W (t i) W (t αi);

CDM, only nodes in C m(t ) are considered as the candidates of the winner. In the allocation policy, nodes ordered higher in C m(t ) are given priorities to win. The algorithm computes whether a node has the ability to win one after another and stops once the ﬁrst qualiﬁed node is identiﬁed. In the following theorems, we prove that such a sequential allocation rule combined with the payments deﬁned in Alg. 1 provides a class of auction mechanisms with remarkable performances.

Theorem 1. The critical diffusion mechanism proposed in Alg. 1 is individually rational and incentive-compatible.

Proof. Assume node g is the winner in Alg. 1. For any node i / C m(t ), her utility is zero. The only way for i to change her utility is to increase her bid and becomes the highest bidder. In this case, she will be the winner according to Alg. 1 and will pay the previous highest bid v m which is greater than her true value vi. For any node i C g(t ) \ {g}, her utility is W (t αi) W (t i). The latter term is independent of node i, and according to diffusion monotonicity, the former term is maximized by choosing a diffusion strategy r i = ri. In addition, becoming the winner is also a bad choice for i since vi W (t i) < W (t αi) W (t i). Regarding to the winner g, her utility is vg W (t g) = W (t αg) W (t g). Because of diffusion monotonicity, it is no good for g to give up the chance of winning through lowering her bid. According to the ﬁrst and second properties of αi, the winner is still node g no matter what strategies nodes in C m(t ) \ C g(t ) choose. That is xi((t i, t i)) = 0 for any i C m(t ) \ C g(t ) and any i s strategy t i. In a word, we conclude that reporting truthfully is a dominant strategy for every node.

Next, we show that a CDM dominates the Vickrey auction, meaning that both the allocation efﬁciency and the seller s revenue are no less than that given in the Vickrey auction.

Theorem 2. The critical diffusion mechanism dominates the Vickrey auction.

Proof. Since only nodes in C g(t) could have non-zero payments, then Rev(t) = P i C g (t) xi(t) = W (t 1) + P i Cg(t)\{1,g}(W (t i+1) W (t αi)) W (t 1). The inequity holds because of the ﬁrst property of αi which means W (t j) W (t αi) for any j di+1.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Because there exists at most one node s type that belongs to {ti}i rs {t1}, then W (t 1) is at least the second highest bid in {ti}i rs. In addition, due to the fact that {ti}i rs t αg and vg = W (t αg), we conclude that any critical diffusion mechanism dominates the Vickrey auction.

Essentially, different choices of αi offer different tradeoffs between the allocation efﬁciency and the revenue. The information diffusion mechanism (IDM) proposed in [Li et al., 2017] is equivalent to a speciﬁc instantiation of the above CDM in which αi is set to be the edge set {(j, i + 1) E} for any i C m(t) \ {m}. According to different preferences of the mechanism designer, one can conveniently generate many such mechanisms. For example, here is a another speciﬁc instantiation of CDM: let βm = and for any i C m(t)\{m}, βi is the minimum subset of {(i, j)}j ri, by cutting which the sale information cannot reach node i + 1. In Theorem 1, we proved that given any type proﬁle t, the lower bound of the seller s revenue in any CDM is W (t 1). This is exactly what the seller obtains in the IDM. Therefore, we directly get the following corollary.

Corollary 1. In all critical diffusion mechanisms deﬁned in Alg. 1, the information diffusion mechanism proposed in [Li et al., 2017] is the one with the lowest revenue.

To give an intuitive description of CDM, we give a running example with respect to βi in Figure 1. Firstly, G is the highest bidder and C G is {B, F, G} by Def. 3. Then, let i = B, if she does not inform of the sale to D nor E, then i + 1 = F cannot join in the auction. Note that in Figure 1, βB = {(B, D), (B, E)} is one, and the minimum one such edge cut set. B loses the item since C is the highest bidder after removing βB from the graph. If B is removed from the graph, the highest bidder becomes A. According to the last line in Alg. 1, B s payment is v A v C = 1 4 = 3, i.e., the seller pays 3 to B. In a similar way, βF = {(F, G), (F, H)}. Since F is the highest bidder after deleting βF , then F wins the item and the algorithm stops here. Since E is the highest if F is removed, then according to lines 6-8 in Alg. 1, F pays v E = 6. Others pay zero. Finally the seller s revenue is 3 + 6 = 3 which is greater than 1 the revenue in the Vickrey auction.

4 Auction Mechanism on Weighted Graph

This section studies auction mechanisms on general weighted graphs. There are two key differences make the problem challenging. On the one hand, L m(t) (or π (t)) could be any simple path from the seller s to m on an unweighted graph while C m(t) is a set of some cut nodes which may or may not be adjacent. For a node i in L m(t) but not in C m(t) (for instance, E in Figure 1), no matter what her strategy t i is, she cannot be in C m((t i, t i)) since m t i. However, on a weighted graph, since the valuations (bids) are mingled with edge weights, such nodes could affect the efﬁcient allocation by strategic diffusion. One the other hand, under the unweighted settings, only nodes in C m(t) are considered as the candidates of the winner. Nonetheless, nodes in L m(t) \ C m(t) cannot be omitted on weighted graphs. For example, in Figure 1, if the weight of edge (D, F) is 5, then if E does not diffuse to

Algorithm 2: The allocation policy of WDM

1 initialize π(t ) = ; 2 compute π (t ), break tie arbitrarily; 3 denote π (t ) by L m(t ) = {1 , 2 , , q = m}; 4 for i 1 to q do 5 compute γi; 6 if i is allocated the item in π (t γi) then 7 set π(t ) = L i (t ); 8 break;

F, then she becomes the winner (also a critical diffusion node) in the auction. In this section, we propose the very ﬁrst mechanism that satisﬁes all the desired properties on general weighted graphs. Deﬁnition 5. For any node i and its neighbor j, if j has neighbor k rj(k = i), then j is an intermediary of i. For instance, in Figure 1, B s intermediaries include nodes A, D and E. Denote Ii by the set of i s intermediaries. Given a reported type proﬁle t , let m be the winner in π (t ) where π (t ) = L m(t ) = {1 , 2 , , q = m}. Since the graph contains no negative cycles, then according to the optimal substructure property of the shortest path [Bondy et al., 1976], for any i L m(t ) we have L i (t ) = {1 , 2 , , i }. Deﬁnition 6. Given a reported type proﬁle t and π (t ), deﬁne γm = and for any i L m(t ) \ {m}, let γi be the edge set {(i , j)|j Ii {(i + 1) }}. Intuitively, γi is an edge cut set following i since once γi is removed from the graph, nodes in L m(t ) \ L i (t ) can only be reached via other nodes but not i . In Figure 1, π (t ) = {B, E, F} and γB = {(B, i)|i {A, D, E}}. When the edge set γB is removed from Figure 1, all simple paths to node E or F, if any, do not pass B. Now we propose the weighted diffusion mechanism (WDM) for general weighted graphs. The allocation policy is given in Alg. 2. In the WDM, we allocate the item to a node i along L m(t ). Node i should be the ﬁrst node which satisﬁes v i P l L i (t γi)\{i} w(l, l + 1) = W (t γi). That is, after removing γi, she is allocated with the item in the efﬁcient allocation with respect to the remaining graph. Note that with such an allocation rule, the nodes who are not in C m(t ) could also win the auction. We give a running example in Figure 1. Firstly, identify the efﬁcient allocation path B E F. Since it is node C instead of B who wins in π (t γB), we move to check node E, but E also loses the auction. Thus ﬁnally, node F wins the item. Before precisely characterizing the payment policy of the WDM, we need another important concept below. Deﬁnition 7. For node i L g(t )\{g} where g is the winner, we call her a secondary node if i wins the item in π ({t γi \ t g} (v g = nil, r g)) where g s reported type is replaced by (nil, r g) in t γi. If node i is a secondary node, then i will be the winner in π (t γi) when g does not bid (v g = nil). Furthermore,

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Algorithm 3: The payment policy of WDM

1 initialize {xi(t ) = 0}i V \{s} and B g(t ) = 0; 2 let L g(t ) be the allocation achieved in Alg. 2; 3 denote w(i, j) = P L j (t γi)\{j} w(l, l + 1);

4 for i L g(t ) \ {g} do 5 compute γi; 6 set xi(t ) = W (t i) W (t γi); 7 if i is a secondary node then 8 update B g(t ) = max{B g(t ), v i w(i, i) + w(i, g)};

9 update B g(t ) = max{B g(t ), W (t g) + w(g, g)}; 10 set xg(t ) = B g(t );

if winner g = m beats node i in the efﬁcient allocation π (t γi), so will node m and this violates the deﬁnition of secondary nodes. Therefore, the secondary nodes could exist only when the winner is m. Since we search for the winner from head to tail along L m(t ), it is important that these secondary nodes are winner s critical opponents. The full characterization of the payment policy is given in Alg. 3. The value B g(t ) computed in Alg. 3 can be explained as the critical value of the winner in our diffusion model. There are two criteria that the critical value should satisfy if g wants to win the item. Firstly, since g wins the item in π (t γg), for any i γg(i = g), the inequality v g w(g, g) > v i w(g, i) must hold, where w(i, j) denotes the total weights of the shortest trading path to j with respect to t γi. To ensure that g wins, her bid v g is at least

max i γg(i =g){v i w(g, i) + w(g, g)}.

Note that w(g, i) and w(g, g) are independent of r g and the node set with non-nil types in γg is minimized when r g = , therefore maxi γg(i =g){v i w(g, i) + w(g, g)} is minimized when g diffuses the sale information to no one, in which case maxi γg(i =g){v i w(g, i)} = W (t g). That is, node g could win the item by reporting (v 1 g = W (t g) + w(g, g), r g = ). On the other hand, due to the fact that all nodes in L g(t ) \ {g} have priorities to win the item, winner g has to beat all of them one after another. Speciﬁcally, given a node i L g(t ) \ {g} and a reported type proﬁle t γi, if node i is not a secondary node, then it sufﬁces for g to beat i by bidding v 1 g . If node i is a secondary node, then according to Alg. 2, line 6, the winner must beat node i in the efﬁcient allocation π (t γi). That is to say, we must have v g w(i, g) > v i w(i, i) which leads to v g > v i w(i, i) + w(i, g). Denote the set of all secondary nodes by SN , above argument means that v g is at least

max i SN {v i w(i, i) + w(i, g)}.

It is not hard to see that the cardinality of SN is minimized when g spreads the sale information to all her neighbors, and therefore node g could beat all secondary nodes by reporting a

type with bid v 2 g = maxi SN {v i w(i, i)+ w(i, g)} and diffusion r g = rg. Therefore, according to the above analysis, winner g can win the item by bidding at least max{v 1 g , v 2 g }. In Figure 1, regarding whether node E wins the item in the efﬁcient allocation after cutting γE = {(E, B), (E, F)}, since node E would win the item in π (t γE) if the winner F does not bid, therefore, node E is a secondary node (actually the only one). According to Alg. 3, winner F will pay a price of at least v E w(E, E) + w(E, F) = v E w(B, E) + (w(B, D) + w(D, F)) = 6 0 + 3 = 9. Since W (t F ) + w(F, F) = 6, then the winner pays 9 to the seller. One could further check that node B and E pay 2 and 0 respectively. The seller s revenue is 2 + 0 + 9 0 = 7 which is greater than 1, the revenue obtained in the Vickrey auction. The identiﬁcation of secondary nodes and the characterization of B g(t ) are the key techniques in proving the property of incentive compatibility. Combining with the following two lemmas, we prove that WDM is IR and IC.

Lemma 1. If there exist secondary nodes in Alg. 2, then the winner cannot increase her utilities by misreporting.

Proof. First of all, the winner must be m if there exist secondary nodes according to Def. 7. For any secondary node j, she is still a secondary node for any m s diffusion strategy r m rm as long as m remains to be the winner. Therefore m s payment is minimized by diffusing the sale information to all her neighbors. Since there exist secondary nodes, then for any secondary node j, the winner m is the only node that beats j in π (t γj). This leads to the fact that when m is trying to become a node along the winning path by lowering her bid, the ﬁrst secondary node in type proﬁle t will become the winner in advance according to Alg. 2, line 6, whereby m s utility becomes zero. Therefore, no matter what strategies m commits, she cannot increase her utility.

Lemma 2. Given any type proﬁle t and any node i L m(t)\ L g(t), i cannot increase her utility by misreporting.

Proof. Firstly, when i spreads the sale information to only a part of her neighbors, there are two possible results: she is still an node in L m(t) in which case g still wins according to Def. 5 and Alg. 2; or she is out of L m(t) which makes her out of L g(t) either. Therefore, her utility remains unchanged by misreporting ri. Secondly, note that unless node i beats g in π (t γg), otherwise g must be the winner and i s utility remains zero according to Alg. 3. Since W (t γg) is greater than vj w(g, j) for any j L m(t) \ L g(t), she can beat g only by increasing her bid such that she wins in Alg. 2. Due to the fact that node g is the winner in π (t γg), node g would be a secondary node if i becomes the winner. In this case, node i has to pay at least vg w(g, g) + w(g, i) = W (t γg) + w(g, i). Therefore, the utility of i by being a winner is at most vi (W (t γg)+ w(g, i)) = (vi w(g, i)) W (t γg) < 0.

Theorem 3. The weighted diffusion mechanism is individually rational and incentive-compatible.

Proof. Firstly, we show that the weighted diffusion mechanism is individually rational. For any node i / L g(t ), her

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

payment is zero. For any node i L g(t ) \ {g}, her utility is W (t γi) W (t i) 0 since t i t γi. As for the winner g, her payment is B g(t ) which is no more than vg. Next we show WDM is IC through following cases. Case 1: For i / L m(t), since {tj}j L m(t) t i, the only chance for i to have a non-zero utility is to bid high enough such that she becomes the winner in π (t ). And in this case she has to pay a price of at least W (t) + w(i, i) which is higher than her true value vi because W (t) > vi w(i, i). Case 2: For i L g(t) \ {g}, her utility is W (t γi) W (t i). Since W (t γi) vi w(i, i), she cannot do better by winning, otherwise she pays at least W (t i)+ w(i, i). The latter term W (t i) is independent of i s strategy and the former term W (t γi) is independent of vi (otherwise she becomes the winner according to Alg. 2, line 6). Due to Def. 5, for any r i ri I i I i ri \ r i. This property induces that γi γ i ri \ r i. That is, after removing γi and γ i from the graph separately, the set of non-nil type nodes follows that γ i γi. Therefore the set of non-nil types in t γi is the largest when i spreads the sale information to all her neighbors, this maximizes her utility. Case 3: For winner g, her utility is vg B g(t). If there are no secondary nodes, then she pays exactly W (t g)+ w(g, g) and her utility is vg w(g, g) W (t g) = W (t γg) W (t g). When she misreports to be in Case 2, her utility becomes W (t γ g) W (t g). Since the set of non-nil types in γg is maximized when g diffuses the sale to all her neighbors, misreporting is a bad choice for her since W (t γg) W (t γ g). On the other hand, the more nonnil nodes exist in the graph, the harder the secondary nodes could exist. Therefore, if g diffuses the sale only to a part of her neighbors, then secondary nodes would be created which in turn will increase her payment according to Alg. 3, lines 4-8. Hence, truthfully reporting is the best strategy for the winner. In addition, if there exist secondary nodes, then misreporting will harm g s proﬁt according to Lemma 1. Case 4: For any node i in L m(t) \ L g(t), according to Lemma 2, misreporting would decrease her utility.

For proving that WDM dominants the Vickrey auction, we ﬁrstly pick out the nodes with zero payments.

Lemma 3. For i L g(t)\{g}, if the intersection of π (t γi) and L m(t) \ L i (t) is not empty, then i s payment is zero.

Proof. According to Def. 6, if we remove γi from the graph, then all nodes in L m(t)\L i (t) can only be reached by other nodes but not i. Therefore, if π (t γi) and L m(t)\L i (t) have some common elements, according to the optimal substructure property of shortest path, node m must be the winner in π (t γi) and node i / π (t γi). Consequently, we have that W (t γi) must equal W (t i) and therefore xi(t) = 0.

For convenience, denote L# g (t) by the nodes in L g(t ) who satisfy π (t γi) L m(t)\L i (t) = , then according to Lemma 3 only L# g (t) can have non-zero payments.

Theorem 4. The weighted diffusion mechanism dominates the Vickrey auction.

Proof. According to the payment policy of WDM and Lemma 3, the seller s revenue can be denoted as

j V \{s} xj(t) X

l L g(t)\{g} w(l, l + 1)

j L# g (t) xj(t) w(g, g)

j L# g (t)\{g} (W (t j) W (t γj))

+ B g(t) w(g, g)

j L# g (t)\{g} (W (t j) W (t γj)) + W (t g)

= W (t 1#) + X

j L# g (t)\{1#} (W (t j) W (t γj 1))

The ﬁrst inequation holds because B g(t) is at least W (t g) + w(g, g) according to Alg. 3, line 9. Since for any j L# g (t), we have that π (t γj) L m(t)\L i (t) = . Then we have W (t j) W (t γj 1) for any j L# g (t) \ {1#} which induces the second inequity. Because {ti}i rs t 1# {t1#}, we have that W (t 1#) is at least the second highest bid in rs. In addition, since vg w(g, g) W (t γ1 ) and {ti}i rs t γ1 , then the allocation efﬁciency of the weighted diffusion mechanism is no less than that given in the Vickrey auction.

It is worth noting that when the weights are zero, WDM degenerates to a CDM.

5 Conclusions In this paper, we formulate the model of information diffusion and auction on both unweigted and weighted graphs and provide generic solutions which not only guarantee IC and IR but also can incentivize information sharing. The key techniques for realizing these mechanisms are graph cut analysis and the integration of bidder s private valuation and social links. Due to the introduction of information sharing incentive, all the instance mechanisms under our solution framework improve both the seller s revenue and the allocation efﬁciency comparing with the Vickrey auction. In practice, these mechanisms can be applied in a recursive way: any new comer will be treated as a bidder if she submits a two-dimensional type. This recursion is terminated if there is no new submission. Then the seller calculates the trading path, and determines the allocation and payments. One immediate future work is: although this work realizes seller s revenue optimization, the problem of its maximization is still unclear. Moreover, what is the underlying impact of αi on the seller s revenue and the allocation efﬁciency, and how to design fast algorithms determining the membership of these sets are also important.

Acknowledgments This work was supported by the National Natural Science Foundation of China (NNSFC) Grant Number 71601029 and JSPS KAKENHI Grant Number JP17H00761.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [Belloni et al., 2017] Alexandre Belloni, Changrong Deng, and Saˇsa Pekeˇc. Mechanism and network design with private negative externalities. Operations Research, 65(3):577 594, 2017. [Bhattacharya et al., 2011] Sayan Bhattacharya, Janardhan Kulkarni, Kamesh Munagala, and Xiaoming Xu. On allocations with negative externalities. In International Workshop on Internet and Network Economics, pages 25 36. Springer, 2011. [Bondy et al., 1976] John Adrian Bondy, Uppaluri Siva Ramachandra Murty, et al. Graph theory with applications, volume 290. Citeseer, 1976. [Bulow and Klemperer, 1996] Jeremy Bulow and Paul Klemperer. Auction versus negotiations. American Economic Review, 86(1):180 94, 1996. [Clarke, 1971] Edward H. Clarke. Multipart pricing of public goods. Public Choice, 11(1):17 33, 1971. [Cramton, 2013] Peter Cramton. Spectrum auction design. Review of Industrial Organization, 42(2):161 190, 2013. [Edelman et al., 2007] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242 259, 2007. [Groves, 1973] Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617 631, 1973. [Haghpanah et al., 2013] Nima Haghpanah, Nicole Immorlica, Vahab Mirrokni, and Kamesh Munagala. Optimal auctions with positive network externalities. ACM Transactions on Economics and Computation, 1(2):13, 2013. [Krishna, 2009] Vijay Krishna. Auction theory. Academic Press, 2009. [Li et al., 2017] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. Mechanism design in social networks. In AAAI, pages 586 592, 2017. [Li et al., 2018] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou. Customer sharing in economic networks with costs. In IJCAI, pages 368 374, 2018. [Myerson, 1981] Roger B. Myerson. Optimal auction design. Mathematics of Operations Research, 6:58 73, 1981. [Rothkopf, 2007] Michael H. Rothkopf. Thirteen reasons why the vickrey-clarke-groves process is not practical. Operations Research, 55(2):191 197, 2007. [Vickrey, 1961] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8 37, 1961. [Zhao et al., 2018] Dengji Zhao, Bin Li, Junping Xu, Dong Hao, and Nicholas R. Jennings. Selling multiple items via social networks. In AAMAS, pages 68 76, 2018.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)