Vessela Daskalova
email: <vessela.daskalova@gmail.com>.

Nicolaas J Vriend
email: vriend@qmul.ac.uk>.

Categorization and Coordination *

Keywords: JEL Classification: C72, D01, D03, D80 Categorization, Coordination, Prediction, Bounded rationality, Behavioural, Heuristics

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

People often make predictions in new situations with the help of categories.1 That is, when encountering a new situation, the decision maker assigns it to some category of past experiences, and makes a prediction based on the average experience in that category. In the experimental literature in psychology and in previous models in economics, two key features of category-based prediction stand out. First, the average experience in the category is used as a predictor, and second, experiences in other categories do not matter (Murphy and Ross, 1994; Mohlin, 2014). For example, an employer may place a new applicant who is "male and engineer" in a category with others who share these characteristics, and make a prediction about the new applicant's suitability for the job based on the category average.

While people often care about making good predictions, they also often care about coordinating their predictions with others. As is well known, the need to coordinate could arise from various factors in different classes of situations -these include strategic complementarity in subsequent actions, reputation concerns, and preference for conformity. Technology adopters may aim to coordinate their predictions on the usefulness of a new technology as their payoffs from adoption increase in the number of other adopters. Equity researchers may have incentives to coordinate their predictions as they might be worried about their reputation if their estimates are too far off from the consensus estimates. Product reviewers, project evaluators or referees on a paper may also have such incentives. 2 Usually there are many different ways in which an individual can sort her experiences into categories. In particular, she can divide her experiences into many categories (relatively fine categorization), or alternatively, she can split them into just a few categories, each category containing a large number of experiences of different types (relatively coarse categorization). Coarse categorization can be linked to a number of biases in decision-making, including discrimination against minorities, persuasion in advertising, and mispricing in markets (Fryer and Jackson, 2008; Mullainathan et al., 2008; Barberis and Shleifer, 2003; Steiner and Stewart, 2015). In spite of this, coarse categorization is common.

This paper provides a parsimonious framework that helps us develop a formal intuition for why and when coarse categorization could be beneficial, in particular in situations when players have incentives to coordinate. Note that the use of few rather than many categories could simply be due to an innate limitation in our brains or to exogenous (e.g. computational) costs of using more categories. Our analysis complements such explanations, as we show when and why coarse categorization can be rational even without such exogenously given costs or limitations.

The starting point is the following problem. Decision makers encounter objects. Each object has a number of observable characteristics plus some ex ante unobservable value. 3 We assume that the agent accumulates a number of experiences for which the value is revealed to her. She, then, faces a oneoff prediction task. That is, she will encounter a new object, and will need to predict the unobservable value. There is an underlying function relating the unobserved value to the observed characteristics, but the agent does not know this function. In our framework the tool for prediction available to the agent are her experiences, which are sorted into categories. That is, she will assign the object to a category on the basis of the observables, and will use her average experience in that category to predict the unobservable value of the newly encountered object. 4 We consider several variants of this prediction task. To begin with, we show that for the individual prediction case described above our results are broadly in line with those of previous literature considering categorization as a tool for individual prediction. 5 The analysis of an individual decision maker's problem, then, serves as a stepping stone for the next two cases, which are the focus of our paper.

First, we examine the properties of different ways of categorizing for the case of decision makers who only want to coordinate their predictions with each other, and second, we examine these properties for the more general case of decision makers who are interested in both correctly predicting the value of the next object and in coordinating their predictions with another person.

Extending our analytical framework for the individual prediction case, we consider a stylized representation of such coordination problems, abstracting from a variety of specific aspects of situations in which people want to coordinate. Two individuals independently accumulate a number of experiences and their goal is to coordinate predictions on the next object. We represent this situation as a one-shot game in which each player's strategy set consists of the set of available categorizations. In the pure coordination case, payoffs are inversely related to the players' expected prediction errors from each other. In the individual prediction and coordination case, payoffs are inversely related to the convex combination of the players' errors from individual prediction and from coordination.

We derive comparative statics on factors affecting which way of categorizing (in terms of coarseness) will help agents minimize expected prediction errors on the next object. The perspective we take is an ex ante one, i.e. prior to experiences being drawn and prior to knowing which object type will be encountered. A key insight of the approach is to think of a categorization as a model containing a set of estimators that agents can use to make predictions.

We begin by showing that whether fine or coarse categorization is optimal for individual prediction depends on the environment, in particular on the noise level and on the number of experiences the agent will have available. If the environment is deterministic, the best the agent can do is to use the finest possible categorization, as it makes unbiased predictions. As noise increases, however, coarser categorizations may make better predictions, as they help to decrease the variance in prediction.

Our key results relate to the case when two players who use categorization as a tool for prediction want to coordinate their predictions. While in a deterministic environment using the same categorization as the other player is always best, and all symmetric categorization profiles are equilibria and are equally efficient, our analysis shows that for stochastic environments this is more nuanced. The extent to which there is multiplicity of equilibria in stochastic environments depends on a number of factors such as the noise level, sample size, and the specifics of the function mapping from observables into the value to be predicted. Our analysis abstracts from the function specifics and shows that for any function, as the noise level increases relative to the sample size, the multiplicity of equilibria is weakly reduced. The reason is that as noise increases relative to sample size an individual may have an incentive to deviate to a coarser categorization and hence a finer categorization profile would no longer be an equilibrium. In the limit, i.e. if noise relative to sample size is sufficiently high, the coarsest possible categorization is the unique equilibrium. Moreover, we show that any coarser symmetric categorization profile is strictly more efficient than any finer categorization profile in any stochastic environment. The intuition is that while using the same categorization helps players decrease the bias in their predictions from each other, coarse categorization helps them decrease their variances in prediction by making predictions less dependent on the idiosyncratic experiences the individuals have accumulated.

In the more general case in which players care both about individual prediction and about coordination of predictions, our analysis shows that equilibrium existence and efficiency arguments again point towards coarser categorization as long as the weight on the coordination motive is sufficiently high. We show that the sufficient threshold weight is a decreasing function of the noise level and an increasing function of the sample size, and for any given weight on coordination there exists a noise level to sample size ratio that is sufficiently high to render coarse categorization optimal.

To sum up, the paper presents both equilibrium existence and equilibrium efficiency arguments for why coarse categorization could be beneficial. However, it paints a more nuanced picture than just "coarseness is good". While the analysis focuses on which factors are the driving forces for coarse categorization, it also shows that under a wide range of parameter values there might be a multiplicity of equilibria. This means that in many situations we may expect to observe the existence of equilibria at intermediate levels of coarseness as well as coexistence of equilibria in categorizations at different levels of coarseness, something in line with casual observation.

On the methodological side, this paper develops a coherent theoretical framework to analyze motives for coarse categorization in both individual decision making and strategic interaction settings. To the best of our knowledge, this is the first paper to consider the question how an individual's optimal categorization is affected by a strategic motive to coordinate predictions with others and to show that such a coordination motive may be a driving force towards coarser categorizations in stochastic environments. A tentative implication of our analysis is that to the extent that coarse categorization can be linked to biases in decisions, such biases might be more likely to arise in stochastic environments in which individuals who sample their experiences independently have incentives to coordinate.

The structure of the paper is as follows. In Section 2 we discuss the paper's relation to the literature. Section 3 describes our model. In Section 4 we present our analysis. Section 5 concludes.

Relation to the Literature

This paper sits at the intersection of several different literatures in economics, as well as psychology, cognitive science, and computer science. Our approach to analyzing categorizations as containing sets of estimators is broadly inspired by the statistics, econometrics, and machine learning literature on prediction (Berry and Lindgren, 1996; Varian, 2014; Li and Racine, 2007; James et al., 2013; Bishop, 2007; Murphy, 2012). The starting point of our analysis -the individual prediction case and the finding that coarse categorization could be better for individual prediction in stochastic environments when individuals have limited sample sizes is consistent with Mohlin (2014) and Al-Najjar and Pai (2014), with the setting in our individual prediction case being most similar to the setting in Mohlin (2014). A key difference with these papers is that whereas they focus on individual prediction only, our focus is on the effect of the coordination motive on the way an individual categorizes. We re-conceptualize the bias-variance decomposition used in individual prediction settings to a suitable counterpart that can be applied in a game-theoretic setting. We then derive comparative statics on equilibrium existence and efficiency.

