# double_auction_on_diffusion_network__86e23019.pdf

Double Auction on Diffusion Network

Miao Li, Yuhan Cao and Dengji Zhao

School of Information Science and Technology, Shanghai Tech University, Shanghai, China {limiao2022, caoyh1, zhaodj}@shanghaitech.edu.cn

Mechanism design on social networks has attracted extensive attention recently. The goal is to design mechanisms to incentivize participants to invite more participants via their social networks, and the challenge is that the participants are competitors. Various mechanisms have been proposed for single- /multiple-unit auctions, but it has been shown that it is challenging to design such mechanisms for more complex settings. We move this forward to investigate a double auction on a network where each trader (a buyer or a seller) can link to other buyers and sellers. Incentiving invitation is more difficult than in multi-unit one-sided auctions, because there are two different roles and a buyer (seller) seems happy to invite a seller (buyer), but again the invited seller (buyer) may invite another buyer (seller) to compete with the original buyer (seller). To combat this, we propose a solution called dynamic trade reduction (DTR), which also guarantees a non-negative revenue for the market owner. Interestingly, our solution is also applicable to the multi-unit one-sided auction when there is only one seller linking to only buyers on the network. We believe that the principle of our solution has the potential to be extended to design the multi-item one-sided auction.

Introduction Double auctions play a vital role in today s economy, offering a rich set of trading rules for commodity exchange among traders (Friedman and Rust 1993). Similar to other auction studies, research in double auctions aims to identify dominant strategies for both sellers and buyers to honestly report their valuations. One well-known mechanism for this purpose is the Vickrey-Clarke-Groves (VCG) mechanism (Vickrey 1961; Clarke 1971; Groves 1973). However, the VCG mechanism can lead to a deficit for the market owner. To remove the deficit, Mc Afee 1992 proposed a trade reduction mechanism, which reduces the number of traded buyers and sellers (i.e. social welfare) to increase their payments. Following Mc Afee s work, several studies (e.g. (Yoon 2001)) were directed at improving social welfare while maintaining a no-deficit condition. We take the study of double auctions to a new perspective, which considers a social network among traders. This is a new trend in mechanism design, and the new goal is to

Copyright 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

incentivize traders to invite their neighbours to join the same auction (Zhao 2021). The challenge is also very obvious because the traders are competitors and they would not invite each other with the existing mechanisms. Existing studies investigated one-sided auctions where the network only contains buyers (Li et al. 2022), while in the double auction, we have two different types of traders (buyers and sellers) in the network. Therefore, we cannot directly apply the techniques from one-sided auctions to the double auction. The very first one-sided auction proposed for the new perspective is for selling a single item (Li et al. 2017). They solved the problem by offering each buyer the marginal contribution on social welfare due to his participation, which will resolve their concern about their invitees competing with them. Following their solution, there is a rich body of studies around single-item auctions (Guo and Hao 2021). However, the problem is very complex in the multi-unit or multi-item settings (Zhao 2022). Double auctions are similar to multi-unit one-sided auctions, but the number of units to be sold is determined by the sellers from the network which is unknown in advance. Therefore, the problem is more challenging than the multi-unit one-sided auctions (Zhao et al. 2018; Kawasaki et al. 2020). Actually, we will propose a double auction mechanism which is also applicable for the one-sided multi-unit auction in the network setting. In the paper, we propose a double auction to satisfy the following goals: traders will truthfully report their valuations (traditional incentive compatibility), the market owner should not run in a deficit (weakly budget balance), and each trader (a seller or a buyer) is incentivized to invite all his neighbours to join the auction (our new goal). In the traditional setting without a network, to achieve the first two goals, Mc Afee s trade reduction is the classic solution (Mc Afee 1992). However, we will show that this cannot be directly used in the network setting to achieve the third goal because the reduction does not consider the competition between invitees and inviters. Our solution, called dynamic trade reduction, is inspired by Mc Afee s trade reduction and we use a modified version of it as a metamechanism of our solution. The high-level intuition of the solution is that we use the meta-mechanism to work on a small set of traders (initially only the traders who are in the market without invitation) to decide which traders cannot trade for sure, and these traders are allowed to invite their

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

