Mechanism Design Powered by Social Interactions: A Call to Arms

1 Introduction

Mechanism design studies how to implement desirable social choice functions in a strategic environment where participants behave strategically [Borgers et al., 2015]. Since the seminal work of Vickrey [Vickrey, 1961], the field has been extensively studied and influenced many domains such as auctions [Groves, 1973; Myerson, 1981; Myerson and Satterthwaite, 1983], social choice [Gibbard, 1973; Satterthwaite, 1975], matching [Shapley and Scarf, 1974; Gale and Shapley, 1962], cooperative games [Shapley, 1953] etc. The studies have also guided the development of many important applications such as online ad auctions, spectrum auctions, school-student matching, and kidney exchanges.

The task of mechanism design is to design mechanisms (aka information games) to achieve desirable properties. For example, in auctions, to maximize social welfare or revenue; in voting, to incentivize voters to report their preferences truthfully; in matching, to incentivize participants to act according to their true preferences; and in coalitional games, to incentivize players to cooperate together. For different settings, we have different techniques such as monetary transfer in auctions and resource exchange in matching to achieve these properties.

Almost all the settings of mechanism design have assumed that the players are independent, which makes many theories hardly applicable in practice [Ausubel and Milgrom, 2006]. In reality, players may know each other and can collude to manipulate the mechanisms. Although it is impossible to avoid collusion in theory, we could explicitly use the connections between players as a new dimension in the design. Especially, we can use their connections to attract new players to achieve better outcomes which is a new trend [Zhao, 2021].

The new challenge is that players are competitors in these games and they would not invite each other under the existing solutions such as Vickrey-Clarke-Groves (VCG) [Groves, 1973], top trading cycle (TTC) [Shapley and Scarf, 1974], and the Shapley value [Shapley, 1953]. Therefore, we need new solutions to offer the invitation incentives.

We have seen some primary results in incentivizing the existing players of a game to invite new players in auctions, matching and coalitional games [Li et al., 2017; Li et al., 2022; Yang et al., 2022; Zhang and Zhao, 2022]. On one hand, the early results showed the value of the new trend. On the other hand, it is very difficult to extend the results from simple settings to general settings. Thus, we discuss the difficulties here, especially in auctions, matching, and coalitional games.

2 The Model

We study a game with n players, denoted by N, and they are connected to form a connected (social) network. Each player i ∈ N has a private type θi = (ri, ti), where ri ⊆ N is i's neighbors (with whom i can directly communicate and i does not know the others N \ ri) in the network and ti is i's other private information defined for the specific game. For example, in a single-item auction, ti is i's valuation for the item. In a house allocation, ti is i's preference on all exchangeable houses. While ti varies in different games, ri stays the same in a given network.

In the game, we assume that only a subset of the players are initially in the game, which is the reason why we need them to invite the others to join the game. The assumption is practical because in reality, when a market owner starts a game, he simply cannot reach everyone on the network by himself. Thus, traditionally, the owner can pay search engines or social platforms to reach more people. Here, we consider a different promotion strategy by incentivizing the existing players to use their connections to invite new players. As discussed above, rational players would not invite others to compete with them. Thus, we need to give them incentives, which is the key challenge of this problem.

The mechanism we are going to design is an information game which requires each player to report his private information. Note that, as not all players are in the game initially, some of the players will be excluded from the game if they are not invited. However, this will make the mechanism and the related properties hard to define, if the number of participants is dynamic. A clean way to handle this mathematically is to assume everyone reports his type and the mechanism decides which reports can be used. The reports from players who are not invited can be treated as their reports once they are invited.

Definition 1. A mechanism takes all players' reports as input and outputs an outcome o from an outcome space O defined for the game. We say a mechanism is a diffusion mechanism if the outcome does not change the status of the players who are not invited and it is independent of their reports.

The general definition of a mechanism is not different from traditional settings and the only difference is that the input space contains their connections. The connections can be used in many different ways, while we specifically use their connections for inviting each other, which is called diffusion mechanism.

Definition 2. We say a mechanism is incentive compatible (IC) if for each player, reporting his type truthfully is a dominant strategy.

Incentive compatibility is the key property we want to achieve here. If a diffusion mechanism is incentive compatible, then players are incentivized to invite all their neighbors to join the game (i.e., reporting their true neighbor set). In the following, we will discuss the challenges to achieve the property in auctions, matching and coalitional games.

3 Auctions

The first diffusion mechanism proposed in a single-item auction used the idea of resale [Li et al., 2017]. In traditional solutions such as second price auction, a winner does not want to invite a buyer who has a higher valuation than his, because the high-value buyer will take the item away from the winner. To solve this conflict, we allow the original winner to resell the item to the high-value buyer. By doing so, even if the original buyer did not win the item in the end, his utility is actually higher than winning the item. Thus, inviting more neighbors will potentially bring the inviter a higher utility.

