Stephen Leider

Markus M Möbius

Tanya Rosenblat Quoc

Anh Do

Ed Glaeser

Muriel Niederle

Adam Szeidl

Elizabeth Murry

DIRECTED ALTRUISM AND ENFORCED RECIPROCITY IN SOCIAL NETWORKS*

We conducted online field experiments in large real-world social networks in order to decompose prosocial giving into three components: (1) baseline altruism toward randomly selected strangers, (2) directed altruism that favors friends over random strangers, and (3) giving motivated by the prospect of future interaction. Directed altruism increases giving to friends by 52% relative to random strangers, whereas future interaction effects increase giving by an additional 24% when giving is socially efficient. This finding suggests that future interaction affects giving through a repeated game mechanism where agents can be rewarded for granting efficiency-enhancing favors. We also find that subjects with higher baseline altruism have friends with higher baseline altruism.

I. Introduction

Real world social networks provide a natural laboratory to study prosocial behavior. Friends help each other frequently and often substantially. In the 1995 General Social Survey, 55% of Americans reported that they first approached close friends and family members when they needed to borrow a large sum of money [START_REF] Mobius | Trust and Social Collateral[END_REF]. In a 2007 UK YouGov survey, 48% of respondents reported lending, on average, $1,800 to friends and relatives during the past twelve months [START_REF] Yougov | What s Money between Friends[END_REF]. Similarly, close friends and relatives are the predominant source of informal insurance against risk in developing countries [START_REF] Townsend | Risk and Insurance in Village India[END_REF][START_REF] Udry | Risk and Insurance in a Rural Credit Market: An Empirical Investigation in Northern Nigeria[END_REF]).

Economists have explored two main explanations of prosocial behaviorselfless altruism and expectations of reciprocal favors in future exchanges. Because people tend to interact frequently with friends toward whom they have the strongest altruistic feelings, these mechanisms are difficult to distinguish empirically.1 In this paper, we use two online field experiments in a real world social network to solve this identification problem. Our design allows us to selectively switch off the reciprocity mechanism in some treatments, and thereby separately measure the strength of the altruism and reciprocity mechanisms.

The ability of our methodology to distinguish between these two mechanisms has several applications. For example, many researchers have documented that as societies transition to market economies, market transactions replace bilateral reciprocal exchanges, leading to a decline in social capital.2 By using our diagnostic games to identify cultures where the social ties are either heavily reciprocity-based or heavily altruism-based, economists may be better able to explain differences in the social disruption caused by markets. Additionally, our finding (described below) that the reciprocal mechanism only applies to transactions that are efficient suggests a policy use of our techniques. Development programs such as microfinance that use social ties to encourage lending and insurance may be most effective in communities where the social networks have a strong reciprocity component, because relationships based on trading efficiency-enhancing favors may help direct resources toward efficient uses. Thus, policymakers could use experiments such as ours to identify areas where intervention may be most effective.

In our experiments, we distinguish three components of prosocial giving: (1) baseline altruism toward randomly selected strangers, (2) directed altruism that favors friends over random strangers, and (3) giving motivated by the prospect of future interaction. We begin by directly measuring the social networks of Harvard undergraduates to identify, for each subject, socially close direct friends, less close friends of friends, and socially 1. Economists and sociologists use both frequency of interaction [START_REF] Marmaros | How Do Friendships Form?[END_REF] and intensity of altruism interchangeably to measure the strength of social connections [START_REF] Granovetter | Economic Action and Social Structure: The Problem of Embeddedness[END_REF][START_REF] Granovetter | Economic Action and Social Structure: The Problem of Embeddedness[END_REF][START_REF] Marsden | Measuring Tie-Strength[END_REF][START_REF] Mitchell | The Components of Strong Ties among Homeless Women[END_REF][START_REF] Perlman | The Development of Intimate Relationship[END_REF][START_REF] Mathews | Association ot Indicators and Predictors of Tie-Strength[END_REF].

2. See for example [START_REF] Coleman | Social Capital in the Creation of Human Capital[END_REF] on the industrial revolution in Western societies, [START_REF] Völker | f Institutions of Communism, the Transition to Capitalism and Personal Networks: The Case of East Germany[END_REF] on the change from communism to capitalism in East Germany, and [START_REF] Yellen | The Transformation of the Kalahari !Kung[END_REF] on the increased participation of the Kalahari !Kung in markets. distant strangers. We then conduct a series of online games where subjects make unilateral allocation decisions for several types of named partners and one nameless partner (a randomly selected participant from the subject's dormitory). The games are either modified dictator games, as in [START_REF] Andreoni | Giving According to GARP: An Experiment on the Consistency of Preferences for Altruism[END_REF], or a new "helping game." Subjects make multiple decisions but are paid for one decision selected at random. For some decisions, neither participant is told which of the decision maker's choices was implemented. In these anonymous decisions, the difference in allocations between friends and strangers allows us to quantify the magnitude of directed altruism. In particular, we find that subjects send on average 52% more money to close friends than to strangers. We also demonstrate that giving to friends is strongly related to the decision makers' underlying baseline altruism toward nameless partners.

For other decisions, both the decision maker and the partner are informed which of the decision maker's choices was selected for payment. We use the difference between this nonanonymous and the anonymous treatment to measure the separate effect of future interaction on prosocial behavior. We find that the nature of the future interaction effect depends crucially on the social welfare effects of prosocial behavior. When giving increases joint surplus, subjects increase giving to friends (relative to strangers) by an additional 24% in the nonanonymous treatment. Thus, directed altruism is roughly twice as strong as future interaction effects in determining giving behavior. When giving decreases joint surplus, subjects do not give more to friends in the nonanonymous treatment. In contrast, the directed altruism effect favors friends over strangers both when prosocial behavior is socially efficient and when it is inefficient.

These differential effects of future interaction on prosocial behavior are well explained by the theory of repeated games. [START_REF] Karlan | Trust and Social Collateral[END_REF] develop a tractable theory for analyzing repeated games in social networks, which we adapt to our setting and call the enforced reciprocity model. In that model, a decision maker can safely grant favors (in the form of larger allocations) to partners when the relationship between them is stronger and more valuable, because the partner would rather repay the favor than damage the friendship. Granting favors, however, only benefits both the decision maker and partner when giving increases social surplus. This conflicts with Benabou and Tirole's (2006) model, where individuals give in order to signal being of an altruistic type. The signaling model predicts that excess giving to friends should increase for all the games (and all exchange rates), because giving still distinguishes altruists from selfish types. The enforced reciprocity model also predicts that giving should increase if the decision maker and partner share a greater number of common friends (controlling for social distance). We confirm this prediction in our data. This provides further evidence for the enforced reciprocity model and distinguishes it from related theories such as preference-based reciprocity [START_REF] Rabin | Incorporating Fairness into Game Theory and Economics[END_REF][START_REF] Dufwenberg | A Theory of Sequential Reciprocity[END_REF]. This result also highlights the influence of second-order links and network structure on economic decisions.

Last, we show that decision makers who exhibit greater baseline altruism are treated more generously by their friends. However, we show that friends do not reward intrinsic kindness, but rather, that kind people tend to have friends who exhibit greater baseline altruism themselves.

Our paper builds on a rich experimental literature on otherregarding preferences and cooperation. Altruistic behavior toward strangers has been observed in a variety of laboratory contexts (see [START_REF] Camerer | Behavioral Game Theory: Experiments in Strategic Interaction[END_REF] for an extensive survey). [START_REF] Hoffman | Social Distance and Other-Regarding Behavior in Dictator Games[END_REF] suggest that a decrease in perceived social distance increases donations in dictator games. Our paper reduces social distance in two ways: (a) we distinguish between giving to friends and giving to strangers; and (b) we either reveal or do not reveal which decision is implemented. Our online experimental design is a significant methodological advance because it provides a practical way to match subjects with their realworld friends.3 Lab experiments that relax traditional anonymous matching of strangers typically reveal demographic characteristics such as gender or ethnicity (for example, see [START_REF] Fershtman | Discrimination in a Segmented Society: An Experimental Approach[END_REF]). Very few laboratory experiments explicitly rely on subjects' ongoing relationships with their friends as we do in our nonanonymous treatment. Instead, repeated interactions are incorporated directly into the experimental design, increasing prosocial behavior (see [START_REF] Roth | Equilibrium Behavior and Repeated Play of the Prisoners' Dilemma[END_REF] and Murninghan and [START_REF] Murninghan | Expecting Continued Play in Prisoner s Dilemma Games[END_REF] for early examples). A notable exception is the seminal work of [START_REF] Glaeser | Measuring Trust[END_REF], who match subjects at various social distances in a trust game.4 In subsequent research, 3. Our experimental design fits the definition of an arte factual field experiment from Harrison and List (2004).

4. See also [START_REF] Polzer | The Effects of Relationships and Justification in an Interdependent Allocation Task[END_REF] comparing allocations to friends and strangers in an ultimatum game. [START_REF] Goeree | Linking and Giving among Teenage Girls[END_REF] have adopted the anonymous treatment of our experimental design (using a standard dictator game) and also find strong evidence for directed altruism in a school network of teenage girls (also see [START_REF] Brañas-Garza | Altruism in the (Social) Network[END_REF] for data from experiments with European university students). To the best of our knowledge, our design is the first to distinguish between directed altruism and future interaction effects in social networks.

The rest of the paper is organized as follows. Section II describes several relevant theoriesenforced reciprocity, signaling, and preference-based reciprocityand reviews their testable implications. Section III presents the experimental design. Section IV summarizes the main features of the data. Our empirical results on directed altruism are presented in Section V. Section VI analyzes decisions under nonanonymity. In Section VII, we consider two benchmarks comparing the importance and magnitude of the directed altruism and future interaction effects. Section VIII shows that friends tend to have similar levels of baseline altruism. Section IX concludes by discussing the implications of our results for the theoretical and empirical analysis of prosocial behavior.

II. Theoretical Framework

