Optimal auditing

Optimal auditing is the study, in economics and game theory, of how a principal should verify reports made by strategic agents when verification is costly. Agents privately observe some piece of information — an income, a loss, a claim, a value — and report it to a principal who cannot observe it directly, but can inspect a report at a cost. Because agents anticipate the auditing policy when choosing what to report, the design of that policy is a problem of mechanism design rather than of statistics: the value of an audit lies mainly in the misreporting it deters, not in the misreporting it detects.

The theory is applied to tax enforcement, insurance fraud, the allocation of scarce resources within organizations, and financial contracting. It is distinct from the practice and institutions of auditing in accounting, which the theory idealizes.

The basic model

In the canonical setting, an agent privately observes a state (for instance an income or the size of a loss) and sends a report to a principal. The principal chooses a payment or allocation as a function of the report, together with an audit policy specifying the probability that a report is verified. Auditing is costly, and an agent found to have misreported may be penalized, though penalties are typically bounded. The principal seeks a mechanism that maximizes expected payoff net of auditing costs, subject to the constraint that agents report truthfully, or at least that their misreporting is anticipated correctly.

A distinction that organizes much of the literature is whether the principal can commit in advance to an audit policy. Under commitment, the principal announces the policy and is bound by it; without commitment, the principal audits only when it is worthwhile to do so given the report received, which agents anticipate. The two assumptions yield materially different mechanisms.

Costly state verification

The foundational model is due to Townsend, who studies contracting between agents when the realized state can be observed by one party only, and the other party can verify it at a cost. He shows that the optimal arrangement takes the form of a standard debt contract: as long as the promised payment is made, no verification occurs, and verification is triggered only by default. This gives a rationale for simple debt-like contracts and for the role of bankruptcy procedures as verification devices, and it establishes the general principle that verification should be concentrated on the reports that are least favorable to the principal.

Gale and Hellwig develop the one-period version of this problem and confirm the optimality of a debt contract with deterministic verification in the default region.

Border and Sobel analyze a risk-neutral principal who wishes to extract a payment from an agent whose wealth is private information but can be verified by a costly audit. Allowing the principal to choose pre-audit payments, post-audit payments and audit probabilities together, they characterize the efficient schemes, subject to the constraints that only monetary incentives are used and that the principal never makes a net payment to the agent. Efficient schemes involve pre-audit payments that increase in reported wealth and audit probabilities that decrease in it, so that low reports are the ones most likely to be checked.

Random versus deterministic audits

Whether the principal should audit deterministically or randomly is a central question. Randomization can economize on auditing costs: if an agent is audited with probability less than one but faces a sufficiently large penalty when caught, truth-telling may still be induced at lower expected cost.

Mookherjee and Png study when random audits are optimal, in a setting that covers both insurance and tax applications. They show that the deterministic verification of Townsend's model is not robust: with a risk-averse agent, the optimal scheme generally involves random auditing, and an agent who is audited and found to have reported honestly should be rewarded rather than left indifferent. Their analysis also clarifies the conditions under which debt-like contracts remain optimal.

Audit cutoffs and threshold policies

A recurring finding is that optimal policies are structured around a threshold, so that reports below some level trigger scrutiny and reports above it do not.

Reinganum and Wilde compare a random audit policy with an audit cutoff policy, under which an audit is triggered when reported income is too low and is not triggered when reported income is sufficiently high. They find that random audit rules are weakly dominated by audit cutoff rules, and that with lump-sum taxes and fines, cutoff rules are the least-cost policies inducing truthful reporting.

Estornell, Das and Vorobeychik study a setting in which agents report features used to score them for resources or scrutiny, and the agency may audit reports at a cost. When the decision is made by applying a threshold to an agent's score, they show that the optimal audit policy is to audit uniformly all agents who could benefit from lying; the scarce-resource case, in which only a limited number of agents can be served, is harder, and they give an approximately optimal policy for it. They also show that deciding whether exact truthfulness can be induced is computationally hard in general, while identifying conditions under which the problem becomes tractable.

