Game theoretic, decentralized, local information based algorithm for community detection in social graphs

Motivated by the observation that communities in real world social networks form due to actions of rational individuals in networks, we propose a novel game theory inspired algorithm to determine communities in networks. The algorithm is decentralized and only uses local information at each node. We show the efficacy of the proposed algorithm through extensive experimentation on several real world social network data sets.

Sustaining cooperation on networks: an analytical study based on evolutionary game theory

We analytically study the role played by the network topology in sustaining cooperation in a society of myopic agents in an evolutionary setting. In our model, each agent plays the Prisoner's Dilemma (PD) game with its neighbors, as specified by a network. Cooperation is the incumbent strategy, whereas defectors are the mutants. Starting with a population of cooperators, some agents are switched to defection. The agents then play the PD game with their neighbors and compute their fitness. After this, an evolutionary rule, or imitation dynamic is used to update the agent strategy. A defector switches back to cooperation if it has a cooperator neighbor with higher fitness. The network is said to sustain cooperation if almost all defectors switch to cooperation. Earlier work on the sustenance of cooperation has largely consisted of simulation studies, and we seek to complement this body of work by providing analytical insight for the same. We find that in order to sustain cooperation, a network should satisfy some properties such as small average diameter, densification, and irregularity. Real-world networks have been empirically shown to exhibit these properties, and are thus candidates for the sustenance of cooperation. We also analyze some specific graphs to determine whether or not they sustain cooperation. In particular, we find that scale-free graphs belonging to a certain family sustain cooperation, whereas Erdos-Renyi random graphs do not. To the best of our knowledge, ours is the first analytical attempt to determine which networks sustain cooperation in a population of myopic agents in an evolutionary setting.

Game theoretic analysis of collusions in nonneutral networks

This paper studies the impact of exclusive contracts between a content provider (CP) and an internet service provider (ISP) in a nonneutral network. We consider a simple linear demand function for the CPs. We studywhen an exclusive contract is benefcial to the colluding pair and evaluate its impact on the noncolluding players at equilibrium. For the case of two CPs and one ISP we show that collusion may not always be benefcial. We derive an explicit condition in terms of the advertisement revenues of the CPs that tells when a collusion is proftable to the colluding entities.

Novel Biobjective Clustering (BiGC) Based on Cooperative Game Theory

We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

Two player game variant of the Erdos-Szekeres problem

The classical Erdos-Szekeres theorem states that a convex k-gon exists in every sufficiently large point set. This problem has been well studied and finding tight asymptotic bounds is considered a challenging open problem. Several variants of the Erdos-Szekeres problem have been posed and studied in the last two decades. The well studied variants include the empty convex k-gon problem, convex k-gon with specified number of interior points and the chromatic variant. In this paper, we introduce the following two player game variant of the Erdos-Szekeres problem: Consider a two player game where each player playing in alternate turns, place points in the plane. The objective of the game is to avoid the formation of the convex k-gon among the placed points. The game ends when a convex k-gon is formed and the player who placed the last point loses the game. In our paper we show a winning strategy for the player who plays second in the convex 5-gon game and the empty convex 5-gon game by considering convex layer configurations at each step. We prove that the game always ends in the 9th step by showing that the game reaches a specific set of configurations.

Pricing and Power allocation in Femtocells using Stackelberg Game Theory

We consider a system with multiple Femtocells operating in a Macrocell. The transmissions in one Femtocell interfere with its neighboring Femtocells as well as with the Macrocell Base Station. We model Femtocells as selfish nodes and the Macrocell Base Station protects itself by pricing subchannels for each usage. We use Stackelberg game model to study this scenario and obtain equilibrium policies that satisfy certain quality of service.

Implementing with veto players: a simple non cooperative game

The paper adapts a non cooperative game presented by Dagan, Serrano and Volij (1997) for bankruptcy problems to the context of TU veto balanced games. We investigate the relationship between the Nash outcomes of a noncooperative game and solution concepts of cooperative games such as the nucleolus, kernel and the egalitarian core.

Competitive Pressure and Job Interview Lying: A Game Theoretical Analysis