Other papers (somewhat further away methodologically) on categorization in individual prediction, focusing in particular on connections between Bayesian models and categorization, include Mullainathan (2002) and Peski (2011). 6 As the model of case-based decision making of Gilboa and Schmeidler (1995), our model of categorization is also a form of decision making on the basis of past experience. In our model, however, as in other categorization models in economics, it is assumed that objects are placed in a category based on their observable attributes and that only objects within a category (in particular, the average experience with them) matter for prediction. These categorization models thus avoid the need to specify a particular similarity function that compares the current case to past cases by treating the current case as absolutely similar to the average of the observations in the category it has been put in. The connection between case-based and categorization models in economics seems somewhat reminiscent of the connection between exemplar and prototype models of categorization in psychology. 7 Again, all of the above papers focus on individual prediction only, whereas our main focus is on decision makers who want to coordinate predictions and decision makers who care both about individual prediction and coordination of predictions. An exception is the recent paper by Argenziano and Gilboa (2019) in which players use similarity-weighted empirical frequencies to predict their best-response to the empirical frequency of moves by the other players in coordination games.

The literature on categorization in strategic interactions has analyzed players who categorize their opponents in games (Azrieli, 2009, 2010), players who bundle nodes at which other players move into analogy classes (Jehiel, 2005), players who partition their own moves into similarity classes (Jehiel and Samet, 2007), players who learn how to categorize their strategies (Daskalova and Vriend, 2015), and players who categorize games (Mengel, 2012b; Grimm and Mengel, 2012; Heller and Winter, 2016; LiCalzi and Mühlenbernd, 2019; Gibbons et al., 2017).8 LiCalzi and Maagli (2016) model players who bargain over a common categorization of a two-dimensional convex compact region. This paper, instead, considers players who categorize their past experiences to make predictions, and derives comparative statics on how optimal categorization coarseness depends on the motive to coordinate predictions with others and on the environment.

By deriving rationales for coarse categorization this paper complements papers studying consequences of coarse categorization. Fryer and Jackson (2008) assume an exogenous limit on the number of categories a decision maker has available and show that discrimination against minorities may result if a decision maker has a limited number of categories available. Mullainathan et al. (2008) show that advertisers may use the tendency of people to think coarsely to persuade them to buy a certain product. Barberis and Shleifer (2003) show that style investing (the tendency to invest in classes of stocks rather than individual stocks) may be an explanation of some biases, in particular under-and overpricing, observed in financial markets. In Steiner and Stewart (2015) frequent trading opportunities can lead to price distortions if traders use categories when making predictions. While it is beyond the scope of our paper to model all the intricacies of the above situations, we hope to contribute to a better understanding at some more basic level as to why people may categorize coarsely and in particular when and why certain biases may be amplified if people want to coordinate predictions.

The main message of the paper that the coordination motive may affect the optimal model for an individual and may lead to coarse categorization in stochastic environments is consistent with casual examples of coarse categorization occurring when people try to coordinate. People may use coarse categories and stereotypes when talking to each other, even though they may individually not think in terms of such crude stereotypes. We often describe political beliefs in rather coarse terms, such as 'left' and 'right', even when our views are much more subtle. The language we use to interact with other people is often vague (Lipman, 2009) and within firms employees tend to use relatively generic jargon (Cremer et al., 2007). When talking to others, people also typically refer to colors using relatively coarse categories, such as e.g. 'red', 'green', 'blue', even though they may be distinguishing much finer nuances, and even though well-defined, finer color schemes exist (Steels and Belpaeme, 2005; Komarova et al., 2007).

The related literature in psychology and cognitive science is vast.9 Most related in spirit is the work by Gigerenzer and Brighton (2009), who look at decision making on the basis of heuristics and argue that less information can improve accuracy in prediction. A complementary approach in psychology is to assume that having many categories entails computational costs for the agent and to derive the optimality of coarse categorization under such exogenous costs (Anderson, 1990, 1991). There is also a literature in psychology and cognitive linguistics focusing on the phenomenon of basic-level categories, e.g. Rosch (1978). Basic-level categories are categories at some intermediate coarseness level, e.g. "chair" rather than "furniture" or "kitchen chair". It is the level at which people prevalently tend to categorize. While explaining basic-level categories as such is not the focus of our paper and there may be other reasons for basic-level categories than those that we consider, our equilibrium analysis showing the possibility of intermediate coarseness levels would be consistent with the use of basic-level categories. While cognitive scientists and psychologists often focus on empirical studies and procedural models of how people categorize, as economists we are particularly interested in understanding rationales for coarse categorization and in the effect of strategic motives, here coordination of predictions, on the optimal categorization for an individual.

Model

The basic set-up of the model is the following. An individual will accumulate a number of experiences and will face a one-off prediction task. That is, she will encounter a new object and will have to predict its unobservable value. To do so she will assign the object to a category based on its observable characteristics, and will make a prediction that its unobservable value is equal to the average of the values experienced in that category. The focus here is on the statistical properties of different ways of categorizing her experiences. In particular, we derive comparative statics on factors affecting which ways of categorizing her experiences will help minimize her expected prediction error (EP E) on the next object. We do so from the perspective of modelers who consider the costs and benefits of using alternative levels of categorization coarseness in different environments. As the perspective we take is an ex ante one, we consider EP E prior to experiences being drawn and prior to knowing which type of object will be encountered next.

We consider three cases: An individual interested only in making correct predictions, individuals interested only in coordinating their predictions with each other, and individuals interested both in correct individual prediction and in coordination of predictions. Before analyzing these three cases, we provide some definitions.

Objects and Categories

An object o is a pair (x, y), where x ∈ X is the vector of attributes that the individual observes and y ∈ R is the (ex ante) unobservable (real-valued) feature that she has to predict. Each object's type is determined by its observable attributes, that is by x only. X is a finite set of object types. The agent will sample a number of objects before having to make a prediction. This is the experience that she will base her prediction on. We denote the set of all objects the individual will experience before having to make a prediction by O. To facilitate analytical tractability we focus on a symmetric setting in which the agent will sample an equal number n of objects from each object type before making a prediction (with n > 0 and n finite). 10 We assume that the values of these experiences are revealed to her before she has to make a prediction.

The unobserved feature y that the individual is trying to predict is a noisy function of the observed attributes of the object, i.e. y = f (x) + . The noise term is i.i.d. normally distributed with mean zero and variance σ 2 , i.e. ∼ N (0, σ 2 ). Thus, the unobserved value for each object is a random variable