Following the first mechanism, there were two significant extensions trying to extend the setting from single-unit supply to multi-unit supply [Zhao et al., 2018; Kawasaki et al., 2020]. Zhao et al. [2018] used the idea of resale, while Kawasaki et al. [2020] used the idea of inviting more buyers increases the chance of winning the item for the inviter.

However, both extensions are not completely incentive compatible. Then, Liu et al. [2022] proposed another mechanism based on the idea of resale to a more advanced setting of multi-unit supply and multi-unit demand. Their mechanism has to remove many buyers to compute the allocation for each buyer. These studies showed that designing good diffusion mechanisms in general settings is challenging.

1 To further elaborate the difficulties to design an incentive compatible diffusion mechanism in the general setting, let's consider a very simple setting of selling two items {A,B} with four buyers shown in Figure 1. S node is the seller and each buyer has a three-dimensional valuation for receiving A, B and {A,B} respectively. If buyer b2 does not invite b3 and b4, then any non-dummy and anonymous mechanism that does not use fixed/reserve prices would allocate {A,B} to b2 and charge b2 10 (critical payment, the minimal valuation report to win {A,B}). If we apply the resale technique to design the invitation incentive, then b2 can invite b3 and b4 and resell A to b3 and B to b4. However, the payments from b3 and b4 together is less than 10, i.e., b2 is losing by reselling. The payments of b3 and b4 are also critical payments 1 . The fact that the resale price of {A,B} is less than what b2 has paid is related to the property of revenue monotonicity [Rastegari et al., 2007]. The property says if we add more buyers into the auction, the revenue of the seller should not decrease. In the above example, if we simply run VCG with four buyers, the revenue of the seller is 3+4, while if we just run it with buyers b1 and b2, the revenue is 10. This is also related to false-name manipulations [Yokoo et al., 2001]. If there are just two buyers b1 and b2 in the game, then b2 would have to pay 10 to get {A,B}. If b2 creates two fake players b3 and b4, then they together can still get {A,B} but pay less. Thus, IC here is coupled with revenue monotonicity and false-name-proofness which are already very hard to achieve.

Definition 3 ([Rastegari et al., 2007]). A mechanism is revenue monotonic if the seller's revenue is guaranteed to weakly decrease as buyers are dropped.

Definition 4 ([Yokoo et al., 2001]). A mechanism is falsename-proof if truth-telling without using false-name identities is a dominant strategy for each buyer.

We conjecture that if a diffusion mechanism is incentive

1 Even if b2 only resells one of the two items, say, A, then the critical payment of b3 becomes 9, which is greater than b3's valuation and also depends on b2's valuation (clear violation of IC).

6

No Author Given Early Career Track

compatible and the seller does not run in a deficit 2 , then in most cases the mechanism is revenue monotonic. Rastegari et al. [2007] proved that in traditional settings, when a mech-

Definition 5 ([Rastegari et al., 2007]). A mechanism satisfies participation if it does not charge a buyer who does not receive any item. It satisfies criticality if any single-minded buyer wins when her bid is greater than a critical value that depends only on the other buyers' reports, and loses if her bid is less. It satisfies maximality if it chooses an allocation that cannot be augmented to make some buyer better off, while making none worse off.

anism satisfies three sensible conditions, it cannot be revenue monotonic and false-name-proof. Fig. 1: An example of social network. Preferences are h3 ≻1 h2 ≻1 h1, h1 ≻2 h2 h3, h1 ≻3 h3 ≻3 h2. Figure 2: A one-sided matching exmaple with three players {1, 2, 3} and their preferences are h3 ≻1 h2 ≻1 h1, h1 ≻2 h2 ≻2 h3, h1 ≻3 h3 ≻3 h2.

Table 1: All possible allocations of figure 1. This table shows under certain preference whether an allocation satisfies specific properties. PO stands for Pareto optimal allocations. items from the subtree rooted at her (not just her neighbors). This extension enlarged the matching space, but it cannot be generalized in general networks.

Theorem 1 ([Rastegari et al., 2007]). For a combinatorial setting with at least two items and three buyers, any incentive compatible mechanism that satisfies participation, criticality, and maximality is not revenue monotonic (false-name-proof).

The three conditions, participation, criticality, and maximality, are sensible requirements in traditional settings, but in the network setting, they are not all necessary. For exmaple, we may not charge a buyer who does not win an item, but we can pay him for inviting others. The critical value to win an item is not necessarily the payment to receive the item (for example, the IDMmechanism does not charge the critical value [Li et al., 2017]). Therefore, the impossibility is not