neighbours to join. This repeatedly proceeds until we cannot get new traders to join the mechanism. This can also be applied to the one-sided multi-unit auction by simply adding a number of dummy sellers without invitation and running our mechanism with the dummy sellers and the buyer network. In summary, our work advances the state of the art as the following:

We propose the first double auction mechanism working on a trader network to incentivize traders to invite each other to enlarge the market. The solution also guarantees that traders will report their valuation truthfully and it will not give the market owner (the auctioneer) a deficit. In the enlarged market, our experiments demonstrate that the social welfare of the solution is almost optimal (although in theory, optimal social welfare is not achievable with the other properties). Surprisingly, our mechanism also offers a solution for the one-sided auction of selling multiple units to a buyer network where each buyer requires at most one unit, which is an open challenge with many failed attempts.

In recent years, mechanism design over social networks is a hot topic that explores truthful mechanisms on social networks (Zhao 2021; Zhang and Zhao 2022; Li et al. 2022). Li et al. (2017) firstly considered a single-item auction design problem on social networks where buyers have incentives to invite their neighbors to join the auction. This inspired a series of followups to extend the setting (Zhao et al. 2018; Kawasaki et al. 2020; Liu, Lian, and Zhao 2023; Fang et al. 2023). Moreover, except for auctions, similar studies were also stimulated in other games such as matching (Kawasaki et al. 2021; You et al. 2022; Yang et al. 2022) and cooperative games (Zhang and Zhao 2022). Our work follows the line of auction design in networks and we propose the very first double auction solution in the network setting.

The Model We consider a double auction market that operates on a social network. The social network is represented by an undirected graph denoted as G = (N, E). It consists of two distinct groups of traders: sellers and buyers. We can represent this as N = B S, where S = {S1, S2, , S|S|} is the set of sellers and B = {B1, B2, , B|B|} represents the set of buyers, each of them offering to sell or buy one unit of the same commodity. The edges between the traders represent their neighbourhood relationship. Specifically, edge (i, j) E indicates that agents i and j are neighbors of each other. Let ri N be the set of all neighbors of agent i in the network. Note that if agents i and j are not neighbors, they are unable to interact with each other (i.e., they do not know each other in practice). This is also the reason why we need traders invitations to involve all traders. In the double auction market on the social network, a third-party called auctioneer runs the auction to decide the winning traders and their payments. We assume that not all traders from the network are in the market initially, i.e., there

is only a subset of traders denoted by N0 = B0 S0 who are aware of the auction from the beginning. Without any promotion, the auction can only run among the initial traders. As we mentioned in the introduction, our goal is to design a new double auction to incentivize the existing traders to invite their neighbours to join the auction. Eventually, only traders who received proper invitations are aware of the auction and can ask/bid to sell/buy. In our model, we model their invitation behavior as reporting their neighbor set to simplify the notations. Thus, the new action of each trader in our model is to report both his valuation and his neighbor set. More formally, θi = (vi, ri) is the private type of trader i N, where vi represents the trader s valuation to own one unit of the commodity. For a seller i S, his goal is to sell one unit at a price not lower than vi, and for a buyer j B, the objective is to purchase one unit at a price not higher than vj. Let θ = (θ1, , θn) denote the type profile of all traders and θT = (θi)i T be the type profile of traders in T only. Additionally, we use θ i to represent the profile of all traders except for trader i, and θ can be written as (θi, θ i). Furthermore, let Θi be the type space of trader i and Θ be the type profile space of all traders. A double auction asks each trader to report his type and let θ i = (v i, r i) be the type report of agent i, where r i ri, indicating that the reported neighbor set is a subset of the true neighbor set1. Let θ = (θ 1, , θ n) be the report profile of all agents in N. Note that in practice, uninvited agents will not be able to join the auction. However, in the model, we assume all agents can report, but only the reports of properly invited agents are used. The uninvited agents reports are used as potential reports if they are invited. This is very useful for us to define the properties such as incentive compatibility, which requires a trader to invite a neighbor or not (so we need to know the report of a uninvited trader in the definition). Given a report profile θ , we generate a directed graph G(θ ) = (N(θ ), E(θ )). In this graph, an edge i, j E(θ ) exists if and only if j r i. This edge indicates that agent i reports agent j as a neighbor. Therefore, the directed graph G(θ ) is constructed based on the reported neighbors, which may not be the original trader network if someone misreported. Given traders type report profile, a general double auction is defined as follows. Definition 1 (Double Auction). A double auction mechanism in the social network is defined by an allocation policy π = (πi)i N and a payment policy p = (pi)i N, where πi : Θ {0, 1} and pi : Θ R are the allocation and payment functions for i N respectively. For a trader i, πi(θ ) = 1 means i holds one unit and πi(θ ) = 0 means not. p(θ ) > 0 indicates that i will pay p(θ ) to the mechanism, otherwise i will receive |p(θ )| from the mechanism. As in practice, only the traders who are properly invited can join the auction, so we should use traders report to first

