Competitive Diffusion is a recently introduced game-theoretic model for the spread of information through social networks. The model is a game on a graph with external players trying to reach the most vertices. In this thesis, we consider the safe game of Competitive Diffusion. This is the game where one player tries to optimize his gain as before, while his opponents' objectives are to minimize the first player's gain. This leads to a safety value for the player, i.e. an optimal minimal expected gain no matter the strategies of the opponents. We discuss safe strategies and present some bounds on the safety value in the two-player version of the game on various graphs. The results are almost entirely on the safe game on trees, including the special cases of paths, spiders and complete trees but also consist of some preliminary studies of the safe game on three other simple graphs. Our main result consists of a Centroidal Safe Strategy (CSS) Algorithm which suggests a safe strategy for a player on any centroidal tree, a tree which has one vertex as centroid, and gives its associated guaranteed gain.

This thesis examines a series of problems with the goal of better understanding the fundamental dilemma of whether to invest effort in obtaining information that may lead to better opportunities in the future versus exploiting immediately available opportunities. In particular this work investigates how this dilemma is affected by competition in an evolutionary setting. To achieve this requires both the use of evolutionary game theory, and Markov decision procesess or stochastic dynamic programming. This thesis grows directly out of earlier work on the Social Learning Strategies Tournament. Although I cast the problem in the biological setting of optimal foraging theory, where it fills an obvious gap, this fundamental dilemma should also be of some interest to economists, operations researchers, as well as those working in ecology, evolution and behaviour. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2012-01-31 19:55:25.11

In a multi‐agent environment, animals must often adopt a stochastic mixed‐strategy approach to maximize reward and minimize costs; otherwise, competitive opponents can exploit predictable choice patterns. This thesis tested the hypothesis that the frontal eye field (FEF) are involved in selecting mixed‐strategy saccades. To this end, I recorded preparatory activity of single FEF neurons and manipulated the preparatory activity of neuronal ensembles within the FEF while a monkey played an oculomotor version of the mixed­‐strategy game ‘matching­‐pennies’. Each trial began with fixation on a central visual stimulus which was extinguished for a predetermined warning period before two targets were presented; one in the center and the other opposite the neuron’s response field. If both the monkey and the adaptive computer opponent chose the same target, the monkey received a liquid reward; otherwise the monkey received no reward for that trial. Like humans, monkeys chose each target in equal proportions but showed a ‘win‐stay’ bias in their choice patterns. Signal detection theory was used to analyze how accurately FEF preparatory activity predicted upcoming saccade choices. My data demonstrates that the accuracy by which FEF preparatory activity predicted upcoming strategic choices gradually increased as the time of saccade execution approached. This pattern of preparatory activity is consistent with an accumulation of evidence for each potential option towards a decision threshold. Subthreshold micro­‐stimulation biased mixed‐strategy saccadic choices, further suggesting a role for the FEF in choosing mixed­‐strategy saccades, albeit unexpectedly, in favor of saccades opposite the stimulation sites. Lastly, a particular advantage of my experiment is that the same monkey performed this task using neurophysiological experimentation in the FEF and intermediate layers of the superior colliculus (SCi). This allowed me to compare the timing and magnitude of neuronal selectivity and effects of subthreshold microstimulation across these two structures, during strategic decision‐making. My results indicate that the selection of mixed­‐strategy saccades occurred earlier and was greater in magnitude in the FEF compared to the SC, indicative of a decision process that occurs earlier in the frontal cortex before being relayed on to premotor regions in the midbrain. / Thesis (Master, Neuroscience Studies) -- Queen's University, 2012-03-28 10:57:30.638

No description available.

Recent applications of game theory to the oligopoly have characterized the nature of the competition in an industry by examining payoff matrices and the strategies chosen by the players. In this study, a game-theoretic model of an oligopoly is developed, wherein the marketing-mix decisions made by the participating firms are represented as alternate strategic options. Econometric methods are employed to estimate the payoffs in the game matrices. Issues in model operationalization are discussed; then the model is applied to two real situations. In each case, the game matrix derived is used to describe the competitive nature of the industry (by examining the strategic decisions made over time), to evaluate the strategies chosen, given the intentions of the firms, and to recommend desirable strategies for the future. / La théorie des jeux, appliquée à l’étude des oligopoles, permet de caractériser la nature de la concurrence industrielle grâce à l’examen des sommes à gagner et des stratégies suivies par les joueurs. Cette étude développe un modèle d’oligopole basé sur la théorie des jeux et dans lequel les décisions de marketing prises par les participants sont représentées par des choix stratégiques. Lps sommes à gagner sont estimées par des methodes économètriques. Le modèle est operationnel et appliqué à deux situations réelles. Dans chaque cas, on parvient à décrire la nature de la concurrence dans l’industrie; à evaluer les stratégies passées; et à recommander de meilleures stratégies pour l’avenir.

