## New Research In

### Physical Sciences

### Social Sciences

#### Featured Portals

#### Articles by Topic

### Biological Sciences

#### Featured Portals

#### Articles by Topic

- Agricultural Sciences
- Anthropology
- Applied Biological Sciences
- Biochemistry
- Biophysics and Computational Biology
- Cell Biology
- Developmental Biology
- Ecology
- Environmental Sciences
- Evolution
- Genetics
- Immunology and Inflammation
- Medical Sciences
- Microbiology
- Neuroscience
- Pharmacology
- Physiology
- Plant Biology
- Population Biology
- Psychological and Cognitive Sciences
- Sustainability Science
- Systems Biology

# Averaging principle for second-order approximation of heterogeneous models with homogeneous models

Edited by Carl de Boor, University of Wisconsin, Madison, WI, and approved October 8, 2012 (received for review May 2, 2012)

## Abstract

Typically, models with a heterogeneous property are considerably harder to analyze than the corresponding homogeneous models, in which the heterogeneous property is replaced by its average value. In this study we show that any outcome of a heterogeneous model that satisfies the two properties of differentiability and symmetry is *O*(ɛ^{2}) equivalent to the outcome of the corresponding homogeneous model, where ɛ is the level of heterogeneity. We then use this averaging principle to obtain new results in queuing theory, game theory (auctions), and social networks (marketing).

Mathematical modeling is a powerful tool in scientific research. Typically, the mathematical model is merely an approximation of the actual problem. Therefore, when choosing the model to work with, one has to strike a balance between complex models that are more realistic and simpler models that are more amenable to analysis and simulations. This dilemma arises, for example, when the model contains a heterogeneous quantity. In such cases, a huge simplification is usually achieved by replacing the heterogeneous quantity with its average value. The natural question that arises is whether this approximation is “legitimate,” i.e., whether the error that is introduced by this approximation is sufficiently small.

Let us illustrate this with the following example, which is discussed in detail below. Consider a queue with *k* heterogeneous servers, whose expected service times are *μ*_{1}, … , *μ*_{k}. We want to calculate analytically the expected number of customers in the system, which we denote* by *F*(*μ*_{1}, … , *μ*_{k}). Although an explicit expression for *F*(*μ*_{1}, … , *μ*_{k}) is not available, there is a well-known explicit expression in the case of *k* homogeneous servers, which we denote by . A natural approximation for the expected number of customers in the system is

where is the average of {*μ*_{1}, … , *μ*_{k}}.

More generally, let *F*(*μ*_{1}, … , *μ*_{k}) denote the “outcome” of a heterogeneous model, let

denote the level of heterogeneity of {*μ*_{1}, … , *μ*_{k}}, and let *F*_{homog.}(*μ*) denote the outcome of the corresponding homogeneous model. If the function *F*(*μ*_{1}, … , *μ*_{k}) is differentiable, then it immediately follows that

Therefore, for a 10% heterogeneity level, the error of approximating *F*(*μ*_{1}, … , *μ*_{k}) with is, roughly speaking, on the order of 10%. In many studies in different fields, however, researchers have noted that the error of this approximation is considerably smaller than ɛ. Moreover, this observation seems to hold even when the level of heterogeneity is not small.

In this study we show that these observations follow from a general principle, which we call the averaging principle. Specifically, we show that any outcome of a heterogeneous model that satisfies the two properties of differentiability and symmetry is *O*(ɛ^{2}) asymptotically equivalent to the outcome of the corresponding homogeneous model; i.e.,

Thus, if the function *F* is also symmetric, the error of the approximation in Eq. **1** for a 10% heterogeneity level is only *O*(1%).

The averaging principle of this study is unrelated to averaging principles that originate from laws of large numbers for *k* ≫ 1, such as mean-field approximations or approximations of a continuous population with a large discrete population (see, e.g., refs. 1 and 2). Thus, for example, this principle holds when there are only few servers in a queuing system or few bidders in an asymmetric auction. The averaging principle can be classified as a perturbation method in analysis. Whereas it can also be viewed as an approximation rule, we note that approximation theory is usually more interested in how well a family of simple functions approximates a given complicated function (see, e.g., ref. 3).

## Averaging Principle

Let *F*(*μ*_{1}, … , *μ*_{k}) be the outcome of a model with a heterogeneous property, captured by the *k* parameters *μ*_{1}, … , *μ*_{k}, that satisfies the following two properties:

*i*)**Differentiability**:*F*is twice continuously differentiable at and near the diagonal*μ*_{1}= … =*μ*_{k}.*ii*)**Symmetry**: For every (*μ*_{1}, …*μ*_{k}) ∈ ℝ^{k}and every*i*≠*j*,*F*(…,*μ*_{i}, …,*μ*_{j}, …) =*F*(…,*μ*_{j}, …,*μ*_{i}, …). Thus, the outcome*F*is independent of the order in which we list the heterogeneous parameters.^{†}

Then, we have the following result:^{‡}

### Theorem 1 (the Averaging Principle).

*Let F be symmetric in its arguments and twice continuously differentiable*. *Then*, *there exist two positive functions δ*(*x*) *and C*(*x*) *such that the following holds*. *Let* ** μ** = (

*μ*

_{1}, … ,

*μ*

_{k})

*be sufficiently close to the diagonal*;

*i.e*.,

*where* , *is the arithmetic average*, *and* ‖⋅‖ *is a vector norm on* ℝ^{k}. *Then*,

*where* .

*Theorem 1* remains valid if *μ*_{1}, … , *μ*_{k} are functions and not scalars; see *Game Theory Application: Assymetric Auctions* below.

### Using the Geometric and Harmonic Averages.

In *Theorem 1*, we averaged *μ*_{1}, … , *μ*_{k} using the arithmetic mean. It is well known in homogenization theory that in some cases the correct homogenization is provided by the geometric or the harmonic mean. To address the question of the “correct” averaging, we recall the following result.

### Lemma 1.

*Let μ* > 0, *and let h*_{1}, … , *h*_{k} ∈ ℝ. *Then*, as ɛ → 0, *the arithmetic*, *geometric*, *and harmonic means of μ* + ɛ*h*_{1}, … , *μ* + ɛ*h*_{k} *are O*(ɛ^{2}) *asymptotically equivalent*.

#### Proof:

We can prove this result, using the averaging principle. Let denote the arithmetic mean of *μ* + ɛ*h*_{1}, … , *μ* + ɛ*h*_{k}. The geometric mean satisfies the symmetry and differentiability properties. Therefore, application of *Theorem 1* gives

The proof for the harmonic mean is similar.

From *Lemma 1* and the differentiability of *F*_{homog}.(*μ*) it follows that

### Corollary 2.

*The averaging principle* (*Theorem 1*) *remains valid if we replace the arithmetic mean with the geometric mean or the harmonic mean*. *In the former case*, *we add the condition that* *μ**has positive coordinates*.

A natural question is which of the three averages is “optimal,” in the sense that it minimizes the constant *C* in Eq. **4**. The answer to this question is model specific. It can be pursued by calculating explicitly the *O*(ɛ^{2}) term, as we do later on.

To extend the scope of the averaging principle, we define a weaker symmetry property.^{§}

**Weak Symmetry.** For every *μ* and *η*, the outcome is independent of the value of *j* for 1 ≤ *j* ≤ *k*, where is the *j*th unit vector in ℝ^{k}.

Thus, *F*(*μ*_{1}, … , *μ*_{k}) is weakly symmetric if, whenever all but one of the parameters are identical, the outcome *F* is independent of the identity (coordinate) of the heterogeneous parameter.

Every symmetric function *F* is also weakly symmetric, but not vice versa.^{¶} Nevertheless, the proof of *Theorem 1* implies the following:

### Corollary 3.

*The averaging principle* (*Theorem 1*) *remains valid if we replace the assumption of symmetry with the assumption of weak symmetry*.

## Queuing Theory Application: An M/M/*k* Queue with Heterogeneous Service Rates

Consider a system with *k* servers. Server *i* has a random service time that is distributed according to an exponential distribution with rate *μ*_{i}. Customers arrive randomly according to a Poisson distribution with arrival rate *λ*. An arriving customer is randomly allocated to one of the nonbusy servers, if such a server exists. Otherwise, the customer joins a waiting queue, which is unbounded in length. Once a customer is allocated to a server, he gets the service he needs and then leaves the system. This setup is known in the Queuing literature as the M/M/*k* model.^{║} Examples for such multiserver queuing systems are call centers, queues in banks, parallel computing, and communications in Integrated Services Digital Network (ISDN) protocols.

Let *F*(*μ*_{1}, … , *μ*_{k}) denote the expected number of customers in the system (i.e., waiting in the queue or receiving service) in steady state. In the case of two heterogeneous servers, *F*(*μ*_{1}, *μ*_{2}) can be explicitly calculated (*SI Text*):

### Lemma 2.

*Consider an M*/*M*/2 *queue with heterogeneous servers*, *where* . *Then*, *the expected number of customers in the system is given by*