1We do not consider the case that a trader can create fake neighbours, so they cannot report traders who are not their neighbours because they are not aware of each other.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

identify which traders are qualified to join the final allocation. We say trader i is qualified under θ if and only if there is at least one directed path from a trader in N0 to i in G(θ ) (a proper invitation chain from one initial trader). Let Q(θ ) be the set of all qualified agents under θ . The a special version of the double auction, called diffusion double auction, is defined to work on only qualified traders.

Definition 2 (Diffusion Double Auction). A diffusion double auction mechanism is a double auction mechanism such that for all reported type profiles θ , it satisfies:

1. for all unqualified agents i / Q(θ ), πi(θ ) = 1 if i is a seller, otherwise πi(θ ) = 0 and pi(θ ) = 0. 2. for all qualified agents i Q(θ ), πi(θ ) and pi(θ ) are independent of the types of all unqualified agents.

A feasible diffusion double auction can only allocate the items between the traders who are qualified. Besides, the number of units in the allocation should be the same before and after the allocation. We only consider feasible allocations in the rest of this paper.

Definition 3. We say an allocation π is feasible if for all traders type report profile θ :

1. for all i S , if i is unqualified, then πi(θ ) = 1; 2. for all i B, if i is unqualified, then πi(θ ) = 0; 3. P i S Q(θ ) πi(θ ) + P i B Q(θ ) πi(θ ) = |S Q(θ )|.

When an allocation is determined, social welfare can be defined as SW (θ , π) = P i S B πi (θ ) v i. Given a report profile θ and a double auction (π, p), the utility of each trader under the auction is defined as:

ui (θ , (π, p)) = πi (θ ) vi pi (θ ) i B

(πi (θ ) 1)vi pi (θ ) i S (1)

Next, we define the key properties to design a diffusion double auction. We say a mechanism is individually rational if for each trader, her utility is non-negative when she truthfully reports her valuation, no matter how many neighbors she invited and what the others do.

Definition 4. A diffusion double auction mechanism M = (π, p) is individually rational (IR) if for i N, ui((θ i = (vi, r i), θ i), (π, p)) 0 for all r i ri and for all θ i Θ i.

The most important property is incentive compatibility, which requires that reporting true type is a dominant strategy for all traders. This guarantees that each trader will not only report his valuation truthfully, but also invite all his neighbours to join the auction (in practice).

Definition 5. A diffusion double auction mechanism M = (π, p) is incentive compatible (IC) if for all i N, all θi Θi and all θ Θ , ui(θi, θ i), (π, p)) ui(θ , (π, p)).

The following property is related to the auctioneer s revenue.

Definition 6. Given a report profile θ θ and a diffusion double auction mechanism M, the revenue/profit of the market owner is defined by the sum of all buyers and sellers

payments, which is denoted by R(θ ) = P i S B pi(θ ). We say M is weakly budget balanced (WBB) if for all report profiles θ θ, R(θ ) 0. With all the notations well-defined, we will design a diffusion double auction that is IR, IC and WBB.

The Dynamic Trade Reduction In this section, we will first introduce Mc Afee s trade reduction and show why it does not work to achieve the properties in the network setting. Then we will modify the trade reduction to consider a reserve price which is the key element of our new mechanism called dynamic trade reduction. Finally, we prove that the new mechanism satisfy all the desirable properties.

Mc Afee s Trade Reduction on Network Mc Afee proposed a trade reduction mechanism for the traditional exchange setting without network (Mc Afee 1992). The idea is to remove the pair with the lowest buying and the highest selling reports from the efficient allocation to set up the payments to the other buyers and sellers. Mc Afee s trade reduction mechanism can be formally extended to the network model (which just ignores the network) as follows:

