A cyber-security problem is a conflict-resolution scenario that typically consists of a security system and at least two decision makers (e.g. attacker and defender) that can each have competing objectives. In this thesis, we are interested in cyber-security problems where one decision maker has superior or better information. Game theory is a well-established mathematical tool that can be used to analyze such problems and will be our tool of choice. In particular, we will formulate cyber-security problems as stochastic games with asymmetric information, where game-theoretic methods can then be applied to the problems to derive optimal policies for each decision maker. A severe limitation of considering optimal policies is that these policies are computationally prohibitive. We address the complexity issues by introducing methods, based on the ideas of model predictive control, to compute suboptimal polices. Specifically, we first prove that the methods generate suboptimal policies that have tight performance bounds. We then show that the suboptimal polices can be computed by solving a linear program online, and the complexity of the linear program remains constant with respect to the game length. Finally, we demonstrate how the suboptimal policy methods can be applied to cyber-security problems to reduce the computational complexity of forecasting cyber-attacks.

Experimental game theory is the use of game theoretic abstractions—games, players, and strategies—in experiments and simulations. It is often used in cases where traditional, analytical game theory fails or is difficult to apply. This thesis collects three previously published papers that provide domain-specific language (DSL) support for defining and executing these experiments, and for explaining their results. Despite the widespread use of software in this field, there is a distinct lack of tool support for common tasks like modeling games and running simulations. Instead, most experiments are created from scratch in general-purpose programming languages. We have addressed this problem with Hagl, a DSL embedded in Haskell that allows the concise, declarative definition of games, strategies, and executable experiments. Hagl raises the level of abstraction for experimental game theory, reducing the effort to conduct experiments and freeing experimenters to focus on hard problems in their domain instead of low-level implementation details. While analytical game theory is most often used as a prescriptive tool, a way to analyze a situation and determine the best course of action, experimental game theory is often applied descriptively to explain why agents interact and behave in a certain way. Often these interactions are complex and surprising. To support this explanatory role, we have designed visual DSL for explaining the interaction of strategies for iterated games. This language is used as a vehicle to introduce the notational quality of traceability and the new paradigm of explanation-oriented programming. / Graduation date: 2012

School of Economics and Political Science, Diss.--London, 2005. / Literaturverz. S. [143] - 145. The work originates from the author's PhD thesis at the London School of Economics and Political Science. (Preface).

Esta dissertação aborda a teoria dos jogos diferenciais em sua estreita relação com a teoria das equações de Hamilton-Jacobi (HJ). Inicialmente, uma revisão da noção de solução em teoria dos jogos é empreendida. Discutem-se nesta ocasião as idéias de equilíbrio de Nash e alguns de seus refinamentos. Em seguida, tem lugar uma introdução à teoria dos jogos diferenciais, onde noções de solução como a função de valor de Isaacs e de Friedman são discutidas. É nesta altura do trabalho que fica evidente a conexão entre este conceito de solução e a teoria das equações de Hamilton-Jacobi. Por ocasião desta conexão, é explorada a noção de solução clássica e é exposta uma demonstração do fato de que se um jogo diferencial possuir uma função de valor pelo menos continuamente diferenciável, esta será uma solução da equação de Hamilton-Jacobi associada ao jogo. Este resultado faz uso do princípio da programação dinâmica, devido a Bellman, e cuja demonstração está presente no texto. No entanto, quando a função de valor do jogo é apenas contínua, então embora esta não seja uma solução clássica da equação HJ associada a jogo, vemos que ela será uma solução viscosa, ou solução no sentido da viscosidade - e a esta altura são discutidos os elementos e propriedades desta classe de soluções, um teorema de existência e unicidade e alguns exemplos. Por fim, retomamos o estudo dos jogos diferenciais à luz das soluções viscosas da equação de Hamilton-Jacobi e, assim, expomos uma demonstração de existência da função de valor e do princípio da programação dinâmica a partir das noções da viscosidade / This dissertation aims to address the topic of Differential Game Theory in its connection with the Hamilton-Jacobi (HJ) equations framework. Firstly we introduce the idea of solution for a game, through the discussion of Nash equilibria and its refinements. Secondly, the solution concept is then translated to the context of Differential Games and the idea of value function is introduced in its Isaacs\'s as well as Friedman\'s version. As the value function is discussed, its relationship with the Hamilton-Jacobi equations theory becomes self-evident. Due to such relation, we investigate the HJ equation from two distinct points of view. First of all, we discuss a statement according to which if a differential game has a continuously differentiable value function, then such function is a classical solution of the HJ equation associated to the game. This result strongly relies on Bellman\'s Dynamic Programming Principle - and this is the reason why we devote an entire chapter to this theme. Furthermore, HJ is still at our sight from the PDE point of view. Our motivation is simple: under some lack of regularity - a value function which is continuous, but not continuously differentiable - a game may still have a value function represented as a solution of the associated HJ equation. In this case such a solution will be called a solution in the viscosity sense. We then discuss the properties of viscosity solutions as well as provide an existence and uniqueness theorem. Finally we turn our attention back to the theory of games and - through the notion of viscosity - establish the existence and uniqueness of value functions for a differential game within viscosity solution theory.