stands for whether the allocation is given by TTC. SCC stands for stable under complete co nents allocations. SWCC stands for stable under weakly complete component allocations. Instead of restricting agents' matching choices under TTC to avoid competitions, Yang et al. [2022] proposed another

directly applicable to the network setting. Theorem 2 (Impossibility for Stability, IC and IR). Given a social network G( and a type profile ⇥, there does not exist a diffusion matching mechanism that sati stability, incentive compatibility and individual rationality. favourite items, they do not care the match of the rest, so their remaining neighbors can be shared with the others. By doing so, the players matched later will have more choices than just their neighbors. This mechanism significantly improves the matching quality compared with the extensions of TTC.

novel mechanism which allows each agent to have a chance to be matched with anyone in the network. The idea behind their method is that when a group of agents are matched with their

Except for finding general IC mechanisms, another challenge is maximizing the seller's revenue [Myerson, 1981]. For example, in a single-item auction, Myerson's optimal mechanism gives an upper bound of the revenue, but it is not achievable with IC here. Proof. Consider the example given in Figure 1, the allocations that satisfy our rede stability are a3 and a6. For allocation a3, agent 1 can misreport her preference as h3 h1 ≻01 h2 to negate this stable allocation(as shown in Table 2, a3 is not stable). In way, the only stable allocation will be a6, which agent 1 prefers compared to a3. In matching, we also care about another two properties called optimality and stability. We discuss them in one-sided matching in the following. Definition 6. A matching mechanism is optimal if the allo-

4 Matching

In traditional one-sided and two-sided matching, we have the classic solutions such as top trading cycle (TTC) [Shapley and Scarf, 1974] and deferred acceptance [Gale and Shapley, prefers compared with a6. In conclusion, for all the stable results, agents have incent to misreport their types to gain better allocations. Thus, stability is incompatible IC and IR. within the group only without making anyone in the group worse off, and at least making one of them better off.

allocation a6, agent 2 can deny this outcome by misreporting type as (h1 ≻2 h2 h3, {1}) to unqualify agent 3, so the only stable allocation will be a3, which age cation of the matching cannot be improved without making anyone worse off. It is stable if there does not exist a subset of the players who deviate from the matching and match

1962]. Both methods are not incentive compatible in the netIt is easy to show that under the network setting, any IC matching mechanism cannot be optimal or stable.

show that players in TTC are not incentivized to invite each other. Definition 8 (Blocking Coalition under Complete Components). Given an all In reality, people would not be able to form any coalition if they do not know each other. Therefore, in the network set-

work setting, because players are competitors. In one-sided matching, TTC does the following: "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 above until there is no agent left." It is easy to Since the stability is incompatible with IC property in social network setting try to restrict the stability to make it possible for a mechanism to satisfy both of two properties. One way is to further restrict the blocking coalitions from conne components to complete components. We will show that the newly defined stabili achievable with IC. Theorem 2 ([Yang et al., 2022]). In one-sided matching, it is impossible to have a diffusion mechanism that is incentive compatible and optimal (stable). The above definitions of optimality and stability are the standard ones which do not consider the network structure.

Consider a simple network shown in Figure 2 with three players {1, 2, 3} where 1 connects to 2 and 2 connects to 3. If we apply TTC, 1 and 3 will exchange. However, if only 1 and 2 are in the market and 3 needs 2's invitation, then 2 would not invite 3 so that 1 and 2 can exchange. tion ⇡(✓) 2 ⇧, we say a set of agents S ✓ N (with items set HS ✓ H) is a bloc coalition for ⇡(✓) if S forms a complete component in G(✓) and there exists an all tion z(✓) 2 ⇧ such that for all i 2 S, zi(✓) 2 HS and zi(✓) ⌫i ⇡i(✓) with at least j 2 S, zj(✓) ≻j ⇡j(✓). ting, we can require each coalition is a connected component. However, even under this restriction, it is still impossible to have it with incentive compatibility [Kawasaki et al., 2021; Yang et al., 2022]. If we further restrict the coalition structure to be a fully connected component, then it is achievable

In order to incentivize existing participants to invite others who are not in the matching game yet, we need to guarantee that invitees will not make their inviters worse off. One way is to add restrictions on TTC. For example, we only Definition 9 (Stability under Complete Components(SCC)). Given a certain cation ⇡(✓), if there is no blocking coalition under complete components for it, we the allocation ⇡(✓) is stable under complete components. with IC [Yang et al., 2022]. However, this turns out to be the best stability we can obtain with IC. We have a good reason to add constraints on stability, but we do not seem to have a proper reason to limit optimality.

2 If we do not care the revenue of the seller, then simple extension of VCG is incentive compatible.

We could add similar constraints like an allocation A1 dominates another allocation A2 further requires that the players who receive different items in A1 and A2 have to form a (fully) connected component. Although this restriction is not intuitive, it may help us to figure out what optimality we could achieve under IC.

The challenge is harder in two-sided matching. In traditional two-sided matching, the deferred acceptance can only have IC for the proposers. In the network setting, we need to consider different combinations, e.g., can men invite men, women or both? Men invite women or women invite men is beneficial for them, but the difficulty is inviting people from your own side.

5 Coalitional Games

1 In traditional coalitional games, there is no private information from the players, and we have a public characteristic function v which defines the value of each coalition. One goal is to find a reward distribution to incentivize all players to form the grand coalition [Peleg and Sudh¨olter, 2007].

In the network setting, we want to incentivize the existing players to invite their neighbors to join their coalition. We assume that the game is monotonic, i.e., adding more players to the coalition is not harmful [Driessen, 2013]. Even though new players may increase the total value of the coalition, it may reduce the reward share of the existing players. Therefore, players may not want to invite new players.

Shapley value is a well-known distribution mechanism satisfying many desirable properties [Shapley, 1953]. It computes the average marginal contribution of each player to join all possible coalitions in the game. Core is another important property, and we say a distribution is in the core if no subset of players can deviate from the grand coalition to receive better rewards [Scarf, 1967]. Shapley value is computable for all coalitional games, but core may not exist for certain games.

Consider a very simple example of two players P1 and P ′1 shown in Figure 3. Assume that initially only player P1 is in the game and P ′1 requires P1's invitation to join in. Then under Shapley value P1 would not invite P ′1 , because P1's reward is reduced from x to x/2 after inviting P ′1 .

In the above example, if we want to incentivize P1 to invite P ′1 , we should guarantee that P1's reward is non-decreasing after inviting P ′1 . Thus, the reward to P ′1 should be zero. In case P ′1 brings an extra value y, then P ′1 can receive at most y. However, if we give y only to P ′1 , then there is no positive incentive for P1 to invite P ′1 . Therefore, to have a positive incentive for P1 to invite P ′1 , there are infinite number of ways to share y among them, which is the solution called weighted permission Shapley value proposed by Zhang and Zhao [2022].

One interesting open question is to characterize all incentive compatible reward distribution mechanisms. Zhang and Zhao [2022] showed the weighted permission Shapley value class is the only IC mechanism for query networks. In general networks, we have more ways to share the reward to achieve IC.

Theorem 3 ([Zhang and Zhao, 2022]). The weighted permission Shapley value mechanisms characterize all incentive compatible mechanisms in query networks under some mild conditions.

Another challenge is to define IC mechanisms that are also in the core. In traditional settings, core has to make sure that any subset of players have no incentive to deviate from the grand coalition. However, in the network setting, not any subset can form a coalition and one minimal requirement is that they have to be connected (otherwise, they need others' permission to form a coalition). This makes many nonconnected deviations not feasible and helps us to find core mechanisms. On the other hand, as invitees have to share their marginal contribution to their inviters to have a positive incentive, this seems a direct conflict with the definition of the core. If a connected group of invitees can achieve a higher value without joining the grand coalition, then they will deviate. However, the question is whether invitees can form coalitions alone, if we assume that the initial players are the owners of the game. Then, we could further require that each deviation should contain some of the initial players.

6 Other Settings

In the above three settings, we utilized players' connections to attract new players. There are also many other ways to use the connections. For example, in social networks, there is a classic study of choosing influential players [Kempe et al., 2003], where the connections are used to measure the influence of players on the network. Since the selection might be beneficial for the selected players, they may misreport their connections to manipulate the selection [Alon et al., 2011; Zhang et al., 2021]. However, the solutions to prevent such manipulations are only found for simple networks such as trees and DAGs to select one single player. The solutions basically assign a selection probability distribution to a set of players who are potential influencers. However, these mechanisms may not work to select more than one influencer with a good performance.

In a cost-sharing problem to connect nodes on a graph to a source (e.g., connect villages to a power station), we have many different ways to allocate the costs to connected nodes [Moulin, 1999]. In this problem, some nodes might need to go through other nodes to reach the source. If the intermediate nodes' cost is increased for linking the others, then the intermediate nodes would prefer to disconnect them. Therefore, we need to design a cost allocation mechanism to incentivize the players to share their connections. This is related to coalitional games and the Shapley value can be applied with a proper definition of the characteristic function [Kar, 2002; Zhang et al., 2022].

Acknowledgments

I am grateful to Luc De Raedt and J´erˆome Lang for their kind invitation and to my team and my collaborators for their excellent contributions cited in this paper.