Algorithm 1: Mc Afee s Trade Reduction (MTR) Input: θ

1. Given the report profile, order all sellers according their valuation reports as v s1 v s2 v sm and all the buyers as v b1 v b2 v bn (with a random tiebreaking). 2. The efficient number of trades is the number k min{m, n} satisfying v bk v sk and v bk+1 < v sk+1. If such k does not exist, then no item will be traded (i.e., πi(θ ) = 1 for all sellers and πi(θ ) = 0 for all buyers, pi(θ ) = 0 for all traders), skip the rest process.

3. If p0 = v bk+1+v sk+1 2 [v sk, v bk], then all the first k sellers and buyers can trade at price p0. 4. Else, only the first k 1 pairs can trade where each seller receives v sk and each buyer pays v bk. Output: π, p

Theorem 1. Mc Afee s trade reduction in the network setting is not IC.

Proof. We prove it via an example in Figure 1. Assume that all traders truthfully report their types. First, order all sellers as S6, S4, S8, S5, S1, S2, S3, S7, and buyers as B5, B6, B1, B3, B4, B2. The efficient number of traders k = 5 since v S1 = 4 v B3 = 4.5 and v S2 = 4 > v B4 = 3.5.

p0 = v S2+v B4 2 = 7.5

2 / [v S1, v B3], so only 4 pairs can trade (Each buyer pays 4.5 and seller receives 4). However, S2 (not trade) will not report S4 honestly and then trade a commodity successfully (receiving 4.5). Thus, directly applying Mc Afee s trade reduction in the network setting is not IC.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Figure 1: An example of MTR not satisfying IC in a social network. Assume that all traders truthfully report their types. The circular border indicates a seller; the square border indicates a buyer; the red border indicates that this trader is in a trade, the black border indicates that this trader is not in a trade; the number in the upper right corner of each trader represents their valuation. The yellow dashed square border indicates the initial traders. The grey line indicates that the two traders it connects are neighbors. Neighbor relationships are not used in MTR.

Figure 2: An example of DTR in a social network. Other than the parts that are the same as Figure 1, the black line indicates that this line has been used for an invitation; the gray line indicates that this line has not been used for an invitation.

Dynamic Trade Reduction Although Mc Afee s trade reduction cannot be directly used in our setting because it ignores the competition between invitees and inviters, its payment policy is still useful to guarantee no deficit. One observation is that if we run the reduction only among the initial traders N0, then those traders who cannot trade now are very unlikely to trade if we get more traders involved. Our new mechanism will use this observation to dynamically involve traders in the reduction. To do so, we will need a modified version of Mc Afee s trade reduction to iteratively check which traders we can involve in the new mechanism. The modification is called Trade Reduction with Reserve Price (TRP). TRP uses a predefined reserve price pair (p s, p b) to reduce the trade, which is defined as follows.

Algorithm 2: Trade Reduction with Reserve Price (TRP) Input: sellers Ts and buyers Tb with their valuation report profile and a reserve price pair (p s, p b) 1. Let qs = |{i|v i p s, i Ts}| and qb = |{i|v i p b, i Tb}| be the quantities of sellers and buyers who satisfy the condition of the reserve prices. 2. Let q = min(qs, qb) and T P be the set of the lowest q sellers and the highest q buyers. Let T U = (Ts Tb)\T P be the untraded traders. 3. If qs > qb, let ps be the (qb + 1)-th lowest seller s valuation and pb be p b. If qs < qb, let ps be p s and pb be the (qs + 1)-th highest buyer s valuation. If qs = qb, let ps be p s and pb be p b. Output: T U, (ps, pb)

