• Setting

We consider a single-item auction in a social network, where each person in the network is a potential customer, and each edge represents a relationship between two customers. In order to increase participation in the auction, we want to give existing participants an incentive to invite more people.

• Main Idea

Resale

• Method

Firstly, identify the diffusion critical node path, in which all nodes must be passed from the seller to the highest bidder in the social network. Then, offer the item along the critical path and each node in the path pays the highest bid (without the buyer participating). Any nodes in the path will stop passing the item if the payment of the next node is less than or equal to the bid of the current node.

• Setting

A seller sells K ≥ 1 homogeneous items and each buyer requires at most one item (single-unit demand) in a social network.

• Main Idea

Resale

• Method

It is a generalized mechanism from IDM. A node will receive an item if and only if she wins under the efficient allocation when her top K-highest valued children do not compete in the auction. Then, her utility is the difference in social welfare between the situations in which her top K-highest valued children do not participate and herself and all her children do not participate.

• Setting

A seller sells K ≥ 1 homogeneous items and each buyer requires at most one item (single-unit demand) in a social network.

• Main Idea

Layer-Based

• Method

Firstly, order all buyers based on their shortest distance to the seller, where buyers with shorter distances have higher priorities. Then, traverse all buyers according to their priorities, and for each buyer, she wins an item with the second-price payment if her bid is among the K'-highest bids without all her children (K' is the number of remaining items). We stop the traversal until all items are sold.

• Setting

A seller sells K ≥ 1 homogeneous items and each buyer has a marginal diminishing valuation (multiunit-demand) in a social network.

• Main Idea

Resale and layer-based

• Method

Firstly, divide buyers into different layers based on their shortest disatnce to the seller. Then, transform the graph-network into the tree-network by deleting the edges between buyers in each layer and randomly remain one edge between each buyer and her parent node. When considering the allocation and payment of buyers in each layer, LDM will remove the potential competitors in the next layer and all buyers below the next layer. Finally, find an allocation that maximizes social welfare in the remaining buyers and a buyer's payment is the difference of social welfare before and after her participation, and compute the allocation and payment for buyers layer by layer until the items are sold out.

[1] Li, B., Hao, D., Zhao, D., & Zhou, T. (2017, February). Mechanism design in social networks. In Thirty-First AAAI Conference on Artificial Intelligence.

[2] Zhao, D., Li, B., Xu, J., Hao, D., & Jennings, N. R. (2018, July). Selling Multiple Items via Social Networks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (pp. 68-76).

[3] Kawasaki, T., Barrot, N., Takanashi, S., Todo, T., & Yokoo, M. (2020, April). Strategy-proof and non-wasteful multi-unit auction via social network. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 02, pp. 2062-2069).

[4] Liu, H., Lian, X., & Zhao, D. (2022). Diffusion Multi-unit Auctions with Diminishing Marginal Utility Buyers. arXiv preprint arXiv:2201.08616.

A cooperative game in the social network is a game where players are connected to form a network and not all players are aware of the game initially. In real-world applications, their connections can represent friendship or leadership. A person who is in the coalition can invite her friends who are not in the coalition yet to join. Without the invitation, these friends will not be informed of the coalition. A larger coalition can increase utility. The question is how to motivate players to invite their friends and distribute the utility among them.

• Main Idea

Average marginal contribution

• Method

Shapley value is defined as the expected marginal contribution of a player to all coalitions by selecting players with equally probabilities.

Shapley value has many pretty properties in the traditional setting, but it can not incentivize the players to invite others.

• Main Idea

Layer-Based

• Method

Layered Shapley value calculates the expected marginal contribution of the players in each layer using the standard Shapley value, but assumes that all the players in the prior layers have already joined the coalition before them. This ensures that players who are closer to the initial players will have higher priorities to get rewards.

• Main Idea

Permission-based

• Method

In a permission structure, a player needs permission from all (or at least one) of her predecessors in order to cooperate with other players. In this sense, a coalition is feasible if and only if for each player in the coalition, all (or at least one) of her predecessors are also in the coalition. Hence, we can redefine the valuation of each coalition with the valuation of its largest feasible subset. With the modified characteristic function, we can compute the permission Shapley value for each player.

• Main Idea

Permission-based + weight

• Method

By assigning weights to players and sampling the players with probabilities proportional to their weights, we can compute the weighted Shapley value. Combining the permission Shapley value and the weighted Shapley value, we can get the weighted permission Shapley value.

[1] Shapley, L. S. (1953). A value for n-person games, Contributions to the Theory of Games, 2, 307–317.

[2] Zhang, W., Zhang, Y., & Zhao, D. (2020, May). Collaborative Data Acquisition. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (pp. 1629-1637).