Finding an explicit solution for *F*(*μ*_{1}, … , *μ*_{k}) when *k* ≥ 3 is computationally challenging, because it involves solving a system of 2^{k} − 1 linear equations. In the homogeneous case *μ*_{1} = … = *μ*_{k} = *μ*; however, it is well known that (e.g., ref. 4)

The function *F*(*μ*_{1}, …, *μ*_{k}) can be written as a sum of solutions of a system of linear equations with coefficients that depend smoothly on *μ*_{1}, … , *μ*_{k} (*SI Text*). Therefore, *F* is differentiable. Because customers are randomly allocated to the free servers, renaming the servers does not affect the expected number of customers in the system. Hence, *F* is also symmetric. Therefore, we can use the averaging principle to obtain an explicit *O*(ɛ^{2}) approximation for *F*(*μ*_{1}, … , *μ*_{k}):

### Theorem 4.

*Consider an M*/*M*/*k queue with heterogeneous servers whose service rates are μ*_{1}, … , *μ*_{k}. *The expected number of customers in the system is given by*

*where* *is given by Eq*. **6**, , *and* ɛ *is given by Eq*. **2**.

For example, by *Theorem 4*, the expected number of customers with two heterogeneous servers is

where

Indeed, substituting in Eq. **5** and expanding in *ɛ* gives Eq. **7**.

In the case of *k* = 8 heterogeneous servers, even writing the system of 2^{8} − 1 = 255 equations for the 255 unknowns is a formidable task, not to mention solving it explicitly. By the averaging principle, however,

where is given by Eq. **6** with *k* = 8.

We ran stochastic simulations of an M/M/8 queuing system with eight heterogeneous servers, using the ARENA simulation software, and used it to calculate the expected number of customers in the system. The simulation parameters were

and ɛ varies between 0 and 1 in increments of 0.05. Because , the average service rate is . Therefore, by *Theorem 4*,

In addition, by Eq. **6**, *F*_{homog}.(5) = 6.2314.

To illustrate the accuracy of this approximation, we plot in Fig. 1 the relative error of the averaging-principle approximation . As expected, this error scales as ɛ^{2}. Note that even when the heterogeneity is not small, the averaging-principle approximation is quite accurate. This is because the coefficient (0.594) of the *O*(ɛ^{2}) term is small.** For example, when ɛ = 0.5, the relative error is ∼2%, and for ɛ = 1 it is below 10%.

#### Remark:

We can also use the averaging principle to obtain *O*(ɛ^{2}) approximations to other quantities of interest that satisfy the symmetry property, such as the average waiting time in the queue or the probability that there are exactly *m* customers in the queue.

## Game Theory Application: Asymmetric Auctions

Consider a sealed-bid first-price auction with *k* bidders, in which the bidder who places the highest bid wins the object and pays his bid, and all other bidders pay nothing.^{††} A common assumption in auction theory is that of independent private-value auctions, which says that each bidder knows his own valuation for the object, does not know the valuation of the other bidders, but does know the cumulative distribution functions (CDF) of the valuations of the other bidders. Bidders are also characterized by their attitude toward risk: The literature usually assumes that bidders are risk neutral, because this simplifies the analysis. More often than not, however, bidders are risk averse.

A strategy of bidder *i* is a function *b*_{i} that assigns a bid *b*_{i}(*υ*_{i}) to each possible valuation *υ*_{i} of that bidder. The bid that a bidder places depends on his valuation *υ*_{i} and on his beliefs about the distributions of the valuations of the other bidders and about their bidding behavior. An equilibrium in this setup is a vector of *k* strategies , such that no single bidder can profit by deviating from his bidding strategy, whatever his valuation might be, as long as all other bidders follow their equilibrium bidding strategies.

Most of the auction literature focuses on the symmetric (homogeneous) case, in which the beliefs of any bidder about any other bidder (e.g., about his distribution of valuations, his attitude toward risk, etc.) are the same. In this case, one can look for a symmetric equilibrium, in which all bidders adopt the same strategy. In practice, however, bidders are usually asymmetric (heterogeneous), both in their attitude toward risk and in the distribution of their valuations. Each bidder then faces a different competition. As a result, the equilibrium strategies of the bidders are not the same.