Given traders Ts Tb, TRP determines the traders who can potentially trade as T P and the untraded traders as T U who are the traders not be able to trade for sure in our new mechanism. Additionally, it also gives a new price pair (ps, pb) to separate T P and T U. It is evident that the new price pair satisfy ps p s and pb p b. Given the above trade reduction with a reserve price, we define our mechanism called Dynamic Trade Reduction (DTR). DTR uses TRP to iteratively update the reserve price pair and dynamically explore the network. The intuition behind DTR is that it decides which traders cannot trade for sure with the current set of traders, the neighbors of those traders are added to the trader set and then repeat this process until we cannot get new traders to join the mechanism. To simplify the description, we introduce a notation that computes all the neighbors for a given set of traders. Definition 7. Given a set of traders T N, we define a function R(T) = S i T r i to represent all the reported neighbors of T.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Algorithm 3: Dynamic Trade Reduction (DTR) Input: θ , S0, B0 1. Initialize T = S0 B0 and let π , p = MTR(θ T ). If i S0, j B0 such that π i (θ T ) = 0 and π j (θ T ) = 1, then let ps = p i (θ T ), pb = p j(θ T ). Otherwise, let ps = min(mini S0 v i, maxi B0 v i), pb = max(mini S0 v i, maxi B0 v i). Let TU = {i|π i (θ T ) = 1, i S0} {i|π i (θ T ) = 0, i B0}. 2. Loop: (a) T = T R(TU). (b) T U, (ps, pb) TRP(θ T \TU , (ps, pb)).

(c) If R(T U) T, terminate the loop, otherwise set TU = TU T U.

3. For all traders i Q(θ ) \ T or i TU, buyers do not receive items and sellers keep their items with zero payments, i.e.,

πi(θ ) = 1 if i is a seller 0 if i is a buyer (2)

pi(θ ) = 0 (3)

For all traders i T \ TU, the allocation π and the payment p are defined as:

πi(θ ) = 0 if i is a seller 1 if i is a buyer (4)

pi(θ ) = ps if i is a seller pb if i is a buyer (5)

Output: π, p

We provide an example depicted in Figure 2 to demonstrate how our mechanism works. In Step 1, T = N0 = {S1, S2, S3, B1, B2, B3}, i.e. S1, S2, S3 and B1, B2, B3 are initial traders. We get TU = {S3, B3} after conducting MTR and choose ps = pb = 5. In Iteration 1 of Step 2, R(TU) = {S5}, then TU = {S2, S3, B3} and ps = 4, pb = 5 after conducting TRP; in Iteration 2 of Step 2, R(TU) = {S4, S5, S6, B4, B5}, then TU = {S1, S2, S3, B3, B4} and ps = 4, pb = 5 after conducting TRP; in Iteration 3 of Step 2, R(TU) = {S4, S5, S6, S8, B4, B5, B6}, then TU = {S1, S2, S3, B3, B4} and ps = 4, pb = 5 after conducting TRP. Since R(TU) T, Step 2 terminates. Finally, T \ TU = {S4, S5, S6, S8, B1, B2, B5, B6}, all sellers sell their item and receive ps = 4, all buyers receive an item and receive pb = 5. To prove the properties of DTR, we define some symbolic representations. The initial price pair set by MTR is denoted as (p0 s, p0 b), the sets of traders who can trade or cannot trade are denoted as (T P )0 and (T U)0 respectively while initial traders are T 0, and the initial number of transactions is denoted as q0 = |(T P )0| 2 . Assume the total number of iterations of Step 2 (TRP) in DTR is k. Similarily, for all i = 1 . . . k, we define the notion (pi s, pi b),(T P )i, (T U)i, qi = |(T P )i| 2 and

T i after the i-th TRP working on sellers T i s and buyers T i b.

Theorem 2. DTR is IC and IR.

Proof. First, we show that every trader reports all her neighbors truthfully. Step 1 of DTR does not use the information of neighbors and is then naturally independent of reported neighbors for all traders. For each iteration i from 1 to k of Step 2, we consider two cases for each trader x T i after conducting the i-th TRP. Case 1: x (T P )i. (pi s, pi b),(T P )i, (T U)i and T i are independent of her reported neighbors, which also implies that the next TRP is independent of her reported neighbors. Case 2: x (T U)i. Then her report of neighbors is independent of her utility because she cannot trade for sure. Hence, all traders i T in all iterations of Step 2 will report truthfully. Second, we show that every trader reports her valuation truthfully. In the i-th iteration of TRP (specially, i = 0 represents MTR), we also consider two cases for a seller x T i. Case 1: x (T P )i. (1) if she misreports her valuation as v x < vx, she is still in (T P )i and pi s, pi b does not change; (2) if she misreports v x > vx, either she cannot trade for sure or she is still in (T P )i with pi s, pi b not changing. Case 2: x (T U)i. (1) if she misreports her valuation as v x < vx to join in (T P )i and change pi s to pi s , she will always have negative or equal utility since vx pi s pi s v x and pi s monotonically decreases (pi+1 s pi s); (2) if she misreports v x > vx, her utility is still zero. The analysis for a buyer is similar. Hence, reporting valuation truthfully is a dominant strategy in all iterations of Step 2 for all traders i T. Obviously, reports of all traders i Q(θ ) \ T are not considered. Thus, any trader has no incentive to misreport. Therefore, DTR is IC. Finally, we prove that DTR is IR. For any seller i, if i T \ TU, her utility is ps vi 0; otherwise, her utility is 0. For any buyer i, if i T \ TU, her utility is vi pb 0; otherwise, her utility is 0 = 0.