We consider a job contest in which candidates go through interviews (cheap talk) and are subject to reference checks. We show how competitive pressure - increasing the ratio of "good" to "bad" type candi- dates - can lead to a vast increase in lying and in some cases make bad hires more likely. As the number of candidates increases, it becomes harder to in- duce truth-telling. The interview stage becomes redundant if the candidates, a priori, know each others' type or the result of their own reference check. Finally, we show that the employer can bene t from committing not to reject all the applicants.

Evolution of Cooperation in the Snowdrift Game with Incomplete Information and Heterogeneous Population

Differently from previous studies of tag-based cooperation, we assume that individuals fail to recognize their own tag. Due to such incomplete information, the action taken against the opponent cannot be based on similarity, although it is still motivated by the tag displayed by the opponent. We present stability conditions for the case when individuals play unconditional cooperation, unconditional defection or conditional cooperation. We then consider the removal of one or two strategies. Results show that conditional cooperators are the most resilient agents against extinction and that the removal of unconditional cooperators may lead to the extinction of unconditional defectors.

Channel Islands marine protected areas first 5 years of monitoring: 2003-2008 [Report produced by the California Department of Fish and Game in collaboration with the Partnership for Interdisciplinary Studies of Coastal Oceans (PISCO), Channel Islands National Marine Sanctuary, and Channel Islands National Park]

The Channel Islands—sometimes called the Galapagos of North America—are known for their great beauty, rich biodiversity, cultural heritage, and recreational opportunities. In 1980, in recognition of the islands’ importance, the United States Congress established a national park encompassing 5 of California’s Channel Islands (Santa Barbara, Anacapa, Santa Cruz, Santa Rosa, and San Miguel Islands) and waters within 1 nautical mile of the islands. In the same year, Congress declared a national marine sanctuary around each of these islands, including waters up to 6 nautical miles offshore. Approximately 60,000 people visit the Channel Islands each year for aquatic recreation such as fishing, sailing, kayaking, wildlife watching, surfing, and diving. Another 30,000 people visit the islands for hiking, camping, and sightseeing. Dozens of commercial fishing boats based in Santa Barbara, Ventura, Oxnard, and other ports go to the Channel Islands to catch squid, spiny lobster, sea urchin, rockfish, crab, sheephead, flatfish, and sea cucumber, among other species. In the past few decades, advances in fishing technology and the rising number of fishermen, in conjunction with changing ocean conditions and diseases, have contributed to declines in some marine fishes and invertebrates at the Channel Islands. In 1998, citizens from Santa Barbara and Ventura proposed establishment of no-take marine reserves at the Channel Islands, beginning a 4-year process of public meetings, discussions, and scientific analyses. In 2003, the California Fish and Game Commission designated a network of marine protected areas (MPAs) in state waters around the northern Channel Islands. In 2006 and 2007, the National Oceanic and Atmospheric Administration (NOAA) extended the MPAs into the national marine sanctuary’s deeper, federal waters. To determine if the MPAs are protecting marine species and habitats, scientists are monitoring ecological changes. They are studying changes in habitats; abundance and size of species of interest; the ocean food web and ecosystem; and movement of fish and invertebrates from MPAs to surrounding waters. Additionally, scientists are monitoring human activities such as commercial and recreational fisheries, and compliance with MPA regulations. This booklet describes some results from the first 5 years of monitoring the Channel Islands MPAs. Although 5 years is not long enough to determine if the MPAs will accomplish all of their goals, this booklet offers a glimpse of the changes that are beginning to take place and illustrates the types of information that will eventually be used to assess the MPAs’ effectiveness. (PDF contains 24 pages.)

The coincidence of the kernel and nucleolus of a convex game: an alternative proof

In 1972, Maschler, Peleg and Shapley proved that in the class of convex the nucleolus and the kernel coincide. The only aim of this note is to provide a shorter, alternative proof of this result.

Cruise Report 70-S-5: Big Game Fish

(PDF contains 4 pages)

Cruise Report 70-S-7: Big Game Fisheries Investigations

(PDF contains 3 pages.)

Cruise Report 72-S-1: Big Game Fisheries Investigations

(PDF contains 5 pages.)

Cruise Report 72-S-4: Big Game Fish Investigations

(PDF contains 2 pages.)