Human-robot interaction is an important and broad area of study. To achieve success- ful interaction, we have to study human decision making rules. This work investigates human learning rules in games with the presence of intelligent decision makers. Par- ticularly, we analyze human behavior in a congestion game. The game models traffic in a simple scenario where multiple vehicles share two roads. Ten vehicles are con- trolled by the human player, where they decide on how to distribute their vehicles on the two roads. There are hundred simulated players each controlling one vehicle. The game is repeated for many rounds, allowing the players to adapt and formulate a strategy, and after each round, the cost of the roads and visual assistance is shown to the human player. The goal of all players is to minimize the total congestion experienced by the vehicles they control. In order to demonstrate our results, we first built a human player simulator using Fictitious play and Regret Matching algorithms. Then, we showed the passivity property of these algorithms after adjusting the passivity condition to suit discrete time formulation. Next, we conducted the experiment online to allow players to participate. A similar analysis was done on the data collected, to study the passivity of the human decision making rule. We observe different performances with different types of virtual players. However, in all cases, the human decision rule satisfied the passivity condition. This result implies that human behavior can be modeled as passive, and systems can be designed to use these results to influence human behavior and reach desirable outcomes.

Mean Field Games (MFG) are the infinite-population analogue of symmetric stochastic differential games with interacting players. By considering a limiting model with a continuum of players, the theory of MFG provides a more tractable representation and can effectively approximate a broad class of perfectly symmetric stochastic dynamic games. This thesis studies games with heterogeneous players, the heterogeneity being expressed either through a type parameter or through asymmetric interactions among players, and aims at understanding under which condition the MFG approximation remains valid for such games and, if it fails, to find a substitute model. In many real-life settings, players do not view themselves as exchangeable and accurate models should incorporate this heterogeneity. We first adapt the MFG paradigm to model more heterogeneous agents by introducing a type parameter in a financial problem that has gained huge interest in the recent years: the competitive Merton problem under relative performance criteria. By deriving a closed-form solution for the finitely many player investment-consumption problem, we show how the risk tolerance and competitivity of the investors influence their optimal strategy in equilibrium. Moreover, this thesis contributes to a very recent line of work bridging MFG theory and network games by studying n-player stochastic dynamic games in which interactions are governed by a graph. For games with perfectly symmetric players, the MFG approximation can be rigorously justified under suitable assumptions for two main reasons: On the one hand, the equilibria of n-player games can be shown to converge to the MFG limit. On the other hand, a solution of the continuum model may be used to construct approximate equilibria for the corresponding n-player model. This thesis extends these results in two cases: first, for games on general graph sequences in the setting of a specific yet rich linear-quadratic model and second, for general games on dense graph sequences. For linear-quadratic games, we show that the MFG is the correct limit only in the dense graph case, i.e., when the degrees diverge in a suitable sense. Even though equilibrium strategies are nonlocal, depending on the behavior of all players, we use a correlation decay estimate to prove a propagation of chaos result in both the dense and sparse regimes, with the sparse case owing to the large distances between typical vertices. We show also that the mean field game solution can be used to construct decentralized approximate equilibria on any sufficiently dense graph sequence. Finally, since graphons have been shown to be the correct limit object for converging dense graph sequences, we develop the theory of graphon-based analogues of MFG. We propose a new formulation of graphon games based on a single typical player's label-state distribution. We show how our notion of graphon equilibrium can be used to construct approximate equilibria for large finite games set on any (weighted, directed) graph which converges in cut norm. The lack of players' exchangeability necessitates a careful definition of approximate equilibrium, allowing heterogeneity among the players' approximation errors, and we show how various regularity properties of the model inputs and underlying graphon lead naturally to different strengths of approximation.

