
## 3. Mathematics Of Collective Intelligence

One common solution to these types of side-effect problems is to have particular agents of the network (e.g., a "network manager" Korilis, Lazar, & Orda, 1995) dictate certain choices to other agents.  This solution can incur major brittleness and scaling problems however. Another kind of approach, which avoids the problems of a centralized manager, is to provide the agents with extra incentives that can induce them to take actions that are undesirable to them from a strict SPA sense. Such incentive can be in the form of "taxes" or "tolls" added to the costs associated with traversing particular links to discourage the use of those links. Such schemes in which tolls are superimposed on the agents' goals are a special case of the more general approach of replacing the goal of each agent with a new goal. These new goals are specifically tailored so that if they are collectively met the system maximizes throughput. A priori, a agent's goal need have no particular relation with the SPA-type cost incurred by that agent's packets. Intuitively, in this approach, we provide each agent with a goal that is "aligned" with the global objective, with no separate concern for of that goal's relation to the SPA-type cost incurred by the traffic routed by that agent.

In this section, we summarize the salient aspects of a Collective Intelligences (COIN) (Wolpert, Wheeler, & Tumer, 2000; Wolpert & Tumer, 1999). In this paper we consider systems that consist of a set of agents, connected in a network, evolving across a set of discrete, consecutive time steps, t ∈ {0, 1, ...}. Without loss of generality, we let all relevant characteristics of a agent η at time t - including its internal parameters at that time as well as its externally visible actions - be encapsulated by a Euclidean vector Cnt with components Cnt:::
We call this the "state" of agent n at time t, and let c, be the state of all agents at time t, while ( is the state of all agent across all time.

World utility, G ((), is a function of the state of all agents across all time.  When η is an agent that uses a Machine Learning (ML) algorithm to "try to increase" its private utility, we write that private utility as gn (ζ), or more generally, to allow that utility to vary in time, 9η,τ (ζ).

We assume that ζ encompasses all physically relevant variables, so that the dynamics of the system is deterministic (though of course imprecisely known to anyone trying to control the system). Note that this means that all characteristics of an agent η at t = 0 that affects the ensuing dynamics of the system must be included in C n n . For ML-based agents, this includes in particular the algorithmic specification of its private utility, typically in the physical form of some computer code (the mathematics can be generalized beyond ML-based agents, as elaborated in Wolpert & Tumer, 1999).

Here we focus on the case where our goal, as COIN designers, is to maximize world utility through the proper selection of private utility functions. Intuitively, the idea is to choose private utilities that are aligned with the world utility, and that also have the property that it is relatively easy for us to configure each agent so that the associated private utility achieves a large value. In this paper, all utilities we consider are of the form E t> r R t ( ζ t ) for reward functions R t (simply E t R t ( ζ t ) for non-time-varying utilities). From now on, we will only consider world utilities whose associated set of { R t } are all time-translations of one another. In particular, as shown below, overall network throughput is expressible this way.