Search for: All records

In this paper, we study the class of games known as hidden-role games in which players are assigned privately to teams and are faced with the challenge of recognizing and cooperating with teammates. This model includes both popular recreational games such as the Mafia/Werewolf family and The Resistance (Avalon) and many real-world settings, such as distributed systems where nodes need to work together to accomplish a goal in the face of possible corruptions. There has been little to no formal mathematical grounding of such settings in the literature, and it was previously not even clear what the right solution concepts (notions of equilibria) should be. A suitable notion of equilibrium should take into account the communication channels available to the players (e.g., can they communicate? Can they communicate in private?). Defining such suitable notions turns out to be a nontrivial task with several surprising conse- quences. In this paper, we provide the first rigorous definition of equilibrium for hidden-role games, which overcomes serious limitations of other solution concepts not designed for hidden-role games. We then show that in certain cases, including the above recreational games, optimal equilibria can be computed efficiently. In most other cases, we show that computing an optimal equilibrium is at least NP-hard or coNP-hard. Lastly, we experimentally validate our approach by computing exact equilibria for complete 5- and 6-player Avalon instances whose size in terms of number of information sets is larger than 1056. 

A mediator observes no-regret learners playing an extensive-form game repeatedly across T rounds. The mediator attempts to steer players toward some desirable predetermined equilibrium by giving (nonnegative) payments to players. We call this the steering problem. The steering problem captures problems several problems of interest, among them equilibrium selection and information design (persuasion). If the mediator’s budget is unbounded, steering is trivial because the mediator can simply pay the players to play desirable actions. We study two bounds on the mediator’s payments: a total budget and a per-round budget. If the mediator’s total budget does not grow with T, we show that steering is impossible. However, we show that it is enough for the total budget to grow sublinearly with T, that is, for the average payment to vanish. When players’ full strategies are observed at each round, we show that constant per-round budgets permit steering. In the more challenging setting where only trajectories through the game tree are observable, we show that steering is impossible with constant per-round budgets in general extensive-form games, but possible in normal-form games or if the per-round budget may itself depend on T. We also show how our results can be generalized to the case when the equilibrium is being computed online while steering is happening. We supplement our theoretical positive results with experiments highlighting the efficacy of steering in large games. 

We introduce a new approach for computing optimal equilibria and mechanisms via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensiveform zero-sum game. This reformulation allows us to apply techniques for learning in zero-sum games, yielding the first learning dynamics that converge to optimal equilibria, not only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning. 

Smallholder agriculture is critical for current and future food security, yet quantifying the sources of smallholder yield variance remains a major challenge. Attributing yield variance to farmer management, as opposed to soil and weather constraints, is an important step to understanding the impact of farmer decision-making, in a context where smallholder farmers use a wide range of management practices and may have limited access to fertilizer. This study used a process-based crop model to simulate smallholder maize (Zea mays) yield at the district-level in Zambia and quantify the percent of yield variance (effect size) attributed to soil, weather, and three management inputs (cultivar, fertilizer, planting date). Effect sizes were calculated via an ANOVA variance decomposition. Further, to better understand the treatment effects of management practices, effect sizes were calculated both for all years combined and for individual years. We found that farmer management decisions explained 27–82 % of total yield variance for different agro-ecological regions in Zambia, primarily due to fertilizer impact. Fertilizer explained 45 % of yield variance for the average district, although its effect was much larger in northern districts of Zambia that typically have higher precipitation, where it explained 72 % of yield variance on average. When fixing a specific fertilizer amount, the “low-cost” management options of varying planting dates and cultivars explained 20–28 % of yield variance, with some regional variation. To better understand why management practices impact yield more in particular years, we performed a correlation analysis comparing yearly management effect sizes with four meteorologically based variables: total growing season precipitation, rainy season onset, extreme heat degree days, and longest dry spell. Results showed that fertilizer’s impact generally increased under favorable weather conditions, and planting date’s impact increased under adverse weather conditions. This study demonstrates how a national yield variance decomposition can be used to understand where specific management interventions would have a greater impact and can provide policymakers with quantification of soil, weather, and management effects. In addition, the variance composition can easily be adapted to a different range of management inputs, such as other cultivars or fertilizer quantities, and can also be used to assess the effect size of management adaptations under climate change. 

CONTEXT Sub-Saharan Africa (SSA) has the climatic and biophysical potential to grow the crops it needs to meet rapidly growing food demand; however, agricultural productivity remains low. While potential maize yields in Zambia are 9 t per hectare (t/ha), the average farmer produces only 1–2. OBJECTIVE We evaluate the contribution of responses to weather risk to that gap by decomposing the yield gap in maize in Zambia. While we know that improved seed and fertilizer can expand yield and profit, they may also increase the variance of yield under different weather outcomes, reducing their adoption. METHODS We use a novel approach combining crop modeling and statistical analysis of survey data to obtain the yield gap components in Zambia driven by input cost and input risk. We use a crop model to simulate district-level marginal effects of fertilizer and seed maturity choice on the mean and variance of expected yield and profit under all-weather outcomes for each district for the past 30 years. We compare input levels that maximize expected yield to those that maximize expected profit and maximize the expected mean-variance trade-off assuming risk-aversion. To determine how much farmers' input choices are made to reduce risk, we then quantify differences in the expected riskiness of inputs by district. RESULTS AND CONCLUSIONS We find approximately one-quarter of the yield gap can be explained by risk-reducing behavior, albeit with a substantial geographic variation. Given this finding, under present conditions, we expect that the average maximum yield that farmers can obtain without increasing risk is 6.75 t/ha compared to a potential profit-maximizing level of 8.84 t/ha. SIGNIFICANCE The risk-related yield gap is only expected to increase with weather extremes driven by climate change. Promoting “one-size-fits all” solutions to closing the yield gap could underestimate the effect of risk mitigation on agricultural production while increasing farmers' risk exposure. 

The existence of simple uncoupled no-regret learning dynamics that converge to correlated equilibria in normal-form games is a celebrated result in the theory of multi-agent systems. Specifically, it has been known for more than 20 years that when all players seek to minimize their internal regret in a repeated normal-form game, the empirical frequency of play converges to a normal-form correlated equilibrium. Extensive-form games generalize normal-form games by modeling both sequential and simultaneous moves, as well as imperfect information. Because of the sequential nature and presence of private information in the game, correlation in extensive-form games possesses significantly different properties than its counterpart in normal-form games, many of which are still open research directions. Extensive-form correlated equilibrium (EFCE) has been proposed as the natural extensive-form counterpart to the classical notion of correlated equilibrium in normal-form games. Compared to the latter, the constraints that define the set of EFCEs are significantly more complex, as the correlation device must keep into account the evolution of beliefs of each player as they make observations throughout the game. Due to that significant added complexity, the existence of uncoupled learning dynamics leading to an EFCE has remained a challenging open research question for a long time. In this article, we settle that question by giving the first uncoupled no-regret dynamics that converge to the set of EFCEs in n-player general-sum extensive-form games with perfect recall. We show that each iterate can be computed in time polynomial in the size of the game tree, and that, when all players play repeatedly according to our learning dynamics, the empirical frequency of play is proven to be a O(T^-0.5)-approximate EFCE with high probability after T game repetitions, and an EFCE almost surely in the limit.