Between Dec 19, 2024 and Jan 2, 2025, datasets can be submitted to DRUM but will not be processed until after the break. Staff will not be available to answer email during this period, and will not be able to provide DOIs until after Jan 2. If you are in need of a DOI during this period, consider Dryad or OpenICPSR. Submission responses to the UDC may also be delayed during this time.

Browsing by Subject "Game Theory"

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Cooperation in Games
    (2019-05) Damer, Steven
    This dissertation explores several problems related to social behavior, which is a complex and difficult problem. In this dissertation we describe ways to solve problems for agents interacting with opponents, specifically (1) identifying cooperative strategies,(2) acting on fallible predictions, and (3) determining how much to compromise with the opponent. In a multi-agent environment an agent’s interactions with its opponent can significantly affect its performance. However, it is not always possible for the agent to fully model the behavior of the opponent and compute a best response. We present three algorithms for agents to use when interacting with an opponent too complex to be modelled. An agent which wishes to cooperate with its opponent must first identify what strategy constitutes a cooperative action. We address the problem of identifying cooperative strategies in repeated randomly generated games by modelling an agent’s intentions with a real number, its attitude, which is used to produce a modified game; the Nash equilibria of the modified game implement the strategies described by the intentions used to generate the modified game. We demonstrate how these values can be learned, and show how they can be used to achieve cooperation through reciprocation in repeated randomly generated normal form games. Next, an agent which has formed a prediction of opponent behavior which maybe incorrect needs to be able to take advantage of that prediction without adopting a strategy which is overly vulnerable to exploitation. We have developed Restricted Stackelberg Response with Safety (RSRS), an algorithm which can produce a strategy to respond to a prediction while balancing the priorities of performance against the prediction, worst-case performance, and performance against a best-responding opponent. By balancing those concerns appropriately the agent can perform well against an opponent which it cannot reliably predict. Finally we look at how an agent can manipulate an opponent to choose actions which benefit the agent. This problem is often complicated by the difficulty of analyzing the game the agent is playing. To address this issue, we begin by developing a new game, the Gift Exchange game, which is trivial to analyze; the only question is how the opponent will react. We develop a variety of strategies the agent can use when playing the game, and explore how the best strategy is affected by the agent’s discount factor and prior over opponents.
  • Thumbnail Image
    Item
    An Empirical Study of Communication-Free Coordination in Human-Robot Teams Through a Coverage Control Game
    (2020-05) Kuan, Jin Hong; Yazıcıoğlu, A. Yasin; Aksaray, Derya
    We investigate the performance in coverage control problems, where some robots are controlled by human operators and there are no explicit communications among the robots for coordination. One example of such a scenario is a team of unmanned and manned vehicles together pursuing a surveillance mission, where each vehicle operates based on local observations without communicating with others due to physical or strategic limitations. For such scenarios, there exist distributed algorithms that ensure (near-) optimal long-run average performance when followed by all robots. This paper is focused on how the team performance changes when some robots are controlled by human operators rather than following such an optimal algorithm. For the empirical analysis, we have designed a multi-player computer game, where each player (human operator) controls a single robot and the autonomous robots follow a noisy greedy algorithm to optimize their marginal contribution to the overall coverage. We present the results obtained on multiple maps with a team of four robots, where the number of players range from zero (all robots are autonomous) to four (each robot is controlled by a player). Our results indicate that long-run average performance degrades with the introduction of human players, but this effect is not always monotonous with respect to the number of human players. Furthermore, through post-test questionnaires we showed that performance is a good predictor of the outcome in human subjective assessments. On the other hand, the number of human players in a team was not found to have any significant effect on subjective assessment.
  • Thumbnail Image
    Item
    Essays in Applied and Computational Game Theory
    (2019-06) Canann, Taylor
    This dissertation considers computational and applied aspects of cooperative and non-cooperative game theory. The first chapter discusses a novel applied game theory approach within the field of vulnerability disclosure policy. I introduce a three-player game between software vendors, software users, and a hacker in which software vendors attempt to protect software users by releasing updates, i.e. disclosing a vulnerability, and the hacker is attempting to exploit vulnerabilities in the software package to attack the software users. The software users must determine whether the protection offered by the update outweighs the cost of installing the update. Following the model set up, I describe why low-type software users, software users that do not get much value out of the software and are thus not very damaged by an attack, prefer Non-Disclosure, and Disclosure can only be an optimal policy in cases when the cost to the hacker of searching for a zero-day vulnerability is small. Many economic problems are inherently non-linear, so in the second chapter we introduce the MGBA, the Modular Groebner Basis Approach, which is a solution technique from Algebraic Geometry that can be used to ``triangularize'' polynomial systems. The MGBA is a computational tool that overcomes the typical computational problems of intermediate coefficient swell and solving for lucky primes that can limit the ability to compute Groebner bases. The Groebner basis is an all-solution computational technique that can be applied to many fields in economics. This chapter focuses on applying the MGBA to Bertrand games with multiple equilibria and a manifold approach to solving dynamic programming problems. Advances in computational power and techniques have greatly benefited both economic theory, in allowing economists to solve more realistic models, and data analysis, such as machine learning. However, the field of cooperative game theory has fallen behind. Therefore, in the final chapter, I introduce the compression value, a computationally efficient approximation technique for the non-transferable utility (NTU) Shapley value. This algorithm gives a reasonable approximation of the NTU Shapley value if the initial guess of Pareto weights is near the actual solution.
  • Thumbnail Image
    Item
    Revenue Choice on a Serial Network
    (University of Bath, 2000) Levinson, David M
    A model to examine the choice by jurisdiction whether to finance roads with taxes or tolls is developed. The idea of decentralized, local control and multiple jurisdictions distinguishes this analysis from one where a central authority maximizes global welfare. Key factors posited to explain the choice include the length of trips using the roads, the size of the governing jurisdiction, the elasticity of demand to revenue instruments, and the transaction costs of collection - which dictate the size and scope of the free rider problem associated with financing. Spatial complexity in this problem results from the fact that jurisdiction residents use both local and non-local networks, and each jurisdiction's network is used by both local and non-local residents. The central thesis argues that, since jurisdictions try to do well by their residents who are both voters and travelers, the effects of a revenue instrument on local residents is a key consideration in the choice of that revenue instrument. Decentralization of control and lower toll collection costs are identified as conditions under which tolls would more likely become the preferred revenue instrument for highways.
  • Thumbnail Image
    Item
    Robust Predictions in Dynamic Games
    (2018-08) Ruiz Gómez, David
    This dissertation is about understanding the robustness property of predictions to misspecification of higher-order beliefs in dynamic games with payoff uncertainty. In particular, it asks: Which simplifying assumptions about beliefs provide robust predictions in dynamic games? The most important result of this dissertation, presented in the second chapter, is to show that lack of robustness is a generic property of predictions consistent with (interim) sequential rationalizability (ISR) unless the prediction is unique. I consider this to be an essential and novel contribution to the literature of robustness in game theory since it challenges the validity of the standard approach to modeling uncertainty in dynamic games because it gives rise, for almost every model of uncertainty, to spurious predictions. Typically, when analyzing a model, different parameters represent different assumptions of the model, and therefore, predictions from the model are sensitive to the specification of those parameters. For example, it is well known that in the standard Bayesian approach to games with incomplete information, a crucial parameter that requires to be specified, and at the same time is neither observable nor verifiable without any error from the point of view of researchers, is players beliefs and hierarchies of beliefs; hence, because of the previous observation, it happens that in many applications hierarchies of beliefs encode strong (informational) assumptions, and as I already mentioned, behavioral predictions (e.g., in the form of Perfect Bayesian Equilibrium, Interim Sequential Rationalizability, among others) depend on those assumptions; moreover, in some cases, this dependence can be very sensitive at the tails of the hierarchies of beliefs specified in the model. The robustness property refers, in this case, to the possibility of guarantee that slight changes in the specification of the parameters do not lead to significant changes in predictions, since at least from a methodological point of view, if the property holds generically it would provide a justification for the validity of the standard approach to model uncertainty. One approach to understanding the robustness property of set-valued solution concepts in games is to ask: Which predictions remain valid after all common certain-belief assumptions are relaxed? Penta (2012) have shown that in (finite) dynamic games with incomplete information the only predictions that remain valid after relaxing all the assumptions about beliefs and hierarchies of beliefs are those consistent with (interim) sequential rationalizability. In other words, ISR is the strongest solution concept such that, for every model of beliefs it is possible to guarantee that an outcome that was ruled out by ISR is ruled out for every approximation of the model. This result implies lack of robustness of any refinement of ISR as, for example, any of the familiar equilibrium concepts. In this dissertation, a stronger notion of robustness is considered, that is if, in addition, it is possible to guarantee that there are no spurious predictions, in the sense that for every predicted outcome of a solution concept there is no approximation ruling that outcome out. This last notion is formalized through a notion of full continuity of predictions with respect to beliefs and hierarchies of beliefs. An approach to this question for static games was given in Ely and Peski (2011). They introduced the concept of critical types as precisely those assumptions on beliefs that are vulnerable to misspecification, that is, as those types to which there are spurious predictions consistent with rationalizability. They showed that critical types are non-generic (rare). The key argument in Ely and Peski's result exploits the fact that, in static games, rationalizability does not depend on the timing of the arrival of players' information. However, in dynamic games, ISR does depend on the timing of information. In particular, players beliefs are restricted only at the beginning of the game, and via conditioning whenever possible. However, at zero probability events, conditional beliefs are unrestricted. I exploit this observation to show that Ely and Peski's result does not hold in dynamic settings: lack of robustness is a generic property of ISR whenever it delivers multiple predictions. As ISR often delivers multiple predictions in applications, this result casts doubts on the interpretation and validity of solution concepts such as Perfect Bayesian Equilibrium, Sequential Equilibrium, and ISR itself. By acknowledging model misspecification of higher-order beliefs, there is no type in Harsanyi's framework at which a researcher can guarantee that no slight perturbation on the modeling assumptions exists which rules some prediction out unless the prediction is unique. Finally, I propose an ongoing research agenda in the problem of robust predictions in dynamic games. In particular, we consider dynamic games with payoff uncertainty and, as in Siniscalchi (2016a,b), assume that players in the game choose strategies according to structural rationality. Players with structural preferences induce, at the beginning of the game, a collection of alternative hypothesis about how the game is going to unfold; and rank any two strategies depending on the expected payoff under those alternative priors in a lexicographic way. A strategy is structurally rational if it is maximal. We propose to study general properties of (weak) interim structural rationalizability (IStR), a solution concept that characterizes the behavioral implications of common certainty in structural rationality. In the case of Bayesian dynamic games with incomplete information, we are particularly interested in the robustness properties of IStR to perturbations of higher-order beliefs. As illustrated by an example, three results are conjecture: a structure theorem of structural rationalizability, a characterization of critical types, and a non-generic result of the set of critical types.
  • Thumbnail Image
    Item
    Two-sided uncertainty in persuasion games.
    (2009-05) Pillai, Evsen Turkay
    I study a communication game between a listener and a speaker in which the speaker sends costless but verifiable messages in order to persuade the listener to take an action that is favorable for the speaker. Because of its practical relevance for many economic, legal, and political matters, this problem has been well studied in economics literature, usually under the assumption that the speaker knows the preferences of the listener. This assumption is restrictive, as in many persuasion problems the speaker might not know the preferences of the listener, possibly because either the listener is not able to communicate her preferences or wants to deliberately keep the speaker uncertain about her preferences. I explore two possible tools that can be used for information extraction in such a game. The first tool is the uncertainty about the listener's preferences (type) that may be maintained or removed. Another tool is to change the ``scale of actions"-for example, increasing or decreasing legal punishment. First, in a persuasion game in which the listener has two possible types and two actions to choose from, I show that when one of the listener's types is more likely, the equilibrium speaker strategies are a subset of those that arise when the speaker knows the listener's type. Further, I show that among the equilibria that deliver the highest expected utility to the more likely type when there is certainty, there is always one that remains in the set of equilibria under uncertainty. These results imply that maintaining uncertainty can be a useful tool only for the less likely type. To analyze the effect of the second tool, I study a legal application of persuasion games with two-sided uncertainty. A defendant (speaker) is trying to persuade a judge by presenting evidence to take a favorable legal action rather than less favorable ones on his case. I show that the equilibrium disclosure of the defendant is not affected by a change in the scale of legal actions when there is no uncertainty on how the judge evaluates evidence. With uncertainty, however, the defendant can be induced to disclose more information by decreasing the severity of the most unfavorable legal action relative to the favorable one.