Individuals within a population can vary in the way that they acquire, store, and act on information from the environment. Researchers have commonly looked at differences in genetic architecture, physical environment, or personality as possible causes of individual variation in cognition. Though cognition is defined as a suite of mechanisms involving the processing of information, we have yet to asses information (i.e. a numerical measure of the uncertainty of an outcome) as a possible cause of individual variation in cognition. This thesis seeks to understand the causes of individual variation in cognition by using approaches that allow quantifying and/or manipulating information acquisition or its use. In Chapter 1, I look at the link between information gathering and exploratory personality by testing the correlation between activity in a novel environment and attraction to novelty in wild-caught black-capped chickadees (Poecile atricapillus). My results validate exploratory personality assessed in an open field test as a measure of information gathering. Fast exploration of a novel environment was positively correlated with novelty seeking, suggesting that exploration is an information gathering strategy. In Chapter 2, I test for experience with informative vs non-informative cues as a cause for individual differences in decision making and learning performance. Here, I manipulated the informational properties (i.e. presence and number of reliable cues) of the developmental environment of juvenile captive zebra finches (Taenopygia guttata). This rare longitudinal and experimental examination of the effect of informative versus non-informative cues during development suggests that experience with informative cues can cause increased discrimination learning accuracy and decision-making speed later in life. Finally, in Chapter 3 I looked into individual variation in information use and decision making using a game theoretic approach. Using a producer-scrounger game, groups of zebra finches were exposed to varying seed distributions. Individual strategy choice in a social-foraging game was not significantly correlated with an individual’s experience with informative cues or learning performance. Still, contrary to my predictions, fear response significantly predicted strategy choice where more fearful individuals were more likely to choose a producer strategy. By addressing information as a parameter, my results suggest that information can affect individual variation depending on context.

Over the last two decades, digitization has been drastically shifting the way businesses operate and has provided access to high volume, variety, velocity, and veracity data. Naturally, access to such granular data has opened a wider range of possibilities than previously available. We leverage such data to develop application-driven models in order to evaluate current systems and make better decisions. We explore three application areas. In Chapter 1, we develop models and algorithms to optimize portfolios in daily fantasy sports (DFS). We use opponent-level data to predict behavior of fantasy players via a Dirichlet-multinomial process, and our predictions feed into a novel portfolio construction model. The model is solved via a sequence of binary quadratic programs, motivated by its connection to outperforming stochastic benchmarks, the submodularity of the objective function, and the theory of order statistics. In addition to providing theoretical guarantees, we demonstrate the value of our framework by participating in DFS contests. In Chapter 2, we develop an axiomatic framework for attribution in online advertising, i.e., assessing the contribution of individual ads to product purchase. Leveraging a user-level dataset, we propose a Markovian model to explain user behavior as a function of the ads she is exposed to. We use our model to illustrate limitations of existing heuristics and propose an original framework for attribution, which is motivated by causality and game theory. Furthermore, we establish that our framework coincides with an adjusted ``unique-uniform'' attribution scheme. This scheme is efficiently implementable and can be interpreted as a correction to the commonly used uniform attribution scheme. We supplement our theory with numerics using a real-world large-scale dataset. In Chapter 3, we propose a decision-making algorithm for personalized sequential marketing. As in attribution, using a user-level dataset, we propose a state-based model to capture user behavior as a function of the ad interventions. In contrast with existing approaches that model only the myopic value of an intervention, we also model the long-run value. The objective of the firm is to maximize the probability of purchase and a key challenge it faces is the lack of understanding of the state-specific effects of interventions. We propose a model-free learning algorithm for decision-making in such a setting. Our algorithm inherits the simplicity of Thompson sampling for a multi-armed bandit setting and we prove its asymptotic optimality. We supplement our theory with numerics on an email marketing dataset.