The addition of asymmetry usually leads to a huge complication in the analysis. For example, consider a first-price auction for a single object with risk-neutral bidders that have private values that are independently distributed in the unit interval [0, 1] according to a common cumulative distribution function *F*. Denote by *b* the symmetric Nash equilibrium bidding strategy. Then *υ*:= *b*^{−1}, the inverse of *b*, satisfies the ordinary differential equation (ODE)^{‡‡}

This equation can be solved explicitly, yielding

Therefore, this case is “completely understood.” From the seller’s point of view, a key property of an auction is his expected revenue. In the symmetric case, Eq. **8** can be used to calculate the seller’s expected revenue *R*_{homog.}[*F*], yielding

In the asymmetric case, where the value of bidder *i* is independently distributed in [0, 1] according to *F*_{i}, the inverse equilibrium strategies are the solutions of the system of ODEs,

for *i* = 1, …, *k*, subject to the initial conditions

and the “end condition” at some unknown ,

Thus, the addition of asymmetry leads to a huge complication of the mathematical model: Instead of a single ODE that can be explicitly integrated, the mathematical model consists of a system of coupled nonlinear ODEs with a nonstandard boundary condition. As a result, Eq. **10** cannot be explicitly solved, and it is poorly understood, compared with the symmetric case.

In ref. 6, Fibich and Gavious considered Eq. **10** in the weakly asymmetric case *F*_{i} = *F* + ɛ*H*_{i}, *i* = 1, … , *k*. After several pages of informal perturbation-analysis calculations, they obtained *O*(ɛ^{2}) asymptotic approximations of the inverse equilibrium strategies . Substituting these approximations in the expression for the seller’s expected revenue showed that it is given by

This is, in fact, a special case of the averaging principle. Indeed, symmetry holds because changing the indexes of the bidders does not affect the revenue. Therefore, assuming differentiability, the averaging principle for functions (*SI Text*) yields

where . Substituting in Eq. **9** and expanding in powers of ɛ gives

Hence, Eq. **11** follows.

In ref. 7, Lebrun rigorously proved that the asymmetric equilibrium bids and the expected revenue are once differentiable. Lebrun noted that this proves Eq. **11** [with *o*(ɛ) error instead of *O*(ɛ^{2})]. In retrospect, this can be viewed as an early application of the averaging principle.

Numerical calculations (ref. 6, table 1, and ref. 8, tables 1 and 2) show that the error of the averaging-principle approximation in Eq. **12** is small (typically below 1%), even when the asymmetry level is not small (e.g., ɛ = 0.4). This provides another illustration that the averaging-principle approximation can be useful even when ɛ is not very small.

The averaging principle not only leads to a simpler derivation of Eq. **11**, but also enables us to derive a more general novel result:

### Theorem 5.

*Consider an anonymous auction*^{§§} *in which all k bidders have the same attitude toward risk*, *and all bidders follow the same* “*rules*” *when they determine their bidding strategies*.^{¶¶} *Let F*_{1}, … , *F*_{k} *be the cumulative distribution functions of the valuations of the bidders*, *and let R*[*F*_{1}, … , *F*_{k}] *be the expected revenue of the seller*. *If R is twice differentiable at and near the diagonal*, *then*

*where* , *is the average of F*_{1}, …, *F*_{k}, *and* ɛ *is the level of heterogeneity*.

Indeed, the assumptions of the theorem imply that *F* is symmetric. Therefore, if *F* is also differentiable, the theorem follows from the averaging principle.

## Social-Networks Application: Diffusion of New Products

Diffusion of new products is a fundamental problem in marketing, which has been studied in diverse areas such as retail service; industrial technology; agriculture; and educational, pharmaceutical, and consumer-durables markets (10). Typically, the diffusion process begins when the product is first introduced into the market and progresses through a series of adoption events. An individual can adopt the product due to external influences such as mass media or commercials and/or due to internal influences by other individuals who have already adopted the product (word of mouth). The internal influences depend on the underlying social-network structure, because adopters can influence only people that they “know.” The social network is usually modeled by an undirected graph, where each vertex is an individual, and two vertices are connected by an edge if they can influence each other.

The first quantitative analysis of diffusion of new products was the Bass model (11), which inspired a huge body of theoretical and empirical research. In this model and in many of the subsequent product-diffusion models:

*i*) A new product is introduced at time*t*= 0.*ii*) Once a consumer adopts the product, he remains an adopter at all later times.*iii*) If consumer*j*has not adopted before time*t*, the probability that he adopts the product in the time interval [*t*,*t*+*s*), given that the product was already adopted by*n*_{j}(*t*) people that are connected to*j*, and that no other consumer adopts the product in the time interval [*t*,*t*+*s*), is

as *s* → 0, where *m*_{j} is the total number of individuals connected to consumer *j* and the parameters *p*_{j} and *q*_{j} describe the likelihood of individual *j* to adopt the product due to external and internal influences, respectively.

We say that a social network is translation invariant if any individual sees exactly the same network structure. Therefore, in particular, *m*_{j} is independent of *j*. Examples of translation-invariant social networks are as follows (Fig. 2 *A–D*):

*A*) A complete graph, in which any two individuals are connected.*B*) A one-dimensional circle, in which each individual is connected to his two nearest neighbors.*C*) A one-dimensional circle, in which each individual is connected to his four nearest neighbors.*D*) A two-dimensional torus, in which each individual is connected to his four nearest neighbors.

We say that the individuals are homogeneous when all individuals share the same parameters; i.e., *p*_{j} = *p* and *q*_{j} = *q* for every individual *j*. Let *N*(*t*) denote the number of adopters at time *t*. The expected aggregate adoption curve *E*_{homog.}[*N*(*t*; *p*, *q*)] in several translation-invariant social networks with homogeneous individuals was analytically calculated in refs. 12 and 13. In these studies, the assumption that all individuals are homogeneous was essential for the analysis.

One of the fundamentals of marketing theory is that consumers are anything but homogeneous. An explicit calculation of the expected aggregate adoption curve *E*[*N*(*t*;{*p*_{j}},{*q*_{j}})] in the heterogeneous case, however, is much harder than in the homogeneous case. As a result, the effect of heterogeneity is not well understood.

The averaging principle allows us to approximate the heterogeneous model with the corresponding homogeneous model. Consider a translation-invariant network. Then, for *t* ≥ 0 the function *F*({*p*_{j}},{*q*_{j}}) := *E*[*N*(*t*;{*p*_{j}},{*q*_{j}})] is differentiable and weakly symmetric (*SI Text*). Therefore, by the averaging principle,

### Theorem 6.

*The expected aggregate adoption curve in a translation-invariant social network with heterogeneous individuals can be approximated with*

*where* *and* *are the averages of* {*p*_{j}} *and* {*q*_{j}}, *respectively*, *and* ɛ *is the level of heterogeneity of* {*p*_{j}} *and* {*q*_{j}}.

*Theorem 6* is consistent with previous numerical findings:

1) In ref. 14, simulations of an agent-based model with a complete graph showed that heterogeneity in

*p*and*q*had a minor effect on the expected aggregate adoption curve.2) Simulations of agent-based models with 1D and 2D translation-invariant networks (ref. 12, figure 18) showed that when the values of {

*p*_{j}} and {*q*_{j}} are uniformly distributed within ±20% of the corresponding values and of the homogeneous individuals, the heterogeneous and homogeneous adoption curves are nearly indistinguishable. Even when the heterogeneity level was increased to ±50%, the two adoption curves were still very close.

## Calculating the *O*(ɛ^{2}) Term

The averaging principle is based on a two-term Taylor expansion of *F*. Therefore, the error of this approximation is given, to leading order, by the quadratic term in this expansion. When *F* satisfies the differentiability and symmetry properties*** and *μ* is the arithmetic mean, this error is given by (*SI Text*)

where

Therefore,

*i*) The magnitude of this error is .*ii*) The sign of this error is the same as the sign of*α*.

A Taylor expansion in *h* gives

This shows that to determine the sign of α, one can compare the effect of adding *h* units to two parameters with the corresponding effect of adding 2*h* units to a single parameter.

The value of *α* can be calculated as follows:

### Lemma 3.

*Assume that F*(*μ*_{1}, … , *μ*_{k}) *satisfies the differentiability and symmetry properties*. *Then*,

Therefore, this calculation requires only the explicit calculations of *F* in the homogeneous case *μ*_{1} = … = *μ*_{k} and in the case that the heterogeneity is limited to a single coordinate (i.e., when *μ*_{2} = … = *μ*_{k}). In many applications this is a considerably easier task than the explicit calculation of *F* in the fully heterogeneous case.