We briefly review the predictions of three different theories that explain decision making when there is a prospect of future interaction. We refer the interested reader to the earlier NBER working paper for a detailed formal treatment of each theory [START_REF] Leider | Directed Altruism and Enforced Reciprocity in Social Networks[END_REF]. We assume throughout that there is a decision maker, M, and a partner, P, who are embedded in a social network. We calculate the social distance Dmp between the decision maker and the partner as the shortest path connecting them: for example, two direct friends have a social distance of 1, whereas a friend of a friend is at distance 2 (see Figure I). The decision maker's allocation decisions in the anonymous treatment (neither decision maker nor partner learns about the decision) and the nonanonymous treatment (both agents learn about the decision) are denoted by xmp and xmp, respectively (coded so that a larger x implies greater prosocial behavior).5

We assume, as a starting point, that decision makers have altruistic preferences whose strength varies with social distance.

5. Therefore, the decision maker's utility is decreasing in x and the partner's utility is increasing in x. We use a simple linear specification to capture decision making in the anonymous treatment, which is a natural extension of existing preferences-based altruism models:6

(1) xMp = ocZmp + YiDmp + YM + tMP.

We control for observable demographic characteristics of both individuals {Zmp). The coefficient ym captures the decision maker's intrinsic generosity toward all partners (independent of social distance), which we refer to as his or her baseline altruism. The coefficient y' determines how the decision maker's altruism varies with social distance, which we call directed altruism.

U.A. Enforced Reciprocity

Repeated games provide a natural framework to analyze the decision maker's allocation, xmp, under the prospect of future interactions. However, repeated games typically admit many equilibria even in a two-person settingthis multiplicity problem is compounded for social networks where hundreds of agents often interact. [START_REF] Karlan | Trust and Social Collateral[END_REF] provide a tractable framework for 6. [START_REF] Andreoni | Impure Altruism and Donations to Public Goods: A Theory of Warm-Glow Giving[END_REF] models altruism as a "warm glow," whereas [START_REF] Fehr | A Theory of Fairness, Competition and Cooperation[END_REF], [START_REF] Bolton | ERC: A Theory of Equity, Reciprocity and Competition[END_REF], and [START_REF] Charness | Understanding Social Preferences with Simple Tests[END_REF] focus on preferences over payoff distributions. modeling repeated game effects in social networks. They assume that decision maker and partner share a relationship that is consumed in the future and gives both of them utility Vmp-A decision maker who is more prosocial under nonanonymity compared to anonymity, such that xmpxmp > 0, grants a favor to the partner and can use the value of the relationship to the partner as social collateral to enforce repayment of the favor. If the partner refuses to return the favor the relationship breaks down and both agents lose the value of the friendship.

In our working paper, we formally show that in the unique subgame perfect equilibrium the decision maker allocates a larger amount under nonanonymity compared to anonymity only when giving is efficient, and thus increases social surplus. In this case, both the decision maker and the partner keep some of the surplus created by the favor. In contrast, when giving is inefficient a favor that has to be repaid makes both the decision maker and the partner worse off.

We can also show that the difference in allocations between the nonanonymous and anonymous treatments, xmpxmp, is increasing in the value of the relationship Vmp because the decision maker is willing to grant, and the partner is willing to repay, larger favors. This motivates the following empirical model of allocation decisions under nonanonymity:

(2) xMp = r]ZMp + 0xMp + </>VMp + vM + ¿mp-

We include the decision maker's anonymous decision, xmp, as a covariate, because our enforced reciprocity model predicts deviations from the anonymous benchmark. The model also predicts that enforced reciprocity and altruism are substitutes (0 < 1): because the decision maker will give the largest enforceable favor (when giving is efficient) and the partner will retain some of the surplus, the decision maker's marginal utility from giving an additional altruistic gift is smaller than in the anonymous case (the partner is now richer than in the anonymous case). We consider two proxies for the value of the relationship, Vmp-First, we expect that relationship value decreases with social distance because a decision maker is less likely to interact with a socially distant partner in the future. Second, the enforced reciprocity model of [START_REF] Karlan | Trust and Social Collateral[END_REF] suggests maximum network flow as an alternative measure. The maximum flow counts the number of distinct paths between decision maker and partner (see Figure I). Network flow captures structural features of the social network that are not captured by social distance alone. For example, having more friends in common increases network flow, whereas social distance is unchanged. Network flow formalizes a common intuition in the sociology literature that dense networks strengthen trust by facilitating informal arrangements [START_REF] Coleman | Social Capital in the Creation of Human Capital[END_REF][START_REF] Coleman | Social Capital in the Creation of Human Capital[END_REF]. In Karlan et al.'s (2009) enforced reciprocity model, each common friend increases the social collateral between the decision maker and the partner. The decision maker is able to extract repayments for larger favors, because if the partner defaults he or she will lose the relationship with all of the common friends as well as the decision maker. Throughout, we calculate network flow by only including links that are at most a distance K = 2 away from the decision maker. [START_REF] Karlan | Trust and Social Collateral[END_REF] justify this choice of a circle of trust of K = 2 by reviewing some of the existing empirical literature in economics and sociology, such as [START_REF] Granovetter | Economic Action and Social Structure: The Problem of Embeddedness[END_REF].

Table I summarizes the main predictions of the enforced reciprocity model (as well as the signaling-and preference-based reciprocity models discussed below).

II.B. Signaling

In recent work, [START_REF] Benabou | Incentives and Prosocial Behavior[END_REF] propose a signaling model that provides an alternative theory for explaining greater generosity to friends under nonanonymity. In their framework, agents care about being perceived as altruistic (rather than greedy) types, so they act more generously when their actions can be observed. Moreover, it is reasonable to extend their model to assume that individuals care more about signaling generosity to friends than to strangers, because they are more likely to interact with friends in the future.

A key distinguishing prediction of the signaling model is that decision makers should increase their allocation decision under nonanonymity compared to anonymity both when prosocial behavior is efficient and when it is inefficient. Larger allocations are just as good (if not better) signals of generosity when giving is inefficient as when giving is efficient. Additionally, excess giving under nonanonymity is independent of the level of altruism in Benabou and Tirole's (2006) model, because signaling utility and distributional utility are additively separable. This effect contrasts with the enforced reciprocity model, where altruism and favors are substitutes.

U.C. Preference-Based Reciprocity

A third possible mechanism for future interaction effects is preference-based reciprocity. [START_REF] Dufwenberg | A Theory of Sequential Reciprocity[END_REF] develop a psychological game theory model of sequential reciprocity, where an individual treats kindly (unkindly) those who have treated/will treat him or her kindly (unkindly). As in enforced reciprocity, the decision maker increases his or her allocation between nonanonymity and anonymity only when giving is efficient, anticipating that with some probability, assumed to be decreasing in social distance, the partner may act to benefit the decision maker.

Under preference-based reciprocity, however, the partner's desire to return the decision maker's favor is intrinsic, rather than designed to preserve the relationship with the decision maker or common friends. Therefore, unlike the enforced reciprocity model, preference-based reciprocity would not predict that the network flow measure independently correlates with increased generosity Helping game (nonanon) named partner

Figure II Overview of Experimental Design (Waves 1 and 2)

In Wave 1, we randomized whether subjects first made all the nameless decisions or whether they first made all the named decisions. For each named partner in Wave 1, we randomized whether subjects first submitted their anonymous choice for that partner or their nonanonymous choice. We also randomized whether a subject first submitted all anonymous (nonanonymous) choices for all partners on a single screen, or whether a subject submitted both anonymous and nonanonymous choices on a separate screen for each partner. Finally, we randomized the order in which the three different exchange rates were listed on subjects' screens.

after controlling for the frequency of future interaction (via social distance).

III. Experimental Design

Figure II presents the major features of our experimental design. In order to recruit more subjects and map a larger social network, all communication with subjects was conducted by e-mail and all choices were submitted on a website (rather than in a laboratory) that subjects could access with a password through their own web browsers. We conducted two waves of the experiment. In each wave, we first used a novel task to elicit the social network truthfully. We then had subjects play an allocation game with other subjects in the network. In Wave 1, we used modified dictator games with varying exchange rates, and in Wave 2, we used a new helping game. In both waves, decision makers first decided on allocations between themselves and other unnamed ("nameless") partners, and then, a few days later, made several allocations between themselves and named partners (identified by real first and last name) at various social distances. For both waves, a single decision was randomly selected for payment and all players were informed of their earnings by e-mail.

We conducted two major information treatments, using a within-subject design in Wave 1 and a between-subjects design in Wave 2. In these treatments, we varied how much information was revealed to both parties at the end of the experiment. In the "anonymous" treatment, each subject was merely informed of his or her total payoff for the experimentneither decision makers nor partners found out which particular decision was implemented. In the "nonanonymous" treatment, both the decision maker and the partner were told both their total payoff and which decision was implemented.

III. A. Design for Wave 1: Coordination Task and Dictator Games

Network Elicitation. To measure the social network, we used a coordination task to provide subjects incentives to truthfully report their friendships. Each subject listed his or her ten best friends and the average amount of time per week he or she spends with each of them.7 Each time a listed friend also listed the subject, the subject was paid 50 cents, with probability 0.5 if their answers about time spent together disagreed, or with probability 0.75 if they agreed. We made the expected payoff (25 or 37.50 cents) large enough to give an incentive to list their friends truthfully, and small enough to discourage "gaming." The randomization was included to limit disappointment if a subject was only named by a few people. To define the social network, we say that two subjects have a direct link if at least one of them named the other. We call this type of social network the "OR-network."8 Allocation Game. After measuring the social network, we randomly assigned each subject the role of decision maker or partner in the dictator games.9 Each decision maker then played modified dictator games with a nameless partner randomly selected from the decision maker's dormitory.10 He or she was asked to make allocation decisions for both the anonymous and 7. The choices were 0-30 minutes, 30 minutes to 1 hour, 1-2 hours, 2-4 hours, 4-8 hours, or more than 8 hours.

8. We find similar results using the "AND-network, where a link exists only it both subjects name each other. The OR-network has desirable monotonicity properties: a subject with an above average number of actual friends will have an above average number of friends in the measured network even if the survey truncates his true network. This is not always true for the AND-network if truncation forces subjects to select randomly from a set of equally close friends. 9. In the experimental instructions, we referred to the two roles simply as player 1 and player 2.