Auditing with scoring

When the principal observes noisy signals correlated with misreporting, auditing can be targeted rather than uniform. Dionne, Giuliano and Picard connect the theory of optimal auditing to the scoring methods used in practice. Classifying fraud signals by how strongly they indicate fraud, they show that the optimal strategy is a red flags strategy, under which a claim is referred for investigation when certain indicators are present. They emphasize that the policy works as a deterrence device and therefore requires the principal to commit to it, and they show the characterization is robust to some manipulation of the signals by defrauders and to imperfect knowledge of the audit frequency.

Audit games

A distinct line of work, developed largely in computer science and artificial intelligence, models auditing explicitly as a game between an auditor and potential violators, and focuses on the computation of optimal audit strategies rather than on their analytical characterization. Whereas the mechanism-design literature above typically studies a principal who designs payments and verification jointly, this literature typically takes the payments as given and asks how a fixed and limited auditing budget should be spread across many potential violations.

Inspection games

The precursor to this line of work is the theory of inspection games, surveyed by Avenhaus, von Stengel and Zamir. An inspection game is played between an inspector, who has limited inspection resources, and an inspectee, who may act illegally and conceal the fact. The framework grew out of the analysis of arms control and disarmament in the 1960s, and covers applications such as nuclear safeguards, material accountancy and data verification. The authors present inspection as a game-theoretic extension of statistical hypothesis testing, in which the data being tested are themselves strategically manipulated by an inspectee who wishes to avoid detection, and they analyze sequential models in which limited inspection resources must be spent over time.

A concept from this literature that carries over directly to auditing is inspector leadership: by announcing and committing to an inspection strategy in advance, the inspector becomes a Stackelberg leader and can obtain a better outcome than in the simultaneous-move game, because the announcement itself deters violations. This is the game-theoretic counterpart of the observation, recurring throughout the auditing literature, that an audit policy works chiefly through deterrence and therefore depends on the auditor's ability to commit.

Deterrence and the economics of enforcement

Audit games also descend from the economic analysis of law enforcement initiated by Becker, in which a potential offender weighs the gain from a violation against the penalty discounted by the probability of being caught. A direct implication is that detection effort and punishment severity are substitutes: the same level of deterrence can be achieved by auditing rarely and punishing harshly, or by auditing often and punishing lightly. Audit-game models retain this trade-off but treat the punishment level as a design variable to be optimized jointly with the allocation of auditing effort, and they impose bounds on penalties, which is what makes the problem non-trivial.

Security games

The immediate technical ancestor of audit games is the literature on Stackelberg security games, in which a defender commits to a randomized allocation of limited protective resources across a set of targets and an attacker, observing this randomization, best-responds by attacking a target. Kiekintveld, Jain, Tsai, Pita, Ordóñez and Tambe develop compact representations and algorithms that make it possible to compute such randomized allocations at realistic scale, an approach that has been fielded in physical security settings. Audit games adapt this machinery to auditing, where the "targets" are potential violations and the "defender resources" are auditors.

The audit game model

Blocki, Christin, Datta, Procaccia and Sinha introduce the audit game model, motivated by the enforcement of privacy policies inside organizations that hold large volumes of personal data, such as hospitals, banks and web service providers, where compliance relies on internal audits of employee accesses. Their model generalizes a standard security game for resource allocation by adding a configurable punishment parameter: the auditor chooses not only how to allocate audit resources probabilistically across potential violations, but also how severely to punish violations that are detected. Punishment is costly to the auditor as well, which prevents the degenerate solution of deterring everything with an unboundedly large penalty and a vanishing audit probability.

The solution concept is the Stackelberg equilibrium, in which the auditor commits to a possibly randomized audit strategy and a punishment level, and the potential violator best-responds. Computing this equilibrium is harder than in ordinary security games because the punishment parameter multiplies the audit probabilities, so the resulting optimization problem has non-convex quadratic constraints. The authors give an additive FPTAS that computes a solution arbitrarily close to optimal.

