More Like this

1. Building rational cooperation on their own: Learning to start small

   https://doi.org/10.1111/jpet.12322  

   Andreoni, James; Kuhn, Michael A.; Samuelson, Larry (August 2018, Journal of Public Economic Theory)

   Abstract We report experimental results for a twice‐played prisoners' dilemma in which the players can choose the allocation of the stakes across the two periods. Our point of departure is the assumption that some (but not all) people are willing to cooperate, as long as their opponent is sufficiently likely to do so. The presence of such types can be exploited to enhance cooperation by structuring the twice‐played prisoners' dilemma to “start small,” so that the second‐stage stakes are larger (but not too much larger) than the first‐stage stakes. We compare conditions where the allocation of stakes is chosen exogenously to conditions where it is chosen by the players themselves. We show that players gravitate toward the payoff‐maximizing strategy of starting small in a twice‐played prisoners' dilemma. Intriguingly, the salutary payoff effects of doing so are larger than those that arise when the same allocation is exogenously chosen. 

   more » « less
2. Translucent players: Explaining cooperative behavior in social dilemmas

   https://doi.org/10.1177/1043463119885102  

   Capraro, Valerio; Halpern, Joseph Y (November 2019, Rationality and Society)

   In the past few decades, numerous experiments have shown that humans do not always behave so as to maximize their material payoff. Cooperative behavior when noncooperation is a dominant strategy (with respect to the material payoffs) is particularly puzzling. Here we propose a novel approach to explain cooperation, assuming what Halpern and Pass call translucent players. Typically, players are assumed to be opaque, in the sense that a deviation by one player in a normal-form game does not affect the strategies used by other players. However, a player may believe that if he switches from one strategy to another, the fact that he chooses to switch may be visible to the other players. For example, if he chooses to defect in Prisoner’s Dilemma, the other player may sense his guilt. We show that by assuming translucent players, we can recover many of the regularities observed in human behavior in well-studied games such as Prisoner’s Dilemma, Traveler’s Dilemma, Bertrand Competition, and the Public Goods game. The approach can also be extended to take into account a player’s concerns that his social group (or God) may observe his actions. This extension helps explain prosocial behavior in situations in which previous models of social behavior fail to make correct predictions (e.g. conflict situations and situations where there is a trade-off between equity and efficiency). 

   more » « less
3. From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

   Behnezhad, Soheil; Blum, Avrim; Derakhshan, Mahsa; HajiAghayi, MohammadTaghi; Mahdian, Mohammad; Papadimitriou, Christos; Rivest, Ronald; Seddighin, Saeed; Stark, Philip (January 2018, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018))

   Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u, p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u, p)-maxmin strategies. 

   more » « less
4. Finding the Best Dueler

   https://doi.org/10.3390/math11071568  

   Zhang, Zhengu; Ross, Sheldon M (April 2023, Mathematics)

   Consider a set of n players. We suppose that each game involves two players, that there is some unknown player who wins each game it plays with a probability greater than 1/2, and that our objective is to determine this best player. Under the requirement that the policy employed guarantees a correct choice with a probability of at least some specified value, we look for a policy that has a relatively small expected number of games played before decision. We consider this problem both under the assumption that the best player wins each game with a probability of at least some specified value >1/2, and under a Bayesian assumption that the probability that player i wins a game against player j is its value divided by the sum of the values, where the values are the unknown values of n independent and identically distributed exponential random variables. In the former case, we propose a policy where chosen pairs play a match that ends when one of them has had a specified number of wins more than the other; in the latter case, we propose a Thompson sampling type rule. 

   more » « less
5. Multi-Player Resource-Sharing Games with Fair Reward Allocation

   M. Wijewardena; M. J. Neely (March 2024, arXiv:2402.05300v2)

   arXiv:2402.05300v2 (Ed.)

   This paper considers a multi-player resource-sharing game with a fair reward allocation model. Multiple players choose from a collection of resources. Each resource brings a random reward equally divided among the players who choose it. We consider two settings. The first setting is a one-slot game where the mean rewards of the resources are known to all the players, and the objective of player 1 is to maximize their worst-case expected utility. Certain special cases of this setting have explicit solutions. These cases provide interesting yet non-intuitive insights into the problem. The second setting is an online setting, where the game is played over a finite time horizon, where the mean rewards are unknown to the first player. Instead, the first player receives, as feedback, the rewards of the resources they chose after the action. We develop a novel Upper Confidence Bound (UCB) algorithm that minimizes the worst-case regret of the first player using the feedback received. 

   more » « less