We introduce a network creation game in which each player (vertex) has a fixed budget to establish links to other players. In this model, each link has a unit price, and each agent tries to minimize its cost, which is either its eccentricity or its total distance to other players in the underlying (undirected) graph of the created network. Two versions of the game are studied: In the MAX version, the cost incurred to a vertex is the maximum distance between the vertex and other vertices, and, in the SUM version, the cost incurred to a vertex is the sum of distances between the vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. We take the social cost of the created network to be its diameter, and next we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. When the sum of players’ budgets is n − 1, the equilibrium graphs are always trees, and we prove that their maximum diameter is Θ( n ) and Θ(log n ) in MAX and SUM versions, respectively. When each vertex has a unit budget (i.e., can establish a link to just one vertex), the diameter of any equilibrium graph in either version is Θ(1). We give examples of equilibrium graphs in the MAX version, such that all vertices have positive budgets and yet the diameter is Ω(√log n ). This interesting (and perhaps counterintuitive) result shows that increasing the budgets may increase the diameter of equilibrium graphs and hence deteriorate the network structure. Then we prove that every equilibrium graph in the SUM version has diameter 2 O (√log n ) . Finally, we show that if the budget of each player is at least k , then every equilibrium graph in the SUM version is k -connected or has a diameter smaller than 4.

Modeling is one of the major research areas in social network analysis whose goal is to study networks structure and its evolution. Motivated by the intuition that members in social networks behave selfishly, network creation games have been introduced for modeling social networks. In this paper, our aim is to measure how much the output graphs of a given network creation game are compatible with a social network. We first show that the precise measurement is not possible in polynomial time. Then we propose a method for its approximation; finally, we show the usability of our method by conducting experiments on real network data.

Open and autonomous environments, such as peer to peer networks or many social networks, are efficient only if cooperation among nodes is ensured. In order to ensure cooperative behavior, we have added a new node type to the system, called inspector and used game theoretical tools to analyze the system. Inspectors punish both misbehaving nodes as well as nodes who provide dishonest ratings about other peers. Analyzing the proposed inspection game ensures that corruption of inspectors and misbehavior of nodes is bounded. The game enables the system designer to set the amount of corruption that is allowed according to the budget.

We consider a network creation game in which, each player (vertex) has a limited budget to establish links to other players. In our model, each link has a unit cost and each agent tries to minimize its cost which is its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two variants of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between that vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between that vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard.

In the [Formula: see text]-subgraph problem, we are given an undirected graph [Formula: see text] with edge costs and two positive integers [Formula: see text] and [Formula: see text], and the goal is to find a minimum cost simple [Formula: see text]-edge-connected subgraph of [Formula: see text] with at least [Formula: see text] nodes. This generalizes several classical problems, such as the minimum cost [Formula: see text]-spanning tree problem, or [Formula: see text]-MST (which is a [Formula: see text]-subgraph), and the minimum cost [Formula: see text]-edge-connected spanning subgraph (which is a [Formula: see text]-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062–1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2008, pp. 119–130] show that the [Formula: see text]-subgraph problem has an [Formula: see text]-approximation (even for 2-node-connectivity) and that the [Formula: see text]-subgraph problem in general is almost as hard as the densest [Formula: see text]-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle inequality), like in the [Formula: see text]-MST problem, then there is an [Formula: see text]-approximation algorithm for the [Formula: see text]-subgraph problem. This essentially generalizes the [Formula: see text]-MST constant factor approximability to higher connectivity.

The complexity of the optimal phase control problem in wireless MIMO systems with scalar feedback quantization and equal-gain transmission is studied. The problem is shown to be NP-hard when the number of receive antennas grows linearly with the number of transmit antennas. For the case where the number of receive antennas is constant, the problem can be solved in polynomial time. An optimal algorithm is explicitly constructed. For practical purposes, a low-complexity algorithm based on local search is presented. Simulation results show that its performance is nearly optimal.

In the last decade, the notion of metric embeddings with small distortion has received wide attention in the literature, with applications in combinatorial optimization, discrete mathematics, and bio-informatics. The notion of embedding is, given two metric spaces on the same number of points, to find a bijection that minimizes maximum Lipschitz and bi-Lipschitz constants. One reason for the popularity of the notion is that algorithms designed for one metric space can be applied to a different one, given an embedding with small distortion. The better distortion, the better the effectiveness of the original algorithm applied to a new metric space. The goal recently studied by Kenyon et al. [2004] is to consider all possible embeddings between two finite metric spaces and to find the best possible one; that is, consider a single objective function over the space of all possible embeddings that minimizes the distortion. In this article we continue this important direction. In particular, using a theorem of Albert and Atkinson [2005], we are able to provide an algorithm to find the optimal bijection between two line metrics, provided that the optimal distortion is smaller than 13.602. This improves the previous bound of 3 + 2√2, solving an open question posed by Kenyon et al. [2004]. Further, we show an inherent limitation of algorithms using the “forbidden pattern” based dynamic programming approach, in that they cannot find optimal mapping if the optimal distortion is more than 7 + 4√3 (≃ 13.928). Thus, our results are almost optimal for this method. We also show that previous techniques for general embeddings apply to a (slightly) more general class of metrics.

We consider the optimal phase control problem in wireless MIMO systems with quantized phases. We show that the problem is NP-hard when number of receive antennas grows linearly with the number of transmit antennas. For the case where the number of receive antennas is constant, we show that the problem is no longer NP-hard by providing a polynomial time algorithm.