Blocki, Christin, Datta, Procaccia and Sinha generalize the model to several audit resources, where each resource may be restricted to auditing only a subset of the potential violations — a restriction that matters in practice, since auditors typically have jurisdiction or expertise over particular categories of access. They give a FPTAS for the resulting non-convex problem, obtained through an optimization transformation, and report that the transformation also accelerates the computation of solutions for a class of ordinary security games.

Auditing strategic reporters

The audit game framework treats violations as actions to be detected, whereas the mechanism-design literature treats reports as messages to be verified. The work of Estornell, Das and Vorobeychik described above sits between the two: agents strategically choose what to report, the agency commits to a publicly announced audit policy, and the problem of computing the policy that minimizes the incentive to lie is analyzed for its computational complexity as well as its structure. This convergence reflects a broader trend in which the algorithmic study of audit strategies and the economic theory of verification address the same underlying design problem with complementary tools.

Commitment

Because auditing deters misreporting only if agents expect it to occur, the principal's ability to commit is consequential. Khalil studies the optimal contract when the principal cannot commit to an audit, so that the contract must give the agent an incentive to comply and simultaneously give the principal an incentive to audit. The central trade-off becomes efficiency against non-compliance, rather than the more familiar trade-off of informational rent against efficiency: the agent earns no informational rent, and when production costs are high the agent is asked to produce more than under full information. Notably, the probability of audit is higher when the principal cannot commit than when he can.

Allocation without monetary transfers

A distinct branch studies auditing when the principal allocates a good rather than collecting a payment, and monetary transfers are unavailable, so that verification is the only instrument for disciplining reports. This setting covers the assignment of budgets, positions or scarce resources within organizations.

Ben-Porath, Dekel and Lipman study a principal allocating an indivisible good among agents who each privately know the value to the principal of receiving it. They show that an optimal mechanism is a favored-agent mechanism, specified by a threshold value and a designated agent: if every other agent reports a value below the threshold, the favored agent receives the good and nobody is audited; otherwise the agent reporting the highest value is audited and receives the good only if the report is confirmed. All optimal mechanisms are essentially randomizations over such mechanisms, the mechanism is ex post incentive compatible, and an agent who is more costly to verify is more likely to be the favored one.

Mylovanov and Zapechelnyuk consider a variant in which verification occurs after the prize has been allocated and the penalty that can be imposed on a false claimant is limited. When there are many agents, the optimal mechanism shortlists all agents above a threshold together with a fraction of those below it, and awards the prize to a randomly chosen agent on the shortlist; when there are few agents, the prize goes to the highest claimant, but the admissible range of claims is restricted from above and below.

Erlanson and Kleiner extend the approach from allocation to collective choice, studying a principal deciding between a new policy and the status quo when the relevant information is held by strategic agents, transfers are unavailable and claims can be verified at a cost. They characterize the optimal mechanism and show that it can be implemented as a cardinal voting rule in which agents cast either a baseline vote or a stronger vote that exposes them to verification.

Chua, Hu and Liu generalize this line of work to the allocation of several identical objects among more agents than there are objects, characterizing optimal mechanisms with costly verification in the multi-unit setting.

Dynamic auditing

When the same agent reports repeatedly, the principal can condition audits on the history of reports. Ravikumar and Zhang study a dynamic model in which a taxpayer begins with low income and may transit to high income, which can then be underreported. They show that the optimal auditing mechanism consists of cycles: a taxpayer reporting low income is initially not audited at all, but once the run of low-income reports exceeds a threshold duration, the audit probability becomes positive. Auditing is less frequent when the cost of auditing is higher or the variance of income is lower.

Related concepts

Optimal auditing is closely related to the design of mechanisms that are immune to manipulation without any verification at all, such as strategy-proof mechanisms, and to models in which misreporting is directly costly to the agent rather than detected by inspection. It is also connected to the analysis of manipulation in the strategic bankruptcy problem, where auditing is one of several devices for deterring claimants from inflating their claims.