Although smart mobile devices have only come into prominence recently, they have quickly become a necessity in the modern world. In 2012, more than 450 million new smartphones are expected to be purchased around the world, exceeding, for the first time, purchases of laptops and desktop PCs combined in a single year. That, in addition to the increasing processing power and low cost of these emerging mobile devices, creates an increasing demand for mobile applications that work in infrastructure-supported environments like WiFi and cellular networks as well as infrastructure-less environments like ad hoc networks. Therefore, the behavior of mobile devices in such scenarios should be a continued focus of research. Several factors contribute to the observed behavior of nodes in Mobile Ad-hoc Networks MANETs. For example, nodes may act selfishly to preserve their limited energy resources. This selfishness may be detrimental to network performance. Therefore, cooperation between peers is necessary to keep these MANETs operational. Beside the need for actively encouraging cooperation by providing incentives, passive encouragement is also needed to overcome the effect of factors that limit cooperation, including malicious behavior, environmental obstruction, and mobility. The contribution of this work is to provide a cooperation model in MANETs that is capable of surviving topology distortions caused by mobility, and is operable in practical distributed scenarios. Towards this goal, we first provide a study of the topology characteristics of MANETs based on real experiments. We study the node degree, link stability, and link symmetry of these networks, and, based on our observations, we suggest a two-state Markov model to model link state in such networks, demonstrating the superiority of this model over the widely-used disk model with mobility. We conclude from this study that both mobility and channel fluctuations have a significant influence on the network topology, which makes it important to study cooperation in scenarios where the topology is changing rapidly. Based on experimental observations of a real network, we propose a coalition game model for cooperation in MANETs that shows that stable, effective coalitions can be maintained, even in the face of a dynamic network topology. We provide an initial evaluation of the model using a centralized simulation approach. We use the notion of reachability to evaluate the proposed model, and we simulate the model under different speeds and node densities. Our simulations show that reachability can be sustained at stable levels despite the deterioration caused by mobility. In addition, we show that our cumulative coalition formation approach gives good results in terms of reachability level and computational complexity. We also show that our proposed model achieves a fair payoff distribution among participating nodes. Motivated by the promising results of our centralized simulation approach, we take a further step towards more practical evaluation. We integrate the cooperation model with an existing MANET routing protocol, OLSR, and evaluate it in this distributed environment. We modify and augment the OLSR messaging mechanism to enable the exchange of the coalition information required to keep the model operating. Beside ensuring that the reachability gain is still attained and the coalition structure is stable, we study the effect of the extra control traffic overhead incurred by the model. We compare deliverability over the network with and without the cooperation model. Although our results show that the cooperation model incurs an average overhead exceeding $100\%$ of that incurred by OLSR in high density scenarios, it shows better reliability in delivering traffic especially among selfish nodes in low and average density scenarios. Counter to what is commonly assumed in the literature, this study shows that cooperation can be be maintained in a distributed manner without causing significant traffic overhead to MANETs run by proactive routing protocols. Due to the simplicity, several extensions can be applied to enhance the performance of the proposed model and diversify its usage. We propose these extensions at the end of this dissertation. / Ph. D.

La négociation est un processus pour atteindre un accord concernant un certain sujet entre deux ou plusieurs agents. Dans la négociation basée sur la théorie des jeux, la négociation est vue comme un jeu. Un jeu est appliqué à chaque situation dans laquelle les participants interagissent pour trouver une solution. La négociation basée sur l’argumentation est faite par un échange d’arguments entre les agents négociateurs. Il y a beaucoup de travaux en négociation par la théorie des jeux qui traitent de tous les aspects de la négociation. D’autre part, les recherches en négociation par argumentation se sont principalement focalisées sur les protocoles pour réguler la négociation et les mécanismes de décisions pour générer et ordonner les offres; Cependant l’étude des aspectsstratégiques qui définissent le comportement de l’agent durant la négociation ont été largement négligés. Cela reste vrai pour la contrainte du temps.Cette thèse essaie de combler ces lacunes en travaillant en trois directions. Premièrement, un cadre pour la négociation par argumentation est proposé et qui est basé sur quelques concepts étudiés en négociation par la théorie des jeux. Ce cadre permet de classer les offres suivant les arguments qui les supportent et de négocier en utilisant une adaptation du très connu Alternating Offers Protocol proposé en théorie des jeux. Pour ce protocole une stratégie générique qui peut être utilisée avec n’importe quelle relation de préférence entre les offres et avec n’importe quelle forme de concession a été définie. Deuxièmement, cette thèse propose quelques tactiques pour la négociation par argumentation avec une contrainte de temps. Les tactiques sont basées sur l’information que l’agent possède sur son adversaire. Cette information est collectionnée durant le processus de négociation ou est obtenue en connaissant le rôle de son opposant. En dernier lieu, une évaluation expérimentale montre que les tactiques et les concessions influencent la longueur de la négociation et l’issue de la négociation, sous les hypothèses de contrainte de temps et de la connaissance de certaines informations sur l’agent adversaire. / Negotiation is the process to reach an agreement concerning matters between two or several agents. In game theoretic negotiation, the latter is seen as a game. A game is applied to every situation in which the participants interact to find a solution. Argumentation-based negotiation is done by exchanging arguments between the participating agents. There is a lot of work in game-theoretic negotiation that deals with all the aspects of negotiation. On the other hand, research in argumentation-based negotiation has focused mainly on the protocols to regulate the negotiation and reasoning mechanisms to generate and order offers; however the study of strategic issues that define the behavior of an agent during the negotiation has been largely neglected. The same holds for the time constraint.This thesis tries to fill this gap by working in three directions. Firstly, a framework for argumentation-based negotiation is proposed which is based on some concepts studied in game-theoretic negotiation. The framework permits to set in order the different offers following the supporting arguments and to negotiate by using an adaptation of the well known Alternating Offers Protocol propounded in game theory. For this protocol a generic strategy which can be used with any form of preference relationship over the set of offers and with any form of concession is given. Secondly, this thesis proposes some tactics for time constrained argumentation-based negotiation. The tactics are based on the information that an agent possesses about his opponent agent. This information is gathered during the negotiation dialogue or is obtained by knowing the role of the opponent agent. Finally, an experimental evaluation is presented that shows how tactics and concessions may influence the negotiation length and outcome, under the assumptions of time constraints and the availability of information on the opponent.