[3] Gilles, R. P., Owen, G., & van den Brink, R. (1992). Games with permission structures: the conjunctive approach. International Journal of Game Theory, 20(3), 277-293.

[4] Gilles, R. P., & Owen, G. (1999). Cooperative games and disjunctive permission structures. Tilburg, the Netherlands: Tilburg University.

[5] Kalai, E., & Samet, D. (1987). On weighted Shapley values. International journal of game theory, 16(3), 205-222.

[6] Zhang, Y., & Zhao, D. Incentives to Invite Others to Form Larger Coalitions. (To appear at AAMAS 2022)

• TTC

• Description

Top Trading Cycle (TTC) Mechanism is a classical solution for the traditional one-sided matching.

TTC: Construct a directed graph by the preference of each agent: each agent points to the agent who has her favorite item remaining in the matching. There is at least one cycle. For each cycle, allocate the item to the agent who points to it and remove the cycle. Repeat the process until there is no agent left.

• Social Network Setting

• There are n agents, and each agent has a house.

• Each agent has a strict preference over all the houses.

• Each agent has neighbors, and each agent can only join the market by the invitation of her neighbors.

• The failure of TTC in social network setting.



Agents may not invite to get a better house.

• Swap With Neighbors (SWN)

• Description

For social network setting, one trivial extension is called Swap With Neighbors (SWN), which only allows agents to swap with their neighbors under TTC.

SWN: Construct a directed graph by the preference of each agent: each agent points to her favorite item among herself and her neighbors remaining in the matching. There is at least one cycle. For each cycle, allocate the item to the agent who points to it and remove the cycle. Repeat the process until there is no agent left.

• Swap With Children (SWC)[1][2]

This mechanism only works in trees.

• Intuition

By restricting the network to trees and allowing each agent to swap with her sub-tree, we make sure that an agent can only trade with her neighbors' neighbor if her neighbor is also contained in this matching.



• Description

SWC: Construct a directed graph by the preference of each agent: each agent points to her favorite item among herself, her neighbors, and her descendants remaining in the matching. There is at least one cycle. For each cycle, allocate the item to the agent who points to it and remove the cycle. Repeat the process until there is no agent left.

This mechanism works in any networks.

• Intuition

Agents can only exchange with neighbors. When a group of agents are matched (leave the market), their remaining neighbors will be regarded as each other's neighbors as well (shared).

• Description

• A random order of agents is given in advance.

• Agents are pushed into a stack according to the order. The Agent in the stack top can point to the owner of her favorite house in neighbors. Specially, the agent can point to the agent in the stack bottom. Then the agent she points to will be pushed into the stack. Continue this process until agent i points to an agent j who is already in the stack. Then agents in the stack between j and i can exchange their houses and leave the market.

• Once the stack is empty, for those agents who left the market, connect their neighbors. Repeat the above procedure until there is no agent left.

[1] Kawasaki, T., Wada, R., Todo, T., & Yokoo, M. (2021, May). Mechanism design for housing markets over social networks. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (pp. 692-700).

[2] Zheng, Y., Yang, T., Zhang, W., & Zhao, D. (2020). Barter Exchange via Friends' Friends. arXiv preprint arXiv:2010.04933.

[3] Yang, T., Zhai, Y., Zhao, D., Li, M., & Song, X. (2022). One-Sided Matching with Permission. arXiv preprint arXiv:2201.05787.

• Setting

The root node wants to find an answer to some questions. She incentivizes her neighbours to find the answer holder among their children. The parents of the answer holder will get a reward.

• Method

To incentivize invitation, each node is offered a reward by its parent, and offers a (smaller) reward to its children. The search down each branch stops when the reward reaches 0, or when a node with an answer is reached. There exists a Nash Equilibrium where each node will invite all her neighbours, and the reward amount is defined by a computable function g(x). Each agent will offer g(x) to its children on receiving x, where g(x) is the amount that maximize her expected utility.

• Setting

There is a bitcoin transaction, and miners can try to "authorize" a transaction. The root node uses a reward distribution scheme to invite more miners aware of this transaction. Once there is a node success to authorize it, agents in the chain from seed to node are all rewarded.

• Method

(β,H)-almost-uniform scheme was used to incentivize miners to broadcast the transaction. In this scheme, we should find the chain from seed to the winner, with length l. If l ≤H, then the winner is rewarded 1+(H-l+1)β, other nodes in the chain get β. If l>H, no nodes get rewards. Under this scheme, each node’s dominant strategy is full propagation and no duplicate.

• Setting

The sender provides a monetary reward by a lottery, which all participants have equal chance to win. Initially, only the sender's friends are in the game.

However, the sender wants to invite as more participants as possible to join the game.

• Method

