Bounded Rationality and Repeated Network Formation

We define a finite-horizon repeated network formation game with consent and study the differences induced by two levels of individual rationality. Perfectly rational players will remain unconnected at the equilibrium, while nonempty equilibrium networks may form when players are assumed to behave as finite automata of limited complexity. We provide structural properties of the sequences of networks which are likely to form in Nash and subgame perfect Nash equilibria of the repeated game. For instance, players can form totally different connected networks at each period or the sequence of networks can exhibit a total order relationship.

Endogenous Two-Sided Markets with Repeated Transactions

We consider homogeneous two-sided markets, in which connected buyer-seller pairs bargain and trade repeatedly. In this infinite market game with exogenous matching probabilities and a common discount factor, we prove the existence of equilibria in stationary strategies. The equilibrium payoffs are given implicitly as a solution to a system of linear equations. Then, we endogenize the matching mechanism in a link formation stage that precedes the market game. When agents are sufficiently patient and link costs are low, we provide an algorithm to construct minimally connected networks that are pairwise stable with respect to the expected payoffs in the trading stage. The constructed networks are essentially efficient and consist of components with a constant buyer-seller ratio. The latter ratio increases (decreases) for a buyer (seller) that deletes one of her links in a pairwise stable component.

A decentralized model of information pricing in networks

We propose a recursive method of pricing an information good in a network of holders and demanders of this good. The prices are determined via a unique equilibrium outcome in a sequence of bilateral bargaining games that are played by connected agents. If the information is an homogenous, non-depreciating good without network effects we derive explicit formulae which elucidate the role of the link pattern among the players. Particularly, we find out that the equilibrium price is intimately related to the existence of cycles in the network: It is zero if a cycle covers the trading pair and it is proportional to the direct and indirect utility that the good generates otherwise.

Bilateral Bargaining in Networks

Each connected pair of nodes in a network can jointly produce one unit of surplus. A maximum number of linked nodes is selected in every period to bargain bilaterally over the division of the surplus, according to the protocol proposed by Rubinstein and Wolinsky (Econometrica 53 (1985), 1133-1150). All pairs, that reach an agreement, obtain the (discounted) payoffs and are removed from the network. This bargaining game has a unique subgame perfect equilibrium that induces the Dulmage-Mendelsohn decomposition (partition) of the bipartite network (of the set of nodes in this network).

Recovering Social Networks from Individual Attributes

One of the most important challenges of network analysis remains the scarcity of reliable information on existing connection structures. This work explores theoretical and empirical methods of inferring directed networks from nodes attributes and from functions of these attributes that are computed for connected nodes. We discuss the conditions, under which an underlying connection structure can be (probabilistically) recovered, and propose a Bayesian recovery algorithm. In an empirical application, we test the algorithm on the data from the European School Survey Project on Alcohol and Other Drugs.

The MNC as an externally embedded organization: An investigation of embeddedness overlap in local subsidiary networks

MNCs have been conceptualized as differentiated networks that, in turn, are embedded in external networks. Previous research has predominantly focused on the embeddedness of established subsidiaries into their local environment, omitting to shed light on the phenomenon of headquarters linkages to the local context which creates embeddedness overlap. We develop a model of why MNCs develop overlapping linkages to local subsidiary networks even if the subsidiaries have grown out of the initial start-up phase. Using detailed information on 168 European subsidiaries, we find that MNCs build and maintain more overlapping network ties when subsidiaries are high performers, hold important resources, operate in turbulent environments, and are closely connected to multinational actors as opposed to purely domestic firms.

Edge-preserving self-healing: Keeping network backbones densely connected