Les protéines et acides ribonucléiques sont les principaux acteurs de nombreux processus cellulaires.Comprendre leurs fonctions, structures et interactions est un challenge important.Les méthodes expérimentales fournissent des informations sur la structure et la dynamique des molécules.Cependant les méthodes expérimentales sont limitées par le nombre de molécules qu'elles peuvent observer et les moyens qu'elles requièrent.Les méthodes de prédiction permettent d'obtenir des informations structurelles de façon quasi-automatique.Pour s'assurer de leur fiabilité, elles sont testées sur des données expérimentales.Nous présentons une procédure basée sur la cinétique inverse pour trouver une transition entre deux conformations d'un ARN tout en conservant sa structure secondaire.Nous obtenons des résultats comparables à l'état de l'art, ce qui montre que notre sélection des degrés de liberté est pertinente.De plus, nous utilisons des données partielles, ce qui permet d'utiliser différents types de résultats expérimentaux.Nous abordons aussi le problème du repliement protéique par une approche de théorie des jeux.Nous représentons une protéine par un jeu où les joueurs sont les acides aminés et les stratégies, les angles dièdres.La prédiction de structure peut alors être vue comme la recherche d'un équilibre dans un jeu multi-joueur où les fonctions d'utilité correspondent à la qualité du repliement.Nous montrons que l'algorithme de non-regret, appelé Hedge, garantit l'élimination des stratégies dominées et la convergence locale vers un équilibre de Nash.Puis, en limitant notre analyse aux jeux de potentiel, nous montrons qu'une classe plus large d'algorithmes, les algorithmes de régularisation, convergent vers un équilibre de Nash presque surement. / Proteins and Ribonucleic Acids are the workhorses of many cellular processes.Understanding their functions, structures and interactions is an important challenge.Experimental methods provide actual information on structure and dynamics of molecules.However they have limitations : they cannot be applied to all molecules, and they need a lot of resources.Prediction methods are almost automatic ways of obtaining structural information.They are tested on experimental data to attest their reliability.We present, here, approaches tackling different problems.We develop a kinematics-based procedure to morph a RNA molecule between conformations while preserving its secondary structure.We obtain results comparable to state of the art methods showing that our selection of degrees of freedom is efficient.Furthermore we only use sparse information allowing for various kinds of experimental inputs.We also look at the protein structure prediction problem from a game theory angle.We represent the protein dynamics as a game, in which players are amino acids and strategies are dihedrals angles.The structure prediction can thus be seen as finding equilibrium in a multi-players game where all players have utility functions corresponding to the quality of the protein structure.We showed that a well-known no-regret algorithm, called Hedge, guarantees dominated strategies to vanish and a local convergence toward Nash equilibria.Furthermore restricting our analysis to potential games we showed that dual-averaging regularized learning algorithms converge toward a Nash equilibrium almost surely.

This thesis describes the social table game Scrabble, and its realization in the form of computer games. Gradually examines all important aspects that affect the performance of the implementation. Especially after the election of the appropriate data structures retained for the vocabulary, affecting the efficiency of generating moves, and the selection of appropriate algorithms with regard to the maximum speed. There is particular emphasis on artificial intelligence opponent and its ability to compete not only amateurs, but professional SCRABBLE players.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第19220号 / 理博第4112号 / 新制||理||1592(附属図書館) / 32219 / 京都大学大学院理学研究科生物科学専攻 / (主査)教授 山内 淳, 教授 石田 厚, 教授 田村 実 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

No description available.