Strategic suppression of grades, as well as early offers and contracts, are well-known phenomena in the matching process where graduating students apply to jobs or further education. In this paper, we consider a game theoretic model of these phenomena introduced by Ostrovsky and Schwarz, and study the loss in social welfare resulting from strategic behavior of the schools, employers, and students. We model grading of students as a game where schools suppress grades in order to improve their students placements. We also consider the quality loss due to unraveling of the matching market, the strategic behavior of students and employers in offering early contracts with the goal to improve the quality. Our goal is to evaluate if strategic grading or unraveling of the market (or a combination of the two) can cause significant welfare loss compared to the optimal assignment of students to jobs. To measure welfare of the assignment, we assume that welfare resulting from a job -- student pair is a separable and monotone function of student ability and the quality of the jobs. Assuming uniform student quality distribution, we show that the quality loss from the above strategic manipulation is bounded by at most a factor of 2, and give improved bounds for some special cases of welfare functions.
Optimum decision fusion in the presence of malicious nodes - often referred to as Byzantines - is hindered by the necessity of exactly knowing the statistical behavior of Byzantines. By focusing on a simple, yet widely studied, set-up in which a Fusion Center (FC) is asked to make a binary decision about a sequence of system states by relying on the possibly corrupted decisions provided by local nodes, we propose a game-theoretic framework which permits to exploit the superior performance provided by optimum decision fusion, while limiting the amount of a-priori knowledge required. We first derive the optimum decision strategy by assuming that the statistical behavior of the Byzantines is known. Then we relax such an assumption by casting the problem into a game-theoretic framework in which the FC tries to guess the behavior of the Byzantines, which, in turn, must fix their corruption strategy without knowing the guess made by the FC. We use numerical simulations to derive the equilibrium of the game, thus identifying the optimum behavior for both the FC and the Byzantines, and to evaluate the achievable performance at the equilibrium. We analyze several different setups, showing that in all cases the proposed solution permits to improve the accuracy of data fusion. We also show that, in some instances, it is preferable for the Byzantines to minimize the mutual information between the status of the observed system and the reports submitted to the FC, rather than always flipping the decision made by the local nodes as it is customarily assumed in previous works.
Many online companies sell advertisement space in second-price auctions with reserve. In this paper, we develop a probabilistic method to learn a profitable strategy to set the reserve price. We use historical auction data with features to fit a predictor of the best reserve price. This problem is delicate - the structure of the auction is such that a reserve price set too high is much worse than a reserve price set too low. To address this we develop objective variables, a new framework for combining probabilistic modeling with optimal decision-making. Objective variables are hallucinated observations that transform the revenue maximization task into a regularized maximum likelihood estimation problem, which we solve with an EM algorithm. This framework enables a variety of prediction mechanisms to set the reserve price. As examples, we study objective variable methods with regression, kernelized regression, and neural networks on simulated and real data. Our methods outperform previous approaches both in terms of scalability and profit.
Two intimately related new classes of games are introduced and studied: entropy games (EGs) and matrix multiplication games (MMGs). An EG is played on a finite arena by two-and-a-half players: Despot, Tribune and the non-deterministic People. Despot wants to make the set of possible Peoples behaviors as small as possible, while Tribune wants to make it as large as possible.An MMG is played by two players that alternately write matrices from some predefined finite sets. One wants to maximize the growth rate of the product, and the other to minimize it. We show that in general MMGs are undecidable in quite a strong sense.On the positive side, EGs correspond to a subclass of MMGs, and we prove that such MMGs and EGs are determined, and that the optimal strategies are simple. The complexity of solving such games is in NP&coNP.
The paper is concerned with distributed learning and optimization in large-scale settings. The well-known Fictitious Play (FP) algorithm has been shown to achieve Nash equilibrium learning in certain classes of multi-agent games. However, FP can be computationally difficult to implement when the number of players is large. Sampled FP is a variant of FP that mitigates the computational difficulties arising in FP by using a Monte-Carlo (i.e., sampling-based) approach. The Sampled FP algorithm has been studied both as a tool for distributed learning and as an optimization heuristic for large-scale problems. Despite its computational advantages, a shortcoming of Sampled FP is that the number of samples that must be drawn in each round of the algorithm grows without bound (on the order of $sqrt{t}$, where $t$ is the round of the repeated play). In this paper we propose Computationally Efficient Sampled FP (CESFP)---a variant of Sampled FP in which only one sample need be drawn each round of the algorithm (a substantial reduction from $O(sqrt{t})$ samples per round, as required in Sampled FP). CESFP operates using a stochastic-approximation type rule to estimate the expected utility from round to round. It is proven that the CESFP algorithm achieves Nash equilibrium learning in the same sense as classical FP and Sampled FP. Simulation results suggest that the convergence rate of CESFP (in terms of repeated-play iterations) is similar to that of Sampled FP.
This paper develops a general approach, rooted in statistical learning theory, to learning an approximately revenue-maximizing auction from data. We introduce $t$-level auctions to interpolate between simple auctions, such as welfare maximization with reserve prices, and optimal auctions, thereby balancing the competing demands of expressivity and simplicity. We prove that such auctions have small representation error, in the sense that for every product distribution $F$ over bidders valuations, there exists a $t$-level auction with small $t$ and expected revenue close to optimal. We show that the set of $t$-level auctions has modest pseudo-dimension (for polynomial $t$) and therefore leads to small learning error. One consequence of our results is that, in arbitrary single-parameter settings, one can learn a mechanism with expected revenue arbitrarily close to optimal from a polynomial number of samples.
We consider the problem of fitting a linear model to data held by individuals who are concerned about their privacy. Incentivizing most players to truthfully report their data to the analyst constrains our design to mechanisms that provide a privacy guarantee to the participants; we use differential privacy to model individuals privacy losses. This immediately poses a problem, as differentially private computation of a linear model necessarily produces a biased estimation, and existing approaches to design mechanisms to elicit data from privacy-sensitive individuals do not generalize well to biased estimators. We overcome this challenge through an appropriate design of the computation and payment scheme.
When securing complex infrastructures or large environments, constant surveillance of every area is not affordable. To cope with this issue, a common countermeasure is the usage of cheap but wide-ranged sensors, able to detect suspicious events that occur in large areas, supporting patrollers to improve the effectiveness of their strategies. However, such sensors are commonly affected by uncertainty. In the present paper, we focus on spatially uncertain alarm signals. That is, the alarm system is able to detect an attack but it is uncertain on the exact position where the attack is taking place. This is common when the area to be secured is wide such as in border patrolling and fair site surveillance. We propose, to the best of our knowledge, the first Patrolling Security Game model where a Defender is supported by a spatially uncertain alarm system which non-deterministically generates signals once a target is under attack. We show that finding the optimal strategy in arbitrary graphs is APX-hard even in zero-sum games and we provide two (exponential time) exact algorithms and two (polynomial time) approximation algorithms. Furthermore, we analyse what happens in environments with special topologies, showing that in linear and cycle graphs the optimal patrolling strategy can be found in polynomial time, de facto allowing our algorithms to be used in real-life scenarios, while in trees the problem is NP-hard. Finally, we show that without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non-negligible missed detection rates, which, unfortunately, affect every commercial alarm system. We evaluate our methods in simulation, assessing both quantitative and qualitative aspects.
Stackelberg security game models and associated computational tools have seen deployment in a number of high-consequence security settings, such as LAX canine patrols and Federal Air Marshal Service. These models focus on isolated systems with only one defender, despite being part of a more complex system with multiple players. Furthermore, many real systems such as transportation networks and the power grid exhibit interdependencies between targets and, consequently, between decision makers jointly charged with protecting them. To understand such multidefender strategic interactions present in security, we investigate game theoretic models of security games with multiple defenders. Unlike most prior analysis, we focus on the situations in which each defender must protect multiple targets, so that even a single defenders best response decision is, in general, highly non-trivial. We start with an analytical investigation of multidefender security games with independent targets, offering an equilibrium and price-of-anarchy analysis of three models with increasing generality. In all models, we find that defenders have the incentive to over-protect targets, at times significantly. Additionally, in the simpler models, we find that the price of anarchy is unbounded, linearly increasing both in the number of defenders and the number of targets per defender. Considering interdependencies among targets, we develop a novel mixed-integer linear programming formulation to compute a defenders best response, and make use of this formulation in approximating Nash equilibria of the game. We apply this approach towards computational strategic analysis of several models of networks representing interdependencies, including real-world power networks. Our analysis shows how network structure and the probability of failure spread determine the propensity of defenders to over- or under-invest in security.
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most kno
