- Award ID(s):
- 2144113
- PAR ID:
- 10496976
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- 2023 62nd IEEE Conference on Decision and Control (CDC)
- ISBN:
- 979-8-3503-0124-3
- Page Range / eLocation ID:
- 7240 to 7246
- Format(s):
- Medium: X
- Location:
- Singapore, Singapore
- Sponsoring Org:
- National Science Foundation
More Like this
-
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
-
Abstract SurA is thought to be the most important periplasmic chaperone for outer membrane protein (OMP) biogenesis. Its structure is composed of a core region and two peptidylprolyl isomerase domains, termed P1 and P2, connected by flexible linkers. As such these three independent folding units are able to adopt a number of distinct spatial positions with respect to each other. The conformational dynamics of these domains are thought to be functionally important yet are largely unresolved. Here we address this question of the conformational ensemble using sedimentation equilibrium, small‐angle neutron scattering, and folding titrations. This combination of orthogonal methods converges on a SurA population that is monomeric at physiological concentrations. The conformation that dominates this population has the P1 and core domains docked to one another, for example, “P1‐closed” and the P2 domain extended in solution. We discovered that the distribution of domain orientations is defined by modest and favorable interactions between the core domain and either the P1 or the P2 domains. These two peptidylprolyl domains compete with each other for core‐binding but are thermodynamically uncoupled. This arrangement implies two novel insights. Firstly, an open conformation must exist to facilitate P1 and P2 exchange on the core, indicating that the open client‐binding conformation is populated at low levels even in the absence of client unfolded OMPs. Secondly, competition between P1 and P2 binding paradoxically occludes the client binding site on the core, which may serve to preserve the reservoir of binding‐competent apo‐SurA in the periplasm.
-
Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [Formula: see text] principles over [Formula: see text]-models of [Formula: see text]. They also introduced a version of this game that similarly captures provability over [Formula: see text]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [Formula: see text] between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [Formula: see text] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [Formula: see text], uncovering new differences between their logical strengths.more » « less
-
Devising models that reliably recognize player goals is a key challenge in creating player-adaptive games. Player goal recognition is the task of automatically recognizing the intent of a player from a sequence of observed player actions in a game environment. In open-world digital games, players often undertake suboptimal and varied sequences of actions to achieve goals, and the high degree of freedom afforded to players makes it challenging to identify sequential patterns that lead toward specific goals. To address these issues, we present a player goal recognition framework that utilizes a fine-tuned T5 language model, which incorporates our novel attention mechanism called Temporal Contrary Attention (TCA). The T5 language model enables the framework to exploit correlations between observations through non-sequential self-attention within input sequences, while TCA enables the framework to learn to eliminate goal hypotheses by considering counterevidence within a temporal window. We evaluate our approach using game trace data collected from 144 players' interactions with an open-world educational game. Specifically, we investigate the predictive capacity of our approach to recognize player goals as well as player plans represented as abstract actions. Results show that our approach outperforms non-linguistic machine learning approaches as well as T5 without TCA. We discuss the implications of these findings for the design and development of player goal recognition models to create player-adaptive games.
-
Guruswami, Venkatesan (Ed.)Traditional fraud detection is often based on finding statistical anomalies in data sets and transaction histories. A sophisticated fraudster, aware of the exact kinds of tests being deployed, might be difficult or impossible to catch. We are interested in paradigms for fraud detection that are provably robust against any adversary, no matter how sophisticated. In other words, the detection strategy should rely on signals in the data that are inherent in the goals the adversary is trying to achieve. Specifically, we consider a fraud detection game centered on a random walk on a graph. We assume this random walk is implemented by having a player at each vertex, who can be honest or not. In particular, when the random walk reaches a vertex owned by an honest player, it proceeds to a uniformly random neighbor at the next timestep. However, when the random walk reaches a dishonest player, it instead proceeds to an arbitrary neighbor chosen by an omniscient Adversary. The game is played between the Adversary and a Referee who sees the trajectory of the random walk. At any point during the random walk, if the Referee determines that a {specific} vertex is controlled by a dishonest player, the Referee accuses that player, and therefore wins the game. The Referee is allowed to make the occasional incorrect accusation, but must follow a policy that makes such mistakes with small probability of error. The goal of the adversary is to make the cover time large, ideally infinite, i.e., the walk should never reach at least one vertex. We consider the following basic question: how much can the omniscient Adversary delay the cover time without getting caught? Our main result is a tight upper bound on this delay factor. We also discuss possible applications of our results to settings such as Rotor Walks, Leader Election, and Sybil Defense.more » « less