.png){kind=icon}
.png){kind=icon}
Return
Adversarial Knapsack for Sequential Competitive Resource Allocation
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-08064-6_13.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 can 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 leaders objective with the followers 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 01 knapsack case, providing a computational hardness result alongside a heuristic solution.
Keywords:
COLONEL-BLOTTO
GAMES
Journal
G
IF:
0
Papers:
16
Citations:
0