10. The decision maker is told in the instructions that the recipient was selected from his or her dormitory. the nonanonymous conditions. The decision maker allocated 50 tokens between himor herself and the recipient. However, the value of a token to the decision maker and to the recipient differed between games. In one case a token was worth 10 cents to the decision maker, and 30 cents to the recipient ("1:3"), whereas in a second case they were worth 20 cents to the decision maker and 20 cents to the recipient ("1:1"), and in a third case they were worth 30 cents to the decision maker and 10 cents to the recipient ("3:1"). We can therefore observe allocations when giving is efficient, neutral, and inefficient. Each decision maker made allocation choices for each of the three token money exchange rates.

A few days later, decision makers played in a second round, in which they were matched in random order with five different named partners listed using their real first and last names: (1) a direct friend (social distance SD = 1), (2) a friend of a friend (SD = 2), (3) a friend of a friend of a friend (SD = 3), (4) a student in the same staircase/floor who is at least distance 4 removed from the student (SD > 3), and (5) a randomly selected student from the same dormitory who falls into none of the above categories.11 Once again, the decision maker was asked to make allocation decisions in both the anonymous and nonanonymous situations. The decision maker made allocation decisions under the three different exchange rates (3:1, 1:1, and 1:3) for each partner.

To control for experimenter demand effects of presentation, we randomized whether subjects first made all the nameless decisions or first made all the named decisions. For each named partner in Wave 1, we randomized whether subjects first submitted their anonymous choice or their nonanonymous choice. We also randomized whether a subject first submitted all anonymous (nonanonymous) choices for all partners on a single screen, or whether a subject submitted anonymous and nonanonymous choices on separate screens for each partner. Finally, we randomized the order in which the three different exchange rates were listed on subjects' screens.

Note that each decision maker made six decisions for each partner involving three different exchange rates under anonymous and nonanonymous treatments (36 decisions in total). This 11. Our selection algorithm used the "AND"-network definition for this step. Because social distance always (weakly) decreases when using the "OR"-social distance definitions, the numbers of observations for columns (1) to (4) in Table II are not equal. made it very difficult for a participant to identify which decision was chosen ex post from her earnings.12 III.B. Design for Wave 2: Trivia Task and Helping Game Network Elicitation. To focus on relationships with a high frequency of interaction, we developed the trivia task technique to elicit the social network for the second wave. Each subject listed ten friends about whom they would answer questions. Over several weeks, several of the listed friends were randomly selected and each were sent an e-mail asking him or her to answer a multiple choice question about himor herself (e.g., "What time do you get up in the morning?"). Subjects then received e-mail directing them to a web page where they had fifteen seconds to answer the same question about their friends. If the subjects and their friends submitted identical answers, they both won a prize. The trivia task provides subjects with incentives to list friends that the subjects spend time with frequently (and thus are more likely to know the friends' habits).

Allocation Game. For the second wave we used a new allocation game to capture the kind of helping behavior that occurs in natural relationships, where an individual might face different opportunity costs to help a friend who needs a favor. In the helping game, each decision maker was endowed with $45, and each partner was endowed with $0. The decision makers were asked to report the maximum price that they would be willing to pay in order for the partner to receive a gain of $30. A random price between $0 and $30 was determined, and if their maximum willingness to pay was equal or greater than the random price the partner received $30 and the random price was deducted from the decision maker's endowment. Otherwise, the decision maker's payoff equalled the endowment of $45, and the partner's payoff equaled the endowment of $0.

Effectively, the decision makers revealed how much they valued a $30 gain for the partners. As in the first design, subjects 12. Although in principle the dictator could reveal his or her allocation to the partner after the experiment in the anonymous case, because dictators were not told which decision was selected for payment, they would have had to make choices with unique payoffs so that they would know which partner to inform, and remember those choices several weeks later when payments were made. Postexperiment breaking of anonymity is also less of a concern in the Helping Game (described in the next section), because the partners could not verify which subjects helped them, because all help yields the same payoff; nor could they verify the helpers cutoff, only that it was higher than the unknown price. made two rounds of decisions: first they played with a nameless partner, and then they played with four named partners. Also, we chose a between-subjects design for the anonymity manipulation: the decisions for the nameless partner were always anonymous, whereas in the second round decisions were either all anonymous or all nonanonymous. Every subject played both roles in the game, that of a decision maker and that of a partner, which allowed us to test whether the baseline altruism of the recipient affects the decision maker's choice. To control for experimenter demand effects of presentation, we randomized the order of named partners.

IV. Data Description

IV.A. Dictator Games

In December 2003, Harvard sophomores, juniors, and seniors at two dormitories were recruited through posters, flyers, and mail invitations. Subjects who logged onto the website were asked to (1) list their best friends' names using the coordination task and (2) fill in a basic demographic questionnaire. Subjects were required to name friends from the two participating dormitories. Subjects were paid their earnings from the coordination task, plus a flat payment of $10 for completing the survey. They were also eligible to earn cash prizes in a raffle, adding $3 (on average) in earnings. Experimental earnings were added to the student's electronic cash card.13

Of the 806 students in those two dormitories, 569 (71%) participated in the social network survey. The survey generated 5,690 one-way links. Of those, 2,086 links were symmetric links where both subjects named each other.14 The resulting OR-network consists of a single connected component with 802 subjects, forming a comprehensive map of the social network.

The dictator game stage was conducted over a one-week period in May 2004. Half of all subjects who participated in the coordination stage were randomly selected to be decision makers. Out of 284 eligible decision makers invited, 193 participated in round 1 (decisions for nameless partners) and 181 of those participated 13. These cards are widely used on campus as a cash substitute, and many off-campus merchants accept the cards.

14. For symmetric links, the two subjects assessment of the amount of time spent together in a typical week did not differ more than one category out of five in 80% of all cases. in round 2 (decisions for named partners). The participants were representative of the coordination stage sample composition.

TV.B. The Helping Game

Information on social networks was collected in December 2004 through an online trivia task advertised on the popular student social website facebook.com.15 A total of 2,360 students signed up, generating 12,782 links between participants out of 23,600 total links16 with 6,880 symmetric links. In total, 5,576 out of the 6,389 undergraduates at Harvard either participated in the trivia task or were named by a participant. Upperclassmen had higher participation rates, with only 34% of freshman responding, but with 45%, 52%, and 53% of sophomores, juniors, and seniors participating, respectively. The social "OR"-network of 5,576 individuals contains a single component (meaning all individuals are connected) with a mean path length of 4.2 between participants.

The helping game stage was conducted in May 200617 over a one-week period with all juniors and seniors who had participated in the previous academic year's trivia task. A total of 776 subjects participated in the first part of the helping game (decisions for nameless partners), and 695 subjects completed the second part (decisions for named partners).

TV. C. Summary Statistics

Table II shows the mean actions of decision makers for the dictator and helping games, for both the anonymous and nonanonymous treatments. Two patterns are clear: in all games and in both treatments, the decision makers' generosity toward their partners decreased with social distance, and for any game and at any social distance, the decision makers' generosity is always higher under nonanonymity than under anonymity. Differences between treatments are significant across all social distances in the dictator game, and for social distances 1 and 2 in the helping game. For both games and both treatments, decision makers' allocation choices are significantly larger for partners who are direct friends than for partners at any other social distance. Notes. Table shows averages of number of passed tokens (dictator games) and average cutoffs (helping game) by social distance (OR-network). Standard deviations are in parentheses. Nameless refers to matches between the decision maker and the partner where the identity of the partner is not known to the decision maker.

In the dictator game with the 1:3 (efficient) exchange rate, the decision maker passes an average of 19. 19 tokens to a direct friend versus 12.20 tokens to a partner at social distance 4. With an (inefficient) exchange rate of 3:1, the decision maker passes only 8.03 versus 6.15 tokens, respectively. In the nonanonymous treatment, for all social distances, the decision maker passes about 4 to 5 more tokens when altruism is efficient and about 2 to 4 more tokens when altruism is inefficient. In the helping game's anonymous treatment, the average willingness to pay is $12.77 for a direct friend, and decreases to $7.09 for a partner at social distance 4. Nonanonymity increases the cutoff by approximately $2 across social distances.

Curiously, in the anonymous treatment for all the dictator games and in the helping game, nameless partners are treated more generously than are friends of friends, despite the fact that the expected social distance of a randomly chosen partner is at least 3. In the nonanonymous treatment, on the other hand, the contributions to nameless partners closely track contributions to named partners at distance 3. The average level of giving to nameless partners in our dictator games is similar to the results reported in [START_REF] Andreoni | Giving According to GARP: An Experiment on the Consistency of Preferences for Altruism[END_REF]. Nameless partners are given 34.8%, 23.2%, and 16.6% of the token endowment in the 1:3, 1:1, and 3:1 exchange rates, respectively, in our experiments, where nameless partners were given 32%, 24.3%, and 20% of the token endowment in the equivalent treatments of [START_REF] Andreoni | Giving According to GARP: An Experiment on the Consistency of Preferences for Altruism[END_REF].

We can interpret nameless decisions under anonymity as the decision makers' baseline or unconditional generosity, because they have no information about the partners. Our data replicate the well-known finding of [START_REF] Andreoni | Giving According to GARP: An Experiment on the Consistency of Preferences for Altruism[END_REF] and of Fisman, Kariv, and Markovits (2007) that individuals are highly heterogenous in their unconditional altruism. In particular, we find that many subjects are perfectly selfish: in the three dictator games, 28%, 46%, and 64% of subjects pass zero tokens, whereas in the helping game, 20% set a cutoff of zero dollars.

V. Anonymity and Directed Altruism

In this section, we use the anonymous treatments to analyze how decision makers' altruistic preferences vary with social distance. In Section II, we motivated the following specification for estimating the strength of directed altruism:

(1) xmp =aZ+ YiDMp + ym + *mp-Recall that xmp is the decision maker's action in the anonymous treatment. Because agents' actions are bounded below by zero and above by fifty in the dictator games, and by zero and thirty in the helping game, we use Tobit regressions to estimate equation (1). We exploit the fact that we observe multiple actions for each decision maker in the anonymous treatment, and control for unobserved heterogeneity in the decision maker's baseline altruistic type y m by including random effects.18 We control for the social distance, Dmp, between the decision maker and the partner by including dummy variables SDÌ (meaning a direct friend at social distance S D = 1) to SD5 (meaning social distance SD = 5). The omitted categories are SD4 for the dictator games and SD5 for the helping game.19 The estimated coefficient on SDÌ in a dictator game, for example, should be interpreted as the number of extra tokens that the decision maker passes to a direct friend compared to a distant partner in the anonymous treatment, whereas the estimated coefficient on SD2 captures directed altruism toward a friend of a friend. The estimates of the Tobit regression for all of the dictator games and for the helping game are reported in the odd-numbered columns of Table III.

We also estimate the specification with additional covariates and report the results in the even-numbered columns of Table III. We include the decision maker's action toward a nameless player in the anonymous treatment as a proxy for the decision maker's baseline altruistic type ym-In the helping game, we can also control for the partner's baseline altruistic type by including the partner's nameless decision (because all subjects played both roles in the helping game). Furthermore, we added dummy variables for both players' gender, their class (sophomores, juniors, or seniors), and whether they share a staircase (dictator game) or a dormitory (helping game).20 Result 1. Baseline altruism and directed altruism are correlated.

Subjects who give more to nameless partners also give more to specific named partners.

The two variables that consistently and strongly predict how generously a decision maker treats a partner in her social network are the social distance from the partner and the generosity displayed toward a nameless partner. Looking across all regression specifications, for both the dictator games and the helping game, each one-unit increase in generosity toward a nameless partner is associated with a 0.56 to 1.40 unit increase in generosity toward a named player. Because the nameless decision and the named decisions were elicited one week apart, this continuity indicates a substantial degree of stability in the decision makers' preferences over time. Because the effect of "nameless altruism" on "named 19. The social network that we used for the second experiment is much larger because it potentially involves all Harvard undergraduates. Therefore, the maximum social distance between subjects is higher.

zO. Because the participation rate was lower tor the helping game, the same entry way" dummy variable is less useful. altruism" is fairly close to 1, we view the nameless decision of a decision maker as a useful proxy measure of his or her baseline altruism, a heterogeneous trait that strongly influences the decision maker's action toward specific named partners.

Result 2. Close social ties induce directed altruism. Allocations to friends are substantially higher than allocations to distant partners/strangers. Moreover, social distance also matters greatly: decision makers are substantially more generous to direct friends than to partners located at greater social distance. Generosity decreases quickly and monotonically with social distance, although the estimated coefficients on SD2 and SD3 are not significantly different from each other for all games. Given the three exchange rates in the dictator games, the distance coefficients are of similar absolute magnitude, which implies that decision makers are making a greater relative sacrifice in the case of inefficient altruism.

Interestingly, neither the subjects' gender nor their geographic proximity has a significant effect on generosity. However, the signs of the estimated gender coefficients for the decision maker are consistent with [START_REF] Andreoni | Which Is the Fair Sex? Gender Differences in Altruism[END_REF], who found that men are more likely to exhibit social surplusmaximizing preferences: they are more generous in dictator games when giving is efficient and less generous when giving is inefficient. College juniors are somewhat more selfish than are sophomores and seniors; however, most of the coefficients on the class dummies are insignificant.

VI. NONANONYMITY AND FUTURE INTERACTION EFFECTS

We now examine how a decision maker's allocation changes under nonanonymity (i.e., both the decision maker and the partner are told which choice was selected for payment) and discuss which modelenforced reciprocity, signaling, or preference-based reciprocitybest fits our results.

VI.A. Graphical Analysis

In Figure III we analyze the change in allocations (for the same named partner) between the nonanonymous treatment and the anonymous treatment. Because our helping game was a between-subjects design, we can only perform this exercise for dictator decisions. We divide decision makers into five groups depending on their generosity in the anonymous treatment (0 to 9, 10 to 19, etc.), where the most selfish subjects passed between 0 and 9 tokens. We then plot the average number of extra tokens passed in the nonanonymous treatment versus the anonymous treatment, %mp -%mp, by group and by social distance (a proxy for relationship value Vmp)-21

Decision makers substantially increase their action from the anonymous treatment to the nonanonymous treatment, except the most generous under anonymity.22 This effect is strongest, up to ten extra tokens, when the decision maker is selfish and when giving is efficient. The effect is half as large when giving is inefficient, where decision makers pass at most five extra tokens.

The main insight from this graph is that the nonanonymity effect is large for close friends and declines with social distance when giving is efficient (and is also somewhat present when giving is neutral). However, when giving is inefficient, the decision makers' additional contributions are quite small, and do not decrease with social distance for four out of the five groups. This result provides some preliminary evidence in support of the enforced reciprocity and preference-based reciprocity mechanisms and against the signaling mechanism.

The graph also suggests that directed altruism and the nonanonymity effect are substitutes: controlling for the strength of a relationship (by fixing either social distance or maximum network flow), we find that the nonanonymity effect decreases monotonically in most cases, as decision makers become more generous in the anonymous treatment.

VLB. Tobit Regressions

In Section ILA, we motivated the following specification for the nonanonymous condition:

(2) 5tMP = T]Z + OXMP + 4>VMP + VM + ¿MP, where xmp is the decision maker's action in the nonanonymous treatment when matched with a specific named partner P. We again use panel Tobit regressions to account for censoring and to control for unobserved heterogeneity in the decision maker's 21. In the NBER working paper we use network flow as an alternative proxy with qualitatively identical results.