To illustrate this, consider again the M/M/*k* example of Fig. 1 with *k* = 8. Whereas the fully heterogeneous case requires solving 2^{k} − 1 = 255 equations, the single-coordinate heterogeneous case requires solving only 2 ⋅ *k* = 16 equations. Solving these 16 equations symbolically and using *Lemma 3* yields (*SI Text*)

where the values of {*c*_{i}, *b*_{i}} are listed in Table 1.

In particular, substituting and *λ* = 28 yields *α* ∼ 0.00837. This leads to the improved approximation

The error of this improved approximation scales as 0.074ɛ^{3} (Fig. 1), which is the next term in the Taylor expansion. In particular, the relative error of Eq. **16** is below 1.5% for 0 ≤ ɛ ≤ 1.

## Final Remarks

The averaging principle is based on a simple observation: The leading-order effects of heterogeneity cancel out when the outcome is symmetric. Nevertheless, it can lead to a significant simplification of mathematical models in all branches of science.

The symmetry and the weak-symmetry properties are usually easy to check. The differentiability of *F* is easy to check in some applications, but can be quite a challenge in others. We note, however, that more often than not, functions that arise in mathematical models are differentiable, unless there is a “very good reason” why they are not. Although this is a very informal statement, we make it to point out that the “generic” case is that the outcome *F* is differentiable, rather then the other way around.

An important issue is the “level of heterogeneity” that is covered by the averaging principle. Strictly speaking, the level of heterogeneity should be “sufficiently small.” In practice, however, in many cases the averaging principle provides good approximations even when ɛ = 0.5. In other words, the coefficient of the *O*(ɛ^{2}) term is *O*(1). Whereas this is also an informal statement, we make it to point out that one should not be “surprised” that the averaging principle holds even when ɛ is not very small.

## Acknowledgments

We thank Uri Yechiali for suggesting the problem of M/M/*k* queues with heterogeneous servers and the solution of the M/M/2 problem. The research of E.S. was partially supported by Israel Science Foundation (ISF) Grant 212/09 and by the Google Interuniversity Center for Electronic Markets and Auctions.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: fibich{at}tau.ac.il.

Author contributions: G.F., A.G., and E.S. performed research.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

↵*To focus on the heterogeneous property, we suppress the dependence of

*F*on other parameters.↵

^{†}For example, in the queuing-system example, switching the identities/locations of two servers does not affect the expected number of customers in the system.↵

^{§}See the social-networks application below for an example of a weakly symmetric outcome that is not symmetric.↵

^{¶}For example,*F*(*μ*_{1},*μ*_{2},*μ*_{3},*μ*_{4}) = (*μ*_{2}−*μ*_{1})^{2}+ (*μ*_{3}−*μ*_{2})^{2}+ (*μ*_{4}−*μ*_{3})^{2}+ (*μ*_{1}−*μ*_{4})^{2}is weakly symmetric but is not symmetric.↵

^{║}For an introduction to queuing theory, see, e.g., ref. 4.↵**This coefficient is computed analytically later on from Eq.

**15**.↵

^{‡‡}See, e.g., ref. 5. Because we consider the case where all bidders use the same strategy, we omit the subscript*i*from*b*and*υ*.↵

^{§§}i.e., an auction in which the winner and the amount that each bidder pays depend solely on their bids and not on the identity of the bidders.↵

^{¶¶}For example, bidders may use bounded rationality (9) when determining their bidding strategies. Thus, bidders may restrict themselves to a class of simple strategies, such as low-order polynomial functions of the valuation*υ*. They may even not be aware of the concept of equilibrium. Nevertheless, as long as all bidders have the “same” bounded rationality, the symmetry requirement holds.↵***Here we cannot assume that

*F*is only weakly symmetric, because we require that for all*i*,*j*.This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1206867109/-/DCSupplemental.

## References

- ↵
- ↵
- ↵
- Timan AF

- ↵
- Gross D,
- Harris CM

- ↵
- Krishna V

- ↵
- Fibich G,
- Gavious A

- ↵
- ↵
- ↵
- Selten R

- ↵
- Mahajan V,
- Muller E,
- Bass FM

*Handbooks in Operations Research and Management Science: Marketing*, eds Eliashberg J, Lilien GL (North-Holland, Amsterdam), Vol 5, pp 349–408. - ↵
- ↵
- Fibich G,
- Gibori R

- ↵
- ↵
- Goldenberg J,
- Libai B,
- Muller E

*Acad Market Sci Rev*2001(9):1–19.

## Citation Manager Formats

## Sign up for Article Alerts

## Article Classifications

- Physical Sciences
- Applied Mathematics