Y (x) ∼ N (f (x), σ 2
). The variance of the noise is homogeneous across agents and across object types.11 A deterministic environment is defined by σ 2 = 0, that is, all objects that can be described by the same vector of observable attributes have the same unobserved value. A stochastic environment (i.e. σ 2 > 0) represents the more realistic case in which observable characteristics do not completely reflect the unobserved value of an object (e.g. same gender, race, or having studied at the same institution do not mean people have the same suitability for a particular job), or in which some variable of interest is not observed by the decision maker (e.g. ability is not directly observed when the agent makes a prediction about someone's suitability for a particular job). In the remainder of this paper we focus on stochastic environments (σ 2 > 0), unless explicitly stated otherwise. We do not make any assumptions on f apart from f : X → R, where X is the set of vectors of observable attributes and R is the set of real numbers. We assume that the agent does not know the function relating unobserved to observed attributes, does not have beliefs about such functions, and uses categories to make predictions about the unobserved attributes. A category C is a subset of the set of object types X.

Category Averages and Categorizations

When encountering a new object, the agent will assign it to a category based on its observable characteristics, and she will predict as y-value of the object the average of the y-values of all her experiences in this category. Thus, each category has a category average attached to it. The category average for category C is Ŷ C = 1 n|C| (x,y)∈O|x∈C y. Note that a category average is a random variable that depends on the exact realization of the y-values of the objects in the category. It is therefore the average of random variables which are independently drawn from a normal distribution and is also normally distributed. In our framework we think of the category averages as estimators the individual uses to make predictions.

A categorization The set of all possible categorizations for a given set of object types is denoted by P.

P = C 1 , C 2 , ...,
We further assume that the vector of observable attributes is binary of length l, i.e. x ⊂ {0, 1} l . Note that there is a finest possible categorization in which each object type has a separate category and a coarsest possible categorization with all object types being assigned to a single category. While there is always exactly one finest and one coarsest possible categorization, at intermediate coarseness levels there will be (possibly many) more categorizations, with the exact number depending on the coarseness level and on the number of different attributes describing the objects. The results in this paper apply to any finite number of object attributes.

In addition to the concept of categorization coarseness, we define a binary relation "refines" denoted by on the set of possible categorizations P. A categorization P refines P , i.e. P P if for each category C ∈ P , there exists a C ∈ P such that C ⊆ C with the subset relation being strict for at least one pair of categories C, C . Note that while P P ⇒ |P | > |P |, the inverse is not true.

Analysis of the Model

The analysis focuses on factors determining which categorizations (in terms of their coarseness) would perform best in different situations. We derive comparative statics on these factors determining optimal coarseness. We first analyze the two benchmark cases, i.e., when an individual cares only about predicting the value of the object correctly, and when agents care only about coordinating their predictions about the value of the next object with one another. We then analyze the case when agents care about both. The results and intuition are in the main text, while the proofs are in Appendix A.

Individual Prediction

Consider an agent whose goal is to make the best possible prediction on the next object she encounters. 12 Assume that the next object is drawn from a discrete uniform distribution of all possible object types. The indicator that we use to measure how good a categorization P is for individual prediction is the expected prediction error the individual would make on the next object she encounters by using this categorization:

EP E IP [P ]. 13 Definition 1. Expected Prediction Error Individual Prediction EP E IP [P ] = C∈P x∈C pE[( Ŷ C -Y (x)) 2 ]
As Definition 1 shows, the expected prediction error on an object type x is the expected mean squared error between the category average of the category the object is assigned to ( Ŷ C ) and the object's unobserved value (Y (x)). Note that Ŷ C and Y (x) are capitalized as they denote random variables. The expected prediction error of a categorization P combines the expected prediction error on all object types, with p = 1 |X| . The mean value for object type x is denoted by

µ x . Lemma 1. Bias-Variance Decomposition of EP E IP EP E IP [P ] = C∈P x∈C pE[( Ŷ C -Y (x)) 2 ] = C∈P x∈C pV ar[ Ŷ C ] + C∈P x∈C pV ar[Y (x)] + C∈P x∈C p(E[ Ŷ C ] -µ x ) 2 = V ar[P ] + V ar[Y ] + Bias 2 [P ]
12 As mentioned before, the focus of this paper is on a static ex ante perspective. While it is outside the scope of this paper, considering the dynamics of categorization coarseness could be an interesting direction for further research. 13 The mean squared error is a standard way of measuring how good an estimator is; see e.g. Berry and Lindgren (1996). Minimizing mean squared error is equivalent to assuming maximization of a utility function that is simply the negative of the mean squared error.

Lemma 1 decomposes the expected prediction error of a categorization in the individual prediction case into a bias and a variance component. 14 Lemma 2 Part 1 shows that the higher the noise in the environment and/or the smaller the sample size (in any stochastic environment), the higher the variance of a categorization. The reason is that each category belief is a normally distributed random variable with a variance equal to the variance in the environment divided by the number of objects in the respective category. A key insight is that in stochastic environments coarser categorizations have lower variance than finer categorizations. The intuition is that coarser categorizations partition a given set of objects into fewer categories and thus there are on average more objects per category in a coarser than in a finer categorization.

We now look at Part 2. The bias of each category average with respect to a given object type is the expected mean squared error between the expected value of the category average (the estimator E[ Ŷ C ]) and the mean of this object type (µ x for object type x). Note that the category average of a category in which there is only one object type will be an unbiased estimator of the mean of this object type, as the expected value of the category average will be equal to the mean for this object type. However, the category average of a category that contains object types with different means will be generally a biased estimator for a particular object type as its expected value will be equal to the average of the means and thus the estimator will be making a mistake towards the means of at least some object types. 16 In Appendix A we show that any category formed through merging of two categories will therefore have a weakly greater bias than the sum of the biases of the categories that were merged to form it. As a result, any categorization P that refines P will have a weakly smaller bias. 17 Lemma 2 illustrates the trade-off of using fine versus coarse categorizations. The benefit of coarser categorizations, on the one hand, is that they have lower variance in noisy environments. The benefit of refinements of categorizations, on the other hand, is that they decrease the bias component of the EP E IP .

We next characterize what an optimal categorization for individual prediction means. A categorization P * is optimal for individual prediction if and only if its EP E IP is smaller than or equal to the EP E IP of any categorization P from the set of available categorizations P. Using the bias-variance decomposition from Lemma 1, this is equivalent to:

EP E IP [P * ] ≤ EP E IP [P ] ∀P ⇔ V ar[P * ] -V ar[P ] ≤ Bias 2 [P ] -Bias 2 [P * ] ∀P (1)
The latter representation shows that for a categorization P * to be optimal for IP, the difference between its variance and the variance of any other categorization available to the agent has to be smaller or equal to the difference in squared biases between the other categorization and P * . The first question we are interested in is how the optimal way of categorizing (in terms of coarseness) depends on the environment the agent is in -whether it is deterministic or stochastic. Proposition 1 describes how the coarseness of the categorization(s) that minimize(s) the EP E IP , depends on the exogenously given noise level and on the sample size.

Proposition 1. Coarseness of the Optimal Categorization(s) for IP .

The coarseness of the optimal categorization(s) for IP is weakly increasing in σ 2 and weakly decreasing in n.

As a starting point consider a deterministic environment. This is an environment without noise and the variance component of any categorization is zero. Hence the finest possible categorization is optimal as it has zero bias. As the noise increases, however, the variance component becomes more important.

The difference in variance between a finer and a coarser categorization increases and coarser categorizations become more attractive compared to finer ones than before and the decrease in variance that they offer may at some point outweigh the increase in bias. 18 The same is true for a decrease in sample size (for any positive noise level). As a result, if the noise level to sample size ratio is sufficiently large, an individual might be able to make better predictions using coarser rather than finer categorizations. 19 The analysis above is under the assumption that the agent accumulates an equal number of past experiences n of each type. While we leave the case of past experiences being drawn from some distribution of types for further research, for the individual prediction case, our informal conjecture is that the qualitative insights concerning the effect of σ 2 and n (Proposition 1) would not change. Thus, we would expect that as the number of the agent's experiences in a particular subset of objects increases, the agent's incentives to form finer categories on that subset increase. This would be also in line with Mohlin (2014).

In the next two sections we further develop the analytical framework of this section and extend some of the results on the individual prediction case to consider the questions that are of main interest to us, those related to categorization coarseness when decision makers have a motive to coordinate their predictions.

Coordination

We now consider the case when players care only about coordinating their predictions. The precise setup is as follows. There are two players. 20 Each of them will independently accumulate n experiences of each object type. 21 The two individuals will, then, face a one-off prediction problem. They will both observe the same object and they independently will have to make a prediction 18 This follows from Lemma 2 (see proof in Appendix A). 19 Proposition 1 is in line with some of the results by Al-Najjar and Pai (2014) and especially Mohlin (2014). 20 In principle the same methods could be applied to the case with more players.

21 Note that the essential differences in the samples between the players concern only the idiosyncratic y-values experienced. That is, our analysis allows for the players to observe exactly the same observable characteristics, as long as the subjective noise term is independently drawn for every instance that an object is perceived by a player. An alternative benchmark would be if the sampled and perceived histories of the two individuals are identical. In Appendix A we derive a general expression for bias-variance decomposition of the EP E C , covering these two benchmark cases as well as intermediate cases in which the players' perceived values are (imperfectly) correlated. In our analysis below we focus on the benchmark case of independent samples, leaving these intermediate cases for further research.

about the object's unobserved value. We assume that this next object will be drawn from the discrete uniform distribution of all possible object types. As before, agents use categorizations to make predictions. We assume here that the goal of the two players is simply to coordinate their prediction on the next object, i.e. to minimize their expected prediction error from each other. We think of this as a reduced-form model, in which the rationale for coordinating predictions is kept implicit in order to focus on analyzing the trade-offs of coarse versus fine categorization in a common strategic interaction setting. 22 In the pure coordination setting the individual is not interested in the true unobserved value, but only in the other person's prediction of it. As there are many alternative ways for each of the two players to categorize her experiences, which categorization each of them uses matters because it will determine their expected prediction error from each other. 23 The indicator that we use to measure how good a given categorization profile is for the coordination of two players' predictions on the next object is the expected prediction error between the two players' predictions. We denote it by EP E C [P 1 , P 2 ], where P 1 denotes the categorization that Player 1 uses and P 2 denotes the categorization that Player 2 uses. As Definition 2 shows, the expected prediction error between the two players' predictions on an object type x is equal to the mean squared error between the respective category averages, Ŷ C 1 for Player 1 and Ŷ C 2 for Player 2, that the players use on this object type x. The expected prediction error of two categorizations from each other combines the expected prediction errors on all object types, weighing them by the probability that an object of a given type is observed. As in this case the players only care about coordinating, the EP E C [P 1 , P 2 ] is the same for both players.

Definition 2. Expected Prediction Error Coordination

EP E C [P 1 , P 2 ] = C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) pE[( Ŷ C 1 -Ŷ C 2 ) 2 ]
22 One could also think of this model more broadly as an ingredient for some more elaborate model in which the value of predictions depends explicitly on some follow-up actions based on these predictions. This is beyond the scope of this paper, but it would be an interesting direction for further research.