Modern organizations (e.g., hospitals, banks, social networks, search engines) hold large volumes of personal information, and rely heavily on auditing for enforcement of privacy policies. These audit mechanisms combine automated methods with human input to detect and punish violators. Since human audit resources are limited, and often not sufficient to investigate all potential violations, current state-of-the -art audit tools provide heuristics to guide human effort. However, numerous reports of privacy breaches caused by malicious insiders bring to question the effectiveness of these audit mechanisms. Our thesis is that effective audit resource allocation and punishment levels can be efficiently computed by modeling the audit process as a game between a rational auditor and a rational or worst-case auditee. We present several results in support of the thesis. In the worst-case adversary setting, we design a game model taking into account organizational cost of auditing and loss from violations. We propose the notion of low regret as a desired audit property and provide a regret minimizing audit algorithm that outputs an optimal audit resource allocation strategy. The algorithm improves upon prior regret bounds in the partial information setting. In the rational adversary setting, we enable punishments by the auditor, and model the adversary's utility as a trade-off between the benefit from violations and loss due to punishment when detected. Our Stackelberg game model generalizes an existing deployed security game model with punishment parameters. It applies to natural auditing settings with multiple auditors where each auditor is restricted to audit a subset of the potential violations. We provide novel polynomial time algorithms to approximate the non-convex optimization problem used to compute the Stackelberg equilibrium. The algorithms output optimal audit resource allocation strategy and punishment levels. We also provide a method to reduce the optimization problem size, achieving up to 5x speedup for realistic instances of the audit problem, and for the related security game instances.

No description available.

This thesis develops a framework to investigate and design novel optimization methods for two important problems: computational advertising (particularly, sponsored search) and wind farm turbine-layout planning. Whereas very different in specifics, both problems share some common abstractions. The existing solution in sponsored search is based on a greedy pay-per-click auction and is suitable only for advertisers seeking a direct response. It does not apply to advertisers who target certain numbers of clicks in a predefined time period. To address this new challenge, we introduce a unified optimization framework combining pay-per-click auctions and guaranteed delivery in sponsored search. Our new method maximizes the revenue of the search engine, targets a guaranteed number of ad clicks per campaign for advertisers willing to pay a premium, and enables keyword auctions for all others. Results combining revenue to the search engine and click rates for the advertisers show superior performance over strong baselines. The proposed framework is based on linear programming with delayed column generation for computational tractability at scale. We design a game theoretic approach to optimize the strategy for individual advertisers, i.e. to optimize their choices between auctions and guaranteed delivery, and analyze the behavior of the new market formed by our framework. Specifically, we introduce a new method for computing the approximate Nash equilibrium where an exact computation would prove computationally intractable. We rely on approximations of complex utility functions, a combination of simulated annealing and integer linear programming as our principled approach. Wind farm layout optimization is the selection of optimal locations for placement of large wind turbines taking into account factors such as topographical features, prevalent but non-constant wind direction and turbine-wake interference. Existing approaches are deficient in their inability to consider long distance turbine interference, changing wind speed and direction and multiple types of wind turbines in optimization. The dissertation develops an optimization framework based on a scalable divided-and-conquer strategy that enables scalability to real-world wind farm scales taking into account the aforementioned complexities in the optimization process. Essentially the process optimizes in a hierarchical manner at different levels of granularity. This hierarchical decomposition approach to optimization is common to both search-advertisement and wind-farm layout challenges.

This paper modifies the two-player Rubinstein bargaining game to include a third player. Analyzing the game through a dynamic model provides parametric changes that cause a longer negotiation period and fewer concessions from each player’s initial demand upon an agreement. The introduction of a free rider problem and limited computational abilities cause these consequences with the addition of a third player. The free rider problem discourages players from conceding their demands and since players have limited strategic abilities, the additional player requires more effort for players to understand the game and thus more time to understand the environment enough to reach an agreement.

The major objective of this thesis is to study optimization problems in finance. Most of the effort is directed towards studying the impact of transaction costs in those problems. In addition, we study dynamic meanvariance asset allocation problems. Stochastic HJB equations, Pontryagin Maximum Principle and perturbation analysis are the major mathematical techniques used. In Chapter 1, we introduce the background literature. Following that, we use the Pontryagin Maximum Principle to tackle the problem of dynamic mean-variance asset allocation and rediscover the doubling strategy. In Chapter 2, we present one of the major results of this thesis. In this chapter, we study a financial optimization problem based on a market model without transaction costs first. Then we study the equivalent problem based on a market model with transaction costs. We find that there is a relationship between these two solutions. Using this relationship, we can obtain the solution of one when we have the solution of another. In Chapter 3, we generalize the results of chapter 2. In Chapter 4, we use Pontryagin Maximum Principle to study the problem limit of the no-transaction region when transaction costs tend to 0. We find that the limit is the no-transaction cost solution.