  The efficient design of networks has been an important engineering task that
involves challenging combinatorial optimization problems. Typically, a network
designer has to select among several alternatives which links to establish so
that the resulting network satisfies a given set of connectivity requirements
and the cost of establishing the network links is as low as possible. The
Minimum Spanning Tree problem, which is well-understood, is a nice example.
  In this paper, we consider the natural scenario in which the connectivity
requirements are posed by selfish users who have agreed to share the cost of
the network to be established according to a well-defined rule. The design
proposed by the network designer should now be consistent not only with the
connectivity requirements but also with the selfishness of the users.
Essentially, the users are players in a so-called network design game and the
network designer has to propose a design that is an equilibrium for this game.
As it is usually the case when selfishness comes into play, such equilibria may
be suboptimal. In this paper, we consider the following question: can the
network designer enforce particular designs as equilibria or guarantee that
efficient designs are consistent with users' selfishness by appropriately
subsidizing some of the network links? In an attempt to understand this
question, we formulate corresponding optimization problems and present positive
and negative results.