23 One could of course also use the same framework to analyze the case in which players care not about minimizing but about maximizing their expected prediction error from coordination.

Lemma 3. Bias-Variance Decomposition of EP E C EP E C [P 1 , P 2 ] = C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) pE[( Ŷ C 1 -Ŷ C 2 ) 2 ] = C 1 ∈P 1 x∈C 1 V ar[ Ŷ C 1 ] + C 2 ∈P 2 x∈C 2 pV ar[ Ŷ C 2 ] + C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) p(E[ Ŷ C 1 ] -E[ Ŷ C 2 ]) 2 = V ar[P 1 ] + V ar[P 2 ] + Bias 2 [P 1 , P 2 ]
Lemma 3 decomposes the expected prediction error in the coordination case into a bias and a variance component. The EP E C [P 1 , P 2 ] is equal to the sum of the expected variance of the categorization P 1 that Player 1 uses, the expected variance of the categorization P 2 that Player 2 uses, and the expected bias of the two players' categorizations from each other. It is increasing in each of these terms. Note that the bias component is different from the one in the individual prediction case. Here we define the bias of the two players' predictions on a given object type as the mean squared error between the expected value of the category average that one player is using and the expected value of the category average that the other player is using. This means that we are extending the definition of bias of an estimator with respect to a 'true' population mean to an analogical concept in a strategic interaction setting, defining the bias with respect to another person's prediction rather than with respect to a 'true' population mean.

Thus, we model the situation in which players want to coordinate their predictions with each other as a two-player one-shot strategic (normal) form game, in which a player's strategy is a categorization from the set of available categorizations P. Players choose categorizations independently from each other. All categorizations are available to each player, so that P is the same for both players. The preference relations of the players are represented by the EP E C [P 1 , P 2 ], which is a function h : P × P → R + mapping from the set of possible categorization profiles to the set of non-negative real numbers.

To understand the determinants of optimal categorizations when players want to coordinate their predictions, we consider the conditions for pure strategy Nash equilibria of this coordination game. An equilibrium here is a categorization profile, one categorization for each player, such that the expected prediction error for each player is minimized given the categorization of the other player, which means that no player has an incentive to deviate to a different categorization.

Let [P *

1 , P * 2 ] denote a categorization profile such that P * 1 is the categorization that Player 1 uses and P * 2 is the categorization that Player 2 uses. The two categorizations could be the same or different, and in case different they could be of the same or different level of coarseness. Using the bias-variance decomposition from Lemma 3, and denoting any categorization from the set of available categorizations with P ∈ P, we can write the equilibrium condition from the perspective of Player 1 as:24

EP E C [P * 1 , P * 2 ] ≤ EP E C [P 1 , P * 2 ] ∀P 1 ⇔ V ar[P * 1 ] -V ar[P 1 ] ≤ Bias 2 [P 1 , P * 2 ] -Bias 2 [P * 1 , P * 2 ] ∀P 1 (2)
A categorization profile is an equilibrium in the coordination game if and only if for each player the variance of the categorization she is using minus the variance of any categorization that she could deviate to is smaller than or equal to the difference in squared bias between the two players' categorizations if she were to deviate minus the respective squared bias if she does not deviate.

Before we present our analysis of the properties of these equilibria, a note on the interpretation of the solution concept may be useful. The equilibrium conditions imply that if players happened to choose a categorization profile that constitutes an equilibrium by chance or because someone advised them of one (Holt and Roth, 2004), then no player could reduce her expected prediction error by deviating from her equilibrium strategy.

Note that our context does not allow for a deductive interpretation of Nash equilibrium, as that would require players to know their own payoffs and the payoffs of their opponents, something that we do not assume here. 25 The situation we consider here is a doubly symmetric two-player game, and the set of strategies involved in strict pure strategy Nash equilibria in such games coincides with the set of evolutionary stable strategies. Moreover, in such games every evolutionary stable strategy is an asymptotically stable state in the replicator dynamics (Weibull, 1995). Thus, one way to think of how equilibrium arises in such a game is through evolutionary forces. An alternative interpretation is to think of a population of players who are randomly rematched each period and may learn which categorizations to use through reinforcement (Sutton and Barto, 2017). 26 If players have either limited memory or face a stochastic dynamic environment, they will be able to accumulate only a finite sample size, and the sample size n introduced in our model serves as a proxy to model such situations.

Our main results in this section are Propositions 2 and 3, in which we analyze the properties (existence and efficiency) of the equilibria in the coordination game, focusing in particular on some comparative statics, i.e. the effect of changes in the environmental parameters on the set of equilibria. Before doing so, in Lemma 4 we give some results on the types of outcomes that can be ruled out in this game.

Lemma 4. Ruling Out Some Outcomes in the Coordination Game .

Part 1. There are no equilibria involving two categorizations at different levels of coarseness for any σ 2 > 0. A profile of two different categorizations at the same level of coarseness cannot be an equilibrium if the two categorizations make different expected predictions on at least one object type.

Part 2. If P * is the finest optimal categorization in IP, then there exists no symmetric equilibrium [P, P ] for any P P * .

Lemma 4 Part 1 rules out the existence of asymmetric equilibria with players using categorizations at different levels of coarseness. Such outcomes are not equilibria because the player who uses the finer categorization always has an incentive to deviate to the same categorization as the opponent. By doing so she decreases both components of the EP E C . The bias component is reduced to zero if they both use the same categorization. The variance component decreases if a player switches to a coarser categorization. Next, in Part 2 we show that there does not exist any symmetric equilibrium in which the two players use any categorization that refines the finest categorization that is optimal for individual prediction, as a player always has an incentive to deviate to the finest optimal categorization for individual prediction. The latter statement is a first argument supporting the point made in this paper that players might have incentives to categorize (in this case: at least weakly) more coarsely if they want to coordinate predictions than if they care about individual prediction.

Proposition 2. Existence of Equilibria in the Coordination Game .

There is a multiplicity of symmetric equilibria in the coordination game if σ 2 n is sufficiently low. The number of equilibria is weakly decreasing in σ 2 and weakly increasing in n. Both players using the coarsest possible categorization is always an equilibrium and may be the unique one if σ 2 n is sufficiently high. Whether there is multiplicity of equilibria in the coordination game will generally depend on several factors, most importantly the environment, i.e. the noise and sample size and the function f that maps the observable attributes into y. We focus on the bias and variance of categorizations as this allows us to derive results that do not depend on specific properties of f .

In a deterministic environment any symmetric categorization profile is an equilibrium, as there is no variance, and the bias of the two players' categorizations from each other is zero when they use the same categorization. Hence no player has an incentive to deviate. In a stochastic environment the analysis becomes more nuanced. For low σ 2 n there may be multiplicity of equilibria. As σ 2 n increases, the variance component gains in importance relative to the bias, and a player may eventually have an incentive to deviate to a coarser categorization. As a result, finer symmetric categorization profiles stop being equilibria if σ 2 n becomes sufficiently high. The coarsest possible categorization is always an equilibrium, as there is no coarser categorization to deviate to. Thus, we have some equilibrium existence argument pointing towards coarser categorization if players want to coordinate their predictions, with the extent to which this is the case depending on the noise to sample size ratio.

Proposition 3. Efficiency of Equilibria in the Coordination Game .

The efficiency of symmetric equilibria is strictly increasing in categorization coarseness.

We have shown in Lemma 4 that for any positive noise level there are no asymmetric outcomes that are equilibria. For symmetric categorization profiles, the bias component is zero and the variance component of any coarser categorization profile is smaller than that of any finer categorization profile for any σ 2 > 0. While in a deterministic environment all symmetric categorization profiles are equally efficient, in stochastic environments any coarser symmetric categorization profile is more efficient than any finer symmetric categorization profile. This also means that any coarser symmetric equilibrium is more efficient than any finer symmetric equilibrium. Thus, Proposition 3 is an efficiency argument for coarse categorization when players want to coordinate in stochastic environments.

As before, we note that the results above are for the case when the agents accumulate an equal number of past experiences from each object type. We informally conjecture that allowing past experiences to be drawn from some distribution would not qualitatively change the insights from Propositions 2 and 3 in the sense that whether there would be a multiplicity of equilibria or not would still depend on σ 2 n and coarser categorization profiles will still have an efficiency advantage relative to finer ones in a stochastic environment. We expect, however, that allowing the players to sample their past experiences from different distributions will mean that the equilibria will not necessarily consist only of symmetric categorization profiles.

