A Coalition game model for spectrum pooling in wireless data access networks

We consider a setting in which several operators offer downlink wireless data access services in a certain geographical region. Each operator deploys several base stations or access points, and registers some subscribers. In such a situation, if operators pool their infrastructure, and permit the possibility of subscribers being served by any of the cooperating operators, then there can be overall better user satisfaction, and increased operator revenue. We use coalitional game theory to investigate such resource pooling and cooperation between operators.We use utility functions to model user satisfaction, and show that the resulting coalitional game has the property that if all operators cooperate (i.e., form a grand coalition) then there is an operating point that maximizes the sum utility over the operators while providing the operators revenues such that no subset of operators has an incentive to break away from the coalition. We investigate whether such operating points can result in utility unfairness between users of the various operators. We also study other revenue sharing concepts, namely, the nucleolus and the Shapely value. Such investigations throw light on criteria for operators to accept or reject subscribers, based on the service level agreements proposed by them. We also investigate the situation in which only certain subsets of operators may be willing to cooperate.

A game theoretic approach for feature clustering and its application to feature selection

In this paper, we develop a game theoretic approach for clustering features in a learning problem. Feature clustering can serve as an important preprocessing step in many problems such as feature selection, dimensionality reduction, etc. In this approach, we view features as rational players of a coalitional game where they form coalitions (or clusters) among themselves in order to maximize their individual payoffs. We show how Nash Stable Partition (NSP), a well known concept in the coalitional game theory, provides a natural way of clustering features. Through this approach, one can obtain some desirable properties of the clusters by choosing appropriate payoff functions. For a small number of features, the NSP based clustering can be found by solving an integer linear program (ILP). However, for large number of features, the ILP based approach does not scale well and hence we propose a hierarchical approach. Interestingly, a key result that we prove on the equivalence between a k-size NSP of a coalitional game and minimum k-cut of an appropriately constructed graph comes in handy for large scale problems. In this paper, we use feature selection problem (in a classification setting) as a running example to illustrate our approach. We conduct experiments to illustrate the efficacy of our approach.

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.

The use of role-play games in teaching: The International Climate Negotiation Game

This paper presents a role-play game designed by the authors, which focuses on international climate negotiations. The game has been used at a university with students all drawn from the same course and at summer schools with students from different levels (undergraduate, master’s and doctoral students and post-doctoral researchers) and different knowledge areas (economics, law, engineering, architecture, biology and others). We discuss how the game fits into the process of competence-based learning, and what benefits games, and role-play games in particular, have for teaching. In the game, students take on the role of representatives of national institutions and experience at first hand a detailed process of international negotiation concerned with climate change.

ADAPTECC: A Role-Play Game about Adapting to Climate Change

The ADAPTECC Climate Change Adaptation Game is a role-play game designed to enable players to experience the difficulties that arise at local and regional levels when authorities have to implement adaptation measures. Adaptation means anticipating the advert effects of climate change (CC) and taking measures to prevent and minimise the damage caused by its impacts. Each player takes the role of the mayor or a councillor of a town affected by CC who must decide what adaptation strategies and measures to take, or of a member of the Regional Environment Department which must distribute funding for adaptation among the various towns. At the end of the game, players should have a greater understanding of the challenges posed by adaptation to CC

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Web Services and Incerta Spiriti: A Game Theoretic Approach to Uncertainty

A web-service is a remote computational facility which is made available for general use by means of the internet. An orchestration is a multi-threaded computation which invokes remote services. In this paper game theory is used to analyse the behaviour of orchestration evaluations when underlying web-services are unreliable. Uncertainty profiles are proposed as a means of defining bounds on the number of service failures that can be expected during an orchestration evaluation. An uncertainty profile describes a strategic situation that can be analyzed using a zero-sum angel-daemon game with two competing players: an angel a whose objective is to minimize damage to an orchestration and a daemon d who acts in a destructive fashion. An uncertainty profile is assessed using the value of its angel daemon game. It is shown that uncertainty profiles form a partial order which is monotonic with respect to assessment.

An Ambiguity Aversion Framework of Security Game under Ambiguities

Security is a critical concern around the world. Since resources for security are always limited, lots of interest have arisen in using game theory to handle security resource allocation problems. However, most of the existing work does not address adequately how a defender chooses his optimal strategy in a game with absent, inaccurate, uncertain, and even ambiguous strategy profiles' payoffs. To address this issue, we propose a general framework of security games under ambiguities based on Dempster-Shafer theory and the ambiguity aversion principle of minimax regret. Then, we reveal some properties of this framework. Also, we present two methods to reduce the influence of complete ignorance. Our investigation shows that this new framework is better in handling security resource allocation problems under ambiguities.

