Abstract In this paper we introduce a capacity allocation game which models the problem of maximizing network utility from the perspective of distributed noncooperative agents. Motivated by the idea of self-managed networks, in the developed framework the decision-making entities are associated with individual transmission links, deciding on the way they split capacity among concurrent flows. An efficient decentralized algorithm is given for computing a strongly Pareto-optimal strategies, constituting a pure Nash equilibrium. Subsequently, we discuss the properties of the introduced game related to the Price of Anarchy and Price of Stability. The paper is concluded with an experimental study.
@cite_38: In the autonomic Internet of the future, auction mechanisms arise as key methods for realizing efficient resource allocation. The major asset of auctions is their obliviousness to node utilities, which renders them capable of achieving a desired resource allocation regime without knowledge of the utility functions of involved entities. Auctions can aid in addressing major research challenges in such autonomic settings, such as the need to cope with diverse and conflicting interests of network entities, the need to carry out resource allocation in a decentralized manner, the requirement for matching dynamic spatiotemporal patterns of demand and supply, and the need to operate under limited or no network state and utility information. In this survey paper, we delineate the main trends and challenges associated with auction design. We start from first principles auction design for maximum auctioneer revenue or maximum allocation efficiency for one or multiple indivisible items and for divisible resources. We gradually move to more composite models, those of position auctions for Internet advertisements and those arising in spectrum sharing in cognitive radio networks. We argue that some directions worth pursuing are: (i) the design of advanced auction models that capture multi-level interaction of involved entities, (ii) the employment of double auctions for multiple seller and buyer interaction, and (iii) the design of decentralized negotiation and resource trading mechanisms.
@cite_35: This paper analyses the stability and fairness of two classes of rate control algorithm for communication networks. The algorithms provide natural generalisations to large-scale networks of simple additive increase multiplicative decrease schemes, and are shown to be stable about a system optimum characterised by a proportional fairness criterion. Stability is established by showing that, with an appropriate formulation of the overall optimisation problem, the network's implicit objective function provides a Lyapunov function for the dynamical system defined by the rate control algorithm. The network's optimisation problem may be cast in primal or dual form: this leads naturally to two classes of algorithm, which may be interpreted in terms of either congestion indication feedback signals or explicit rates based on shadow prices. Both classes of algorithm may be generalised to include routing control, and provide natural implementations of proportionally fair pricing.
@cite_33: We study how protocol design for various functionalities within a communication network architecture can be viewed as a distributed resource allocation problem. This involves understanding what resources are, how to allocate them fairly, and perhaps most importantly, how to achieve this goal in a distributed and stable fashion. We start with ideas of a centralized optimization framework and show how congestion control, routing and scheduling in wired and wireless networks can be thought of as fair resource allocation. We then move to the study of controllers that allow a decentralized solution of this problem. These controllers are the analytical equivalent of protocols in use on the Internet today, and we describe existing protocols as realizations of such controllers. The Internet is a dynamic system with feedback delays and flows that arrive and depart, which means that stability of the system cannot be taken for granted. We show how to incorporate stability into protocols, and thus, prevent undesirable network behavior. Finally, we consider a futuristic scenario where users are aware of the effects of their actions and try to game the system. We will see that the optimization framework is remarkably robust even to such gaming.
@cite_24: We propose a mechanism for auctioning bundles of multiple divisible goods. Such a mechanism is very useful for allocation of bandwidth in a network where the buyers want the same amount of bandwidth on each link in their route. We first propose a single-sided VCG-type mechanism. However, instead of reporting types, the players only reveal a two-dimensional bid signal - the maximum quantity that they want and the per unit price they are willing to pay. We show the existence of an efficient Nash equilibrium in the corresponding auction game of the mechanism. We show through an example that not all Nash equilibria are efficient but provide a distributed algorithm that yields the efficient one. Further, we provide a sufficient characterization of all efficient Nash equilibria. We then present a double-sided auction mechanism for multiple divisible goods, and show that there exists a Nash equilibrium of the auction game which yields the efficient allocation.
@cite_68: 
@cite_10: Abstract We present a game theoretic-mechanism characterization of perfect competition: we prove the perfectly competitive mechanism is the only Pareto optimal, individually rational, dominant strategy allocation mechanism. Thus, perfect competition is uniquely capable of efficiently and non-coercively solving the incentive bargaining problem when there is incomplete information, i.e., when each individual knows his own tastes and production possibilities better than anyone else. We also show one can interpret any dominant strategy, demand-revealing mechanism as “working” because it mimics the reward scheme that characterizes the perfectly competitive market, namely, the marginal product reward scheme.
Furthermore, another type of games called auctions @cite_68 seems very suitable for computer network applications @cite_38 . In @cite_33 classic Vickerey-Clarke-Groves (VCG) mechanism @cite_10 , together with the so-called Kelly mechanism (based on results obtained in @cite_35 ), is used for the network resource allocation. In @cite_24 the capacity allocation problem is stated as an auction game between flows (users), seen as buyers, and network operator, seen as an auctioneer. A distributed algorithm to find efficient Nash equilibrium is proposed. The presented mechanism is described as VCG-like, since, on the contrary to the classic VCG auction, it does not require a full valuation function.