Initially, each node only has a small probability to win. She can increase her utility by inviting her friends to join. If one of the friends wins, she withholds part of the reward and gives the remaining part to the winner. In this way, she can increase her winning chance by expanding her subtree. Other nodes will adopt the same strategy to increase the expected utility. This work designs a free market, where each participant can invite any of her neighbours and decide by herself the amount of reward to withhold. There is a Nash Equilibrium where each agent invites all friends and withholds a sufficiently small amount of rewards.

• Setting

The sponsor has a monetary budget and is willing to propagate some information via social networks. The goal is to design a budget distribution scheme where all of the budgets is distributed, and each agent has an incentive to invite all neighbours.

• Method

The agents are divided into layers according to their distance from the sponsor in the graph. Then use peer pressure to inspire competition among agents, hence incentivising them to do further propagation. When an agent propagates, she will get a reward from her competitors. Her reward must be given to other agents at the same time. Adopting this method to all layers, the budget distribution mechanism is IC, IR and budget balance.

• Setting

The setting is similar as before, except the reward provided by the sponsor is heterogeneous, each agent may have different value to different parts of the resource.

• Method

The agents are also divided into layers. Initially, the resource is randomly allocated to the first layer's agents. For each layer k in the graph, find all edges that start at layer k and end at layer k+1. Then we visit these edges and reallocate the resource of other agents in layer k to edges' end points. This mechanism incentivizes agents not only to invite all neighbours but also to report their true valuation to the resource. A minimum utility is guaranteed for each agent even if she does not invite anyone.

[1] Kleinberg, J., & Raghavan, P. (2005, October). Query incentive networks. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) (pp. 132-141). IEEE.

[2] Babaioff, M., Dobzinski, S., Oren, S., & Zohar, A. (2012, June). On bitcoin and red balloons. In Proceedings of the 13th ACM conference on electronic commerce (pp. 56-73).

[3] Chen, J., & Li, B. (2021). Maximal Information Propagation via Lotteries. arXiv preprint arXiv:2110.10606.

[4] Shi, H., Zhang, Y., Si, Z., Wang, L., & Zhao, D. (2020). Maximal Information Propagation with Budgets. In ECAI 2020 (pp. 211-218). IOS Press.

Given a network with all agents, how to select the first k (k≥1) influential agents by their reported relationships?

The motivation for this research comes from many scenarios, for example, the selection of the most influential user on Twitter. Challengingly, the agents always attempt to make themselves chosen by misreporting their true relationships, and hence, incentive compatible (IC) mechanisms are required.

Naturally, there are two different approaches to satisfy IC: deterministic mechanisms and probabilistic mechanisms.

Definition: map a given graph on the set of agents to a k-subset of selected agents.

Alon et al.[1] have proved that deterministic k-selection mechanisms by in-degree keep IC and good finite approximation ratios if and only if all n agents are selected, i.e. k=n.

There is no follow-up study so far.

Definition: map a given graph on a probability distribution on all possible k-subsets of agents (or all subsets with no more than k agents).

The current research can be divided into three categories according to different measures of influence.

• From In-degree Perspective

Select agents with as high in-degrees as possible.

• The Random m-partition Mechanism[1]

• Setting

In any directed graphs, agents can add or hide their edges arbitrarily. We want to select k (k≥1) agents.

• Method

(Random partition) Divide all agents into m subsets randomly, and agents can only be selected by those from the other subsets. Then select the first k/m agents with the highest in-degrees in each subset.

• The Permutation Mechanism[2]

• Setting

In any directed graphs, agents can add or hide their edges arbitrarily. We want to select the most influential agent (k=1).

• Method

(An extend version of the random partition method) Given a random permutation of all agents, traverse them and compare the in-degree of the current agent with the agents before her one by one. Initially, the agent ranking first in the permutation is selected. If the current pointed agent's in-degree (only count edges from agents before her except the selected one) is not less than the selected agent, then update the selected agent (the current max in-degree is updated as all edges from agents before her); If not, maintain the selected agent.

• From Diffusion Perspective

Select agents with high influential indices as possible. Here, the influential index of a node is intuitively proportional to the probability that a random walk with a random start on the graph passes the node.

• The Two Path Mechanism[3]

• Setting

In any directed graphs*, agents can add or hide their edges arbitrarily. We want to select the most influential agent.

• Method

Inspired by the friendship paradox, i.e. neighbors always have better diffusion influence in expectation, we start two independent random paths from two randomly chosen agents in the network. If the two paths intersect, then the agent on the first intersection will be selected; If not, then delete all agents in the related paths and do the above process repeatedly. Obviously, an agent is more likely to be selected if more random walks can reach her.

*The two path mechanism is only IC on the family of DAGs. For general graphs, it needs to randomly delete edges to make them be acyclic. Moreover, it only has a good approximation in the cases of trees or forests.

