Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception

Longxu Pan Yue Guan Daigo Shishika Panagiotis Tsiotras · 2026

Read Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception by Longxu Pan Yue Guan Daigo Shishika Panagiotis Tsiotras (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25070.txt.

Introduction

Pan, Guan, Shishika and Tsiotras study deception in defence of resources. A defender splits resources between a true asset and decoys, hoping to draw an attacker away from the real prize. They solve for the Perfect Bayesian Nash Equilibrium and show the linked belief-and-policy problem has a direct linear programming form, with no iteration. In tests, the policies balance real defence with belief-shaping, deceiving only when it helps.

Catalog record

CREATORLongxu Pan Yue Guan Daigo Shishika Panagiotis Tsiotras
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52492
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymmetric-Information Resource Allocation Games: An LP Approach to Purposeful Deception Longxu Pan Yue Guan Daigo Shishika Panagiotis Tsiotras Abstract In this work, we introduce the Deceptive Resource Allocation Game (DRAG), which studies purposeful deception within a Bayesian game framework. In DRAG, a Defender allocates resources across the true asset and several decoys to influence an Attacker’s beliefs and actions, with the goal of diverting the Attacker away from the true asset. We seek to characterize purposeful deception , whereby the Defender deceives only when doing so improves its performance. To this end, we solve for the Perfect Bayesian Nash Equilibrium (PBNE) of the corresponding game. We show that, despite the coupled belief–policy interdependence, the problem admits an efficient, non-iterative linear programming formulation. Numerical results demonstrate that the resulting policies naturally balance effective allocation and belief manipulation, giving rise to purposeful and emergent deceptive behaviors. I Introduction Deception plays a fundamental role in domains such as military operations [ 8 ] , security [ 1 ] , and autonomous systems operating under adversarial influence [ 11 ] . A common framework for studying deception is through asymmetric-information games, where agents possess unequal knowledge about the underlying environment. In such settings, an agent with informational advantage may strategically manipulate observable signals, such as trajectories or action histories, to influence other agents’ beliefs and, consequently, influence their decisions [ 16 ] . A well-studied line of work includes goal recognition and deceptive path planning (DPP). Goal recognition [ 18 , 14 , 15 ] focuses on inferring a mobile agent’s intent by observing its trajectory, while DPP [ 2 , 10 , 12 , 4 ] studies how a mobile agent can reach its goal while reducing the accuracy of an adversarial observer’s inference of its intent. However, much of this literature optimizes surrogate metrics of deception (e.g., ambiguity or bias) rather than task performance, often resulting in “deception for the sake of deception.” Recent DPP works [ 17 , 16 ] address the previous limitation by adopting a Bayesian game formulation. In these settings, an Attacker is assigned a private goal from a set of candidates, while the Defender seeks to identify the true goal and allocate resources accordingly. The Attacker’s trajectory serves as the observable signal that shapes the Defender’s belief, requiring the Attacker to balance path optimality with deception to limit defensive allocation to the true goal. In particular, [ 16 ] proposes an efficient sequential rationalization method for computing Perfect Bayesian Nash Equilibria, enabling a principled notion of purposeful deception. However, this approach is limited to just two candidate goals, and–critically–relies on a key structural assumption: the informed agent has full control over the observable signal. In this paper, we study the Deceptive Resource Allocation Game (DRAG), a natural dual of the DPP formulation, in which a Defender allocates limited resources across a true asset and decoy sites to mislead the Attacker. An illustrative example is shown in Fig. 1 . Fig. 1 : The Deceptive Resource Allocation Game. Left: Attacker’s perspective. Right: Defender’s perspective. Similar in spirit to DPP, the Defender in DRAG must balance two competing objectives: allocating resources to the true asset to maximize performance, and allocating to decoys to manipulate the opponent’s belief. This trade-off gives rise to purposeful deception, where deception is employed only when it improves the Defender’s performance. Crucially, the mechanism is not merely to induce uncertainty, but to shape beliefs in order to influence the opponent’s decisions at critical states. One key structural difference between DRAG and DPP is that the informed player in DRAG (the Defender) does not fully control the game history. Instead, the Defender influences the Attacker’s belief through its allocation actions, while the Attacker governs the evolution of the game state and, in turn, influences the Defender’s allocations. As a result, the observable signal arises from the interaction of both agents, creating a coupling between belief formation and strategic behavior that is absent in prior DPP formulations. To formalize this interaction between beliefs and Defender actions, we adopt a Bayesian game framework and solve for Perfect Bayesian Nash Equilibria (PBNE), in which agents optimize performance while accounting for belief updates. Prior work has studied asymmetric-information games and proposed linear programming formulations for computing PBNE when only the informed player controls the game state [ 6 , 3 ] . Despite the coupled belief–policy interdependence in our setting, we show that the DRAG problem still admits an efficient linear programming formulation on the game tree. Contributions: The main contributions of this work are threefold. First, we introduce the DRAG problem, a novel formulation that is dual to the goal recognition and deceptive path planning problems. Second, we identify a key structural insight: the informed player (the Defender) can influence the uninformed player (the Attacker) by shaping the distribution of observable allocation histories, thereby steering the Attacker ’s belief updates. Third, despite the coupled belief–policy interdependence, we show that the DRAG problem admits an efficient linear programming formulation on the game tree, enabling the computation of PBNE. Our linear programming approach is general and applies to arbitrary graphs with multiple candidate goals, significantly extending prior DPP work [ 16 ] , which is limited to two-goal settings. Numerical results demonstrate that the resulting PBNE policies naturally balance deception and performance, giving rise to purposeful deceptive behaviors. I-A Notations Bold letters denote vectors, and \Delta(E) denotes the set of probability distributions over a finite set E . We write [f(\theta)]_{\theta} for the |\Theta| -dimensional vector whose entries are given by f\!\left({\theta}\right) for each \theta\!\in\!\Theta . We use \left[{0:T}\right] to denote the index set \{0,1,\ldots,T\} . II Problem Formulation The Deceptive Resource Allocation Game (DRAG) is a discrete-time dynamic game between a Defender and an Attacker over a graph \mathcal{G}=(\mathcal{S},\mathcal{E}) , where \mathcal{S} and \mathcal{E} are the node set and the edge set, respectively. Let \Theta\subseteq\mathcal{S} denote a set of candidate asset nodes. At the start of the game, Nature selects an asset \theta_{\mathrm{true}}\in\Theta according to the prior \mathbf{b}_{0} and privately reveals it to the Defender, who aims to protect it, without disclosing it to the Attacker. The Defender is said to be of type \theta if the candidate asset \theta is selected by Nature. At each time step, the Attacker moves on the graph \mathcal{G} , while the Defender allocates defensive resources to one of the candidate assets in \Theta . The Defender aims to maximize the total resources accumulated at the true asset, while the Attacker seeks to minimize it by inferring the true asset from Defender’s allocation actions. By allocating resources to decoy assets, the Defender can strategically mislead the Attacker’s inference of \theta_{\mathrm{true}} , thereby delaying its progress toward the true asset and gaining additional time to reinforce it. Conversely, the Attacker must infer \theta_{\mathrm{true}} from the observed allocation history and reach it within a prescribed horizon T , while minimizing the resources accumulated to \theta_{\mathrm{true}} . Formally, the DRAG problem is defined as \texttt{DRAG}=\langle\mathcal{S},\mathcal{E},\Theta,r,m,s_{0},\mathbf{b}_{0},T\rangle, whose components are described in detail below. State and action spaces The game state is given by the Attacker position s_{t}\in\mathcal{S} . At each time step, the Attacker selects an edge u_{t}=(s_{t},s_{t+1})\in\mathcal{E} and attempts to move to the next node s_{t+1} .

Read the complete text