Empathetic Social Choice on Social Networks
Contents
1. We have obtained the original data sets from www dublincountyreturningofficer com a 0 05 0 1 0 25 0 5 0 75 Borda 26 0 58 7 25 0 55 8 22 2 53 0 15 1 42 5 7 3 28 8 Plurality 28 8 59 8 26 7 58 1 22 7 J 53 8 16 9 46 9 7 8 31 3 Table 4 Average NSWL decision disgreement global vs intrinsic varying a u 0 05 0 1 0 25 0 5 0 75 Borda 27 6 59 2 24 3 54 9 21 3 52 3 15 6 42 5 8 1 31 1 Plurality 27 2 58 6 24 5 55 5 23 3 54 7 16 5 46 1 8 0 31 5 Table 5 Average NSWL decision disgreement global vs intrinsic a drawn from truncated Gaussian mean u and std dev 0 1 100 a global vs intrinsic Plural S 90 global vs local Plural wawa S local vs intrinsic Plural 80 global vs intrinsic Borda suum 2 global vs local Borda 22 s 9 70 local vs intrinsic Borda seses oO is 60 50 g 40 B D 30 oO A 20 E 10 F zZ j 2 Zz Zz N x N N fo Oz 2o 29 Figure 3 Average NSWL m 10 varying y hierarchical orientation as often found in economic e g supply chain organizational management employee struc ture and even some social networks e g forms of status following etc We replace each undirected edge in the pref erential attachment network with a directed edge from the younger node to the older2. The older node reciprocates with a directed edge to the younger with probability y If y 1 our standard bidirectional network results as above when y 0 we obtain a completely hierarchical network Fixing m 10 Fig 3 depicts NSWL for both Borda and plurality as y varies Networks that are more hierarchical have higher NSWL for the global vs intrinsic models in dependent of the scoring rule while NSWL for local vs in trinsic is almost constant However plurality seems more susceptible to increasing loss due to hierarchical structure than Borda for all three combinations Unlike earlier re sults when the network is very hierarchical e g y 0 the global and local models do not approximate each other well Number of Iterations of ICE Finally we examine how the self loop weight a affects the expected number of iter ations required by the ICE algorithm We fix m 5 and vary a Fig 4 illustrates estimated social welfare for each alternative in one representative run a 0 25 Borda scor ing this instance of ICE converges in 24 iterations with computation time under 2 ms despite the large number of voters Alternative a4 is eliminated at iteration 16 a5 at 17 ai at 20 and a2 at 24 leaving ag as optimal Note that the relative order of the alternatives is unchanged after 6 iterations suggesting early termination as a robust means of approximation Table 6 shows the average number of it erations for various a
3. Social and economic networks play a fundamental role in facilitating interactions and behaviours between individuals businesses and organizations It is widely acknowledged that the behaviors and to a lesser extent preferences of individuals connected in a social network are correlated in ways that can be explained in part by network structure 13 16 24 Because of this and the increasing availabil ity of data that allows one to infer such relationships the study of social choice group decision problems on social networks is one of tremendous practical import Arguably Appears in Alessio Lomuscio Paul Scerri Ana Bazzan and Michael Huhns eds Proceedings of the 13th Inter national Conference on Autonomous Agents and Multiagent Systems AAMAS 2014 May 5 9 2014 Paris France Copyright 2014 International Foundation for Autonomous Agents and Multiagent Systems www ifaamas org All rights reserved 693 Craig Boutilier Department of Computer Science University of Toronto Ontario Canada cebly cs toronto edu most group decision problems whether social corporate or policy oriented involve people at least some of whom are linked via myriad social ties These ties may provide strong clues as to the preferences of individuals which can then be used to facilitate preference aggregation and implement a social choice function or make a group decision Despite these natural connections social choice within so ci
4. alternative Things are more subtle in the global empathetic model Computing the utility vector u a for alternative a requires solving a linear system to find the fixed point of Eq 2 A unique solution is not guaranteed to exist however in addition to our assumptions above of non negativity i e W gt 0 and normalization i e X p Wjk 1 for all j a third mild condition on the social network W is sufficient to ensure a unique fixed point solution namely positive self loop wjj gt 0 for all j Let D be the n x n diagonal matrix with dj wjj We can write Eq 2 as u a W D u a Du a 4 As a consequence PROPOSITION 1 FIXED POINT UTILITY Assuming non negativity normalizaton and positive self loop Eq 4 has a unique fixed point solution u a I W D Du a Proofs of all results are included in an online appendix As in the local model SWM in the global model can be seen as weighted maximization of intrinsic preference COROLLARY 1 In the global empathetic model global social welfare of alternative a is given by swg a u w u where w e I W D 7 D Once again in scoring rule based voting contexts one can view the global empathetic model as trading off one s own satisfaction for a winning alternative with the overall sat isfaction of one s neighbors not merely their intrinsic pref erence Fig 1 c illustrates the distinctions when either Borda or pl
5. gt 4a a network and preferences b local empathetic weights c global empathetic weights Figure 1 A social network with ranked preferences with weights under the local and global empathetic model Using Borda or plurality based utility the consensus winner is different in each model a under intrinsic b under local empathetic c under global empathetic 2 4 Related Models and Concepts The term empathy is used in several different ways in the literature 17 Sometimes it refers to seeing the world through the eyes of others without being affected by this view and such preferences 6 or extended sympathy 36 3 is used to frame interpersonal comparison of utilities 23 6 However our model is more consistent with an affective understanding of another and having concern for that per son s welfare 29 or having other regarding preferences 26 Empathy has recently drawn attention in neuroeco nomics and social neurosience 38 to study the extent people can place themselves in the position of others and share an other s feelings This further motivates computational study of empathy and its application to social choice The impact of others actions and utilities is considered in some economic models see e g accounts of envy sympa thy empathy in various contexts 30 26 6 Most closely related to our work is the model of Maccheroni et al 30 who establish the axiomatic fou
6. time In general matrix inversion is no harder than matrix multiplication 14 Thm 28 2 but its complexity cannot be less than O n since all n entries must be computed Therefore straightforward computation of a in the global model cannot have complexity less than O n nm For large n e g voting in large cities Facebook Twitter algorithms that scale linearly or better in n are needed Many iterative methods have been proposed for matrix in version and solving linear systems e g Jacobi Gauss Siedel which have O n complexity in sparse systems per iter ation and tend to converge very quickly in practice We now describe one technique that exploits a standard Jacobi method for computing a in the global model We consider a simple iterative method for computing u a Let u a be the vector of the estimated utilities of a after t iterations THEOREM 1 Consider the following iteration ut a W D u a Du a Assuming nonnegativity normalizaton and positive self loop this method converges to u a the solution to Eq 4 For each j M the method computes ul a wyjuj a X wru a kA 5 OVO y ae where u a is agent j s estimated utility for a after t iter ations This scheme has a natural interpretation suppose that each agent repeatedly observes her friends revealed utilities and updates her own utility for various options in response This process will con
7. Empathetic Social Choice on Social Networks Amirali Salehi Abari Department of Computer Science University of Toronto Ontario Canada abari cs toronto edu ABSTRACT Social networks play a central role in individual interactions and decision making While it is recognized that networks can correlate behaviors and preferences among connected agents relatively little work has considered mechanisms for social choice on such networks We introduce a model for so cial choice specifically consensus decision making on so cial networks that reflects dependence among the utilities of connected agents We define an empathetic social choice framework in which agents derive utility based on both their own intrinsic preferences and the satisfaction of their neigh bors We translate this problem into a weighted form of clas sical preference aggregation e g social welfare maximiza tion or voting and develop scalable optimization algorithms for this task Empirical results validate the effectiveness of our methods and the value of empathetic preferences Categories and Subject Descriptors 1 2 11 Artificial Intelligence Distributed Artificial In telligence Multiagent Systems J 4 Social and Behavioral Sciences Economics and Sociology General Terms Algorithms Economics Human Factors Theory Keywords Social Choice Social and Economic Networks Voting Pref erence Aggregation Empathy Decision Making 1 INTRODUCTION
8. al networks has received until recently relatively little at tention Recent work has examined for example the forma tion of hedonic coalitions on social networks 12 11 social network games 37 coalition structure generation 39 and stable matching on social networks 7 4 The influence of social networks on voting behavior has received attention in the social sciences 2 33 10 and the emergence of online so cial networks has spawned research on mechanisms for vote delegation 8 This paper considers the problem of consensus decision making or group recommendation on social networks such as voting over some option space Specifically we wish to select a single option from a set of alternatives for some group of individuals connected by a social network e g a local constituency electing a political representative or friends selecting a vacation spot or a movie While indi viduals have personal intrinsic utility over the options we also incorporate a novel form of empathetic utility on social networks the utility or satisfaction of an individual with an alternative a is a function of both her intrinsic utility for a and her empathetic utility for the happiness of her neigh bors Empathetic utility in this sense reflects the fact that a person s happiness may be influenced by the happiness of others with whom they are connected 18 This inherent in terdependency of agent utilities is captured in the econom
9. cision mak ing process fully transparent We present the model using SWM but draw connections to weighted voting In the local model determining the weights associated with each agent s intrinsic preference is straightforward As sume network weights W Let u a be the n vector of agent utilities to be computed as a function of the corresponding vector u a of intrinsic utilities for a fixed alternative a By Eq 1 u a Wu a Letting w e W where e is a vector of ones the local social welfare of a is w u a 3 Thus SWM under the local model is simply weighted max imization of intrinsic preferences where the weight of j s intrinsic utility wj is the sum of its incoming edge weights Fig 1 b shows the weights derived for each agent under the local model Using preference rankings and any scoring rule e g Borda plurality k approval etc to determine intrin swi a u 695 sic utilities the decision may be different in the local model than when only intrinsic preferences are used e g for both Borda and plurality a wins in the intrinsic model while b wins in the local model see Fig 1 a and b Indeed using score based voting rules we can readily interpret this model as a form of empathetic voting where the weight one assigns to a neighbor can be interpreted as the extent to which one would trade off one s own preferences with that neighbor s intrinsic satisfaction with the winning
10. e consider the specific case in which these influences are induced by con nections in a social network though the notion need not be confined to networks We focus on utility functions rather than preference rankings since these allow the direct ex pression of quantitative tradeoffs between intrinsic and em pathetic preference We assume a directed weighted graph G W E over agents with an edge jk indicating that 7 s utility is depen dent on its neighbor k s preference with the strength of dependence given by edge weight wj A loop jj indicates that 7 s utility depends on her own intrinsic preferences at certain points below we assume that all such loops exist We assume wjk gt 0 for any edge jk and gt gt wjx 1 for any j We treat missing edges as having weight 0 thus rep resent G with a weight matrix W wij We generally think of these edges as corresponding to some relationship in a social network see Fig 1 a for an illustration We consider pure consensus social choice scenarios in which a single option a is selected We take j s utility for a to be a linear combination of its own intrinsic preference for a and the empathetic preference derived from each of its neighbors j M where weights determine the relative im portance of each neighbor General non linear models are possible also Letting ej a denote the empathetic utility derived by j from k define j s utility u a to be uj a wj
11. e to both intrinsic and empathetic preferences We do not require agents to compute such combined preferences indeed they need not even have knowledge of their neigh bors preferences Instead agents specify only their prefer ences for options and the extent to which they care about their neighbors satisfaction the latter potentially estimated from social network structure We describe methods for computing optimal options under the local and global mod els The former unsurprisingly corresponds to a simple form of weighted preference aggregation or voting in which each agent implicitly delegates a portion of her vote to her neighbors The latter because individual utilities are co dependent indeed utility spreads much like PageRank values 34 requires the solution of a linear system to deter mine the optimal fixed point option We describe mild conditions under which such fixed points exist and show that it too results in a form of weighted voting Experi ments demonstrate the effectiveness of our algorithms and show that in some settings ignoring empathetic preferences results in suboptimal decisions and high social welfare loss 2 SOCIAL EMPATHETIC MODEL We outline our basic social choice model describe our empathetic models and discuss related work 2 1 The Social Choice Setting Apart from empathetic preferences on a network the so cial choice framework we adopt is standard We assume a set of a
12. for Borda and plurality In all cases the number of iterations is small relative to network size 699 with 2000 L 1500 T 9 a 1000 p 5 2 5 500 uw 0 1 1 1 1 1 1 1 1 1 1 1 0 2 4 6 8 10 12 14 16 18 20 22 24 The number of Iterations Figure 4 Estimated social welfare vs iterations of ICE one sample run a 0 05 0 1 0 25 0 5 0 75 Borda 104 1 51 4 19 5 8 7 4 7 Plurality 98 7 48 6 18 6 8 3 4 6 Table 6 Average number of iterations varying a ICE is quite insensitive to the scoring rule and termination time declines dramatically with increasing a 5 CONCLUDING REMARKS We have presented a novel model for social choice combin ing intrinsic and empathetic preferences the latter reflecting one s desire to see others satisfied with a chosen alternative Using a social network to measure degree of empathy our al gorithms allow efficient computation of optimal decisions by weighting the contribution of each agent and have a natural interpretation as empathetic voting when scoring rules are used Critically individuals need only specify their intrin sic preferences and network weights they need not reason explicitly about the preferences of others This model is a starting point for the broader investiga tion of empathetic preferences in social choice We are ex ploring more realistic processes for simultaneous generation of netwo
13. g differences in social welfare helps calibrate the comparison between experiments We can nor malize RSWL by considering the range of possible social welfare values actually attainable Let alternative a have minimum social welfare under the true model Normalized social welfare loss NSWL is sw a swt aa sw az sw a_ This offers a more realistic picture of loss caused by using an inconsistent assumed utility model by compar ing it to the loss of the worst possible decision under the true model Impartial Culture We first consider RSWL and NSWL for all nine combinations of assumed and true utility mod els We fix m 5 options and use Borda scoring Average maximum losses are reported in Table 1 while the decision disagreement percentage is shown in Table 2 While RSWL is relatively small on average though maximum losses are quite large this is largely due to the uniformity of prefer ences generated by impartial culture all options have the same expected score By normalizing we obtain a more ac curate picture of the loss incurred by using non empathetic voting average normalized loss shows that the controllable error is quite large especially when comparing the stan dard intrinsic model to either of the empathetic models Moreover the intrinsic model chooses the incorrect alterna tive in over half of all instances in both cases Interestingly assuming either the local model or global mode
14. ic literature on empathy envy and other forms of other re garding preferences 30 26 6 our models also have ties to work on opinion spread and social learning 24 1 see Sec 2 4 We consider two varieties of empathetic preference In our local empathetic model the utility of individual 7 for al ternative a combines her intrinsic preference for a with the intrinsic preference of i s neighbors for a where the weight given to 7 s preference depends on the strength of the re lationship of i with j For instance i may be willing to trade off some of her intrinsic preference for a restaurant if her colleagues are happier with the cuisine as her happi ness depends to those of her friends and she defers more to her closer friends In our global empathetic model i s utility for each a depends on her intrinsic preference and the total utility of her neighbors for a not just their intrinsic prefer ence she wants her neighbors not only to be satisfied with a but to have high utility which depends on the utility of their neighbors and so on For example in political voting i may have a mild preference for a over b but if b is strongly preferred by her neighbors their neighbors and others in the community she may prefer to see b elected rather than have grumpy neighbors for the next few years Our main contribution is a model for preference aggre gation that selects consensus alternatives in a way that is sensitiv
15. ic preferences exist ignoring them by using classical preference aggrega tion techniques will lead to poor decisions Specifically we measure the percentage of decision disgareement DD over 2500 instances for a fixed setting in which the the true and 5This is only one of many models that can be used Results are similar for other types of networks t del assumed model rue mode intrinsic local global intrinsic 1 4 9 9 1 1 8 0 28 4 100 22 6 100 2 9 19 3 0 1 3 2 sts 28 5 100 T 2 86 9 1 8 12 7 0 1 2 7 global 59 3100 1 11970 Table 1 Avg max RSWL 1st rows and NSWL 2nd rows Borda m 5 rr assumed model intrinsic local global intrinsic 57 76 50 48 local 58 12 11 72 global 50 84 11 72 Table 2 Percentage decision disagreement Borda m 5 assumed models propose different optimal decisions We also measure the average loss in social welfare arising from making decisions using an assumed model that differs from the true model Let sw and sw be social welfare under the true and assumed models respectively and at and aa be the corresponding optimal options or winners Rather than directly comparing social welfare under various models we define relative social welfare loss RSWL to be sw at sw aa sw at we often report it as a percent age RSWL by scalin
16. ility function though unlike typical models of externalities an agent s utility depends on the utility of her neighbors for the chosen alternative rather 696 than the behavior of or the direct allocation made to her neighbors Bodine Baron et al 7 study stable matchings e g of students to residences with peer effects that in duce local network externalities Branzei and Larson address coalition formation on social networks where agent utility for a coalition depends on either her affinity weights 11 or dis tance to others in a network 12 Maran et al 31 study preference aggregation in combinatorial domains given the presence of social influence Finally auction design in social networks with externalities is studied in 22 Boldi et al 8 study delegative democracy where an in dividual can either express her preferences directly or to delegate her vote to a neighbor In our model individuals do not delegate their votes we simply consider the depen dency of their preferences on those of others Our empathetic model bears some resemblance to cer tain centrality measures in social and information networks which use self referential notions of node importance Some well known examples include eigenvector centrality 9 hubs and authorities 27 and PageRank 34 Apart from concep tual differences and the fact that we address decision social choice problems a key technical distinction is the use of self lo
17. ilosophy 13 2 261 280 1997 J H Fowler and N A Christakis Dynamic spread of happiness in a large social network Longitudinal analysis over 20 years in the Framingham Heart Study British Medical Journal 337 a2338 2008 700 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 J R French A formal theory of social power Psychological Review 63 3 181 194 1956 N Friedkin and E Johnsen Social influence and opinions J Math Soc 15 193 206 1990 B Golub and M O Jackson Naive learning in social networks and the wisdom of crowds Amer Econ J Microeconomics 2 112 149 2010 N Haghpanah N Immorlica V Mirrokni and K Munagala Optimal auctions with positive network externalities ACM EC 11 pp 11 20 2011 J C Harsanyi Rational Behaviour and Bargaining Equilibrium in Games and Social Situations Cambridge 1977 M O Jackson Social and Economic Networks Princeton 2008 J G Kemeny and J L Snell Finite Markov Chains Springer Verlag New York 1976 A Kirman and M Teschl Selfish or selfless The role of empathy in economics Philosophical Transactions of the Royal Society B Biological Sciences 365 1538 303 317 2010 J Kleinberg Authoritative sources in a hyperlinked environment JACM 46 604 632 1999 S Konrath E O Brien C Hsing Changes in dispositional empathy in american col
18. juj a wjreje a kj The ratio of wjj to aren w jr captures the relative impor tance of intrinsic and empathetic utility to j Our framework does not impose empathetic preference fully self interested agents are represented by self loops of weight 1 We consider two ways of defining empathetic preferences In the local empathetic model we define ejg a uz a i e j s utility for a combines the intrinsic utilities of each of its neighbors including itself if wj gt 0 u a So wrug a 1 k This model reflects agents 7 who are concerned about the direct preference of their neighbors k for a but the fact that k s utility may depend on k s own neighbors does not impact j Consider a family deciding on a movie the prefer ences of certain family members e g parents for a film may depend on the preferences of others e g children whom they want to ensure are entertained In the global empathetic model we define e a ux a so that k s total utility for a which may depend on k s neighbors influences j s utility for a giving rise to uj a wyjuj a X wjkur a k j Here j s utility for a depends on the utility not just intrin sic preferences of its neighbors For example a voter may care about the overall satisfaction of her neighbors when voting for a political representative but recognize that their satisfaction also depends on their neighbors etc Compa nies linked in co
19. l when the true model is the other gives reasonable results this means that the local model offers a good first order approximation to the global model see Sec 3 Irish Voting Data Impartial culture is often viewed as an unrealistic model of real world preferences For this reason we tested our methods using preferences drawn from 2002 Irish General Election using electoral data from the Dublin 698 tre modii assumed model intrinsic local global intrinsic 27 3 46 1 22 3 39 0 local 28 0 46 3 5 6 8 6 global 22 9 39 3 5 5 8 6 Table 3 Percentage decision disagreement plural ity Borda West Dublin m 9 RSWL global vs intrinsic DD global vs intrinsic sw RSWL global vs local RSWL local vs intrinsic wasasa DD global vs local DD local vs intrinsic ssn 100 90 80 70 RSWL Decision Disagreement DD 60 50 40 30 20 10 j 2 Ss Figure 2 RSWL and decision disgreement DD plu rality b d 2 2 S S O D Q West constituency which has 9 candidates and 29 989 bal lots of top t form of which 3800 are complete rankings We assign full rankings drawn randomly from the set of 3800 complete rankings to nodes in our network Decision dis agreement under both plurality and Borda scoring Table 3 is quite high ranging from 22 46 Average NSWL not shown is not as high as with impartial culture fro
20. lege students over time A meta analysis Personality and Social Psych Rev 15 180 198 2011 H Leibenstein Beyond Economic Man A New Foundation for Microeconomics Harvard 1976 F Maccheroni M Marinacci and A Rustichini Social decision theory Choosing within and between groups Review of Economic Studies 79 4 1591 1636 2012 A Maran N Maudet M S Pini F Rossi and K B Venable A framework for aggregating influenced CP nets and its resistance to bribery AAAI 13 pp 668 674 2013 C D Meyer Matrix Analysis and Applied Linear Algebra volume 2 SIAM 2000 D C Mutz Cross cutting social networks Testing democratic theory in practice American Political Science Review 96 1 111 126 2002 L Page S Brin R Motwani and T Winograd The pagerank citation ranking Bringing order to the web Technical Report 1999 66 Stanford InfoLab November 1999 A Salehi Abari and C Boutilier Ranking networks NIPS 18 Workshop on Frontiers of Network Analysis Methods Models and Applications 2013 A K Sen Collective Choice and Social Welfare North Holland Publishing Co Amsterdam 1970 S Simon and K R Apt Social network games Journal of Logic and Computation 2013 T Singer The neuronal basis and ontogeny of empathy and mind reading Review of literature and implications for future research Neuroscience and Biobehavioral Reviews 30 6 855 863 2006 T Voice S D Ramchurn and N R Jen
21. lternatives or options A a1 m and a set of agents V 1 n Each agent j has intrinsic pref erences over A in the form of either a strict preference ranking or a cardinal utility function uj We describe preferences in terms of utility functions but discuss below how to interpret voting procedures within our model Our goal is to select a consensus option a A that im plements some social choice function f relative to the pref erences of M For example if agent utilities are dictated solely by intrinsic preference and f is utilitarian social wel fare maximization SWM we select a arg max uj a We ignore ties in the SWM option for ease of exposition If preferences are given by preference rankings f might corre spond to some voting rule 2 2 Empathetic Preference on Social Networks We depart from standard social choice by considering em pathetic preferences in which the preferences of one agent 1Computational models of empathy may prove relevant in online social applications to address a recently observed de cline in empathy among young adults in which online social networks and media may have a role 28 Our model applies directly to more general social choice problems such as assignment problems with network exter nalities matching etc without difficulty Our algorithms however are specific to the single choice assumption 694 are dependent on those of other agents W
22. m 1 3 with maximum loss around 40 The effect of m Fig 2 shows the average RSWL and deci sion disagreement DD for three true vs assumed models as we increase the number of alternatives m using plurality scoring We observe that average RSWL increases with m and approaches 70 when m 200 while the optimal de cision is rarely made NSWL for the instrinsic model not shown even at m 5 averages 20 30 With Borda scor ing the effect of m is much less pronounced because of rel atively small utility differences or smoothing between ad jacent candidates intrinsic loss ranges from 20 30 across all values of m but the pattern decision disagreement is almost identical to plurality Self loop weight a Varying the self loop weight a has a significant effect on NSWL and decision disagreement when true utility is global but intrinsic utility is assumed Table 4 shows that for both Borda and plurality increasing a i e decreasing overall degree of empathy decreases both NWSL and DD Similar trends hold for the local model We also used a model in which nodes have different self loop weights drawing each node s a from a truncated Gaussian As we vary the mean js we see a similar trend in Table 5 The impact of directionality The results above use networks with bi directional edges by replacing each undi rected edge with two directed edges To explore how di rectionality impacts NSWL we consider networks with a
23. mplex supply chain may care about the suc cess of their suppliers and customers and consider adopting industry specific or economic policies in that light In the 2 3Suitable qualititative expression of such tradeoffs is an im portant ongoing research direction global model the circular dependence of utilities requires a fixed point solution to the linear system Eq 2 see below Correlations of behavior and or preferences among agents connected in social network is widely accepted and can be explained by a variety of mechanisms 16 24 Among these are information diffusion in which agents become aware of opportunities or innovations from connections to their neigh bors network externalities in which the benefits of adopting some behavior increase when more neighbors do the same or homophily in which people with similar characteristics say preferences more readily form social ties Our empathetic model is somewhat different in that a person s intrinsic pref erences over options A are not presumed to be correlated with their neighbors but their revealed preferences might be their choices or stated utilities reflect some considera tion however determined of their neighbors preferences 2 3 Weighting Agent Intrinsic Utilities In realistic social choice situations agents with empa thetic preferences must often perform sophisticated reason ing about not only their own intrinsic preferences but also those
24. ndations of interdependent other regarding preferences in which the outcome expe rienced by others affects the utility of an agent In their general formulation the utility of an agent for an act in corporates both its subjective expected utility for that act and an expected externalities function over the agent s per ceived social value of its own act and others acts While the general form of these externalities can model our notion of empathy the specific axioms proposed for the application of their model e g their anonymity axiom prevents the agent from distinguishing which of its peers attains a specific out come preclude its direct application to our setting Our work bears some connection to models of opinion for mation and social learning in social networks 24 1 Ch 8 However that work focuses on convergence of consensus and correct opinion among individuals with different ini tial opinions as individuals learn from one another Our empathetic model can be viewed mathematically as a spe cial case of a general model due to Friedkin and Johnson 20 other special cases include 15 19 Our goal in empathetic social choice is of course different we capture preference in terdependence in our model as a form of empathy and focus on algorithms and mechanisms to implement a social choice function not propagate beliefs Empathetic utilities can also be viewed as a form of net work externality in an agent s ut
25. nings On coalition formation with sparse synergies AAMAS 12 pp 223 230 2012
26. of their neighbors Even in the local setting expressing preferences e g voting is difficult since agents usually have incomplete and in some cases no information about the preferences of their friends neighbors or colleagues The global empathetic setting is even more complex since an agent is required to reason about her neighbors connections as well as their intrinsic empathetic tradeoffs In our models preference aggregation and optimization are simpler agents need only specify their intrinsic pref erences as is standard in social choice and the empathetic weights they assign to their acquaintances In social scenar ios this can remove a considerable informational and cogni tive burden from agents who might otherwise be required to explicitly compute or otherwise determine their total utility for alternatives In other settings agents might not wish to reveal their preferences to their neighbors but still want their neighbors to obtain a favorable result e g compa nies voting on economic policy who are linked together in supply chain relationships which correlate their stability or profitability Fortunately given a network G consensus decision making with empathetic preferences can be recast as a weighted preference aggregation problem over intrinsic preferences alone This eases the burden on agents and also allows one to recast the problem as simple weighted voting or weighted utilitarian SWM rendering the de
27. ops in our empathetic model which allows each node to contribute intrinsic utility to its fixed point value 3 COMPUTING WINNERS To compute the social welfare maximizing alternative in both the local and global empathetic models recall that so cial welfare can be expressed as sw a u w u a for a suitable weight vector w Given vectors u a for any a A we can compute the optimal option a arg maxacaw ul a in O nm time So we focus on i computation of w in each model and ii for the global model a method for computing a without full computation of w In the local model w requires only a single vector matrix multiplication w e W in time O n However social networks are generally extremely sparse with the number of incoming edges to any node j bounded by some small constant c In such sparse networks w can be computed in O n time since w is simply the sum of j s incoming edge weights and a can be determined as above in O nm time Thus the complexity of computing optimal alterna tives in the local empathetic model is no different than that of straightforward SWM or weighted voting In the global model w has a more complicated expres sion w e A D where A I W D see Cor 1 The difficulty lies largely in matrix inversion AT can be computed via Gauss Jordan elimination which has complex ity O n This implies that straightforward computation of a requires O n nm
28. or all j E N a E A An iteration of ICE consists of 1 updating estimated utilities using Eq 5 for all j and a C 2 computing estimated social welfare of each a C 3 determining the maximum estimated social welfare sw 4 testing each a C for domination i e sw sw a gt 2n d c 1 amp and 5 eliminating all dominated options from C The algorithm terminates when one option a remains in C ICE runs in O tm time where t is the number of iterations required and if the number of outgoing edges is bounded O tmn As we demonstrate below ICE converges quickly in practice 4 EMPIRICAL RESULTS We describe experiments on randomly generated networks and intrinsic preferences to analyze our algorithms and to contrast the decisions that result under non empathetic stan dard local empathetic and global empathetic models Experimental Setup We assume that individual intrin sic utilities arise from an underlying preference ordering over A In all experiments we draw a random ordering for each agent j using either the impartial culture in which all rank ings are equally likely or the Irish voting data set which we explain in detail below To draw connections to voting meth ods j s utility for a is given by the Borda or plurality score of a in its ranking As utilities these embody very differ ent assumptions Borda treats utility differences as smooth and linear whereas plurality utilit
29. ork externalities The American Economic Review 102 5 1773 1804 2012 A L Barabasi and R Albert Emergence of scaling in random networks Science 286 5439 509 512 1999 K Binmore Natural Justice Oxford 2005 E Bodine Baron C Lee A Chong B Hassibi and A Wierman Peer effects and stability in matching markets SAGT 11 pp 117 129 2011 P Boldi F Bonchi C Castillo and S Vigna Voting in social networks CIKM 09 pp 777 786 2009 P Bonacich Power and centrality A family of mesasures Amer J Sociology 1170 1182 1987 R Bond C Fariss J Jones A Kramer C Marlow J Settle and J Fowler A 61 million person experiment in social influence and political mobilization Nature 489 295 298 2012 S Branzei K Larson Coalitional affinity games and the stability gap IJCAI 09 pp 79 84 2009 S Branzei and K Larson Social distance games IJCAI 11 pp 91 96 2011 N A Christakis and J H Fowler Connected The Surprising Power of Our Social Networks and How They Shape Our Lives Back Bay Books 2011 T Cormen C Leiserson R Rivest C Stein Introduction to Algorithms MIT Press 2009 M H DeGroot Reaching a consensus Journal of the American Statistical Association 69 345 118 121 1974 D A Easley and J M Kleinberg Networks Crowds and Markets Cambridge 2010 P Fontaine Identification and economic behavior Sympathy and empathy in historical perspective Economics and Ph
30. rks and preferences that better explain preference correlation see e g our ranking network framework 35 Methods to assess the prevalence of empathetic preferences the extent to which social network structure reflects such preferences and how they can be discovered effectively are critical Testing our model and these extensions on large data sets is of course critical to validating the existence of empathy of this form Our model can be applied to match ing assignment and other group decision problems each requiring its own algorithmic developments Other impor tant directions include voting schemes where agents spec ify tradeoffs between intrinsic and empathetic preference in a qualitative fashion and analysis of manipulation in the context of such externalities in voting 6 ACKNOWLEDGMENTS This research is supported by Natural Sciences and Engi neering Research Council of Canada NSERC 7 1 10 11 12 13 14 15 16 17 18 REFERENCES D Acemoglu and A Ozdaglar Opinion dynamics and learning in social networks Dynamic Games and Applications 1 1 3 49 2011 S L Althaus Information effects in collective preferences American Political Science Review 92 3 545 558 1998 K J Arrow Extended sympathy and the possibility of social choice Philosophia 7 2 223 237 1978 M Baccara A Imrohorolu A J Wilson and L Yariv A field study on matching with netw
31. urality is used as scoring rule in this example alternative c wins under the global model a wins in the in trinsic model and 6 wins in the local model We discuss weight computation in Sec 3 Nonnegativity normalization and positive self loop are not the only collective conditions under which fixed point utilities are guaranteed to exist Viewing the network as a Markov chain if one assumes the process is aperiodic i e the greatest common divisor of all directed cycle lengths is 1 and irreducible i e any node is reachable from any other node with non zero probability 25 32 fixed point solutions are also guaranteed to exist One might also adopt a weaker variation of our assumptions by imposing positive self loop only on a subset of agents this would suffice if all closed strongly connected partitions of the network have at least one node with positive self loop 21 However we be lieve our assumptions and in particular positive self loop over all individuals are appropriate in most social choice settings Consider two individuals j and k with wj wee 0 Wik Wey 1 u a 0 1 and uj a 1 The induced system does not have a unique fixed point solution a gt b gt ic a gt 2e gt gb a gt 1b gt 1 a gt 2c gt 2b wi 0 7 w2 0 4 wy 0 7147 wa 0 2715 w3 1 5 w4 14 w3 0 6511 w4 2 3627 b gt 3 a gt 3 c c gt 4b gt 4a b gt 3a gt 3c c gt 4b gt 4a b gt 3 a gt 3 c gt 4b
32. verge even if the updates are asynchronous Under this iterative process the local empathetic model provides a first order approximation to the global model simply let u a u a Critically the error in the estimated utilities at the t iteration can also be bounded THEOREM 2 In the iterative scheme above o o a a u a u a co where mini lt i lt n Wii Hence societies in which individuals have self loops with relatively large weight i e less empathy converge to fixed point utilities faster than societies with greater empathy This error bound allows one to bound the error in esti mated social welfare if the utilities of all options are esti mated this way Let sw a 5 u a THEOREM 3 Assume u a uf a c d for allj Then sw a sw a lt n d c 1 amp for all t under the conditions above where MiNi lt i lt n Wii As a result we know that under the same assumptions PROPOSITION 2 If sw b sw a gt 2n d c 1 w then sw b gt sw a We can exploit Prop 2 in a simple algorithm called it erated candidate elimination ICE for computing a The 697 intuition is simple we iteratively update the estimated util ities of the subset C C A of options that are non dominated and gradually prune away any options that are dominated by another until only one a remains ICE first initializes C A and u a c f
33. y is all or nothing We generate random social networks using a preferential attach ment model for scale free networks 5 starting with no initial nodes we add n nodes in turn with a new node con nected to k lt no existing nodes where node 7 is selected as a neighbor with probability deg i gt 7 deg j We set no 2 and k 1 in all experiments We direct the graph by replacing each undirected edge with the two corresponding directed edges add a self loop to each node with weight a then distribute weight 1 a equally to all other out going edges Parameter a 0 1 represents the degree of self interest and 1 a the degree of empathy Unless noted all experiments have n 1000 agents nodes 0 25 and are run over 50 random preference profiles on each of 50 random networks 2500 instances Performance Metrics To examine the importance of modeling empathy in social choice we distinguish actual user preferences referred to as the true model from how preferences are modeled in a group decision support system namely the assumed model Specifically we let the true and assumed models be any of our intrinsic non empathetic local or global models 9 possible combinations We are interested in the extent to which these models disagree in their decisions and the loss in social welfare that results from such disgareement If these measures are large it indicates that in situations where empathet
Download Pdf Manuals
Related Search