Title: Adversarial Knapsack for Sequential Competitive Resource Allocation Show Chinese title

Title: 对抗性背包问题的顺序竞争资源分配

Abstract: This work addresses competitive resource allocation in a sequential setting, where two players allocate resources across objects or locations of shared interest. Departing from the simultaneous Colonel Blotto game, our framework introduces a sequential decision-making dynamic, where players act with partial or complete knowledge of previous moves. Unlike traditional approaches that rely on complex mixed strategies, we focus on deterministic pure strategies, streamlining computation while preserving strategic depth. Additionally, we extend the payoff structure to accommodate fractional allocations and payoffs, moving beyond the binary, all-or-nothing paradigm to allow more granular outcomes. We model this problem as an adversarial knapsack game, formulating it as a bilevel optimization problem that integrates the leader's objective with the follower's best-response. This knapsack-based approach is novel in the context of competitive resource allocation, with prior work only partially leveraging it for follower analysis. Our contributions include: (1) proposing an adversarial knapsack formulation for the sequential resource allocation problem, (2) developing efficient heuristics for fractional allocation scenarios, and (3) analyzing the 0-1 knapsack case, providing a computational hardness result alongside a heuristic solution. Show Chinese abstract

Abstract: 本文研究了顺序设置下的竞争资源配置问题，其中两个玩家在共享兴趣的对象或位置上分配资源。 不同于同时进行的上校博弈模型，我们的框架引入了一个顺序决策动态过程，玩家在部分或完全了解之前行动的情况下进行操作。 与依赖复杂混合策略的传统方法不同，我们关注确定性的纯策略，简化计算的同时保留了战略深度。 此外，我们将收益结构扩展到适应分数分配和收益的情况，超越二元的全有或全无范式，以允许更精细的结果。 我们将这个问题建模为一个对抗性背包游戏，并将其表述为一个双层优化问题，整合领导者的目标和跟随者的最优反应。 这种基于背包的方法在竞争资源配置的背景下是新颖的，先前的工作仅部分利用它来进行跟随者分析。 我们的贡献包括：（1）提出了顺序资源配置问题的对抗性背包公式，（2）开发了针对分数分配场景的有效启发式算法，以及（3）分析了0-1背包案例，提供了计算复杂性结果以及启发式解决方案。