¿2. iiiven in this case, the majority ot decision makers do not decrease their actionthe negative averages result from a few decision makers decreasing their contributions substantially in the nonanonymous treatment. response to the nonanonymous treatment. We proxy for the strength of the decision maker's relationship with the partner, Vmp, by including either social distance dummies or the maximum network flow measure.23 The omitted social distance is SD4 for the dictator games and SD5 for the helping game. The estimated coefficient on SDÌ in a dictator game, for example, should be interpreted as the number of extra tokens that the decision maker passes to a direct friend under nonanonymity compared to the number of extra tokens that he or she passes to a stranger under nonanonymity. All of our regressions control for the academic class of the decision maker and of the partner, because we expect the nonanonymity effect to be smaller for juniors and (especially) seniors, because the participants are less likely than sophomores to interact with each other in the future. On the right-hand side we also include the decision maker's action toward a nameless partner in the nonanonymous treatment as a proxy for the random effect VM that captures heterogeneity in how decision makers respond to nonanonymity.

Importantly, we control for the decision maker's intrinsic altruism toward the same partner P by including her decision in the anonymous treatment, xmp, on the right-hand sides of all of our regressions. This inclusion poses a problem for the helping game given its between-subject design, because for no decision maker/partner pair in the nonanonymous treatment do we observe the decision maker's choice for that partner in the anonymous treatment. Therefore, we estimate it by running an auxiliary random-effects Tobit regression with data from the anonymous treatment, and include social distance dummies and the same set of covariates Z (nameless decision, class dummies) as in our empirical specification of the nonanonymity mechanism.

For each of the three dictator games and for the helping game, we estimate three variants of our empirical model. We first use only social distance to proxy for the strength of a decision maker's relationship to the partner, then use only maximum network flow, and finally use both measures in the same regression. All results are reported in Table IV. Result 3. The observability of decisions by partners increases giving more for friends than for strangers. The differential effect is only induced when giving is efficient; therefore, the prospect of future interactions increases the surplus created.

w O i BC w Q I Q I I O Q co § O O o ¡ O o * <-v NTtHlOW0OXHCD^Oit^H Ci
W W w | w | w | w | w | w w CO J^ ^ ^ ^ ^ ^ C ^ CO 00 Oí E*" CO iO Q5 O5 CJi CD O 5 on • t> co Ttoocoi> cooocoocoo oãwoqo oopo cq^<N<Ncq<N "cj do dodo i> co ^' co ò h g ^ I w I w I w I w w *^ ^-^ ^-v r-^ /-v í-v ^^ ^v _^ ^^iOCDOiCOXO OO^Í4 CO CO (N H t^ t> i>coioiooooooo coo thococmcoo ■^ oqqiniflcoioiNTti PP cou3<n(nco(N OOOtHOtHOt-h ^S ^O^'O^CÍ- Í-v ^-v ^^ /-s ^"V Í-N "!^V í-s ^^ -, QOHOOOOHOHlNINNCOlfl H H ^ N t^ H en oinaicoco^cocooiooiio o ^ h co w a> 3-WO^H^lOOHOHHO O ÎÛ (N Tf

I 1é^

Itili co -g a» 5 Our main finding is that, controlling for a decision maker's anonymous action, her response to nonanonymity increases with the strength of the relationship to the partner, but only if giving is efficient (i.e., surplus-increasing). This is true regardless of whether we proxy for the strength of a relationship using social distance or maximum network flow. Note that this result is consistent with both the enforced reciprocity and the preference-based reciprocity mechanisms, but not with the signaling mechanism (which predicts excess generosity toward friends for all exchange rates).

^-v ^-n 3 «c "rt '3 « ^H Cl Í3 y tí rt J^ _, 00 Q CO O «j § H 8. 2 I tö 5B HONORS ^^^^^ - IO ¡a s O) s O s? CD » * s í -g s * ^ t^ IO O) O CD M * tí cö -a ^ t^ IO hoohS O) O CD M * ? a tí .« cö 3 -a -g ^-^ W ? ÍD CO
The magnitude of the nonanonymity effect is large, particularly in the dictator game with exchange rate 1:3. In this game, decision makers increase their action by 4.18 tokens when their partners are direct friends as opposed to socially distant partners (statistically significant at the 1% level). The social closeness effect is smaller, but still significantly different from zero, at the 5% level for friends of friends (SD2) in the efficient dictator game.24

Our results also provide some evidence for enforced, rather than preference-based, reciprocity.

Result 4. The nonanonymity effect increases with maximum network flow.

In Table IV we estimate a specification for each game including both social distance dummies and maximum network flow as covariates. For both the efficient dictator game and the helping game, we find that the coefficients on the social distance dummies decrease and become insignificant when we add network flow, whereas the coefficient on flow remains significant for the helping game. Additionally, for the helping game, a likelihood ratio test rejects the specification excluding network flow in favor of the specification with both social distance and network flow (p < .01).25

We also estimate a specification for the dictator game using network flow for allocations to direct friends, presented in Table V, to further demonstrate that network flow is capturing information about allocations not included in social distance (because here all partners have a social distance of one). Moreover, for direct friends, 24. In contrast, when we tested for directed altruism, we did not find such a strong effect for friends of friends.

25. For all three dictator games and the helping game, we cannot reject the specification with only network flow in favor of the specification with both network flow and social distance (p > .40 for all specifications). Notes. Standard errors are reported in parentheses. The dependent variable is the number of tokens passed by the decision maker to a direct friend in the nonanonymous dictator games. All specifications are estimated as Tobit regressions with decision-maker random effects. "Anonymous action" denotes the decision maker's action for the specific partner in the anonymous treatment. Network flow is calculated for a circle of trust K = 2. Average time spent per week is a categorical variable which takes the values 0 (less than half an hour per week), 1 (30 minutes to 1 hour), 2 (1 hour to 2 hours), 3 (2 hours to 4 hours), 4 (4 hours to 8 hours), and 5 (more than 8 hours a week).

Significance levels: ]: 10%; *: 5%; **: 1% .