• From Progeny Perspective

Select agents with high progenies (i.e., the number of her descendants) as possible.

• The Babichenko Mechanism[4]

• Setting

In any directed forests (the roots are sink nodes), agents can add or hide their edges arbitrarily. We want to select the most influential agent (k=1).

• Method

Give a selection probability distribution to influential nodes in the forest. An agent in the network is an influential node if she has the maximum progeny after deleting all her out-edges.

• Geometric Mechanism[5]

• Setting

In any DAGs, agents can only hide their edges arbitrarily. We want to select the most influential agent (k=1).

• Method

Similar to the Babichenko Mechanism, give selection probability distribution to influential nodes in the DAG. In addition, agents' manipulation spaces are restricted: an agent can only report a subset of her real out-edges.

[1] Alon, N., Fischer, F., Procaccia, A., Tennenholtz, M.: Sum of us: Strategyproof selection from the selectors. In: Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge. pp. 101-110 (2011).

[2] Fischer, F., Klimm, M.: Optimal impartial selection. SIAM Journal on Computing 44(5), 1263-1285 (2015).

[3] Babichenko, Y., Dean, O., Tennenholtz, M.: Incentive-compatible diffusion. In: Proceedings of the 2018 World Wide Web Conference. pp. 1379-1388 (2018).

[4] Babichenko, Y., Dean, O., Tennenholtz, M.: Incentive-compatible selection mechanisms for forests. In: EC'20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020. pp. 111-131. ACM (2020).

[5] Zhang, X., Zhang, Y., & Zhao, D. (2021, September). Incentive Compatible Mechanism for Influential Agent Selection. In International Symposium on Algorithmic Game Theory (pp. 79-93). Springer, Cham.

• Setting

Consider a group of agents located at different points and there is also a source. The agents need to connect to the source directly or indirectly in order to get a service or information. The cost of connecting any pair of agents is known and the total cost of connecting them has to be shared among all connected agents. The question is how to allocate the total cost among all connected agents.

• Method

The setting is modelled as a weighted undirected complete graph where the nodes represent the agents and the source, the edge represents the connection between two nodes and the weight represents the cost to connect them.

The value function v(S) is the minimum total cost of connecting all the agents in S. Note that it cannot use the agents outside S to compute v(S). The method is described as follows. First, for each subset of all agents, compute the value function. Second, compute each agent's Shapley value (i.e. cost share) using value functions.

• Setting

The setting is similar with that of Kar solution. The difference is that each agent's strategic behaviour is considered.

To connect with the source, an agent may need to go through other agents. The intermediate agents can strategically block the connections if blocking the connections can reduce their cost share. The question is how to allocate the total cost to prevent such strategic behaviour, i.e. each agent is incentivized to share all its adjacent edges.

• Method

The setting is modelled as a weighted undirected graph where the nodes, edges and weights have the same meanings as those of the Kar solution. The key idea of the AMC solution is that each agent pays an average marginal cost to connect the agent to the source.

The value function v(S) represents the minimum total cost of connecting all the agents in S. Note that it can use the agents outside S to compute v(S). Then compute each agent's Shapley value (i.e. cost share) using value functions.

• Setting

The setting is same as that of AMC solution. The only restriction for each agent is that it has limited budgets, which is not considered in the AMC solution.

• Method

The key idea of the SCS solution is that each agent's cost share is computed in terms of its savings which is the difference between its budgets and the total cost.

The value function v(S) represents the savings of S. Formally, v(S)=the sum of all nodes' budgets in S' - the cost of the minimum spanning tree of the graph induced by the set of S' and s, where S' is a subset of S. Then we compute each agent's Shapley value using value functions. Finally, each agent's cost share is the difference between its budgets and Shapley value. If an agent has lower budgets, it cannot be selected and its cost share is 0.

Here is a running example of the solution.



First, compare the node B's budget with the weight of edge (s,B). Since 9>7, node B can be selected. Second, compare the node A's budget with the weight of edge (A,B). Since 12>8, node A can be selected. Similarly, we get that nodes C and D can also be selected. Next, compute the value functions. For example, when S={A,B} $, the set of selected nodes is S'={A,B}. Then we have v({A,B}) =6. Thus, the Shapley values of agents A-D are 4,3,0.5,0.5. Finally, the cost shares of agents A-D are 8,6,6.5,5.5.

The SCS solution are truthful, budget feasible, budget balanced and cost monotonic.

[1] Kar, A. (2002). Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior, 38(2), 265-277.

[2] Zhang, T., Zhao, D., Zhang, J., & Gu, S. (2022). Cost Sharing for Connectivity with Budget. arXiv preprint arXiv:2201.05976.