This thesis looks into the economics of crowdsourcing using game theoretic modeling. The art of aggregating information and expertise from a diverse population has been in practice since a long time. The Internet and the revolution in communication and computational technologies have made this task easier and given birth to a new era of online resource aggregation, which is now popularly referred to as crowdsourcing. Two important features of this aggregation technique are: (a) crowdsourcing is always human driven, hence the participants are rational and intelligent, and they have a payoff function that they aim to maximize, and (b) the participants are connected over a social network which helps to reach out to a large set of individuals. To understand the behavior and the outcome of such a strategic crowd, we need to understand the economics of a crowdsourcing network. In this thesis, we have considered the following three major facets of the strategic crowdsourcing problem. (i) Elicitation of the true qualities of the crowd workers: As the crowd is often unstructured and unknown to the designer, it is important to ensure if the crowdsourced job is indeed performed at the highest quality, and this requires elicitation of the true qualities which are typically the participants' private information. (ii) Resource critical task execution ensuring the authenticity of both the information and the identity of the participants: Due to the diverse geographical, cultural, socio-economic reasons, crowdsourcing entails certain manipulations that are unusual in the classical theory. The design has to be robust enough to handle fake identities or incorrect information provided by the crowd while performing crowdsourcing contests. (iii) Improving the productive output of the crowdsourcing network: As the designer's goal is to maximize a certain measurable output of the crowdsourcing system, an interesting question is how one can design the incentive scheme and/or the network so that the system performs at an optimal level taking into account the strategic nature of the individuals. In the thesis, we design novel mechanisms to solve the problems above using game theoretic modeling. Our investigation helps in understanding certain limits of achievability, and provides design protocols in order to make crowdsourcing more reliable, effective, and productive.

This research involves the design, development, and theoretical demonstration of models resulting in integrated misbehavior resolution protocols for ad hoc networked devices. Game theory was used to analyze strategic interaction among independent devices with conflicting interests. Packet forwarding at the routing layer of autonomous ad hoc networks was investigated. Unlike existing reputation based or payment schemes, this model is based on repeated interactions. To enforce cooperation, a community enforcement mechanism was used, whereby selfish nodes that drop packets were punished not only by the victim, but also by all nodes in the network. Then, a stochastic packet forwarding game strategy was introduced. Our solution relaxed the uniform traffic demand that was pervasive in other works. To address the concerns of imperfect private monitoring in resource aware ad hoc networks, a belief-free equilibrium scheme was developed that reduces the impact of noise in cooperation. This scheme also eliminated the need to infer the private history of other nodes. Moreover, it simplified the computation of an optimal strategy. The belief-free approach reduced the node overhead and was easily tractable. Hence it made the system operation feasible. Motivated by the versatile nature of evolutionary game theory, the assumption of a rational node is relaxed, leading to the development of a framework for mitigating routing selfishness and misbehavior in Multi hop networks. This is accomplished by setting nodes to play a fixed strategy rather than independently choosing a rational strategy. A range of simulations was carried out that showed improved cooperation between selfish nodes when compared to older results. Cooperation among ad hoc nodes can also protect a network from malicious attacks. In the absence of a central trusted entity, many security mechanisms and privacy protections require cooperation among ad hoc nodes to protect a network from malicious attacks. Therefore, using game theory and evolutionary game theory, a mathematical framework has been developed that explores trust mechanisms to achieve security in the network. This framework is one of the first steps towards the synthesis of an integrated solution that demonstrates that security solely depends on the initial trust level that nodes have for each other.

No description available.

