A principal managing multiple agents is considered. Agents engage in a network formation game by creating directed links with each other, while the principal pays them to stimulate formation of the desired network. Principal maximizes the difference between revenue derived from the network and rewards paid to the agents, while each agent maximizes the difference between the received reward and costs for links creation and maintenance. The novelty of the setting is that the set of agents is also chosen by the principal.
Suppose the principal chooses some set of agents and wants to implement a certain network as a strong Nash equilibrium of the agents’ game. Then, as shown in Gubko (2004), he or she has to compensate each agent’s costs of this network formation. This gives rise to a discrete optimization problem of searching a cost-minimizing network over a set of admissible networks.
We study a subclass of optimal network problems originated from the models of supply network design. With the set S of producers and the set D of consumers being fixed along with their demands and supplies L S D, the problem is to build a network of intermediary agents who dispatch and distribute product flows. Cost function c({s1, …, sk}, {d1, …, dl}) of an agent depend on the flows s1, …, sk, d1, …, dl L, running through the input and output links of the agent. This general notation catches both flow routing complexity effects (costs may depend on the number of links) and scale effects (costs may depend on the content of each input or output link, e.g. flows intensity).
Instead of searching a cost-minimizing network for every possible set of agents, we look for the locally tested conditions on a cost function that make possible general predictions about the shape of an optimal network. These implications limit the search space and release from redundant networks enumeration.
It is established that in the absence of routing complexity effects the optimal structure of the network is pretty simple and consists of no more than two intermediate layers. The conditions on the cost function are derived for each intermediary node of the optimal network to have exactly two input links and/or two output links. These conditions generalize the notion of the, so called, narrowing cost function, introduced by Voronin and Mishin (2002) for the hierarchy optimization problem.
We prove that in the absence of scale effects few technical assumptions result in the optimality of a coupled tree. It consists of a concentrating funnel and a distributing funnel connected by their necks. We show that every node in a concentrating funnel of an optimal coupled tree tends to have the same in-degree, and the same holds for out-degrees of the nodes in a distributing funnel. We use the results of Goubko, Mishin (2008) to derive analytic estimates for the optimal degrees, and also for the costs of an optimal coupled tree.
The research is supported by the grant 10-07-00104 of Russian Foundation for Basic Research.