The result that equilibrium existence and efficiency considerations may point towards coarser categorizations is perhaps somewhat counterintuitive. If two individuals want to coordinate predictions with each other, intuition might suggest that it will always help or at least not hurt if they both try to be precise in the sense of minimizing the bias with respect to the object value by both using the most detailed (i.e. finest) categorization. If both players use coarse categorizations, the prediction error with respect to the object value may be large. However, if players only want to coordinate their predictions, what matters for them is their prediction error with respect to each other. In a stochastic environment, by both using the same categorization they minimize the bias component of EP E C [P 1 , P 2 ], and by both using the coarsest categorization they minimize its variance component. That is, when categorizing coarsely, the two individuals are placing a larger number of experiences in each category, and by doing so they are decreasing the dependence of each person's prediction on the randomness of her past experience, something they cannot take advantage of when using the finest categorization.

Note that as players in this benchmark case care only about coordinating predictions, they could in principle solve the coordination problem by stating some fixed value, independent from the observed characteristics of the object type drawn. From a coordination point of view, however, the crucial question is which fixed value they should use, as there will be infinitely many. As is true for any standard coordination problem in which players choose independently and have no opportunity to communicate, simply assuming that players are coordinated on some given solution means begging the whole coordination question. We know salience might matter (Schelling, 1960). But different values may be salient depending on the specific circumstances in which players need to coordinate. In this analysis we abstract from such circumstantial factors, and in that sense it can be seen as complementary to any salience theory of coordination. 27

Individual Prediction and Coordination

In the previous two sections we derived comparative statics on factors determining optimal categorization coarseness for an individual who is interested only in making a correct prediction about the unobserved value of an object, and for agents who are only interested in coordinating their predictions. More generally, economic agents may care both about making correct predictions and about coordinating their predictions with each other. In this section we consider this IP &C case. The IP &C case is a version of the coordination game such that the preference relations of player i are represented by EP E IP &C i .

Definition 3. Expected Prediction Error Individual Prediction & Coordination

EP E IP &C i [P 1 , P 2 ] = wEP E IP i [P i ] + (1 -w)EP E C [P 1 , P 2 ]
The EP E IP &C i [P 1 , P 2 ] of player i is the convex combination of the expected prediction errors from Definition 1 and from Definition 2. Let w denote the weight that the individual places on making correct predictions about the object value, and (1w) denote the weight she places on coordinating her predictions with the other. 28 We assume that both players place the same weight w on individual prediction. 29 If the two players use different categorizations, then in the IP &C case their expected prediction errors will normally be different from each other as they would be making different mistakes with respect to the object value, even though they would be making the same error with respect to each other.

In Lemma 5 we derive a bias-variance decomposition of the EP E IP &C i . The EP E IP &C i is increasing in the variance of the categorization the player uses, in the variance of the underlying object types in the population, in the bias of the categorization that the player uses, in the variance of the other player's categorization, and in the bias of their predictions from each other.

27 This abstraction will be particularly useful when we move to the more general case in which players care about coordinating their predictions as well as about predicting the value of the object encountered. Clearly, in this third case, predicting any fixed value independent from the observed characteristics of the object type drawn will generally not be optimal.

28 In our analysis of the mixed motives case we assume 0 ≤ w ≤ 1 unless otherwise noted. Note that w = 1 would correspond to the individual prediction case, whereas w = 0 corresponds to the pure coordination of predictions case.

29 The analysis can be extended to allow for the players to place different weights on individual prediction.

Lemma 5. Bias-Variance Decomposition of EP E

IP &C EP E IP &C i [P 1 , P 2 ] = wEP E IP i + (1 -w)EP E C = w(V ar[P i ] + V ar[Y ] + Bias 2 [P i ]) + (1 -w)(V ar[P 1 ] + V ar[P 2 ] + Bias 2 [P 1 , P 2 ])
For [P * 1 , P * 2 ] to be an equilibrium in the IP &C game, no player should have an incentive to deviate to any other (finer, equally coarse or coarser) categorization given the categorization of the opponent. Using the bias-variance decomposition from Lemma 5 to write this condition, and denoting with P 1 any categorization in the set of possible categorizations, we get the following from the perspective of Player 1.

EP E IP &C 1 [P * 1 , P * 2 ] ≤ EP E IP &C 1 [P 1 , P * 2 ] ∀P 1 ⇔ V ar[P * 1 ] -V ar[P 1 ] ≤ w Bias 2 [P 1 ] -Bias 2 [P * 1 ] + (1 -w) Bias 2 [P 1 , P * 2 ] -Bias 2 [P * 1 , P * 2 ] ∀P 1 (3)
For a categorization profile to be an equilibrium in the IP &C game, the change in variance from deviating to any other categorization has to be weakly smaller than the weighted sum of the difference between the new and the old squared bias in individual prediction and the difference between the new and the old squared bias in the coordination case.

Our main results in this section are Propositions 4 and 5, in which we characterize properties (existence and efficiency) of the equilibria in the IP &C game. We first give results on the type of outcomes that cannot be equilibria in this game. Lemma 6. Ruling Out Some Outcomes in the IP &C game .

Part 1. There are no equilibria involving two categorizations at different levels of coarseness for any σ 2 > 0 if w is sufficiently low. The sufficient threshold is increasing in σ 2 n . A profile of two different categorizations at the same level of coarseness cannot be an equilibrium if the two categorizations make different expected predictions on at least one object type.

Part 2. If P * is the finest optimal categorization in IP, there exists no symmetric equilibrium [P, P ] for any P P * in IP &C.

Lemma 6 Part 1 describes sufficient conditions under which asymmetric equilibria can be ruled out. Given two categorizations at different levels of coarseness, the player with the finer categorization has an incentive to deviate to the same categorization as the other player if the weight placed on coordination (1-w) is high enough. As we show in Appendix A, what constitutes a sufficiently high weight on coordination depends on the parameters of the environment. The noisier the environment and the smaller the sample size (in any noisy environment), the less weight on coordination is sufficient to rule out asymmetric equilibria.

Part 2 states that any symmetric profile consisting of both players using a categorization that refines the finest individually optimal categorization is not an equilibrium in the IP &C game. The reason is that a player can unilaterally profitably deviate to the finest individually optimal categorization. This will decrease her EP E IP as well as make it easier to coordinate with the other player.

Proposition 4. Existence of Equilibria in the IP &C Game .

The number of symmetric equilibria is weakly decreasing in σ 2 and weakly increasing in n. Both players using the coarsest possible categorization is always an equilibrium, regardless of σ 2 n as long as w ≤ 1/2. In addition, for any w > 1/2, the coarsest possible categorization profile is an equilibrium if σ 2 n is sufficiently high.

Proposition 4 shows that also in the IP &C game finer symmetric categorization profiles will stop being equilibria as the noise level increases or the sample size decreases, as a player will eventually have an incentive to unilaterally deviate to a coarser categorization to decrease the variance in her prediction. To check that the coarsest possible categorization is always an equilibrium, we only need to examine unilateral deviations to a finer categorization. We show that a sufficient though not necessary condition for any such deviation not to be profitable in any stochastic environment, regardless of the noise level and sample size, is that the players assign at least as much weight to being coordinated as to predicting the value of the object correctly. Even in case the players assign more weight to the latter, the coarsest categorization profile is an equilibrium if the noise level to sample size ratio is high enough. The intuition is that if the players assign more weight to IP , finer categorizations might have an advantage as they could reduce the bias in individual prediction. However, the higher the noise level and the smaller the sample size, the lower the importance of such a decrease in bias compared to the decrease in variance that coarser categorizations offer. Proposition 5 provides necessary and sufficient conditions under which any coarser symmetric categorization profile is Pareto-superior to any finer symmetric categorization profile in the IP &C game.

It first states that when the bias of any coarser categorization is greater than the bias of any finer categorization, we can Pareto-rank any coarser symmetric categorization profile as Pareto-superior to any finer symmetric categorization profile if the weight on coordination (1w) is sufficiently high. The sufficient threshold for this Pareto-ranking depends on the parameters in the environment. The higher the noise in the environment and the smaller the sample size, the lower the weight on coordination that is sufficient. Any given weight on coordination (i.e. any 0 < 1-w ≤ 1) can induce a Pareto-ranking where any coarser symmetric categorization profile is more efficient than any finer symmetric categorization profile under a high enough noise level to sample size ratio σ 2 n . Note that (i) is relevant when comparing any categorizations such that the finer one refines the coarser one, as Lemma 2 states that for such categorizations the condition on the biases specified for case (i) will always be satisfied. If the finer categorization does not refine the coarser, this condition on the biases may or may not hold. If it does hold, case (i) will still be relevant. If this condition on the biases does not hold, the second part of Proposition 5 is the relevant one.

Case (ii) says that if the bias of any coarser categorization is weakly smaller than the bias of any finer categorization, then Pareto-ranking (with coarser symmetric categorization profiles being better) is guaranteed regardless of w, and σ 2 n (provided σ 2 > 0). This is true because in this case finer categorizations do not have any advantage in terms of lower bias in individual prediction.

