Events Calendar

PhD Thesis Proposal - Omkar Thakoor

Title: Adversarial Knapsack for Sequential Competitive Resource Allocation
 
Date and Time: Friday, April 25th - 2:00pm
 
Location: EEB 219
 
Committee Members: Victor Prasanna (Chair), Jyotirmoy Deshmukh, Paul Bogdan, Vatsal sharan, Rajgopal Kannan
 
Abstract: 
Game Theory has become a key theoretical tool for analyzing important decision-making processes in various fields. One such common scenario has two or more agents strategically allocating respective resources to gain control of shared items. A prime example of this is in the defense sector where warfare resources are allocated to gain control of conflict territories. Colonel Blotto game is a long-studied model for this problem that considers simultaneous interactions between the players. Our work focuses on 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. Another recent and successful model of Stackelberg Security Games (SSG) consider sequential interactions but with largely dissimilar actions for agents – rather than the agents contesting for items with resource allocation, they consider a defender protecting targets versus an attacker selecting ones to attack. In this project, we investigate the scenario where both the agents have the same goal of optimizing resource allocation, but in a sequential setting, thus distinguishing from both the aforementioned lines of works. While we use the defense resource allocation as an exemplary application, our analysis and results will be general and applicable to other domains.
 
Our current contributions include formalizing an adversarial knapsack game model that captures the scenario as described above. We have laid foundation with a base setting of the model that gives rise to a bilevel knapsack problem: How should a leader assign weights to given items with known values, so as to minimize the output of a follower trying to maximize the value of her knapsack subject to limited capacity? We study this problem in various settings such as the follower’s optimization being a 0-1 versus a fractional knapsack problem, and with the leader’s weight variables being real (continuous) versus integers (discrete). This knapsack-based approach is novel in the context of competitive resource allocation, with rare instances in 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.
 
Our focus in future is to explore other utility functions of the resource allocation that the knapsack-solving follower makes, such as non-linear concave utility functions. Secondly, the synchronicity of decision-making among the game players is closely tied with the information sharing and availability that applies to the gameplay. The existing models often assume perfect and complete information that is not practical in most cases. The imperfect and incomplete information settings allow for manifestation of two different techniques: Deception and Persuasion. Deception in our context could see the leader using certain tools to deflate or inflate his perceived resource allocation from the follower’s perspective, thereby misleading the follower into playing suboptimally. Persuasion focuses on how the leader can influence follower's decisions via strategic information revelation — often described as a signaling scheme — to yield the most desirable equilibrium outcome. These techniques are best realized in a multi-step or repeated game setting, which we also aim to investigate for our future analysis.
 

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 219

Audiences: Everyone Is Invited

Contact: Omkar Thakoor

This event is open to all eligible individuals. USC Viterbi operates all of its activities consistent with the University's Notice of Non-Discrimination. Eligibility is not determined based on race, sex, ethnicity, sexual orientation, or any other prohibited factor.

Add to Google Calendar