Although DTR satisfies IC, there is no positive incentive to report truthfully. This can be solved by mild extensions on DTR. Here we give one simple variation case. In new DTR, we can add a new step between Step 2 and Step 3. In this new step, all sellers (buyers) in T can invite all their buyer (seller) neighbors to join T and then run TRP one more time. After this adjustment, it is easy to prove that it still satisfies all properties shown in Theorems 2 and 3. Since the extensions complicate the proofs a lot, we do not elaborate on them here. We next prove that DTR is WBB. Not only can DTR avoid deficits, but we can also show that DTR is comprehensively superior to MTR only for initial traders (without diffusion). More specifically, we show that for the number of transactions, social welfare, and revenue, DTR is always greater than or equal to MTR for initial traders.

Theorem 3. DTR is WBB, and for the number of transactions, social welfare, and revenue, DTR is always greater

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

than or equal to MTR only for initial traders (without diffusion).

Proof. Since R(θ ) = P i B pi(θ ) + P i S pi(θ ) = P i T \TU (pb ps) 0, DTR is WBB. Next, we show that the number of transactions, social welfare, and revenue monotonically increase during each iteration of TRP in DTR. Due to the monotonically increasing property, Theorem 3 stated above can be proved. We firstly show that the number of transactions qi monotonically increases. It is easily proved that (T P )i 1 T i s T i b for each 1 i k. This result implies that (T P )i 1 S (T i s T i b) S = T i s. Thus, in the i-th iteration of TRP, qi s = |{i|v i pi 1 s , i T i s}| qi 1 = |{i|v i pi 1 s , i (T P )i 1 S}| and similarly qi b qi 1. Therefore, qi = min{qi s, qi b} qi 1, which means qi monotonically increases. Secondly, the i-th iteration of TRP lets items be assigned to the buyers with qi highest valuations from qi lowest valuations of sellers in T i. Meanwhile, since the number of transactions monotonically increases, social welfare also monotonically increases. Finally, for the revenue, since pi s pj s and pi b pj b for all i < j, (pi 1 b pi 1 s )qi 1 (pi b pi s)qi for 1 i k. Thus, revenue also monotonically increases.

Experiments

As proved in the last section, we show that the social welfare of DTR is always greater than or equal to Mc Afee s trade reduction, which is applicable exclusively to initial traders. However, to what extent DTR can enhance, and how large the gap with the optimal solution is, remain questions. Thus, we aim to evaluate the efficiency of our mechanism in increasing social welfare. This assessment involves altering the graph s connectivity and adjusting the initial number of traders. Our findings indicate that our mechanism performs effectively in both of these settings. We adopt the small-world network structure (Watts and Strogatz 1998) as the foundation of our experiments, known for its ability to effectively model real-world social networks. In each experimental group, we will compare two mechanisms (MTR for initial traders and DTR) with optimal social welfare. We run MTR among initial traders to assess our mechanism s influence on inviting other traders and compare it with the ideal result to measure the gap from optimality. The ratio between the social welfare of the two mechanisms and the optimal social welfare is used to illustrate the results.

Connectivity of Social Networks

In this experiment, we study the impact of the connectivity, denoted as c = k |N|, where the parameter k indicates the expected number of neighbors for each agent in Wattz and Strogatz s model. We maintain fixed values of |N0| = 300, |S| = |N|

2 = 500 and fixed rewiring probability pr = 0.3.

Figure 3: The changes of social welfare ratio in 1000 smallworld graphs generated for c [0, 1]. The minimum scale for c is 0.004.