Concluding Remarks

Motivated by the observations that people often use categories to make predictions and that situations in which they have incentives to coordinate their predictions abound, this paper aims to improve our understanding of when and why decision makers may be better off categorizing coarsely.

We develop a framework that looks at categorizations as containing sets of estimators on the basis of which agents make predictions. We apply this framework to derive comparative statics on factors affecting optimal coarseness in two benchmark cases, one in which individuals only care about predicting correctly and the other in which they only want to coordinate their predictions with each other. Using these two benchmark cases as stepping stone, we, then, analyze the more general case of situations where they care about both.

The paper gives an insight into how the optimal model for an individual is affected by the environment and by strategic considerations. The key contribution, relying on both equilibrium existence and efficiency arguments is to show that incentives to coordinate might provide a rationale for coarse categorization in stochastic environments. The theory thus enhances our understanding of why people may categorize coarsely. As coarse categorization can be linked to various biases in decision making ranging from mispricing in markets to discrimination against minorities, our analysis suggests a possible role for the coordination motive in understanding such biases.

A Appendix: Proofs Lemma 1. Bias-Variance Decomposition of EP E IP Proof.

EP E IP

[P ] = C∈P x∈C pE[( Ŷ C -Y (x)) 2 ] = C∈P x∈C p E[( Ŷ C ) 2 ] -2E[ Ŷ C ]E[Y (x)] + E[(Y (x)) 2 ] = C∈P x∈C p V ar[ Ŷ C ] + (E[ Ŷ C ]) 2 -2E[ Ŷ C ]E[Y (x)] + V ar[Y (x)] + (E[Y (x)]) 2 = C∈P x∈C p V ar[ Ŷ C ] + V ar[Y (x)] + (E[ Ŷ C ] -E[Y (x)]) 2 = C∈P x∈C pV ar[ Ŷ C ] + C∈P x∈C pV ar[Y (x)] + C∈P x∈C p(E[ Ŷ C ] -µ x ) 2 = V ar[P ] + V ar[Y ] + Bias 2 [P ]
In the proof above, we use

E[ Ŷ C Y (x)] = E[ Ŷ C ]E[Y (x)]
as Ŷ C and Y (x) are independent random variables. Note that for any random variable X, Proof.

E[X 2 ] = V ar[X] + (E[X]) 2 . We use this for E[( Ŷ C ) 2 ] and for E[(Y (x) 2 ].
p C∈P x∈C V ar[ Ŷ C ] + p C∈P x∈C V ar[Y (x)] = p C∈P x∈C σ 2 |C|n + p C∈P x∈C σ 2 = p C∈P |C|σ 2 |C|n + |X|σ 2 |X| = pσ 2 |P | n + σ 2
The category average is a random variable equal to the average of the realizations of random variables, independently drawn from the normal distribution and hence the variance of any category average is equal to σ 2 divided by the number of objects in the category. The number of objects in the category is equal to the number of different object types in this category |C|, times the sample size n of each object type. We assumed that V ar[Y (x)] is the same for all j and that it is equal to σ 2 . Thus, under the assumption of equal variance for each object type in the population, equal probability of observing an object from each type, and of an equal number of observations from each type in the agent's experience, the variance of category average for each category in a given categorization is the same. On the one hand, a category containing more object types has a smaller variance due to the larger number of objects in it. On the other hand, the next object is more likely to be drawn from this category than from a category containing fewer object types. Under our symmetry assumptions, the two effects cancel out exactly. All categorizations at the same level of coarseness have the same variance. We now compare the variance of a finer categorization P with the variance of a coarser categorization P .

V ar[P

] -V ar[P ] = pσ 2 |P | n + σ 2 - pσ 2 |P | n + σ 2 = pσ 2 (|P | -|P |) n
That is, any finer categorization has a greater variance than any coarser categorization (for any σ 2 > 0). The difference in variance between a finer and a coarser categorization is strictly increasing in their difference in coarseness (|P | -|P |) and in σ 2 , and is strictly decreasing in n.

Part 2.

Proof. To prove Part 2, we show that the Bias 2 of the category average of any category containing t + v object types is always weakly greater than the sum of the biases of the category averages of any two categories with t and with v object types, respectively, through the merging of which it can be formed. This implies that the Bias 2 [P ] is weakly greater than Bias 2 [P ], where P is any categorization that refines P .

The Bias 2 of the category average of a category with t object types (under the assumption that the agent has sampled an equal number of objects of each type) is equal to: Bias

2 [ Ŷt ] = t i=1 p(E[ Ŷt ] -µ i ) 2 , where E[ Ŷt ] = t i=1 µ i t
is the expected value of category average and µ i is the mean of object type i in the categorization is positive and strictly increasing in σ 2 . If before inequality (1) was fulfilled, as σ 2 increases the LHS becomes even more negative (and the RHS does not change). Thus, if before using a categorization P * was equally good or better than using a finer categorization, this will be even more so as σ 2 increases. Therefore, no categorization finer than P * can become optimal after an increase in σ 2 if it was not optimal before the increase.

ii) Next, consider a potential deviation to a categorization of equal coarseness. The change in σ 2 has no effect on the fulfillment of inequality (1), as the variances of all categorizations at the same level of coarseness are equal. No categorization that is equally coarse as P * can become optimal after an increase in σ 2 if it was not optimal before the increase.

iii) Finally, consider a potential deviation to a coarser categorization. If before inequality (1) held, as σ 2 increases the LHS increases while the RHS stays the same. Eventually the LHS has to become greater than the RHS, thus making use of a coarser categorization profitable.

We have thus shown that as σ 2 increases, it cannot become optimal to use a categorization that was not optimal before and that is finer than or equally coarse as the initially optimal one(s). Only coarser categorizations can become optimal. Note that the above result implies that if before the change in σ 2 there were several optimal categorizations at different levels of coarseness, no categorization that was not optimal before and that is finer than or equally coarse as the coarsest of those that were initially optimal can become optimal after the increase in σ 2 .

We can use the same arguments as above to show that as n increases only a finer categorization than the initially optimal one(s) can become profitable.

Lemma 3. Bias-Variance Decomposition of EP E C Proof. EP E C [P 1 , P 2 ] = C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) pE[( Ŷ C 1 -Ŷ C 2 ) 2 ] = C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) p E[( Ŷ C 1 ) 2 ] -2E[ Ŷ C 1 Ŷ C 2 ] + E[( Ŷ C 2 ) 2 ] = C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) p V ar[ Ŷ C 1 ] + (E[ Ŷ C 1 ]) 2 -2Cov[ Ŷ C 1 , Ŷ C 2 ] -2E[ Ŷ C 1 ]E[ Ŷ C 2 ] + V ar[ Ŷ C 2 ] + (E[ Ŷ C 2 ]) 2 = C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) p V ar[ Ŷ C 1 ] + V ar[ Ŷ C 2 ] -2Cov[ Ŷ C 1 , Ŷ C 2 ] + (E[ Ŷ C 1 ] -E[ Ŷ C 2 ]) 2 = C 1 ∈P 1 x∈C 1 pV ar[ Ŷ C 1 ] + C 2 ∈P 2 x∈C 2 pV ar[ Ŷ C 2 ] -2 C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) pCov[ Ŷ C 1 , Ŷ C 2 ] + C 1 ∈P 1 C 2 ∈P 2 x∈(C 1 ∩C 2 ) p(E[ Ŷ C 1 ] -E[ Ŷ C 2 ]) 2 = V ar[P 1 ] + V ar[P 2 ] -2Cov[P 1 , P 2 ] + Bias 2 [P 1 , P 2 ]
Above we use that for any two random variables E

[XY ] = Cov[X, Y ] + E[X]E[Y ] and apply it to E[ Ŷ C 1 Ŷ C 2 ]
. Below we will focus on the case when the two players have sampled their experiences independently from each other, then Cov[P 1 , P 2 ] = 0 and

EP E C [P 1 , P 2 ] = V ar[P 1 ] + V ar[P 2 ] + Bias 2 [P 1 , P 2 ].
Lemma 4. Ruling Out Some Outcomes in the Coordination Game .

Part 1.

Proof. We first prove that categorization profiles such that the two players use categorizations at different levels of coarseness cannot be equilibria. Consider any categorization profile such that Player 2 uses a coarser categorization than Player 1. Player 1 always has an incentive to deviate to the exact same categorization that Player 2 uses as it would strictly reduce her EP E C . This is beneficial both from a variance and a bias perspective. Moving to a coarser categorization reduces the variance (see Lemma 2 Part 1). Moving to the same categorization as the other player eliminates the bias.

