This paper presents a game theoretical framework for data classification, based on the interplay of pairwise influences in multivariate choices. This consists of a voting game wherein individuals, connected through a weighted network, select features from a finite list. A voting rule captures the positive or negative influence of an individual's neighbours, categorized as attractive (friend-like relationships) or repulsive (enemy-like relationships). Payoffs are assigned based on the total number of matching choices from an individual's neighbours. We show that our approach constitutes a natural generalization of the K-nearest neighbours’ method, establishing the proposed game as a theoretical framework for data classification. Computationally, we construct a mixed-integer linear programming formulation to approach the Nash equilibria of the game, facilitating their applicability to real-world data. Our results provide conditions for the existence of Nash equilibria and for the NP-completeness of its characterization. On the empirical side, we use the proposed approach to impute missing data and highlight its competitive advantage over the K-nearest neighbour’s approach.

We propose an extension of zero-sum games in which the row player may first select rows and remove columns from the associated matrix, subject to a budget constraint. Hence, the row player seeks to determine an optimal set of row selections and column removals to purchase and a corresponding (mixed) strategy for the game. We call this the matrix game designer problem (MGD) and show it can be formulated as a mixed-integer linear program (MILP). Our work is motivated by applications of MGD in the security domain and is similar to existing Bayesian Stackelberg game approaches to security scheduling. We differ from previous works in security games in that, whereas previous works focus solely on scheduling existing resources, we instead model the problem of determining which resources to invest into as well as how to employ them. We provide analytical results concerning our formulation, inequalities that strengthen our MILP formulation, and two heuristic approaches for obtaining solutions quickly. Our computational experiments then show that heuristic approaches on average obtain suboptimal solutions with at least a 20\% relative gap with those obtained by our MILP formulation.

Fraudulent or illegal activities are ubiquitous across many 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 is detrimental, as it may compromise safety or impose disproportionate negative externalities on particular population groups.
To mitigate the potential harms of users engaging in fraudulent activities, we study the problem of policing such 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 fraudulent or illegal activities at those locations. For this security game, we study both welfare and revenue maximization administrator objectives. In both settings, we show that the problem of computing the optimal administrator strategy is NP-hard and develop natural greedy algorithm variants for the respective settings that achieve at least half the welfare or revenue as the welfare-maximizing or revenue-maximizing solutions, respectively. We also establish a resource augmentation guarantee that our proposed greedy algorithms with just one additional resource, i.e., $R+1$ resources, achieve at least the same welfare (revenue) as the revenue-maximizing (welfare-maximizing) outcome with $R$ resources that is NP-hard to compute.
Finally, since the revenue and welfare maximizing outcomes can differ significantly and, in particular, a revenue-maximization administrator objective can substantially hamper welfare, we extend our security game framework to incorporate contracts. In this contract game, a welfare-maximizing principal offers contracts to a revenue-maximizing administrator to compensate it for the welfare it contributes to the system. For this contract game, we show that our developed algorithmic approaches and theoretical guarantees for the earlier studied welfare and revenue maximization administrator objectives naturally carry forward in studying optimal administrator strategies. Moreover, we introduce a dense-sampling approach to compute a near-optimal solution to the principal's problem of selecting an optimal contract to maximize its payoff. Finally, we present numerical experiments that highlight the effectiveness of contracts in bridging the gap between welfare and revenue-maximizing outcomes.

We consider strategic retail pricing in markets, where retail companies buy commodities at fluctuating wholesale prices and resell them to final consumers by applying dynamic retail tariffs. This is of especially large relevance in the context of energy markets, where substantial wholesale price fluctuations are observed. Policy makers currently foster the introduction of such dynamic tariff schemes. From a modelling point of view, we propose a multi-leader-follower problem to investigate the implications of strategic retail pricing and we compare the impacts of implementing dynamic tariffs on retailers and final consumers. Our analysis tackles different aspects: first, we formulate the model and provide theoretical results. Second, we develop algorithms, which solve the multi-leader-follower problem and allow us to characterize the resulting market equilibria. Third, we calibrate and solve our framework based on data of the German retail electricity market for the years 2020 and 2021. This allows us to quantitatively assess the impact of introducing real time prices on retailers’ profits and customers’ benefits. As our results show, dynamic real-time pricing on the one hand typically increases market efficiency, which confirms previous results obtained without the explicit consideration of strategic behavior. On the other hand, however, as a novel aspect, dynamic real-time pricing turns out to significantly reduce equilibrium profits in case of strategic firms. This effect is especially large in environments with strongly fluctuating wholesale prices.