The valuations of all traders are randomly selected (independently and uniformly) from the set {0, 1, 2, . . . , 10000}. The experimental results are shown in Figure 3. Given the constant value of |N0|, the average social welfare of MTR for initial traders maintains at a low level. In contrast, the average social welfare of DTR increases very rapidly and when c 0.03, the outcomes of DTR approach nearly optimal social welfare.

The Number of Initial Traders In the second experiment, we shift our focus to investigate the impact of the number of initial traders |N0|. We set |N| = 1000, c = 0.3 and fixed rewiring probability pr = 0.3 to generate networks, while also keeping |S| = |N|

2 = 500 fixed. The valuations of all traders are randomly selected (independently and uniformly) from the set {0, 1, 2, . . . , 10000}. The experimental results are shown in Figure 4. As the number of initial traders increases, the average social welfare of MTR for initial traders demonstrates a linear rise, gradually approaching the optimum level. Similar to the first experiment, the outcomes of DTR increase very rapidly and closely approach the optimal social welfare when |N0| 200. When |N0| = |N|, the average social welfare of both DTR and MTR for initial traders nearly approaches the optimal level.

Application to Multi-unit One-sided Auction Double auctions are similar to multi-unit one-sided auctions, but they present more difficulties because the number of units to be sold determined by the sellers is unknown in advance. In this section, we will illustrate that our approach, the DTR mechanism for double auctions within social networks, can also work for the multi-unit one-sided auction setting.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Figure 4: The changes of social welfare ratio in 1000 smallworld graphs generated for |N0| [5, 1000]. The minimum scale for |N0| is 1.

Multi-unit auctions in a social network address scenarios where a seller offers multiple homogeneous items for sale and only buyers are allowed to strategically report their valuations and social connections. These auctions aim to attract more buyers to increase the seller s revenue. However, designing mechanisms that satisfy the essential incentive compatibility (IC) property has been proven challenging. Previous attempts, such as GIDM (Zhao et al. 2018) and DNA-MU (Kawasaki et al. 2020), failed to ensure IC due to buyers potential manipulations for the auction outcome. Another mechanism, SNCA (Xiao, Song, and Khoussainov 2022), addressed budget constraints among buyers, but it deviates from the standard multi-unit diffusion auction. Consequently, achieving an IC mechanism remains an enticing challenge. Recent research has proposed two mechanisms that satisfy truthfulness in multi-unit diffusion auctions. The LDMTree mechanism (Liu, Lian, and Zhao 2022) employs competition localization, concentrating competition within layers of a tree based on agent distance from the seller. MUDAN (Fang et al. 2023) is an iterative mechanism that allocates items to winners during graph exploration. Different from these approaches, our mechanism offers a novel perspective on problem-solving. The key insight is that, until the final iteration, no winners and their payment can be determined during the iterative exploration. In the following, we will present the adaptation of the DTR mechanism to the setting of multi-unit one-sided auctions. Consider a scenario where there is a seller with k items, and all buyers are connected in a single network. In this scenario, each buyer intends to purchase only one item. To set up a double auction mechanism, we introduce a set N0 comprising not only initial buyers but also k dummy sellers, each offering one item. These dummy sellers possess zero valuation for the item without neighbors, and the buyers neighbors are other buyers. In this setup, the DTR

can be directly employed to address the multi-unit problem. We provide the formal description as follows:

Algorithm 4: Dynamic Trade Reduction for Multi-unit Auction (DTR4MA) Input: the report profile of all buyers θ B, the set of initial buyers B0, and the number of units k. 1. Let S0 be k dummy sellers and their report profile is θ S0 where θ i = (0, ) for i S0. 2. π, p = DTR(θ B S0, S0, B0). 3. The actual seller s revenue is the sum of all the buyers payments. Output: π, p

We ve established earlier that DTR is an incentivecompatible (IC), individual-rational (IR), and weakly budget-balanced (WBB) mechanism. This extends to the multi-unit scenario as well. As a result, our approach offers an alternative mechanism that ensures IC in multi-unit auctions, presenting a valuable solution for such cases.