we can include a control for the amount of time that the decision maker spends with the partner, because this would be an aspect of the relationship possibly omitted by social distance that would still be consistent with the preference-based model of reciprocity.26 We find that when giving is efficient, greater network flow increases the decision maker's generosity toward a direct friend under nonanonymity, even when we control for time spent together. Thus, network flow predicts generous allocations beyond the social distance information. Moreover, the estimated coefficient on time spent together is consistently insignificant and negative. We interpret these findings as evidence for the enforced reciprocity model. Result 5. The nonanonymity effect and directed altruism are substitutes. Altruistic individuals have a smaller change in allocations under nonanonymity than selfish individuals.

We also find that the estimated coefficients on the decision maker's anonymous action, xmp, are always less than one, which 26. However, the measure of time spent together is uncorrelated with our network flow measure for direct friends (p = .03). Thus, any predictive power of network flow appears not to relate to the frequency of interaction. Notes. An "average" row is calculated by dividing estimates for directed altruism (Table III) and the effect of nonanonymity (Table IV) by the average nameless decision in the anonymous treatment (Table II, "Nameless" column). A "standard deviation" row is determined by calculating the increase in nameless decision (measured in standard deviations) that would have a predicted increase in choice equal to the estimates for directed altruism and nonanonymity. For the "network flow" column we report the estimated effect of a onestandard-deviation increase in network flow (equal to 10 units of network flow for "circle of trust" K = 2).

implies that directed altruism and the decision maker's response to nonanonymity are indeed substitutes. The total difference between the nonanonymous allocation and the anonymous allocation will be smaller for a more altruistic subject than for a selfish subject. This conclusion is also consistent with the enforced reciprocity model.

VII. Comparing Altruism to Enforced Reciprocity

Having established that both directed altruism and enforced reciprocity play a substantial role in determining allocation decisions when subjects are connected through a social network, we now attempt to benchmark the relative importance of each effect, compared to baseline altruism, for each condition we study. In Table VI, we divide the estimated coefficients on social distance dummies (SDÌ to SD3) from both the anonymous (i.e., measuring directed altruism) and the nonanonymous (i.e., measuring enforced reciprocity) allocations by the average generosity toward nameless partners in the anonymous treatment. In other words, we calculate what percent of the baseline altruism effect (relative to selfishness) the network effects represent. For the nonanonymous case, we also include the estimated effect of a one-standard-deviation increase in network flow. Directed altruism toward friends is equal to 52% of the average nameless generosity shown in the efficient dictator game, and is equal to 88% for the helping game. When altruism is inefficient, the directed altruism effect almost equals average nameless generosity (a 95% increase)nearly double the magnitude of the efficient case (although, recall that the absolute increase in tokens is slightly smaller). Social distance, therefore, is as important a determinant of a subject's generosity as his or her baseline altruism, particularly when giving is inefficient.

In the nonanonymous treatment, friends receive an extra transfer of surplus, equal to almost 24% of average nameless generosity for the efficient dictator game and about 35% of nameless generosity for the helping game. Friends of friends receive an extra transfer of about 18% of nameless generosity in the efficient dictator game. We find a similar pattern, but with slightly smaller magnitudes, for the neutral dictator game. Taken all together, the effect of nonanonymity is about half as large as the directed altruism effect.

Additionally, the nonanonymity effect is generally weaker for decision makers who are juniors and seniors: the signs on the junior and senior dummies are consistently negative, although they are not always statistically significant. This finding is consistent with our model of enforced reciprocity, because the length of the future relationship (and, thus, its value) is potentially shorter (lower) for upperclassmen, because they will live in the same dorm for a shorter time.

We also consider a different benchmark for the magnitude of directed altruism and enforced reciprocity: how large an increase in baseline altruism (i.e., how many standard deviations) would it take to equal the effect of social connections?27 Therefore, in Table VI, we also report the estimated coefficients on SDÌ, SD2, SD3, and network flow as percentages of the standard deviation of the distribution of nameless decisions. We find that greater social proximity to the partner in the anonymous dictator games moves the decision maker's generosity by at least 0.39 standard deviation, and by a maximum of 1.93 standard deviations in the anonymous helping game. Similarly, the effect of enforced reciprocity by this comparison represents an additional increase in generosity almost half as large as the altruism effect for the efficient dictator game and the helping game (a change of 0.14 and 0.69 standard deviation, respectively).

VIII. Correlation in Altruistic Preferences

Our design allows us to analyze whether subjects who are more altruistic also have friends who are more altruistic. We separate decision makers into (approximate) quintiles based on their choices for nameless partners. Tables VII and VIII present the resulting distributions of friends' generosity. Result 6. Friends sort by baseline altruism. Subjects with a high level of baseline altruism have more friends with a high level of baseline altruism, whereas selfish subjects have more selfish friends.

First, we find that altruistic and selfish subjects have the same number of friends.28 However, a subject's baseline altruism is correlated with the baseline altruism of his or her friends (x2 test: DG p < .001, HG p < .01). That is, selfish subjects have a greater number of selfish friends, and fewer altruistic friends, whereas altruists have fewer selfish friends and a greater number of altruistic friends. In particular, the most altruistic quintile in the helping game has 25% more highly altruistic friends than any other group; in the dictator game, the two most altruistic groups had over 20% more highly altruistic friends than any other group. Moreover, a subject's friends' mean nameless allocation choice increases with the subject's baseline altruism. The most altruistic subjects have friends that are 25% more altruistic than the most selfish subjects in the dictator game, and 14% more altruistic in the helping game. Using ¿-tests, the third, fourth, and fifth quintiles are significantly different from the first in the helping game, and the fourth and fifth are different from the first in the dictator game. A nonparametric equality-of-medians 28. The same holds for the number of people who list the subject as a friend. test rejects the hypothesis that the five quintiles are drawn from distributions with the same median (DG p = .039, HG p < .026). It seems that either subjects prefer to become friends with people who have similar social preferences, or their social preferences become more similar after they initiate a friendship.

An important consequence of the correlation in friends' baseline altruism is that it pays to be generous. For the anonymous treatment of the helping game, Table IX (column (1)) displays the results of regressing the average allocation to partners from decisions made by direct friends on the partners' baseline altruism (by quintile): partners with higher baseline altruism have substantially higher earnings. For example, direct friends of the most altruistic partners set the cutoff more than five dollars higher than the direct friends of the most selfish partners. Interestingly, this effect is entirely due to kinder partners having nicer friends, and is not due to generally kind partners being treated more nicely by their friends: we have already shown in our directed altruism regressions in Table III that decision makers do not treat generous partners better. Indeed, when we also control for the average baseline altruism of the decision makers in Table IX (column (2)), the partners' baseline altruism no longer predicts their earnings from friends' decisions.

IX. Conclusion

We use large field experiments in real-world social networks to jointly measure two explanations of prosocial behavior: the prospect of future interaction and directed altruism. We find support for both mechanisms, although the future interaction effect is half as strong as the directed altruism effect. The mechanisms also have different welfare effects: directed altruism promotes equitable allocations, whereas enforced reciprocity promotes efficient allocations.

Our results suggest that it is difficult to measure the importance of norms of reciprocity empirically (based on dynamic game effects) without first measuring underlying directed altruism. For example, in empirical studies of informal lending and risk sharing, it may be as important to measure directed altruism across social ties (using diagnostic games) as it is to observe cash and inkind transfers. Although both directed altruism and enforced reciprocity suggest that capital in small communities will more likely be directed toward close friends and relatives, the relative importance of altruism over reciprocity may suggest that resources are not being allocated efficiently to the most profitable projects. A better understanding of the strength and reach of altruistic ties within and across families can help policy makers target outside transfers more effectively.29

Our result that friends cluster by baseline altruism raises another interesting question for future research: do our friends shape our social preferences (treatment effect), or do we seek out friends with similar social preferences (selection effect)? This could help explain to what extent the distribution of preferences, as observed in the laboratory by [START_REF] Andreoni | Giving According to GARP: An Experiment on the Consistency of Preferences for Altruism[END_REF] and [START_REF] Fisman | Individual Preferences for Giving[END_REF], is endogenous. In Leider et al. (forthcoming), we provide preliminary evidence against selection based on altruistic type. When we elicit beliefs of partners about the generosity of their friends toward them and toward anonymous others, we find that partners expect to be treated better by their friends, but subjects do not incorporate their friends' specific baseline altruism into their beliefs. Therefore, it appears that although friends tend to cluster by their altruistic type, their beliefs about decision makers' generosity are mostly 29. [START_REF] Angelucci | Insurance in the Extended Family[END_REF] show that random positive income shocks from the Progresa natural experiment are shared within rather than across extended families (consistent with a model of directed altruism).

  Figure I Examples to Illustrate Difference between Maximum Network Flow and Social Distance All links are assumed to have unit capacity. The examples illustrate the different features of the social network that are captured by social distance and maximum network flow, respectively: the addition of common friends will necessarily increase flow but can leave social distance unchanged.

  N = 206) (N = 286) (N = 312) (N = 97) (N = 4) (N = 193) Ex.

  Figure III Difference between Number of Passed Tokens in the Nonanonymous and Anonymous Treatments in the Dictator Game by Social Distance For each decision maker/partner pair, the difference between the number of tokens allocated in the nonanonymous and the anonymous treatments was calculated. Bars show average difference grouped by the decision maker's contribution level in the anonymous treatment and by social distance. The number of subjects in each group is presented below the bar.

  's actions under nonanonymity and anonymity, respectively, and V^p describes the value of the relationship between decision maker and partner (proxied by social distance).

		TABLE I
	Testable Predictions about Decision Makers' Allocation Decisions under
	nonanonymity versus anonymity
		Enforced		Preference-based
		reciprocity	Signaling	reciprocity
	Greater generosity toward friends (0 > 0) when giving is	Yes	Yes	Yes
	efficient Greater generosity toward friends (0 > 0) when giving is	No	Yes	No
	inefficient Altruistic decision	Yes	No	Yes
	makers are relatively less generous toward friends compared to
	strangers Maximum network flow	Yes	No	No
	is a separate predictor of generosity beyond social distance
	Note. We estimate the empirical model x^jp = r¡Z + Oxj^p + ^MP + VM + €MP> where x^p and x'jp are the decision maker

