Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u, p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u, p)-maxmin strategies.

In November 2008, we audited contests in Santa Cruz and Marin counties, California. The audits were risk-limiting: they had a prespecified minimum chance of requiring a full hand count if the outcomes were wrong. We developed a new technique for these audits, the trinomial bound. Batches of ballots are selected for audit using probabilities proportional to the amount of error each batch can conceal. Votes in the sample batches are counted by hand. Totals for each batch are compared to the semiofficial results. The ldquotaintrdquo in each sample batch is computed by dividing the largest relative overstatement of any margin by the largest possible relative overstatement of any margin. The observed taints are binned into three groups: less than or equal to zero, between zero and a thresholdd, and larger thand. The number of batches in the three bins have a joint trinomial distribution. An upper confidence bound for the overstatement of the margin in the election as a whole is constructed by inverting tests for trinomial category probabilities and projecting the resulting set. If that confidence bound is sufficiently small, the hypothesis that the outcome is wrong is rejected, and the audit stops. If not, there is a full hand count. We conducted the audits with a risk limit of 25%, ensuring at least a 75% chance of a full manual count if the outcomes were wrong. The trinomial confidence bound confirmed the results without a full count, even though the Santa Cruz audit found some errors. The trinomial bound gave better results than the Stringer bound, which is commonly used to analyze financial audit samples drawn with probability proportional to error bounds.

Canvass audit by sampling and testing (CAST) is a method to decide on the basis of a hand count of a random sample of batches of ballots whether to count the entire audit trail of a contest by hand. Data are collected in stages. At stages, one computesPs, an upper bound on theP-value of the hypothesis that the apparent outcome is wrong, conditional on the results of previous audit stages. IfPsis less than a thresholdalphas-strong evidence that the apparent outcome is correct-the audit stops. Otherwise, the audit advances to stages+1 . If the audit has not stopped by stages=S, there is a full hand count. The thresholds{alphas}s=1Sare chosen to guarantee that whenever the apparent outcome is wrong, the chance of a full hand count is at least1-alpha: The risk of certifying an incorrect outcome is at mostalpha. Conditioning allows deliberate selection of some batches of ballots for audit. CAST can use any sampling and testing scheme for which upper bounds on conditionalP-values can be calculated. A turn-key implementation for proportionally stratified random samples is given, using the maximum relative overstatement of pairwise margins as the test statistic. This implementation works with contests that cross jurisdictional boundaries and contests that allow voters to select more than one candidate.

Postelection audits of a random sample of batches of ballots against a trustworthy audit trail can limit the risk of certifying an incorrect electoral outcome to alpha, guaranteeing that - if the apparent outcome is wrong - the chance of a full hand count of the audit trail is at least 1-alpha. Risk-limiting audits can be built as sequential tests that audit more batches until either 1) there is strong evidence that the outcome is correct, given the errors found, or 2) there has been a complete hand count. TheP-value of the hypothesis that the outcome is wrong is the largest chance, for all scenarios in which the outcome is wrong, that overstatements of the margins between winners and losers would be ldquono largerrdquo than they were observed to be. Different definitions of ldquolargerrdquo give differentP-values. A smallP-value is strong evidence that the outcome is correct. This paper gives simple approaches to calculating a conservativeP-value for several ways of summarizing overstatements and several ways of drawing the sample of batches to audit, emphasizing sampling with probability proportional to a boundupon the error in thepth audit batch (PPEB sampling). AP-value based on Markov's inequality applied to a martingale constructed from the data seems the most efficient among the methods discussed; there are plans to use it to audit contests in two California counties in November 2009.

If the measure of the support of a function f is small, its symmetric decreasing rearrangement f* is more nearly bandlimited to low frequencies than f, while their norms are equal. An immediate corollary is that the time-limited zero-order prolate spheroidal wavefunction is the extremal function for a new optimization problem involving time- and bandlimiting. The result has an application in exploration seismology.>