Healing algorithms play a crucial part in distributed peer-to-peer networks where failures occur continuously and frequently. Whereas there are approaches for robustness that rely largely on built-in redundancy, we adopt a responsive approach that is more akin to that of biological networks e.g. the brain. The general goal of self-healing distributed graphs is to maintain certain network properties while recovering from failure quickly and making bounded alterations locally. Several self-healing algorithms have been suggested in the recent literature [IPDPS'08, PODC'08, PODC'09, PODC'11]; they heal various network properties while fulfilling competing requirements such as having low degree increase while maintaining connectivity, expansion and low stretch of the network. In this work, we augment the previous algorithms by adding the notion of edge-preserving self-healing which requires the healing algorithm to not delete any edges originally present or adversarialy inserted. This reflects the cost of adding additional edges but more importantly it immediately follows that edge preservation helps maintain any subgraph induced property that is monotonic, in particular important properties such as graph and subgraph densities. Density is an important network property and in certain distributed networks, maintaining it preserves high connectivity among certain subgraphs and backbones. We introduce a general model of self-healing, and introduce xheal+, an edge-preserving version of xheal[PODC'11]. © 2012 IEEE.

Picking up the Pieces: Self-Healing in reconfigurable networks

We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. We present a new algorithm, DASH, that provably ensures that: 1) the network stays connected even if an adversary deletes up to all nodes in the network; and 2) no node ever increases its degree by more than 2 log n, where n is the number of nodes initially in the network. DASH is fully distributed; adds new edges only among neighbors of deleted nodes; and has average latency and bandwidth costs that are at most logarithmic in n. DASH has these properties irrespective of the topology of the initial network, and is thus orthogonal and complementary to traditional topology- based approaches to defending against attack. We also prove lower-bounds showing that DASH is asymptotically optimal in terms of minimizing maximum degree increase over multiple attacks. Finally, we present empirical results on power-law graphs that show that DASH performs well in practice, and that it significantly outperforms naive algorithms in reducing maximum degree increase.

Identity and Link Reliability in Social Networks

This paper considers a non-cooperative network formation game where identity is introduced as a single dimension to capture the characteristics of a player in the network. Players access to the benefits from the link through direct and indirect connections. We consider cases where cost of link formation paid by the initiator. Each player is allowed to choose their commitment level to their identities. The cost of link formation decreases as the players forming the link share the same identity and higher commitment levels. We then introduce link imperfections to the model. We characterize the Nash networks and we find that the set of Nash networks are either singletons with no links formed or separated blocks or components with mixed blocks or connected.

Investigation of AIMD based charging strategies for EVs connected to a low-voltage distribution network

In this paper we consider charging strategies that mitigate the impact of domestic charging of EVs on low-voltage distribution networks and which seek to reduce peak power by responding to time-ofday pricing. The strategies are based on the distributed Additive Increase and Multiplicative Decrease (AIMD) charging algorithms proposed in [5]. The strategies are evaluated using simulations conducted on a custom OpenDSS-Matlab platform for a typical low voltage residential feeder network. Results show that by using AIMD based smart charging 50% EV penetration can be accommodated on our test network, compared to only 10% with uncontrolled charging, without needing to reinforce existing network infrastructure. © Springer-Verlag Berlin Heidelberg 2013.

On-off based charging strategies for EVs connected to a Low Voltage distributon network

The development of appropriate Electric Vehicle (EV) charging strategies has been identified as an effective way to accommodate an increasing number of EVs on Low Voltage (LV) distribution networks. Most research studies to date assume that future charging facilities will be capable of regulating charge rates continuously, while very few papers consider the more realistic situation of EV chargers that support only on-off charging functionality. In this work, a distributed charging algorithm applicable to on-off based charging systems is presented. Then, a modified version of the algorithm is proposed to incorporate real power system constraints. Both algorithms are compared with uncontrolled and centralized charging strategies from the perspective of both utilities and customers. © 2013 IEEE.

Probabilistic Inference in Credal Networks: New Complexity Results

Credal networks are graph-based statistical models whose parameters take values in a set, instead of being sharply specified as in traditional statistical models (e.g., Bayesian networks). The computational complexity of inferences on such models depends on the irrelevance/independence concept adopted. In this paper, we study inferential complexity under the concepts of epistemic irrelevance and strong independence. We show that inferences under strong independence are NP-hard even in trees with binary variables except for a single ternary one. We prove that under epistemic irrelevance the polynomial-time complexity of inferences in credal trees is not likely to extend to more general models (e.g., singly connected topologies). These results clearly distinguish networks that admit efficient inferences and those where inferences are most likely hard, and settle several open questions regarding their computational complexity. We show that these results remain valid even if we disallow the use of zero probabilities. We also show that the computation of bounds on the probability of the future state in a hidden Markov model is the same whether we assume epistemic irrelevance or strong independence, and we prove an analogous result for inference in Naive Bayes structures. These inferential equivalences are important for practitioners, as hidden Markov models and Naive Bayes networks are used in real applications of imprecise probability.