TABLE II Summary

 II Statistics for Decision Makers' Actions in Dictator and Helping Games

TABLE V

 V Effects of "Average Time Spent per Week" and Network Flow on Decision Makers' Generosity toward Direct Friends under Nonanonymity (Dictator Game Only)

		Dictator 1:3	Dictator 1:1	Dictator 3:1
		(1)	(2)	(3)
	Anonymous pass	0.25	0.238	0.474
		(0.063)**	(0.211)	(0.115)**
	Network flow	0.676	-0.024	0.155
		(0.306)*	(0.395)	(0.262)
	Average time spent per week	-0.328	-0.089	-0.060
		(0.368)	(0.488)	(0.323)
	Const.	12.131	13.946	4.998
		(3.640)**	(5.493)*	(3.286)
	Obs.	206	206	206

TABLE VI Relative

 VI Magnitudes of Directed Altruism and Nonanonymity Effects as Percentages of all the Decision Makers' Average Nameless Action and as Percentages of a Standard Deviation in Nameless Actions

	Directed altruism relative to Effect of nonanonymity relative to
	SDÌ SD2 SDS	SDÌ SD2 SDS Network flow
	52 Standard dev 39 Average	8 -8 8 -4	Dictator game (1:3) 24 18 14 10	3 2	19 11
	52 16 Standard dev. 41 14 Average	3 5	Dictator game (1:1) 21 12 24 14	9 10	10 11
	95 49 43 Standard dev. 48 25 23 Average	Dictator game (3:1) -7 8 -4 4-1	-3	-6 -3
	88 36 12 Standard dev. 192 82 28 Average	Helping game 35 13 69 25	19 38	30 59

TABLE IX Regressing

 IX Average Allocation to Partners from Direct Friends on Baseline Altruism . Standard errors are reported in parentheses. The dependent variable is a partner's average allocation in anonymous treatment from decisions made by friends.

		Helping game
		(1)	(2)
	Partner's nameless decision e [1, 5]	1.048	0.357
		(1.02)	(0.96)
	Partner's nameless decision e [6, 12]	3.074	0.545
		(0.93)**	(0.91)
	Partner's nameless decision e [13, 15]	4.567	0.521
		(0.92)**	(0.98)
	Partner's nameless decision e [16, 30]	5.275	-0.384
		(1.17)**	(1.27)
	Decision maker's nameless choice		-0.474
			(0.054)**
	Const.	9.747**	7.679**
		(0.73)**	(0.73)**
	Obs.	549	549

Notes

More than 90% of Harvard undergraduates were already members of f acebook . com at that time.

Subjects could also list nonparticipants in our experiment as friends.

During both waves ot the experiment, the network information was also used for other experiments.

Our results are very similar when we estimate equation (1) using standard random effects or fixed effects GLS.

In one specification, we include both measures in the same regression.

This measure is used in[START_REF] Andreoni | Giving According to GARP: An Experiment on the Consistency of Preferences for Altruism[END_REF] and[START_REF] Fisman | Individual Preferences for Giving[END_REF].

Williams, and Kate Ambler for very careful proofreading and numerous suggestions. Rosenblat thanks the Federal Reserve Bank of Boston for its hospitality. We are grateful to the Social Security Administration and the Center for Retirement Research at Boston College for financial support through a Sandell Grant (Möbius, Rosenblat) and to the National Science Foundation (Leider). the President and Fellows of Harvard College and the Massachusetts Institute of Technology.

driven by expectations of directed altruism. Future research can utilize carefully designed field experiments to measure the relative strength of selection versus social interaction in the formation and evolution of social preferences.


Guillaume Theyssier
email: guillaume.theyssier@cnrs.fr

The Mirage of Universality in Cellular Automata

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Eric, the collector

The present note responds to an invitation to contribute to a book at the occasion of Eric Goles 70th birthday. Before diving into the scientific content, I should say a few words about Eric and the motivation behind this note.

Anyone knowing Eric certainly had the pleasure to listen to some of his colorful anecdotes (I certainly did). He owns a large collection, large enough to adapt to a wide variety of listeners and circumstances. The collection is in fact twice as large, because each anecdote, usually told to an international audience, is doubled with a more confidential Chilean version full of slang words. Eric's pleasure of telling stories is obvious, he has generously shared his collection, but nobody has listened to the same sequence of anecdotes and we all end up with a different global picture, much like the adventurous readers of the antinovel of Cortázar.

The collection of models and systems studied by Eric in its numerous scientific publications is equally striking. It abounds in small examples that are carefully analyzed and shown to capture important phenomena. It connects different points of view and different communities of researchers. It seems to never end up in the exact same theoretical framework and invites us to think about details that make a difference. In short, there is an anti-Bourbakist quality to it.

At the heart of this scientific collection (at least from what I can tell from my collaboration with Eric), there is the question of the computational universality of small dynamical systems, and how it manifests itself in the complexity of various associated decision problems. Computational universality of dynamical systems is a topic that might seem boring to the classical computer scientist (after all Turing showed the existence of a universal machine in the 1930s) and not serious for the dynamical systems community (this is not real maths ). Part of the problem is that this kind of research is endangered by what I would call the mirage of universality: the illusion that there must be universal consequences to the fact of being "computationally universal" independently of the precise definition used, and that such a statement, even given without technical details, gives information by itself. Pursuing this mirage, one is tempted to put forward vague theorem statements and hide the concrete mathematical result in the proofs (or sketch of). To make an analogy, no paper in computational complexity would use theorem statements like "Problem X is hard" and then, hidden in the proof details, unveil the definition of "hard". On the contrary, computational complexity theory has been extremely fruitful by putting forward a vast "zoo" of precisely defined complexity classes, often with a corresponding notion of reduction.

Of course, there is a lot to say and a lot has already been said about the mathematical formalization of computational universality in dynamical systems, but my intention here is clearly not to start a comprehensive survey on the topic [START_REF] Delvenne | Decidability and universality in symbolic dynamical systems[END_REF][START_REF] Ollinger | Universalities in cellular automata a (short) survey[END_REF]. Instead, I would like to invite the reader to a quick tour of examples and properties that break this mirage of universality. Most of them were encountered or established during my collaboration with Eric, and I hope this note can give a clue about the richness of Eric's scientific collection.

Content of the note:

To simplify exposition, I chose to restrict to (classical) cellular automata and tackle three main topics in three separate sections. Each topic shows examples of "computationally universal" cellular automata that, in some sense, do not behave as expected, or pair of examples that behave differently with respect to some parameter:

• efficient versus unbounded computations: how some cellular automata are able to embed one type of computations but not the other;

• transient versus repeatable circuit simulations: about the existence of (at least) two fundamentally different ways to simulate Boolean circuits in cellular automata, and their consequences;

• hidden universality: how cellular automata might seem 'simple' according to some parameter despite being actually universal.

Before starting, some standard definition are given below to set up our framework.

It should be noted however that a growing trend in symbolic dynamics has shown the importance of computability considerations. Some of these results were even published in real math journals...

Standard definitions and notations

For any finite set (the alphabet) and positive integer (the dimension), we consider the space of configurations Z , i.e. the set of maps giving a state from to each position in the lattice Z . The state of configuration ∈ Z at position ∈ Z will be denoted either ( ) or .

For ∈ N, let B ( ) be the set of positions of Z of maximum norm at most :

B ( ) = { ∈ Z : ∞ ≤ }.
Then for any ∈ B ( ) , we define the cylinder set [ ] centered on cell 0 by:

[ ] = { ∈ Z : ∀ ∈ B ( ), = }.
These cylinder sets can be chosen as a base of open sets of the space Z endowing it with a compact topology [START_REF] Kůrka | Topological and symbolic dynamics[END_REF]. Equivalently, the same topology can be defined by the Cantor distance:

( , ′ ) = 2 -min{ ∞ : ≠ ′ } .
A cellular automaton of dimension and state set is a map acting continuously on configurations and translation invariant way. Equivalently (Curtis-Lyndon-Heldund theorem [START_REF] Hedlund | Endomorphisms and Automorphisms of the Shift Dynamical Systems[END_REF]), it can be defined locally by a neighborhood (a finite subset of Z ) and a local transition map :

→ as follows:

∀ ∈ Z , ( ) = +
where + denotes the map ′ ∈ ↦ → + ′ . The radius of is the smallest integer such that ⊆ B ( ) where is some neighborhood for which there is a local map : → defining as above. induces an action on finite patterns as follows. For any ∈ N and any ∈ B ( + ) , ( ) is the finite pattern ∈ B ( ) obtained by application of on at each position from B ( ), i.e. such that

∀ ∈ [ ], ( ) ∈ [ ].
We are now going to define a notion of universality for cellular automata. We choose this one for two reasons: first it is one of the strongest form of universality and will serve us as a benchmark in the following, and second, it is intrinsic to the model of cellular automata and make no reference to other models of computation (for more details, see [START_REF] Ollinger | Universalities in cellular automata a (short) survey[END_REF][START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF][START_REF] Delorme | Bulking II: Classifications of cellular automata[END_REF]).

This notion, called intrinsic universality, is based on a notion of (intrinsic) simulation that is defined through two ingredients [START_REF] Delorme | Bulking II: Classifications of cellular automata[END_REF][START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF].