Energy consumption and its management have been clearly identified as a challenge in computing and communication system design, where energy economy is obviously of paramount importance for battery powered devices. This thesis addresses the energy efficiency of mobile communication at the user end in the context of cellular networks. We argue that energy efficiency starts by energy awareness and propose EnergyBox, a parametrised tool that enables accurate and repeatable energy quantification at the user end using real data traffic traces as input. EnergyBox offers an abstraction of the underlying states for operation of the wireless interfaces and allows to estimate the energy consumption for different operator settings and device characteristics. The tool is used throughout the thesis to quantify and reveal inefficient data communication patterns of widely used mobile applications. We consider two different perspectives in the search of energy-efficient solutions. From the application perspective, we show that systematically quantifying the energy consumption of design choices (e.g., communication patterns, protocols, and data formats) contributes to a significantly smaller energy footprint. From the system perspective, we devise a cross-layer solution that schedules packet transmissions based on the knowledge of the network parameters that impact the energy consumption of the handset. These attempts show that application level decisions require a better understanding of possible energy apportionment policies at system level. Finally, we study the generic problem of determining the contribution of an entity (e.g., application) to the total energy consumption of a given system (e.g., mobile device). We compare the state-of-the-art policies in terms of fairness leveraging cooperative game theory and analyse their required information and computational complexity. We show that providing incentives to reduce the total energy consumption of the system (as part of fairness) is tightly coupled to the policy selection. Our study provides guidelines to select an appropriate policy depending on the characteristics of the system.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Balasubramaniam Natarajan / With the explosive growth of wireless systems and services, bandwidth has become a treasured commodity. Traditionally, licensed frequency bands were exclusively reserved for use by the primary license holders (primary users), whereas, unlicensed frequency bands allow spectrum sharing. Recent spectrum measurements indicate that many licensed bands remain relatively unused for most of the time. Therefore, allowing secondary users (users without a license to operate in the band) to operate with minimal or no interference to primary users is one way of sharing spectrum to increase efficiency. Recently, Federal Communications Commission (FCC) has opened up licensed bands for opportunistic use by secondary users. A cognitive radio (CR) is one enabling technology for systems supporting opportunistic use. A cognitive radio adapts to the environment it operates in by sensing the spectrum and quickly decides on appropriate frequency bands and transmission parameters to use in order to achieve certain performance goals. A cognitive radio network (CRN) refers to a network of cognitive radios/secondary users. In this dissertation, we consider a competitive CRN with multiple channels available for opportunistic use by multiple secondary users. We also assume that multiple secondary users may coexist in a channel and each secondary user (SU) can use multiple channels to satisfy their rate requirements. In this context, firstly, we introduce an integrated modeling and forecasting tool that provides an upper bound estimate of the number of secondary users that may be demanding access to each of the channels at the next instant. Assuming a continuous time Markov chain model for both primary and secondary users activities, we propose a Kalman filter based approach for estimating the number of primary and secondary users. These estimates are in turn used to predict the number of primary and secondary users in a future time instant. We extend the modeling and forecasting framework to the case when SU traffic is governed by Erlangian process. Secondly, assuming that scheduling is complete and SUs have identified the channels to use, we propose two quality of service (QoS) constrained resource allocation frameworks. Our measures for QoS include signal to interference plus noise ratio (SINR) /bit error rate (BER) and total rate requirement. In the first framework, we determine the minimum transmit power that SUs should employ in order to maintain a certain SINR and use that result to calculate the optimal rate allocation strategy across channels. The rate allocation problem is formulated as a maximum flow problem in graph theory. We also propose a simple heuristic to determine the rate allocation. In the second framework, both transmit power and rate per channel are simultaneously optimized with the help of a bi-objective optimization problem formulation. Unlike prior efforts, we transform the BER requirement constraint into a convex constraint in order to guarantee optimality of resulting solutions. Thirdly, we borrow ideas from social behavioral models such as Homo Egualis (HE), Homo Parochius (HP) and Homo Reciprocan (HR) models and apply it to the resource management solutions to maintain fairness among SUs in a competitive CRN setting. Finally, we develop distributed user-based approaches based on ``Dual Decomposition Theory" and ``Game Theory" to solve the proposed resource allocation frameworks. In summary, our body of work represents significant ground breaking advances in the analysis of competitive CRNs.

ITC/USA 2006 Conference Proceedings / The Forty-Second Annual International Telemetering Conference and Technical Exhibition / October 23-26, 2006 / Town and Country Resort & Convention Center, San Diego, California / Spectrum allocation in wireless communication and telemetry systems of the future may be performed in a dynamic and distributed manner, as opposed to static centralized regulations currently in place. This paper surveys a new area of research in the communications field known as cognitive radio which will allow dynamic sharing of spectral bands. An introduction to cognitive radio, a review of existing research results, and discussion of open problems in the area is provided.