Project Topics
Get Complete Project Material File(s) Now! »
Targeting in Social Networks with Anonymized Information (joint with Francis Bloch1)
Abstract
This paper studies whether a planner who only has information about the net-work topology can discriminate among agents according to their network position. The planner proposes a simple menu of contracts, one for each location, in order to maximize total welfare, and agents choose among the menu. This mechanism is immune to deviations by single agents, and to deviations by groups of agents of sizes 2, 3 and 4 if side-payments are ruled out. However, if compensations are allowed, groups of agents may have an incen-tive to jointly deviate from the optimal contract in order to exploit other agents. We iden-tify network topologies for which the optimal contract is group incentive compatible with side-payments: undirected networks and regular oriented trees, and network topologies for which the planner must assign uniform quantities: single root and nested neighborhoods directed networks.
Introduction
Anonymizing personal and social data before they can be shared or used seems like a promising avenue, because it presumably preserves privacy without depriving the soci-ety from the benefits of data analysis. As is known from the statistical and computer science literature, privacy-preserving data disclosure can be achieved in multiple ways, from a com-plete elimination of any identification of the individual (anonymization) to algorithmic and statistical methods to avoid identification (differential privacy). The recent advances in pri-vacy protection, together with the fast development of data sharing and data disclosure raises the following question: How valuable are anonymized data (rather than full individ-ual data) for a third party whose objective is not aligned with the welfare of individuals? When will the third party be able to achieve the same value with anonymized data and with the full, personal and social data?
Anonymized social data describe the network topology, the architecture of the network without specifying the identity of agents at different nodes. For example, anonymized social network data can be geo-data describing a network of roads and houses with no specifica-tion of the inhabitants, or an organizational chart for a company or a criminal organization with no identification of the individuals, or a snapshot of a fraction of a large digital so-cial network (Twitter, LinkedIn or Facebook) with lacunary evidence on the identity of the nodes.
We suppose that the social network describes local positive externalities in the choices of agents, and consider a third party whose objective is to maximize total surplus. The third party could be a monopolist, selecting discriminatory prices to exploit local consumption externalities (by lowering the price to stimulate consumption of individuals generating im-portant externalities), or a firm who wishes to maximize output, when the social networks describes synergies in efforts by pairs of workers. In particular, agents have linear quadratic payoffs, yielding linear best-responses. In the presence of local network externalities, the objective of the planner and of individuals are not aligned: the planner internalizes positive externalities that an agent produces on other agents, raising consumption (in the case of the monopolist) or effort (in the case of the firm) beyond the optimum of individuals.
A planner can observe anonymized social data but does not know the identity of agents. To be more precise, anonymized social data are modeled by an unlabeled network structure, where each vertex corresponds to the location of a given agent, whose identity is not known to the planner. Hence there exists a one-to-one mapping between the set of locations in the network and the set of agents. We assume that each agent only knows her location in the network. Hence the set of possible types is the set of all permutation of identities (labels) over the set of locations (vertices). The planner offers a menu of contracts (quantities or efforts), corresponding to the decisions at each location. Locations are correlated, in the sense that two agents can not occupy the same location and each can be assigned a single location in the network.
When full data are available, the planner can target agents and offer them the exact con-tract which maximizes her objective. But when the planner only knows the network topol-ogy, she is only able to offer a contract for each location in the network, with no certainty that agents will indeed choose the contract corresponding to that location. This is the incen-tive problem we study in this paper, where we analyze for which network architectures this incentive constraint is binding or not.
We first observe, unsurprisingly, that correlation in the locations of agents allows the planner to achieve his first-best outcome when agents can only make unilateral deviations. Indeed, because the set of locations in the network is fixed and finite, if the planner proposes a menu of contracts, one for each location, and all other agents pick the contract correspond-ing to their location, the deviating agent must be selecting the same contract as another agent. The planner can use this evidence to ascertain that one of the agents has lied, and punish all agents (for example by offering a level lower than any agent’s optimum), thereby ensuring that all agents have an incentive to choose the contract corresponding to their true location.1
We thus turn our attention to joint deviations, where subsets of agents decide to “lie” about their locations, and choose contracts which do not correspond to their true position in the network. Given that the objective of the planner is to maximize social surplus, why do groups of agents have an incentive to “lie” about their locations and exchange their con-tracts? Why would an agent who already receives a consumption or effort level above her optimal choice accept to exchange her contract with another agent with a higher level? The answer to these questions stems from the fact that, by exchanging their contracts, agents are able to increase the externalities they receive from other agents, while reducing the externalities they create for agents outside the deviating coalition. For example, consider a directed network architecture where the hub of the star (the “influencer ») produces positive consumption externalities on all other agents but receives no externalities in return. The planner, internalizing this externality, assigns a very high consumption to the hub, and a lower consumption to a peripheral agents. But the hub may have an incentive to exchange her contract with a peripheral agent, increasing her utility by reducing her consumption level, at the expense of all other peripheral agents, who now receive a much lower level of externalities.
The first main Proposition of the paper asserts that, when the size of the deviating group is two, three or four, the optimal contract is in fact immune to deviations by groups of agents. The proof of the Proposition in the case of pairwise deviations is clear. For an agent to accept to exchange her contract for a higher one (e.g. for a peripheral agent to accept the high level of the hub), whereas her current contract is already too high given the contracts of other agents, she must receive higher externalities in return from the members of the deviating coalition. But when a pair of agents deviates, the externalities inside the deviating coalition do not change, as agents only exchange their contracts and the externality they exert on each other remains the same. Hence, in any pairwise deviation, absent any compensation, the agent with the lower contract must be unwilling to exchange her contract with the other agent.2
Based on this observation, we consider a more restrictive group incentive compatibility condition, by allowing agents in the deviating coalition to make side-payments. Under this condition, a contract is group incentive compatible if no coalition, by choosing a permuta-tion of the announcements of their locations, can increase the sum of utilities of its members. In the particular context of a linear-quadratic game, we show that this condition is equiva-lent to assuming that, whenever an agent i has a higher contract than an agent j, the sum of externalities received by agent i must be at least as large as the sum of externalities received by agent j.
This characterization drives the second main result of the paper. When externalities are reciprocal (the graph representing the social network is undirected), then the optimal con-tract of the planner is immune to group deviations with side-payments. The intuition underlying this result is that an agent will receive a higher contract in the first-best if and only if she is more central (in the sense of Katz-Bonacich) than the other agent. But this centrality measure is defined recursively: an agent has a higher Katz-Bonacich centrality if and only if the sum of the Katz-Bonacich centralities of her neighbors is higher. In other words, when influence is reciprocal, an agent with a higher contract in the first-best is also an agent who receives (and produces) higher externalities, and the sum of utilities of the agents cannot increase through an exchange of contracts.
The situation changes dramatically when externalities are asymmetric. We next focus on directed networks with a hierarchical structure: the set of agents can be partitioned into an ordered collection of subsets (or tiers of the hierarchy) such that agents at higher tiers influence agents at lower tiers, but agents at lower tiers never influence agents at higher tiers. In this family of hierarchical social networks, we first show that the optimal contract is group incentive compatible when side-payments are ruled out. But when agents in a deviating coalition can make side-payments, we uncover two situations where the optimal contract of the planner cannot be sustained.
First, when there exists one agent who influences all other agents the single root and the number of tiers is larger than two, then in an optimal contract which is immune to group deviations with side-payments, all agents in tiers lower than two must receive the same contract as the root. The intuition is as follows: if the root receives a higher contract than agents at lower tiers, there is an incentive to exchange the higher quantity of the root with the lower quantity of the lower tier agent, as the latter receives externalities but not the former. Hence, any contract which is immune to deviations by groups with side-payments must assign a lower contract to the root than to agents at tiers lower than two.3 However, as the root produces externalities on all other agents, whereas other agents may not influence or be influenced by all other agents, the planner also has an incentive to increase the contract of the root with respect to the contract of any other agent. Hence, at the optimum, the contract of the root must be exactly equal to the contract offered to all agents at tiers lower than two. Notice that this implies that targeting is impossible, and may result in large efficiency losses with respect to the first-best.
Second, suppose that neighborhoods are nested, so that an agent at a lower tier is influenced by all agents who also influence agents who influence him. Multiple roots can exist, and agents can be connected to multiple roots, but the structure of nested neighborhoods implies that the set of influencers of an agent is included in the set of influencers of the agent she influences. Assume furthermore that the size of the tiers is increasing: there are strictly more agents at lower tiers. In this hierarchical structure, as in the case of single roots, we show that the optimal contract is not group incentive compatible with side-payments, and that any root has an incentive to exchange her contract with an agent at lower tier. As in the case of a single root, the planner would like to increase the quantity of the root, so that the optimal contract which is group incentive compatible with side-payments results in a uniform contract for all agents.4 Again, the group incentive compatibility constraint is binding, and induces a total inability to discriminate among agents. Finally, we consider a hierarchical structure where the optimal contract is immune to deviations by coalitions making side payments: regular oriented tree. In these structures, ev-ery agent is influenced by a single other agent; namely, the social network is an oriented tree. Furthermore, the number of agents influenced by an agent at any given tier is identical across agents of the same tier, and strictly decreasing with the tier. This is what we call a “regular » oriented tree. In that specific hierarchy, agents at higher tier must have a higher contract than the agents they influence, because every agent they influence receives his ex-ternalities from his immediate predecessor, but the predecessor receives externalities from other agents. When the structure is regular, the planner will also want agents at higher lev-els of the hierarchy to receive higher contracts, so that the first-best contract is indeed group incentive compatible with side-payments.
Our results thus show that the optimal contract of the planner is immune to deviations by groups whenever influence is reciprocal, or agents at higher levels of the hierarchy receive more influence than agents at lower levels of the hierarchy. When on the other hand agents at higher levels of the hierarchy produce more influence but receive less influence than agents at lower tiers, the first-best contract is susceptible to group deviations, and the plan-ner may in extreme cases be forced to assign a uniform contract to all agents. These results thus show how the architecture of the network matters to determine whether anonymized data are sufficient or not for the planner to implement the first-best.
We also explore the robustness of our results with respect to the assumptions made in the model. First, we note that we put a very strong restriction on the structure of deviat-ing coalitions by assuming that they are adjacent (i.e. any pair of agents in the deviating coalition must be connected by a link). Absent this restriction, more coalitions can deviate and in fact, even in the case of undirected networks and regular oriented trees, the first-best contract may become impossible to implement.
Second, we analyze the effect of increasing the complexity of the contract, by allowing the planner to extract information about agents’ local neighborhood. We show that if the planner can collect information about an agent’s neighbors’ identity, the first-best contract becomes immune to group deviations with side-payments. Finally, we explore what hap-pens when the planner knows the identity of some agents in the network. For example, sup-pose that the network knows the identity of the main influencers (the roots of the directed social network). We show through an example that this partial information may greatly help the planner and allow him to discriminate much more effectively among the agents.
Related literature. Our paper is related to the study of targeting in social networks, as surveyed in Bloch [22]. The linear-quadratic model of interaction in networks we consider was introduced in Ballester, Calvo-Armengol and Zenou [10]. General problems of targeting where the planner seeks to maximize social welfare in the presence of complementarities have been recently studied by Demange [43] and Galeotti, Golub and Goyal [50].
The problem of a monopolist pricing in the presence of local consumption externalities has first been studied by Candogan, Bimpikis and Ozdaglar [33] and Bloch and Quérou [23]. Candogan, Bimpikis and Ozdaglar [33] and Bloch and Quérou [23] both look at the relation between the centrality of consumers in a given network and the prices and quantities they are offered by a monopolist; in the context of perfect knowledge of the network structure. They both show that when the network is undirected – that is two directly connected con-sumers influence each other equally – consumers are offered quantities proportional to their Bonacich centrality for the same price. Fainmesser and Galeotti [45] consider a monopo-list which can price discriminate based on her knowledge of either the in-degrees of con-sumers (their influence), the out-degree of consumers (their susceptibility to influence) or both. They show that the knowledge of in-degree (respectively out-degree) is more valuable when the dispersion in in-degrees (respectively out-degree) in the network is higher.
A handful of recent papers extend the analysis of monopoly pricing and targeting to situ-ations of incomplete information. Jadbabaie and Kakhbod [63] consider the pricing problem when the strength of influence among agents is private information. Ata, Belloni and Can-dogan [8], take a different approach and assume that there is a seller who faces two groups of agents: observable and latent. There are local consumption externalities among mem-bers of the same group and across groups. The seller can observe past purchasing decisions only of the group of observable agents and can try to deduce from these observations in-formation on influence patterns. Finally, in a paper which shares our motivation about the planner’s incentives to elicit information about the network, Shi and Xing [90] consider a model where buyers draw their in and out-degrees independently from a common distri-bution. They characterize the optimal contracts in the framework of random graphs. The novelty in our model is to introduce incomplete information with regard to the network it-self by assuming that the structure is observable but the locations or identities of agents is private information.
The model
Agents, utilities and network effects
We consider a set N of agents (labeled “he »), indexed by i = 1; 2; ::; n. Agents are connected in a social network, which we represent by a graph g, with nodes i = 1; 2; ::n and edges gij 2 f0; 1g. We denote by G the adjacency matrix of the graph g.
Each agent i chooses an action xi 2 R+, which will be interpreted as his consumption or effort. The utility of agent i depends on his action and the actions of his neighbors in the social network. Following a well-established model, initiated by Ballester, Calvo-Armengol and Zenou [10], we assume that utilities are quadratic, so that Ui = aixi xi +gijxixj; where > 0 is a strictly positive externality parameter.5 For the main part of the analysis, we assume that all agents are identical, except for their location in the social network. For homogeneous agents, ai = a and we normalize bi = b = 1 so that 5With > 0, the payoff function yields a game of pure complements. However, had the the externality parameter been strictly negative, the payoff function would yield a game of pure substitutes (e.g. Cournot game with n firms) and our results would change substantially. For a discussion, see Bramoulle and Kranton (2016) [32].
The planner’s first-best
We consider a planner (labeled “she ») with perfect knowledge of the network g who chooses the vector of actions x = (x1; ::xn) in order to maximize the sum of utilities of the agents, V = Ui = axi 1xi2 + gijxixj; (1.1) where > 0. The first-order conditions result in a system of linear equations: a xi +(gij + gji)xj = 0 j2N
Letting 1 denote an n 1 vector of ones, 0 an n 1 vector of zeros and I the n n identity matrix, we can rewrite the above conditions in matrix6 form: a1 Ix + (G + GT )x = 0:
Let denote the largest eigenvalue of the matrix real symmetric matrix (G + GT ). Fol-lowing Ballester, Calvo-Armengol and Zenou [10] we compute the optimal solution of the planner’s problem as the solution to the system of linear equations when external effects are not too large,
Proposition 1.1 If 1 > the optimal solution of the planner ’s problem is given by x = (I (G + GT )) 1a1:
Next recall that the Katz-Bonacich (Katz [70] and Bonacich [27]) centrality measure (R; ) of an agent in a matrix of relationships R with discount factor , is the discounted sum of walks originating from that agent. Formally, for < 1 where is the largest eigenvalue of R, It is easy to check that, the planner’s solution is to assign to each agent i an action which is proportional to its Katz-Bonacich centrality measure in the network (G+GT ) under discount factor > 0, x / ((G + GT ); ):
Hence the optimal choice of the planner is to assign discriminatory actions to the agents, in proportion to their Bonacich centrality measure in the network7 (G + GT ). We now ob-serve that the planner’s general problem encompasses different situations of pricing and targeting in networks.
Pricing with network externalities
Consider, as in Candogan, Bimpikis and Ozdaglar [33] and Bloch and Quérou [23] a mo-nopolist setting prices on a market where consumers experience positive consumption ex-ternalities. For simplicity, assume that the monopolist faces a constant marginal unit cost c. Consumer i’s utility depends both on his own consumption and on the consumption of his neighbors in the social network. If the monopolist sets a unit price pi to consumer i, and offers a quantity xi, the utility of the consumer is given by Ui = axi 1xi2 + gijxixj pixi:
Assuming that the monopolist can fully discriminate among consumers, she will select a price pi to capture the entire surplus of the consumer and make a profit X X 1 xi2 X = (pi c)xi = (a c)xi + gijxixj ; an objective function which is equivalent to the objective function V in equation (1.1) after a renormalization.
Targeting and efforts
Next we consider as in Galeotti, Golub and Goyal [50] the decision xi chosen by an agent with utility function Ui = axi +gijxixj:
The planner intervenes by subsidizing or taxing the marginal stand-alone utility of the effort, resulting in a^i = a + ti, where ti is the tax or subsidy of agent i. Any intervention leading to a change from a to a^i will result in a change in the effort level xi. Hence an intervention can be interpreted as a choice of decisions xi to maximize the sum of utilities of the agents V = axi xi2 +gijxixj :8
Network architectures and information structure
Proposition 1.1 characterizes the first-best solution when the planner has complete informa-tion on the social network. We now introduce the constraints faced by the planner when she only has access to anonymized information on the network architecture. To be more pre-cise, vertices in a network correspond to locations ‘ = fl1; l2; : : : ; lng. There is a one-to-one mapping which assigns to each agent in the set N = f1; 2; : : : ; ng a unique location in the network. This mapping is unknown to the planner and this is precisely how we model anonymized information. Hence, the set of types is the set of all permutations of agents in the set N over locations ‘; which is exactly the set of all vertex-labelled graphs. Formally, the planner observes a network structure, which we denote by g^(‘), where an identif ier in ‘ is assigned to each vertex. Agents (i) know their own location, that is a given agent i knows at which location in ‘ he is at, and (ii) observe the locations in ‘ that correspond to his neighborhood and the neighbors of neighbors, without knowing the identity of any of them.
A menu of contracts
In the benchmark case, we restrict the planner to offer a menu of contracts. The planner offers a menu of contracts x(^g(‘)) = fx‘1 ; : : : ; x‘n g, corresponding to the decisions at each location in the observed network structure g^. Every agent then selects a contract among the menu x(^g(‘)) = fx‘1 ; : : : ; x‘n g. If all agents select different contracts, each agent obtains the contract he selected. Otherwise, if several agents select the a contract for the same location, the planner punishes all agents and chooses an outcome x(^g(‘)) f0g.
The menu of contracts x(^g(‘)) = fx‘1 ; : : : ; x‘n g is to ex-post incentive compatible for any network structure g^, whenever agents have an incentive to select the contract intended for their location rather the contract designed for any other location.
Table of contents :
Introduction (English)
Introduction (Français)
1 Targeting in Social Networks with Anonymized Information
1.1 Introduction
1.2 The model
1.2.1 Agents, utilities and network effects
1.2.2 The planner’s first-best
1.2.3 Network architectures and information structure
1.2.4 A menu of contracts
1.2.5 Efficient incentive compatible contracts
1.2.6 Group incentive compatible contracts
1.3 Undirected Networks
1.4 Hierarchical Networks
1.4.1 Single root
1.4.2 Nested neighborhoods
1.4.3 Regular Oriented Trees
1.4.4 Connected agents at the same tier of the hierarchy
1.5 Robustness and Extensions
1.5.1 Nonadjacent agents
1.5.2 Richer information structures and mechanisms
1.5.3 Partial information
1.5.4 Heterogenous marginal returns to own efforts
1.6 Conclusion
1.7 Appendix
1.7.1 Proof of proposition 1.4
1.7.2 Proof of proposition 1.5
1.7.3 Proof of proposition 1.7
1.7.4 Proof of proposition 1.9
2 Hidden Opinions
2.1 Introduction
2.2 Related work in social psychology
2.2.1 Hidden Profiles
2.2.2 Dynamic social Impact theory
2.3 The model
2.3.1 Set-up
2.3.2 Expression heuristic
2.3.3 Micro-foundation
2.4 Opinion Dynamics
2.4.1 Long-run opinions of expressers
2.4.2 The process of interpersonal influence
2.4.3 Patterns of long-run opinions: consensus and bi-polarization
2.5 Network topology and opinion patterns
2.5.1 Example
2.5.2 Agregate statistics
2.6 Conclusion and the way forward
2.7 Appendix
2.7.1 Proof of Proposition 2.1
2.7.2 Proof of Proposition 2.2
2.7.3 Proof of Lemma 2.1
2.7.4 Proof of Theorem 2.1
2.7.5 Proof of Proposition 2.3
2.7.6 Proof of Lemma 2.2
2.7.7 Network Statistics
2.7.8 Eigenvector centrality
3 Strategic cultural migration with peer effects
3.1 Introduction
3.2 Historical context
3.2.1 Migration decision: The procedure
3.3 The model
3.3.1 Set-up
3.3.2 The game
3.3.3 Equilibrium outcomes
3.4 Empirical evidence
3.4.1 Data
3.4.2 Definition of proxy variables
3.4.3 Empirical Strategy
3.4.4 Results
3.5 Conclusion
3.6 Appendix
3.6.1 Proof of Lemma 3.1
3.6.2 Proof of proposition 3.1
3.6.3 Beyond the Italian Border
Bibliography