The first ingredient is a notion of cell-wise simulation that works by restriction to a sub alphabet and then projection onto the target alphabet. To be more precise let and be cellular automata of dimension . We denote by ⊳ the fact that is obtained from by cell-wise restriction and projection, formally: ∃ : ⊆ → surjective such that for all ∈ Z

• ( ) = • ( ) where : Z → Z is the cell-wise application of . In the language of dynamical systems, ( , Z ) is a factor of ( , Z ) which is a sub-system of ( , Z ). Now we add the second ingredient, rescaling, that allows to turn a cell-wise simulation into a simulation that works by blocks: blocks of cell of the first CA are simulated by blocks of cell of the second CA. Given a rectangular shape m = ( 1 , . . . , ) and some alphabet we define the bloc recoding map m from Z to

1 2 ••• Z by: m ( ) ( 1 , . . . , ) = ( 1 1 , . . . , ), . . . , ( 1 1 + 1 -1, 2 2 , . . . ,
),

(

1 1 , 2 2 + 1, 3 3 , . . . , ), . . . ( 1 1 + 1 -1, . . . , + -1)
It is a bijection that recodes any configurations by blocks of shape m. Now if is a positive integer and z ∈ Z , we define the rescaling of of parameters m and as the CA <m, > = m • • -1 m . We finally say that simulates , denoted ≤ , if there are parameters m, ,m ′ and ′ such that <m, > ⊳ <m ′ , ′ > . We also say that strongly simulates if there are parameters m and such that ⊳ <m, > . Then, a CA is intrinsically universal if for any CA we have ≤ . It can be shown that an intrinsically universal CA can in fact strongly simulate any CA [START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF].

Finally, we assume the reader is familiar with basic notions and results of computability and complexity theory. We will use the following standard classes of decision problems:

• P is the set of problems which can be solve be a deterministic Turing machine in polynomial time;

• NLOGSPACE is the set of problems which can be solve be a non-deterministic Turing machine in logarithmic space;

• Σ 0 1 is the set of recursively enumerable problems (which contains the halting problem).

Without explicit mention and when speaking about P-completeness we consider LOGSPACE reductions. When speaking about Σ 0 1 -completeness we usually consider many-one reductions.

Efficient vs. unbounded computations

It is well-known that, besides the reference model of Turing machines, there are other ones that fundamentally differ because they either only allow efficient but bounded computation (like Boolean circuits) or unbounded but slow computations (like Minsky machines) [START_REF] Minsky | Computation: Finite and Infinite Machines[END_REF]. We would like to illustrate this aspect in the framework of cellular automata in a precise manner. To simplify, we restrict to dimension 1 in this section. We first define two classical problems associated to any CA which will serve as canonical indicators for both aspects mentioned above: efficiency and unboundedness of computations.

The first one is about short-term predictability within a bounded time range and provides a fine-grained complexity measurement within class P. Definition 1 Let be any CA of radius and alphabet . The prediction problem PRED is defined as follows:

• input: > 0 and ∈ B ( ) • output: ( ) ∈ .
The second one asks for a prediction about an unbounded future and provides a coarse-grained complexity measure allowed to cross the decidable barrier. It could be refined in many ways as in the definition of universality for dynamical symbolic systems from [START_REF] Delvenne | Decidability and universality in symbolic dynamical systems[END_REF]. We prefer to keep it simple for the clarity of exposition. We say a configuration ∈ Z is eventually bi-periodic if it is eventually periodic to the left and eventually periodic to the right, said differently if it is of the form ∞ • • ∞ where , and are finite words.

Definition 2 Let be any CA of radius and dimension 1. The reachability problem UBPRED is defined as follows:

• input: an eventually bi-periodic configuration = ∞ • • ∞ and a state .

• output: decide whether there is ∈ N such that ( ) 0 = .

One of the well-know results of computational universality in cellular automata is about elementary rule 110 given by the local rule : {0, 1} 3 → {0, 1} with

( , , ) = (1 - ) • max( , ).
It is interesting to note that the first proof of computational universality of this cellular automaton due to M. Cook [START_REF] Cook | Universality in elementary cellular automata[END_REF] was enough to prove undecidability of UBPRED but did not give information about problem PRED . It is only later, by a strong improvement in one step the the reduction, that PRED was proven to be P-complete [START_REF] Neary | P-completeness of cellular automaton rule 110[END_REF]. The purpose of this section is precisely to make clear that there is generally no implication in either direction between the P-hardness of PRED and the undecidability of UBPRED. Definition 3 A CA is a freezing CA if, for some (partial) order ≤ on states, the state of any cell can only decrease, i.e.

( ) ≤

for any configuration and any cell .

The definition above was introduced in [START_REF] Goles | Introducing freezing cellular automata[END_REF] in studied more in depth in [START_REF] Ollinger | Freezing, bounded-change and convergent cellular automata[END_REF]. Similar cellular automata corresponding to bounded changes or bounded communications were also considered in the literature with the point of view language recognizers [START_REF] Vollmar | On cellular automata with a finite number of state changes[END_REF][START_REF] Kutrib | Cellular automata with sparse communication[END_REF][START_REF] Olivier Carton | Counter machines and distributed automata -A story about exchanging space and time[END_REF]. Under the hypothesis that NLOGSPACE ≠ P, the following results show examples of cellular automata that can embed arbitrary unbounded computation, but not in an efficient way.

Theorem 1 (Section 4.3 of [23])

For any freezing CA of dimension 1, the problem PRED is in NLOGSPACE. There exists a 1D freezing CA such that UBPRED is Σ 0 1 -complete.

We are now going to build an example with the opposite computation embedding properties: as hard as it can be in the short term (it can embed efficiently bounded computations), but decidable in the long term (it can not embed unbounded computations). It is inspired from [START_REF] Ollinger | Freezing, bounded-change and convergent cellular automata[END_REF]Example 7] and consists in a simulation of some P-complete cellular automaton inside finite zones, with some head controlling the simulation and forced to move back and forth inside the zone and shrink it by one cell at each bounce on a boundary. The simulation is such that one step of the simulated cellular automaton is done at each pass so that there is only a quadratic slowdown (see Figure 1). Let be any 1D CA on alphabet with radius 1 and local map : 3 → . We define Z on alphabet = { , + , } ∪ ′ with ′ = × × {←, →, , } and radius 1 as follows:

• , the error state, is a spreading state: any cell with in its neighborhood turns into state ; a configuration is valid if never appears in its orbit;

• , the blank state, never changes except in presence of the error state; + becomes except in presence of the error state; a maximal connect component of cells in state ′ is a working zone;

• in a working zone, patterns of the form ( , ,

) ( ′ , ′ , ), or ( ′ , ′ , ) ( , , ), or ( , , ) ( ′ , ′ , ′ ) with { , ′ } ⊆ {←, →}, or ( , , ) ( ′ , ′ , ) or ( , , ) ( ′ , ′ , )
with ∈ {←, →}, are forbidden and generate an state when detected; therefore in a valid configuration and in each working zone there is at most one occurrence of a state of the form ( , , {←, →}) called the head;

• a cell without forbidden pattern (from previous item) and without head in its neighborhood doesn't change its state;

• the movements and actions of the heads are as follows:

-inside a working zone, the head in state ← moves left, the head in state → moves right; the local map is only applied the head moves left to right; precisely we have the following transitions:

( , , ), ( ′ , ′ , ←), ( ′′ , ′′ , ) ↦ → ( ′ , ′ , ) ( , , ), ( ′ , ′ , ), ( ′′ , ′′ , ←) ↦ → ( ′ , ′ , ←) ( , , ), ( ′ , ′ , →), ( ′′ , ′′ , ) ↦ → ( ′ , ′ , ) ( , , →), ( ′ , ′ , ), ( ′′ , ′′ , ) ↦ → ( ( , ′ , ′′ ), ′ , →)
-when a boundary of the working zone is reached, the head bounces, changes of direction and the working zone get shrinked by one cell; precisely we have the following transitions:

, ( , , ), ( ′ , ′ , ←) ↦ → ( , , ←) , ( , , ←), ( ′ , ′ , ) ↦ → ( , , →) , ( , , →), ( ′ , ′ , ) ↦ → ( , , ) , ( , , ), ( ′ , ′ , →) ↦ → + ( , , →), ( ′ , ′ , ), ↦ → ( ′ , ′ , →) ( , , ), ( ′ , ′ , →), ↦ → ( ′ , ′ , ←) ( , , ), ( ′ , ′ , ←), ↦ → ( ′ , ′ , ) ( , , ←), ( ′ , ′ , ), ↦ → +
(note the swap between and in the third transition above to initialize the sequential application of ) -finally the head disappears in a working zone of size 1, precisely: ′ , ( , , ), ′′ ↦ → ( , , ) for any { ′ , ′′ } ⊆ { , + }.

Theorem 2 For any , the problem UBPRED Z is decidable in polynomial time.

If is chosen so that PRED is P-complete, then PRED Z is P-complete.

Proof For the first part of the Theorem, let us consider an eventually bi-periodic configuration = ∞ • • ∞ . There are four cases:

•

is not a valid configuration, which means that it contains a working zone with a forbidden pattern. Since the forbidden pattern are locally detectable, such a forbidden pattern must be detected inside the finite word (considering the worst case where or is of size 1). Therefore, in time which is linear in the sizes of , and we have Z ( ) 0 = ;

• is a valid configuration and position 0 belong to a finite working zone in . Since the left and right boundary of this zone must belong either to , or or , the zone is of linear size and it gets completely shrinked in quadratic time, meaning that the state of position 0 will no longer change after a quadratic time;

• is a valid configuration and position 0 belongs to an infinite zone in . In this case, the position of the head must belong to either , or and the same for the eventual (unique) boundary of the zone. Therefore, after a linear time in the worst case, cell 0 will never change again (for instance, the head comes from the right, bounces to the left boundary, crosses once more position 0, but never comes back again);

• is a valid configuration but position 0 does not belong to some working zone, then for any ≥ 1 we have Z ( ) 0 = .

We deduce that that after a quadratic time the state of cell 0 does not change any more, so it is sufficient to simulate Z on for this number of states to solve problem UBPRED Z .

For the second part of the Theorem, see [23, Lemma 1 and Proposition 5].

Transient vs. repeatable circuit simulation

