When Simple is Near Optimal in Security Games

Devansh Jalota, Michael Ostrovsky and Marco Pavone

Papers from arXiv.org

Abstract: Fraud is ubiquitous across applications and involve users bypassing the rule of law, often with the strategic aim of obtaining some benefit that would otherwise be unattainable within the bounds of lawful conduct. However, user fraud can be detrimental. To mitigate the harms of user fraud, we study the problem of policing fraud as a security game between an administrator and users. In this game, an administrator deploys $R$ security resources (e.g., police officers) across $L$ locations and levies fines against users engaging in fraud at those locations. For this security game, we study both payoff and revenue maximization administrator objectives. In both settings, we show that computing the optimal administrator strategy is NP-hard and develop natural greedy algorithm variants for the respective settings that achieve at least half the payoff or revenue as the payoff-maximizing or revenue-maximizing solutions, respectively. We also establish a resource augmentation guarantee that our proposed greedy algorithms with one extra resource, i.e., $R+1$ resources, achieve at least the same payoff (revenue) as the payoff-maximizing (revenue-maximizing) outcome with $R$ resources. Moreover, in the setting when user types are homogeneous, we develop a near-linear time algorithm for the revenue maximization problem and a polynomial time approximation scheme for the payoff maximization problem. Next, we present numerical experiments based on a case study of parking enforcement at Stanford University's campus, highlighting the efficacy of our algorithms in increasing parking permit earnings at the university by over \$300,000 annually. Finally, we study several model extensions, including incorporating contracts to bridge the gap between the payoff and revenue-maximizing outcomes and generalizing our model to incorporate additional constraints beyond a resource budget constraint.

Date: 2024-02, Revised 2024-08
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2402.11209 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2402.11209

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().