A Game-Theoretic Approach for Threats Detection and Intervention in Surveillance

Threat prevention with limited security resources is a challenging problem. An optimal strategy is to eectively predict attackers' targets (or goals) based on current available information, and use such predictions to prevent (or disrupt) their planned attacks. In this paper, we propose a game-theoretic framework to address this challenge which encompasses the following three elements. First, we design a method to analyze an attacker's types in order to determine the most plausible type of an attacker. Second, we propose an approach to predict possible targets of an attack and the course of actions that the attackers may take even when the attackers' types are ambiguous. Third, a game-theoretic based strategy is developed to determine the best protection actions for defenders (security resources).

Improvisation, Indeterminacy and Game-Mediated Participation in Network Music Performance

This chapter focuses on the relationship between improvisation and indeterminacy. We discuss the two practices by referring to play theory and game studies and situate it in recent network music performance. We will develop a parallel with game theory in which indeterminacy is seen as a way of articulating situations where structural decisions are left to the discernment of the performers and discuss improvisation as a method of play. The improvisation-indeterminacy relationship is discussed in the context of network music performance, which employs digital networks in the exchange of data between performers and hence relies on topological structures with varying degrees of openness and flexibility. Artists such as Max Neuhaus and The League of Automatic Music Composers initiated the development of a multitude of practices and technologies exploring the network as an environment for music making. Even though the technologies behind “the network” have shifted dramatically since Neuhaus’ use of radio in the 1960’s, a preoccupation with distribution and sharing of artistic agency has remained at the centre of networked practices. Gollo Föllmer, after undertaking an extensive review of network music initiatives, produced a typology that comprises categories as diverse as remix lists, sound toys, real/virtual space installations and network performances. For Föllmer, “the term ‘Net music’ comprises all formal and stylistic kinds of music upon which the specifics of electronic networks leave considerable traces, whereby the electronic networks strongly influence the process of musical production, the musical aesthetic, or the way music is received” (2005: 185).

A game-theoretic network formation model

We study the dynamics of a game-theoretic network formation model that yields large-scale small-world networks. So far, mostly stochastic frameworks have been utilized to explain the emergence of these networks. On the other hand, it is natural to seek for game-theoretic network formation models in which links are formed due to strategic behaviors of individuals, rather than based on probabilities. Inspired by Even-Dar and Kearns (2007), we consider a more realistic model in which the cost of establishing each link is dynamically determined during the course of the game. Moreover, players are allowed to put transfer payments on the formation of links. Also, they must pay a maintenance cost to sustain their direct links during the game. We show that there is a small diameter of at most 4 in the general set of equilibrium networks in our model. Unlike earlier model, not only the existence of equilibrium networks is guaranteed in our model, but also these networks coincide with the outcomes of pairwise Nash equilibrium in network formation. Furthermore, we provide a network formation simulation that generates small-world networks. We also analyze the impact of locating players in a hierarchical structure by constructing a strategic model, where a complete b-ary tree is the seed network.

Real options and game theoretical approaches to real estate development projects: multiple equilibria and the implications of different tie-breaking rules

This paper contributes to a fast growing literature which introduces game theory in the analysis of real option investments in a competitive setting. Specifically, in this paper we focus on the issue of multiple equilibria and on the implications that different equilibrium selections may have for the pricing of real options and for subsequent strategic decisions. We present some theoretical results of the necessary conditions to have multiple equilibria and we show under which conditions different tie-breaking rules result in different economic decisions. We then present a numerical exercise using the in formation set obtained on a real estate development in South London. We find that risk aversion reduces option value and this reduction decreases marginally as negative externalities decrease.

The LDC debt problem: a game-theoretical analisys

We review the LDC debt crisis since 1982, by means of game theory. New insights are obtained into the reasons behind the formation of the creditors' carte1 and the nature of the difficu1ties invo1ved in the formation of the debtors' carte1. The standard view that Rubinstein's barganing mode1s are appropriate for dea1ing with debt re1ief is shown to be faulty, un1ess the debtor buys out the debt.

NASH game and mixed H2/H∞ control

In this work a Nonzero-Sum NASH game related to the H2 and H∞ control problems is formulated in the context of convex optimization theory. The variables of the game are limiting bounds for the H2 and H∞ norms, and the final controller is obtained as an equilibrium solution, which minimizes the `sensitivity of each norm' with respect to the other. The state feedback problem is considered and illustrated by numerical examples.

A further note on the college admission game

When a stable matching rule is used for a college admission market, questions on incentives facing agents of both sides of the market naturally emerge. This note states and proves four important results which fill a gap in the theory of incentives for the college admission model. Two of them have never been demonstrated but have been used along the years and are responsible for the success that this theory has had in explaining empirical economic phenomena.