Analogically, there exists no asymmetric equilibrium such that the two players use different categorizations at the same level of coarseness as long as the categorizations that the two players use make different expected predictions on at least one object type. It would be then profitable for either player to deviate to using the exact same categorization at the same level of coarseness as the other player rather than using different categorizations at that level, as this would decrease bias to zero while variance stays constant.

Part 2.

Proof. To prove that any [P, P ] with P P * cannot be an equilibrium, we show that Player 1 has an incentive to deviate to P * , i.e. to the finest optimal categorization in IP. That is, we show:

EP E[P 1 , P 2 ] > EP E[P * 1 , P 2 ]
Applying the result derived in inequality (2), this is equivalent to:

V ar[P 1 ] -V ar[P * 1 ] > Bias 2 [P * 1 , P 2 ] (5)

Assume that one player uses a categorization P , which has, besides some other categories, two categories of which one with t different object types and the other one with v different object types, with category averages Ŷt = respectively. The other player uses a coarser categorization P , which has a category that merges the category with t and the category with v object types, and her category average is Ŷt+v = t+v i=1 µ i t+v . Note that under the assumption of an equal number of objects of each type Ŷt+v = t Ŷt+v Ŷv t+v . As all their other categories are equal, the Bias 2 of the two players' predictions from each other is:

Bias 2 [P , P ] = t i=1 ( Ŷt -Ŷt+v ) 2 + v i=1 ( Ŷv -Ŷt+v ) 2 = t Ŷt - t Ŷt + v Ŷv t + v 2 + v Ŷv - t Ŷt + v Ŷv t + v 2 = tv( Ŷt -Ŷv ) 2 t + v
We know from Lemma 2 Part 2 that:

Bias Proof. To show that a symmetric categorization profile [P * , P * ] is an equilibrium we need to show that the condition specified in inequality (2) is fulfilled. We omit the indices for the players, as the categorization profile considered is symmetric. We have shown in Lemma 4 Part 1 that no player ever has an incentive to use a categorization that is finer than the one the opponent uses and that no player ever has an incentive to deviate to using a different categorization at the same level of coarseness as the opponent. Throughout this proof we therefore focus our attention on potential deviations to a coarser categorization |P | < |P * |. Applying the result derived in inequality (2), this can be rewritten as:

V ar[P * ] -V ar[P ] ≤ Bias 2 [P, P * ] Observe that the squared bias component of the two players' EP E C from each other (RHS) will always be nonnegative and finite and that it is not affected by changes in σ 2 or n. The LHS does depend on σ 2 n . If σ 2 n = 0, then LHS = 0, hence LHS ≤ RHS for every P and every P * . Therefore all symmetric categorization profiles are equilibria. This covers the case of a deterministic environment.

For equilibrium multiplicity in a stochastic environment, it is sufficient that RHS > 0 for every P for at least one P * where P * is not the coarsest possible categorization, because this means that there will be some σ 2 n such that LHS ≤ RHS for at least one P * other than the coarsest one.

Take some [P * , P * ] and again look at the inequality we derived above. From Lemma 2 we know that the difference in variance between a finer and a coarser categorization is positive, strictly increasing in σ 2 , and strictly decreasing in n (for any σ 2 > 0). Thus, for a given Bias 2 [P, P * ], as σ 2 increases or n decreases, the LHS increases and eventually for any pair of categorizations [P * , P * ] there will be a point at which the LHS > RHS for some |P | < |P * |, i.e. a player will have an incentive to deviate to some coarser categorization and [P * , P * ] will no longer be an equilibrium. Thus, the number of symmetric equilibria weakly decreases as σ 2 increases or n decreases.

At the coarsest level there is no coarser categorization to deviate to and thus both players using the coarsest possible categorization is always a NE. If σ 2 is sufficiently large and n sufficiently small it will be the only one.

Proposition 3. Efficiency of Equilibria in the Coordination Game .

Proof. We show that we can Pareto-rank all symmetric profiles in the coordination game, i.e. all outcomes such that both players use the exact same categorizations. Let us denote a symmetric categorization profile by [P, P ]. For all symmetric profiles, since players are using the exact same categorizations their bias from each other is always Bias 2 [P, P ] = 0. Thus, the EP E C of these categorization profiles depends only on the variance. It is equal to EP E C [P, P ] = V ar[P ] + V ar[P ]. We know from Lemma 2 that the coarser the categorization, the smaller its variance. This means that in any stochastic environment (σ 2 > 0) the EP E C of a coarser symmetric categorization profile will always have a smaller variance component than the EP E C of a finer symmetric categorization profile. Symmetric categorization profiles are therefore Pareto-ranked with coarser outcomes being more efficient than finer outcomes for any positive noise level. In the case of σ 2 = 0, V ar[P ] = 0 for all categorizations, and therefore all symmetric categorization profiles are equally efficient.

Note also that as all categorizations at the same level of coarseness have an equal variance, all symmetric categorization profiles at the same level of coarseness will be equally efficient at any given noise level in the coordination game.

Lemma 5. Bias-Variance Decomposition of EP E IP &C Proof. This follows directly from combining Lemma 1 and Lemma 3. Lemma 6. Ruling Out Some Outcomes in the IP &C Game .

Part 1.