To the best of our knowledge, this is the very first work in designing a double auction mechanism over social networks, where all traders (sellers and buyers) are distributed within a single social network. We propose a solution to incentivize traders to invite each other to join the auction and do not give the market a deficit. Especially, our mechanism can also solve the multi-unit one-sided auction problem easily. This gives us a hint that our approach has the potential to be extended to more general combinatorial settings. To design the invitation incentive, the main technique used by the existing mechanisms relies on that an agent can gain the payment difference when the agents invited by the agent won the items (a kind of resale process). This technique is not scalable to combinatorial settings (Zhao 2022). Our technique is very different from this main approach, and it dynamically determines who cannot win for sure and allow them to invite their neighbors to join the auction. Since an agent cannot win anyway, it does not hurt to invite others, but it may also not bring any positive utility to invite others. This could be compensated by manually adding some positive incentives. We believe that our approach could be extended to design multi-item auctions on networks, which is a very challenging open question.

Acknowledgments

This work is supported by Science and Technology Commission of Shanghai Municipality (No. 23010503000 and No. 22ZR1442200), Shanghai Frontiers Science Center of Human-centered Artificial Intelligence (Shang HAI) and the Key Laboratory of Intelligent Perception and Human Machine Collaboration (Shanghai Tech University), Ministry of Education.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

References Clarke, E. H. 1971. Multipart Pricing of Public Goods. Public Choice, 11: 17 33. Fang, Y.; Zhang, M.; Liu, J.; Khoussainov, B.; and Xiao, M. 2023. Multi-unit Auction over a Social Network. ar Xiv:2302.08924. Friedman, D.; and Rust, J. 1993. The Double Auction Market: Institutions, Theories and Evidence. 14. Groves, T. 1973. Incentives in Teams. Econometrica, 41(4): 617 631. Guo, Y.; and Hao, D. 2021. Emerging Methods of Auction Design in Social Networks. In Zhou, Z., ed., Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, 4434 4441. Kawasaki, T.; Barrot, N.; Takanashi, S.; Todo, T.; and Yokoo, M. 2020. Strategy-Proof and Non-Wasteful Multi Unit Auction via Social Network. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, 2062 2069. Kawasaki, T.; Wada, R.; Todo, T.; and Yokoo, M. 2021. Mechanism Design for Housing Markets over Social Networks. In AAMAS 21: 20th International Conference on Autonomous Agents and Multiagent Systems, 692 700. Li, B.; Hao, D.; Gao, H.; and Zhao, D. 2022. Diffusion auction design. Artificial Intelligence, 303: 103631. Li, B.; Hao, D.; Zhao, D.; and Zhou, T. 2017. Mechanism Design in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). Liu, H.; Lian, X.; and Zhao, D. 2022. Diffusion Multi-unit Auctions with Diminishing Marginal Utility Buyers. Co RR, abs/2201.08616. Liu, H.; Lian, X.; and Zhao, D. 2023. Diffusion Multi-unit Auctions with Diminishing Marginal Utility Buyers. In Agmon, N.; An, B.; Ricci, A.; and Yeoh, W., eds., Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2023, London, United Kingdom, 29 May 2023 - 2 June 2023, 2715 2717. Mc Afee, R. 1992. A dominant strategy double auction. Journal of Economic Theory, 56(2): 434 450. Vickrey, W. 1961. Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance, (1): 8 37. Watts, D. J.; and Strogatz, S. H. 1998. Collective dynamics of small-world networks. nature, 393(6684): 440 442. Xiao, M.; Song, Y.; and Khoussainov, B. 2022. Multi-Unit Auction in Social Networks with Budgets. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5): 5228 5235. Yang, T.; Zhai, Y.; Zhao, D.; Li, M.; and Song, X. 2022. One-Sided Matching with Permission. Ar Xiv, abs/2201.05787. Yoon, K. 2001. The Modified Vickrey Double Auction. Journal of Economic Theory, 101(2): 572 584.

You, B.; Dierks, L.; Todo, T.; Li, M.; and Yokoo, M. 2022. Strategy-Proof House Allocation with Existing Tenants over Social Networks. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 1446 1454. Zhang, Y.; and Zhao, D. 2022. Incentives to Invite Others to Form Larger Coalitions. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 1509 1517. Zhao, D. 2021. Mechanism Design Powered by Social Interactions. In AAMAS 21: 20th International Conference on Autonomous Agents and Multiagent Systems, 63 67. Zhao, D. 2022. Mechanism Design Powered by Social Interactions: A Call to Arms. In Raedt, L. D., ed., Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, 5831 5835. 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, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, 68 76.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)