In this section we focus on dimension 2 and simulation of Boolean circuit and logical gates by cellular automata. Showing how a cellular automaton can embed Boolean circuits is one of the common methods used to claim its Turing universality (see for instance [START_REF] Durand | Cellular Automata: a Parallel Model, volume 460 of Mathematics and its Applications[END_REF][START_REF] Banks | Universality in cellular automata[END_REF][START_REF] Ollinger | Universalities in cellular automata a (short) survey[END_REF]).

We are now going to describe two modes of simulation of a set of logical gates by a cellular automaton, which were formalized in [START_REF] Goles | On the complexity of two-dimensional signed majority cellular automata[END_REF]. The basic simulation mechanism behind both simulation modes uses square blocks concatenated in a grid-like fashion. Each such square block represents a part of a concrete Boolean circuit (either a node or wire). The definition doesn't require any specific way of representing information inside the blocks, just that the family of blocks use coherent representation of information so that the Boolean logic works when assembling them. More concretely, they communicate information with their four neighbors (north, east, south, west) in such a way that each one implements a Boolean function with at most 2 inputs and at most 2 outputs.

In the sequel all considered blocks will compute one of the following maps (we represent them using type {0, 1} 4 → {0, 1} 4 in order to make explicit the position of inputs and outputs among the neighbors in the order north, east, south, west): AND( , * , * , ) = 0, min( , ), 0, 0 OR( , * , * , ) = 0, max( , ), 0, 0 CROSS( , * , * , ) = 0, , , 0 NOP( * , * , * , * ) = 0, 0, 0, 0 FORK( * , * , * , ) = 0, , , 0

WIRE , ∈ {0, 1} 4 = ∈ {0, . . . , 3} ↦ → ( ) if = 0 else
for any ≠ ∈ {0, . . . , 3}. Note that any function above is such that (0, 0, 0, 0) = (0, 0, 0, 0).

We denote by ( ) the set of 4-uple that can be obtained as an image of . The WIRE , functions are just all the possible ways to read a bit on one side and transmit it to another side. Together with the NOP and FORK function they represent the basic planar wiring toolkit denoted in the sequel. The NOP gate is special in that one considers it has 4 inputs and 4 outputs.

The two circuit simulation modes share the same block representation of circuit and information, but they differ in their requirement about the dynamical evolution of blocks. In the first mode, called transient mode, the gates can be used only once and nothing is granted concerning their evolution afterwards. The second mode, called repeatable mode, asks for each gate to go back to some acceptable state each time they are used so that they can be used again. Both modes require the simulation to work in constant time.

Let G ⊆ {AND,OR,CROSS} be a set of gates. Let be a CA with states set and > 0 be an integer. Consider a set ⊆ × of patterns, the valid blocks, each of which as a type where ∈ G ∪ and ∈ ( ) and such that, for any , there is some block of of type . If a block ∈ has type ( , , , ) for some , we say it has north value , east value , south value and west value . Finally let Δ > 0 be some constant. A configuration is valid if it is a concatenation of valid blocks where output sides of a block must face input sides of its corresponding neighbors. Given a block ∈ of type in a valid configuration, we say that it makes the correct transition if it becomes a block of type after Δ steps where = ( , , , ) is the output of on the input read from surrounding blocks, precisely: the block at the north of has south value , the block at the east of has west value , etc.

Transient simulation. We say that simulates the set of gates G in transient mode with delay Δ and valid blocks if for any valid configuration , the configuration Δ ( ) is valid and for any ∈ G ∪ , any block of type (0,0,0,0) in makes the correct transition.

Repeatable simulation. The simulation is repeatable if any block in any valid configuration makes the correct transition.

Before stating some theorems, let us define a decision problem associated to any 2D cellular automaton that will serve as a benchmark to separate the two kinds of circuit simulation above. Definition 4 Let be any 2D CA of radius and alphabet , and a non-decreasing function such that 1 ≤ ( ) ≤ 2 ( ) The prediction problem CYCLE is defined as follows:

• input: a periodic configuration of period × • output: is the length of the temporal cycle reached from strictly greater than ( )? The first mode of simulation (the repeatable mode) is the strongest one, and is actually equivalent to intrinsic universality even if we use only monotone gates. In this case, although the definition does not explicitly provide crossing gates, it is always possible to realize a dynamical crossing and build arbitrary reusable bloc elements leading to intrinsic universality.

Theorem 3 ([11]

) A 2D CA is intrinsically universal if and only if it can simulate a AND, OR circuitry in a repeatable way. In this case PRED is -complete, UBPRED is Σ 0 1 -complete and CYCLE is PSPACE-complete for some . To illustrate the difference between the two modes we shall use the symmetric signed majority cellular automaton: it is essentially a majority rule where the state of each neighboring cell can be inverted or not before evaluating majority, this being done according to a local invariant sign vector and in a symmetric way: if cell inverts the value of its neighbor ′ , then ′ will also invert the value of . We use the von Neumann neighborhood = {(0, 0), (0, 1), (1, 0), (0, -1), (-1, 0)}. The symmetric signed majority cellular automaton 1 is defined over state set = {-1, 1} 6 . To simplify notation, we will see each state ∈ as a pair ( ( ), ( )) where ( ) ∈ {0, 1} represent the inner state and ( ) ∈ {-1, 1} is a sign vector associating a sign to each neighbor of the von Neumann neighborhood. For any configuration ∈ Z 2 , any cell and any cell ′ ∈ + we define the symmetric weight ′ ∈ {-1, 1} as ′ = ( ( ) ( ′ -)) ( ( ′ ) ( -′ )). We note that ′ = ′ , hence the name symmetric. 1 is then defined as follows.

1 ( ) = ( , ( )) where

= 1 if ′ ∈ + ′ ( ′ ) > 0, -1 otherwise.
The following theorem shows that transient simulations are strictly weaker than repeatable simulations, 1 being an example capable of the former, but not the latter.

Theorem 4 ([11]

) If a 2D CA can simulate a {AND, OR, CROSS} circuitry in transient mode, then its associated problem PRED is -complete. 1 defined above can simulate a {AND, OR, CROSS} circuitry in transient mode. However, 1 is not intrinsically universal and such that the problem CYCLE 1 is in P if ≡ 1 and trivial else.

Hidden universality

When proving that some cellular automaton is computationally universal, it can be acceptable to avoid a precise definition of universality if the construction makes it clear enough. However, a precise definition seems necessary when ones want to show that some cellular automaton is not universal. To avoid formalism, one could be tempted to use a shorter path: prove that, according to some well-chosen parameter, the considered cellular automaton is too simple to be universal. The intuition is that a universal cellular automaton should have roughly the highest complexity for the parameter. This approach can be made precise and yield some proof tools of non-universality in some contexts [START_REF] Goles | Communication complexity and intrinsic universality in cellular automata[END_REF]. The purpose of this section is to recall that things can get counter-intuitive and such a parameter must be chosen carefully.

Hidden Minsky machines simulation

The limit set of a cellular automaton is the nonempty closed subset

Ω = ∈N ( ).
It represents the set of configurations that may appear arbitrarily far in the evolution and the restriction of to Ω is often considered as the asymptotic dynamics of . The limit language is the set of finite patterns that occur in some configuration of Ω . It is not difficult to see that the limit language is always co-recursively enumerable. However, there are known examples of non-recursive ones [START_REF] Hurd | Nonrecursive cellular automata invariant sets[END_REF]. The attentive reader of [START_REF] Čulik | On the limit sets of cellular automata[END_REF] has probably spotted the affirmation that universal cellular automata have a non-recursive limit set. Depending on the definition of universality, this affirmation can be false. The following theorem shows that arbitrary Minsky machine simulations can be realize while maintaining a simple limit set (see [START_REF] Goles | On the limit set of some universal cellular automata[END_REF] for the precise definition of simulation).

Theorem 5 ([10])

For any Minsky machine there exists a CA of dimension 1 that simulates but whose limit language is regular.

Hidden intrinsic universality

Following Theorem 5, one can go one step further and hide intrinsic universality behind a simple limit set (at the price of a complexity increase from regular to NLOGSPACE). The main trick of the next theorem is inspired from [START_REF] Kari | Rice's theorem for the limit sets of cellular automata[END_REF]: adding to a given cellular automaton on alphabet , a firing squad component (see Figure 2) that is able to fill-in the limit set restricted to the component, and therefore make it simple independently of . Fig. 2 J. Kari's firing squad trick: a synchronous apparition of can be triggered arbitrarily far in time, thus allowing to complete the limit set on some component of states to the full-shift.

Z #' 1 1 2 2 1 2 2 1 X # #' 1 2 Y 1 1 2 2 1 2 Y #' 1 2 2 1 X # #' #' #' # #' 1 2 2 1 1 1 2 2 1 2 Z #' 1 2 2 1 1 2 2 1 X # #' 1 2 2 1 1 2 2 1 1 2 Y #' # #' #' #' #' #' #' #' #' #' #' #' #' #' #' #' # #' #' #' #' #' #' #' # #' #' #' # #' 1 2 2 1 1 2 2 1 1 2 Z #' 1 2 2 1 1 2 2 1 X # #'

Theorem 6 ([13])

There exists an intrinsically universal CA whose limit language is NLOGSPACE.

Given ∈ N, the column factor of width of , Σ ( ), is the set of columns that can appear in space-time diagrams of :

Σ ( ) = ( ) ∈N : ∈ , = ( ) [1, ] , ∈ Z .
To Σ ( ) we associate its language of finite patterns (Σ ( )) defined as the set of words • • • + for some ( ) ∈N ∈ Σ ( ) and , ∈ N. The approach of [START_REF] Delvenne | Decidability and universality in symbolic dynamical systems[END_REF] to define universality for general dynamical systems translates into the following in our settings. To we associate the model checking problem:

• input: and a regular language over alphabet ,

• question: decide whether intersects (Σ ( )).

is BDK-universal if its associated model checking problem is r.e.-complete. Like for limit sets, column factors can be filled up and thus simplified by increasing the alphabet starting from an arbitrarily complex cellular automaton.

Theorem 7 ([13])

There exists an intrinsically universal CA such that (Σ ( )) are regular languages computable from . In particular, such is not BDK-universal.

Fig. 1

 1 Fig.1The shrinking zone trick behind the construction of Z (time goes from bottom to top).