Proposition 5 .

 5 Efficiency of Equilibria in the IP &C Game . Any [ |P | is Pareto-superior to any [P, P ] if and only if one of the following holds: (i) If Bias 2 [ ∼ P ] > Bias 2 [P ] and w is sufficiently low, with the sufficient threshold strictly decreasing in σ 2 n . (ii) If Bias 2 [ ∼ P ] ≤ Bias 2 [P ] regardless of w, σ 2 > 0, and n.

Lemma 2 .

 2 Comparative Statics of Bias and Variance Components of EP E IP Part 1.

  2 [P ] -Bias 2 [P ] = tv( Ŷt -Ŷv ) 2 t + v Thus, we have shown that Bias 2 [P , P ] = Bias 2 [P ] -Bias 2 [P ]. This holds for any two categorizations with consecutive coarseness levels where the second refines the first. Analogically, Bias 2 [P, P * ] = Bias 2 [P * ] -Bias 2 [P ] holds for all P P * . Thus, inequality (5) is equivalent to: V ar[P ] -V ar[P * ] > Bias 2 [P * ] -Bias 2 [P ] This can be re-written as EP E[P ] > EP E[P * ]. And since we assumed P * is the finest optimal categorization for IP this is by definition true, because all categorizations finer than P have a greater EP E IP . Proposition 2. Existence of Equilibria in the Coordination Game .

  C K is a decision maker's complete model for making predictions. It is a set of categories that partition the set of object types X. The focus of our analysis is on the coarseness of the different possible categorizations. Coarseness is determined by the number of categories a categorization contains, that is by its cardinality denoted as |P |. We say a categorization P is finer than P if and only if |P | > |P |. P is coarser than P if and only if |P | < |P |. P and P are equally coarse if and only if |P | = |P |.

  It shows that the EP E IP [P ] increases if any of the following components increases: the expected variance of the category averages of the categorization V ar[P ], the expected variance of the underlying object types V ar[Y ], and the expected bias of the category averages of the categorization Bias 2 [P ]. For expositional convenience from now on we write bias and variance instead of expected bias and expected variance component of the expected prediction error. 15 Lemma 2. Comparative Statics of Bias and Variance Components of EP E IP . Part 1. For any categorization P , V ar[P ] + V ar[Y ] = pσ 2 |P | n + σ 2 is strictly increasing in σ 2 and strictly decreasing in n. It is strictly increasing in the number of categories |P |.

Part 2. For any P P : Bias 2 [P ] ≤ Bias 2 [P ].

Both casual observation and abundant research in psychology, cognitive science, and more recently economics suggest so, see e.g.Lakoff (1987), Cohen and Lefebvre (2005),[START_REF] Grimm | An Experiment on Learning in a Multiple Games Environment[END_REF] Mengel (2012), or Mengel (2012a).

Some papers discussing these and other situations in which the coordination motive matters include[START_REF] Scharfstein | Herd Behavior and Investment[END_REF],[START_REF] Meub | Strategic Coordination in Forecasting: An Experimental Study[END_REF][START_REF] Scott | Information Aggregation and Product Reviews in the Entertainment Industry[END_REF].

We will use the term 'object' broadly to denote any observation or any experience a decision maker may have. It may stand, for example, for a job applicant faced by an employer. In that case observed characteristics may be education, age, race, gender, etc., and the unobserved value that the agent is trying to predict may be the applicant's suitability for a particular job.

In this model we assume that people categorize. On the complementary question as to why decision makers may want to use categories at all to make predictions, see e.g.[START_REF] Peski | Prior Symmetry, Similarity-based Reasoning, and Endogenous Categorization[END_REF], who also provides a comparison of a categorizing and a Bayesian decision maker. The model presented here is non-Bayesian, it is closer to classical/frequentist statistics, and as such complementary to the Bayesian paradigm. Note in particular that in this model a decision maker does not need to have prior beliefs, and instead it can be seen as one way to model how priors are generated.

See in particular[START_REF] Mohlin | Optimal Categorization[END_REF], as well as Al-Najjar and Pai (2014), and the literature in econometrics and machine learning discussed in the next section.

There is also a less related literature on categorization that focuses on different questions than the prediction issue[START_REF] Manzini | Categorize Then Choose: Boundedly Rational Choice and Welfare[END_REF][START_REF] Mandler | A Million Answers to Twenty Questions: Choosing by Checklist[END_REF][START_REF] Azrieli | Categorization Generated by Extended Prototypes: An Axiomatic Approach[END_REF].

On prototype models, see[START_REF] Rosch | Cognitive Representations of Semantic Categories[END_REF][START_REF] Rosch | Principles of Categorization[END_REF]. On exemplar models, see[START_REF] Nosofsky | Attention, Similarity, and the Identification-Categorization Relationship[END_REF][START_REF] Robert | The Generalized Context Model: An Exemplar Model of Classification[END_REF].

Mengel (2012a) takes an evolutionary approach to explain categorization.

For some overviews, see[START_REF] Ashby | Human Category Learning[END_REF] Maddox (2005), Zaki et al. (2003), and[START_REF] Smith | Categories and Concepts[END_REF].

The analysis can be extended to allow e.g. for objects of each type to be sampled from some probability distribution.

The analysis can be extended to allow for objects of different types to have different variance of the noise term.

This is an analogy to bias and variance as properties of an estimator, but here we apply the concepts to the phenomenon of categorization, which in our framework has a set of estimators, i.e. a set of category averages, attached to it.

The term variance can have different meanings in other contexts. Throughout this paper, we use it exclusively to denote the variance component of an EP E.

Apart from the trivial case when the means of all object types are equal.

The biases of categorizations that are not related by the "refines" relation are not directly comparable without making additional assumptions.

Analogous conditions can be written down for Player 2.

See also[START_REF] Hart | A Reinforcement Procedure Leading to Correlated Equilibrium[END_REF], who consider equilibria in situations in which a player knows neither her own payoff function, nor the characteristics of the other players.

See Börgers and Sarin (1997) for an analysis of the close relation between reinforcement learning and evolutionary replicator dynamics.

[P 1 , P

] >

received funding for this work from the Agence Nationale de la Recherche (Programme Investissement d'avenir), grant number ANR-17-EURE-0010, from the IDEX Chair, Information, Deliberation and Collective Choice at IAST, and from Cambridge-INET.

population. After some algebraic transformations the Bias 2 can be rewritten as:

For a category that has v or t + v object types, we replace t in equation ( 4) by v and t + v, respectively. We now show that:

As t > 0 and v > 0 and the remaining term is squared, the above inequality always holds.

Proposition 1. Coarseness of the Optimal Categorization(s) for Individual Prediction

Proof. We now derive how the coarseness of the optimal categorization(s) changes with changes in σ 2 . Note that changes in σ 2 and in n do not affect the bias terms, i.e. the RHS of inequality (1). Therefore, in inequality (1) only the LHS will change.

i) First, consider a potential deviation to a finer categorization. In Lemma 2 Part 1 we showed that the difference in the variance between a finer and a coarser

If the LHS is negative or equal to zero, then the last inequality will always be satisfied (for any 0 ≤ w ≤ 1), as the RHS is always positive. Hence the remaining condition to be checked is the case that the LHS is positive. In this case we can rewrite the inequality as:

Note that the only terms affected by σ 2 and n are the variances in the numerator of the RHS of this inequality, with the difference between these two increasing if σ 2 increases and/or n decreases. This means that the maximum weight on individual prediction that can be allowed for this condition to hold increases as σ 2 goes up and/or n goes down. For any given w (with 0 ≤ w ≤ 1) there will be some σ 2 n that is sufficiently high to satisfy the threshold condition. Finally, to rule out asymmetric equilibria, we need to consider two players using a different categorization at the same coarseness level. If they make a different prediction in expectation for at least one type of object, then one of the two players has an incentive to deviate to the categorization used by the other player. This is true for any 0 ≤ w < 1 as the variance is not affected, but one of the two categorizations will have a smaller bias component of the EP E IP and it is always good to move to using the same categorization from a coordination point of view.

Part 2.

Proof. We need to show that if P * is the finest optimal for IP, then [P, P ] is not an equilibrium in the IP &C game for any P P * . We show this by showing that Player 1 has a profitable deviation to P * , i.e. EP E IP &C EP E IP &C 1 [P * 1 , P 2 ]. Applying again the result derived in inequality (3), we get:

We know from Lemma 4 Part 2 that Bias 2 [P * 1 , P 2 ] = Bias 2 [P * 1 ] -Bias 2 [P 1 ] for any P P * . Thus, the inequality becomes:

We know that this holds as P * is the finest optimal categorization for IP .

Proposition 4. Existence of Equilibria in the IP &C game .

Proof. Assume a symmetric categorization profile is an equilibrium in the IP &C game for a given σ 2 n . Consider an increase in σ 2 . Can this lead to a player having an incentive to unilaterally deviate to a finer categorization? The RHS (last two lines) of inequality (3) is not affected by a change in σ 2 . The LHS is the difference in variances between a coarser and a finer categorization. This difference is smaller than or equal to zero in any stochastic environment, and increasingly negative with any increases in σ 2 . Thus, if the inequality (3) held before the change in σ 2 , it will continue to hold after an increase in σ 2 . Can a player have an incentive to unilaterally deviate to another equally coarse categorization after an increase in σ 2 ? Lemma 2 showed that categorizations of equal coarseness have the same variances regardless of the noise level. Thus, both the LHS and the RHS are not affected by the change in noise level and a player who had no incentive to unilaterally deviate to another categorization at the same level of coarseness before the increase, will still not have an incentive to do so after the increase. Can a player have an incentive to unilaterally deviate to a coarser categorization? In this case the LHS is the difference in variances between a finer and a coarser categorization. It is positive and increasing in σ 2 . The RHS is not affected. Thus, if σ 2 is sufficiently high, the LHS will become greater than the RHS and it will be profitable for a player to unilaterally deviate to a coarser categorization. This means that as σ 2 increases, finer symmetric categorization profiles that were equilibria before the noise increase may stop being equilibria, thus reducing the number of symmetric NE. The proof for a decrease of the sample size n is analogous.

Next, we derive a sufficient condition for the coarsest possible categorization profile, denoted here by [P * 1 , P * 2 ], to be an equilibrium in the IP &C game regardless of the noise level and the sample size. Since there is a unique coarsest categorization, there is no other categorization at the same level of coarseness or coarser to deviate to. We only need to examine unilateral deviations to a finer categorization. Let P 1 ∈ P denote any categorization finer than the coarsest. For [P * 1 , P * 2 ] to be an equilibrium, we need inequality (3) to hold. In this case, the LHS is the difference in variance between a coarser and a finer categorization which is always ≤ 0. A sufficient though not necessary condition for inequality (3) to hold is thus that the RHS is ≥ 0. This is guaranteed if (1w)[Bias 2 [P 1 , P * 2 ] ≥ w Bias 2 [P * 1 ] -Bias 2 [P 1 ] for any P 1 ∈ P finer than the coarsest. Note that as long as w ≤ 1 2 this condition always holds for any P P * and hence for all possible categorizations as all of them refine P * . For w > 1 2 , the LHS would be smaller than the RHS for sufficiently high σ 2 n .

Proposition 5. Efficiency of Equilibria in the IP &C Game .

Proof. We derive when EP E

We know that in any stochastic environment V ar

We know from Lemma 2 Part 1 that V ar[P ] -V ar[ ∼ P ] is strictly increasing in σ 2 and strictly decreasing in n (for any σ 2 > 0). Hence as σ 2 increases or n decreases, the RHS of the above inequality increases. This means that the noisier the environment and the smaller the sample size, the lower the threshold weight on coordination that is sufficient to Pareto-rank any coarser symmetric equilibrium as more efficient than any finer symmetric equilibrium. What is more, for any 0 ≤ w < 1, there will be some noise σ 2 to sample size n ratio that is high enough to allow for such a Pareto-ranking of the equilibria in the IP &C game.

(ii). If Bias 2 [ ∼ P ] -Bias 2 [P ] ≤ 0, then it is straightforward to show that inequality (6) holds for any 0 ≤ w ≤ 1, any σ 2 > 0, and any n ≥ 1.