Firms routinely outsource their business requirements to external agents for many reasons; for example, to focus on their core competencies or to save costs. However, overbilling by agents has been well-acknowledged as a notorious problem across major industries, including healthcare, information technology, legal services, and engineering. Mitigating overbilling is challenging in practice; typical options for firms include auditing agents or suspending relationships with them. While firms would like to combat overbilling by utilizing these options, they also want to minimize their total cost, including agents’ payments and auditing costs. We consider a repeated principal–agent setting in which, in each period, the principal makes two decisions: (i) Whether to allocate the task to the agent or an outside option. (ii) If the agent executes the task, whether to audit the agent’s cost. We propose a class of Dynamic Auditing mechanisms under which it is near-optimal for the agent to report his costs truthfully and the principal’s cost is also near-optimal, for sufficiently large discount factors. We study the role of auditing in our dynamic mechanism design framework. We show that auditing is an effective tool for the principal if either (i) the unit cost of auditing is sufficiently small, or (ii) the principal lacks knowledge of the agent’s cost distribution. We also show that our results are robust when there is competition among multiple agents for the principal’s business, and when the agent can deliberately inflate his costs by performing additional (redundant) work.
Many firms routinely rely on external agents, for example, vendors, suppliers, and consultants, to procure goods and services that facilitate business operations. Outsourcing business needs and contracting with agents allow firms to focus on their core competencies, lower costs, and improve service quality. In firm–agent relationships, a contractual agreement between a firm and an agent usually outlines the expectations for trade between the two parties, including the structure of the payments. However, due to their domain knowledge and expertise, agents are typically endowed with more information about the requirements of the business transactions, for example, the quality and quantity of resources required to satisfy the firm’s needs, and thus can strategically exploit this information asymmetry to overbill the firm by, for example, deliberately inflating their actual costs or billing for unnecessary work. Indeed, overbilling has been well-acknowledged as a notorious problem that has persisted for many decades and is widespread across most industries, including healthcare, information technology, and legal services.
To provide context to our subsequent discussion, we begin by presenting a few illustrative examples of overbilling across different industries.
Integrated Pain Associates, a pain management clinic in Killeen, Texas, and Central Texas Day Surgery Center, an affiliated ambulatory surgery center, were alleged to have overbilled federal healthcare programs. These providers were accused by the government of inflating the units and level of the medical services provided to patients when they requested reimbursement for these services from the government; for example, using a single facet-joint injection, but claiming reimbursement for three facet-joint injections for the same service.
Broadly, in the U.S. healthcare sector, the Federal Bureau of Investigation estimates that overbilling constitutes 3%–10% of the total spending (Drabiak and Wolfson, 2020).
In 2010, Adam Victor, an energy industry executive, hired DLA Piper, a global law firm, to prepare a bankruptcy filing for one of his companies. In 2013, Mr Victor accused the law firm of a “sweeping practice of overbilling.” The emails that surfaced as part of the litigation allegedly demonstrated that the law firm inflated bills by overstaffing and performing redundant activities. There was also evidence in support of alleged churning by the law firm, a practice in which unnecessary work was created and performed in order to increase the total number of hours billed to the client.
There is an extensive empirical literature that highlights the practice of overbilling in the legal industry. For example, based on the survey data from the Legal Services Commission, an independent regulatory body in Queensland, Australia, 91% of the respondents indicated that their firms used hourly billing, 34% reported concerns about billing practices in their organizations, and 23% reported having observed one or more instances of “padding” bills for artificial work (Parker and Ruschena, 2011).
Telophase Corporation, headquartered in Baltimore, Maryland, with core competencies in cyber defense, space engineering, enterprise technology, and data science, was accused of overbilling the National Aeronautics and Space Administration (NASA). Specifically, Telophase was alleged to have submitted false claims to NASA by billing labor hours and rates in excess of those that were actually incurred during the execution of its cost-plus-fixed-fee contract.
Another well-known case in the IT sector involved the company Unisys, which was accused of overbilling by the Transportation Security Administration (Washington Post, 2005).
Similar documented cases of overbilling abound in all major industries. It should also be noted that the scale of overbilling is perhaps much larger than what eventually gets established, as many cases go unnoticed or are not reported in the press.
Mitigating overbilling is a challenging task. There are a few options that firms typically have at their disposal. Firms can audit their agents (e.g., through credible third-party auditors) for compliance with respect to work and billing practices. This includes tracking the time and location of workers, reviewing documentation, and employing machine-learning techniques to identify behavioral patterns related to overbilling. Without auditing, a firm may only have coarse information regarding the costs reported by an agent. An audit can reveal granular information on the agent’s execution of the tasks, thus enabling the firm to better assess the validity of the reported costs, and subsequently, incorporate this knowledge in her outsourcing decisions.
Auditing, however, is typically both expensive and time-consuming. Further, an audit can result in noisy information that may be insufficient for a firm to impose monetary penalties on an agent for overbilling. Under the Fair Labor Standards Act, withholding payments to an agent on overbilling concerns in the presence of insufficient evidence may, in turn, invite a counterclaim from the agent for missed wages. Instead of pursuing a (costly) legal action against their agents, another option for firms is to suspend relationships with their (current) agents if they suspect overbilling, and use other alternatives (e.g., more costly suppliers) to address their business needs.
Table 1 presents a set of real-world cases to further highlight the role of repeated interactions, and the use of auditing and suspension as instruments to mitigate overbilling. The first two cases illustrate situations where healthcare providers were accused of overbilling and were subsequently suspended from participating in federal reimbursement programs (e.g., Medicare and Medicaid) for 5 years. The third case involves a firm replacing its lawyers due to overbilling concerns. The final two cases are instances in the construction industry where service providers were found to have overbilled and were subsequently suspended from bidding on contracts in the near future. In both instances, the use of external auditors to detect overbilling is explicitly mentioned.
Additional industry examples to motivate key features of our model.
Padding invoices, billing staff at higher rates, charging for unrelated expenses
Yes; for more than 5 years
Yes
Yes; permanently banned
In summary, while firms would like to combat overbilling by utilizing the above options meaningfully and intelligently, they also would want to do so by keeping their total cost (payments to external agents and the cost of auditing) over the long term as low as possible.
An informal description of our base setting
Motivated by the examples discussed above, we study the following setting: Consider a principal1 (e.g., firm) who has access to an agent (e.g., contractor) and an outside option (e.g., a more expensive contractor) for executing different tasks over time. In each period over an infinite time horizon, the principal faces a task that requires one period for completion, and can delegate the execution of that task either to the agent or to the outside option. Our infinite-horizon setting closely approximates repeated interactions of reasonably long duration.
The outside option and agent differ only in their costs. The cost of the outside option is known to the principal. The agent’s cost (that is realized at the end of the period after the task is completed) is privately known to the agent. To get reimbursed, the agent reports his execution cost to the principal, who reimburses that cost plus a fixed, predetermined profit margin. This is referred to as a cost-plus contract. Such contracts are common across many industries, and especially in applications where the costs of performing tasks are a priori unknown. While cost-plus billing protects the agent by guaranteeing a strictly positive utility from completing any given task, it also creates incentives for the agent to overbill the principal due to the agent’s superior domain knowledge. The principal has the option of conducting a costly and noisy audit of the agent’s reported cost to reduce this information asymmetry. Thus, for each task (i.e., in each period), based on the prior information available (i.e., the history of the costs reported by the agent and the auditing outcomes, if any, from previous periods), the principal makes two decisions:
[Allocation Decision] Whether to allocate the task to the agent or to the outside option.
[Auditing Decision] If the agent is selected, then whether or not to audit the agent’s reported cost for that task. The result of the audit is assumed to be immediately available.
As discussed earlier, imposing monetary penalties on the agent may not be feasible in practice. Therefore, our focus is on nonmonetary mechanisms in which the principal can only make allocation and auditing decisions (the payments to the agent are outcomes of the principal’s allocation decisions and the costs reported by the agent). The principal’s problem is to jointly determine her allocation and auditing decisions in each period, with the objective of minimizing her total expected discounted cost, which includes the payments to the agent, the costs incurred from using the outside option, and the costs incurred from auditing.
To appreciate the complexity of the principal’s problem, we briefly discuss the main trade-offs. Since the agent is assumed to be less expensive than the outside option on average, the principal prefers to outsource tasks to the agent but may suffer if the agent overbills. In our repeated-interaction setting, the principal can observe the history of the costs reported by the agent and, based on these reports, assess the truthfulness of the agent’s billed amounts. If the agent is deemed to be overbilling, the principal can ban the agent (i.e., select the outside option for executing tasks) for one or more periods. Doing so hurts the profitability of the agent, as he is guaranteed a strictly positive payoff if he bills truthfully under the cost-plus contract. Banning the agent also increases the principal’s costs as she needs to work with the relatively more expensive outside option. The option of auditing reduces the principal’s informational disadvantage and improves her ability to correctly determine whether and when to ban the agent. However, auditing itself is also costly. Thus, there is a trade-off between decreasing the principal’s execution costs and decreasing her auditing costs. On the one hand, to keep the execution costs low, the principal needs to allocate more tasks to the agent. However, doing so may require more auditing to deter the agent from overbilling. This increases the principal’s auditing costs.
The class of (dynamic) mechanisms that are feasible for the principal’s problem is large, as the principal’s allocation and auditing decisions in each period can depend on the entire history of information available until that period. Our goal in the paper is to identify a class of dynamic mechanisms such that, for any given , there is a mechanism in our class that satisfies the following two properties:
Property 1 (-Incentive Compatibility): Truthful reporting is an -optimal response for the agent. Formally, the total expected discounted utility of the agent under the truthful reporting strategy is within of his optimal utility.
Property 2 (-Optimality): The principal’s total expected discounted cost is within of her cost in an optimal mechanism.
The notion of -incentive compatibility, namely Property 1 above, has been widely used in the mechanism design literature (see, e.g., Azevedo and Budish, 2019; Balseiro et al., 2024; Gupta et al., 2021; Lubin and Parkes, 2012; Nazerzadeh et al., 2013). We provide a brief explanation for the rationale behind this notion. In the search for an optimal mechanism, the Revelation Principle (Myerson, 1981) allows us to restrict attention to incentive-compatible (IC) mechanisms, that is, those in which the agent reports his private information truthfully to the principal. For the problem we analyze, however, finding an IC mechanism is challenging. Since our focus is on nonmonetary mechanisms, the principal can only leverage the allocation of tasks and the threat of auditing to incentivize truthful reporting from the agent. Also, in our repeated-interaction setting, the principal can use complex allocation and auditing rules to reduce her total cost. Thus, characterizing the agent’s optimal dynamic reporting strategy in response to the principal’s mechanism is analytically challenging, in general. Therefore, for tractability, it has become common in such cases to approximate the IC requirement with an -IC requirement, under which we impose that the agent does not gain much by deviating from truth-telling.
In order to establish -optimality, namely Property 2 above, we consider the centralized setting in which there is only one decision-maker, namely the principal. In this setting, the principal knows the agent’s cost for each task. It is obvious that under the centralized setting, there is no need for auditing, and the principal’s total expected discounted cost under that setting is a lower bound on the principal’s total expected discounted cost under any given (including the optimal) mechanism. We use this lower bound to quantify the performance of our mechanism relative to the optimal mechanism.
An informal description of the dynamic auditing mechanism
For the principal’s problem, we introduce and define the class of Dynamic Auditing (DA) mechanisms, indexed by three parameters, namely the phase length and two thresholds and , where . Under this mechanism, we divide the time horizon into a sequence of phases, where each phase consists of periods. The phases are identical and follow the same sequence of events; thus, we focus our discussion on the first phase of the DA mechanism. The agent is endowed with a score whose value is initialized to 0 in the first period, and can increase or decrease over the duration of the phase based on the agent’s reports of his execution costs, the principal’s allocation decisions, and the signals generated from the principal’s audits, if any. In each period (i.e., for each task), the principal’s allocation and auditing decisions only depend on the agent’s score at the beginning of that period. The two thresholds, and , divide the possible values of the agent’s score into three intervals, namely , , and . If the agent’s score is above , the principal delegates the task to the agent. In addition, if the score is between and , the principal also commits to audit the agent after the task is completed at the end of the period. If the agent’s score drops below at any time during the phase, then the principal delegates all tasks for the remainder of the phase to the outside option.2 At the end of each period, the principal updates the agent’s score for the next period, as a function of the allocation and auditing decisions, the cost reported by the agent, and the information generated from auditing, if any, in the current period.
An informal description of our contributions
We briefly summarize our main theoretical and managerial contributions as follows:
Theoretical Contributions
In Section 4, we establish that for any and sufficiently high discount factor, there exist values of the parameters such that under the DA mechanism with these parameters, it is -optimal for the agent to report his costs truthfully to the principal, and the principal’s expected total cost under that mechanism is within of that in the centralized setting. Thus, the given class of DA mechanisms satisfies our two desired properties, namely Properties 1 and 2; see Theorem 1.
In Section 5, we investigate the role of auditing under DA mechanisms by considering two settings which differ in whether or not the principal has knowledge of the agent’s cost distribution (across different tasks), in particular, the mean of the distribution:
When the agent’s mean cost is known, we show that while auditing is not necessary for achieving the asymptotic guarantees (i.e., Properties 1 and 2), its use strictly benefits the principal if the unit cost of auditing is sufficiently small and the discount factor is sufficiently large. To show the benefits, we define the agent’s truth-telling regret as the loss in the agent’s expected utility from using the truthful reporting strategy rather than an optimal reporting strategy. We show that, as the discount factor converges to 1, the agent’s truth-telling regret converges to zero at a faster rate with auditing than without auditing. Further, the principal’s total cost (which is the sum of the execution and auditing costs) is also lower with auditing than without auditing; see Theorems 2 to 4.
When the agent’s mean cost is unknown, we show that it becomes imperative for the principal to use auditing to achieve the two properties. Since the DA mechanism requires knowing the agent’s mean cost, and hence is not applicable for the setting where the mean is unknown, we propose a modification, referred to as the DA mechanism, for that setting. The main idea underlying the DA mechanism is that it divides every phase into two subphases, namely an exploration subphase in which the principal leverages auditing to construct an estimate of the agent’s mean cost, and an exploitation subphase in which the principal uses the estimate to determine the allocation of tasks between the agent and outside option. We carefully choose the lengths of the exploration and the exploitation subphases such that the DA mechanism achieves our desired properties; see Theorem 5.
In Section 7.1, we analyze a competitive setting in which the principal needs to outsource multiple tasks in each period and has access to a pool of a finite number of agents. Since the principal has more agents than the number of tasks, the principal has to decide which agents to prefer and when. We propose a generalization of the DA mechanism, referred to as the DA mechanism, that maintains a subset of the agents from the pool as “preferred agents” for the allocation of the tasks, and carefully updates this set over time to achieve our desired properties; see Theorem 6.
Managerial contributions
Our paper shows how firms can leverage competition among agents for the firm’s future business and auditing as strategic instruments to mitigate overbilling when outsourcing projects using cost-reimbursement contracts. Firms should view auditing not only as a compliance check, but as a strategic incentive-alignment tool that influences the agents’ reporting behavior over time. Consistent auditing policies can serve as a deterrent to inflating costs, and are proven to be cost-effective if the cost per audit is low or if the principal lacks information on the agent’s cost structure. The severity of the information asymmetry between the principal and agent may vary depending on the business context. For example, IT project clients often lack the expertise needed to assess the complexity and resource requirements of their projects and thus have limited ability to estimate costs. In contrast, healthcare services are often billed while being subject to rigorous documentation and record-keeping regulations. There are standard codes for describing medical services and standard rates for reimbursement. Thus, the principal may face a more severe information asymmetry in IT procurement than in healthcare. As a consequence, it is more appropriate to use the DA mechanism (which requires knowing ) for the healthcare billing case, and the DA mechanism (which does not require ) in the IT procurement case.
Related literature
Our work mainly contributes to three streams of literature: dynamic mechanism design, auditing, and overbilling. We briefly review the most relevant work in these streams and highlight how our paper distinguishes itself from the extant literature.
Dynamic mechanism design
Dynamic adverse-selection settings have been used by many authors in the O.M./O.R. literature to study a variety of applications. For example, Zhang and Zenios (2008) derive an optimal menu of continuation utilities to induce truthful revelation of states in a Markov decision process, with multiple applications including dynamic pricing and supply chain contracting. Other examples of dynamic adverse-selection settings in O.M. include Oh and Özer (2013) (dynamic capacity management), Gao (2015) (dynamic risk management), Lobel and Xiao (2017) (dynamic supply chain contracting), Chen (2017) (dynamic auctions for display advertising), and Gershkov et al. (2018) (dynamic pricing). Our paper contributes to this literature by considering a repeated cost-reimbursement setting in which overbilling is known to be a major concern, and proposes a DA mechanism that incentivizes agents to report their costs truthfully.
There are several settings in practice where the use of nonmonetary instruments is preferred over money. For example, many firms use nonmonetary awards such as “Supplier of the Year” award to recognize and encourage superior performance from their suppliers over the long term (Gupta et al., 2023b). Nonmonetary mechanisms are also preferred in other settings such as the distribution of food among food banks (Prendergast, 2022), optimal course allocation among students (Budish et al., 2017), allocation of medical surplus products (Zhang et al., 2020), optimal distribution of funds (Arora et al., 2021; Gupta et al., 2024), dynamic bargaining (Feng et al., 2015), and welfare-maximizing, dynamic truth-telling mechanisms (Balseiro et al., 2019). Like ours, there have been a few studies that have proposed and analyzed score-based mechanisms for dynamic settings; see, for example, Budish et al. (2017), Gorokh et al. (2021), Gupta et al. (2023b), and Gupta et al. (2024). Since our problem setting is more closely related to Gorokh et al. (2021) and Gupta et al. (2024), we provide an in-depth comparison of our work relative to these two papers to clarify our contributions.
Both Gorokh et al. (2021) and Gupta et al. (2024) study a dynamic mechanism design problem in which the principal has only one lever, namely the allocation of resources, to mitigate the misalignment of incentives with the agents. In contrast, in our paper, the principal has two levers, namely the allocation of tasks and the option to audit the costs reported by the agents, to incentivize truthful reporting from the agents. The presence of the auditing option allows us to make several new contributions to this literature, in terms of developing new technical results and generating new insights; the details of this analysis are provided in Section 5.
We also analyze a competitive setting in which the principal needs to outsource multiple tasks in each period to a pool of many agents. Our competitive setting differs substantially from the ones studied in Gorokh et al. (2021) and Gupta et al. (2024). Specifically, in both papers, the authors assume “excludability” under which it is possible for the principal to abandon (or exclude) all agents, and as a result, not allocate resources to any agent in a given period. However, in our setting, since the principal has a fixed number of tasks to allocate in each period, we need at least that many agents to be under consideration for the allocation of tasks. Thus, the excludability assumption does not hold, and it becomes necessary for us to design a new score-based mechanism that is applicable to our competitive setting. Further, the analysis of this mechanism requires significantly new analysis; the details of this analysis are in Section 7.1.
Auditing
There is a large body of literature that studies the use of auditing in principal–agent settings for mitigating incentive issues that arise due to information asymmetry. A significant proportion of this literature has focused on static settings; see Dawande and Qi (2021) for a comprehensive survey of auditing-related studies. In contrast, a limited number of papers have examined auditing in dynamic settings. We discuss a few representative studies.
Chen et al. (2020) characterize an optimal dynamic contract that balances the trade-off between using monetary payments and monitoring sessions to motivate effort from an agent in order to reduce the arrival rate of adverse events. Our paper differs from Chen et al. (2020) in several aspects. First, Chen et al. (2020) study a moral-hazard (i.e., private effort) problem, whereas we study an adverse-selection (i.e., private information) problem. Second, monitoring in Chen et al. (2020) and auditing in our paper have different meanings. In Chen et al. (2020), monitoring the agent over an interval of time ensures that he exerts the desired level of effort during that interval. In contrast, in our paper, auditing results in a noisy signal on the agent’s private information. Third, in Chen et al. (2020), the principal can use money (in conjunction with monitoring) to incentivize long-term effort from the agent. In contrast, in our paper, the principal can only use nonmonetary incentives such as the allocation of current and the promise of future business (in conjunction with auditing) to incentivize long-term truthful reporting behavior from the agent.
Wang et al. (2016) consider a regulator who can inspect the firm for the presence of an environmental hazard and derive an optimal dynamic policy (for inspection, reward, and remediation) to minimize the expected societal cost in the long run. Our paper differs from Wang et al. (2016) in several ways: First, the information that is private in Wang et al. (2016) occurs only once at a random time. Second, the principal employs a different type of reward—the principal imposes a one-time subsidy or fine on the agent upon the detection of the hazard.
Zhang et al. (2022) consider a multitier supply chain in which the buyer can audit the social-responsibility compliance of its suppliers and study the joint effect of auditing, network topology, and pricing, to determine the optimal auditing policy. The role of auditing in that paper is fundamentally different from ours. In Zhang et al. (2022), the purpose of auditing is to determine the one-shot selection of suppliers, which influences the buyer’s procurement cost. A more stringent auditing policy weakens the competition and increases the buyer’s procurement cost. In contrast, in our paper, auditing is used as one of the two instruments to weaken the agent’s incentive to overbill in a repeated cost-reimbursement setting.
Overbilling
Given the scale of healthcare spending and reimbursements in the United States, many researchers have focused on the U.S. medical claims’ data to develop data-driven methods for estimating and detecting overbilling (see, e.g., Fang and Gong, 2017; Heese, 2018; Matsumoto, 2020; Shekhar et al., 2023). There is a stream of literature that uses experimental and field studies to understand the role of behavioral interventions in moderating the extent of overbilling. As discussed in HBR (2015) and Desai and Kouchaki (2015), choosing an appropriate reporting format, that is, asking an agent to report his units of work (e.g., hours spent and tasks completed) rather than the overall price, can help reduce the amount of overbilling. In contrast, a different study by Rilke et al. (2016) concluded that due to lie aversion, asking an agent to report work in segmented units results in more overbilling than reporting in one shot.
Our paper differs from this literature in that our focus is on operational levers, such as the dynamic allocation of current and future business, and the threat of auditing, to address the issue of overbilling. While the existing literature focuses on estimating overbilling, our focus is prescriptive in that we prescribe how to intelligently use these two levers to enable truthful billing from the agent. We prescribe a practically appealing method (namely, our DA mechanism) and establish theoretical guarantees on its performance. Thus, the novelty of our paper lies in the joint use of auditing and allocation in a dynamic mechanism design framework.
Model and preliminaries
Consider a principal (firm) who has access to an agent (contractor) and an outside option (a more expensive contractor) for executing different tasks over time. Consider an infinite time horizon with time periods indexed by and a per-period discount factor . At the beginning of each period , , the principal faces a new task (also denoted by for ease of exposition) that needs to be completed. It takes one time period (e.g., 2 weeks) to complete any task. The principal can delegate the execution of any given task either to the agent or to the outside option. The agent differs from the outside option in two fundamental ways: (i) On average, the cost of executing the task is lower for the agent than the outside option. (ii) If the agent executes the task, then after completion, the agent privately realizes his execution cost, which makes the agent more informed than the principal and allows the agent to leverage this information by overbilling the principal. In contrast, if the outside option executes the task, then that cost is known to the principal.
Let denote the cost incurred and privately realized by the agent after completing task , where . We assume that the probability density function underlying is strictly positive. Let be the mean of . For the base model, we assume that is known to the principal. In Section 5.2, we analyze the setting in which is unknown to the principal. The average cost incurred by the principal from using the agent for executing any given task is , where denotes the agent’s fixed, predetermined profit margin. The average cost of using the outside option for executing any given task is . Without loss of generality, we assume that to avoid the trivial outcome in which the principal delegates the task in every period to the outside option.3
If the agent is selected to execute task , then at the end of period (i.e., after the task is completed and the agent has billed the principal for that task), the principal has an option to incur to audit the agent’s reported cost for that task. The audit results in a signal on the agent’s cost , where represents the noise in auditing. The mean of is equal to zero. In practice, the principal and agent can reduce the auditing noise through a response and rebuttal process. Since the agent knows the actual cost (i.e., ), if the auditing signal turns out to exhibit more noise than what is deemed reasonable, the agent can furnish supporting evidence, such as purchase orders, key card records, work schedule, and so on, to improve the accuracy of the auditing signal. Such a process can reduce auditing noise but may not eliminate it. The auditing noise in our model can be viewed as the auditing noise that remains after the response and rebuttal process. As is common in the auditing literature (see, e.g., Dawande and Qi, 2021), we assume that the outcome of the audit (i.e., ) is public information. Further, we assume that the auditing signal is immediately available.4 We assume that the tasks are ex-ante independent and identically distributed across time. Thus, and are independent, and the pair is independent and identically distributed across . Table A.1 (in online Appendix A) summarizes our notation.
The sequence of events in any period is as follows:
At the beginning of period , the principal decides whether to select the agent or the outside option to execute task .
If the principal selects the agent, then the agent executes the task and, upon its completion, privately realizes and incurs the cost . The principal asks the agent to report his cost and reimburses the agent his reported cost plus the profit margin .
If the principal selects the outside option, then the principal incurs the cost .
If the agent is selected to execute the task, then after the agent completes the task and reports his cost for reimbursement, the principal has the option to audit the agent’s reported cost by incurring an auditing cost of . The audit generates the signal on the agent’s actual cost .
Let us define the set of admissible mechanisms as follows: An admissible mechanism is defined by a sequence of functions , where and , respectively, represent the principal’s allocation and auditing decisions in period . The function can depend on all information available to the principal until the beginning of period , and maps that information to the value 1 if the principal selects the agent for executing task and to the value 0 if the principal selects the outside option for that task. Similar to , the function can also depend on all information available to the principal until the beginning of period and, in addition, also on the cost reported by the agent in period , and maps that information to the value 1 if the principal audits the agent for task , and to the value 0 otherwise.5
Given an admissible mechanism , the agent optimally decides his strategy (or policy) of reporting his costs over time under that mechanism. A feasible reporting policy for the agent is defined by a sequence of functions , where, for any , the function maps the information available to the agent in period to the cost that the agent reports in that period; we denote the agent’s reported cost in period under policy by . Let denote the truthful reporting policy under which the agent reports his cost truthfully (i.e., ) in each period. We assume that any feasible must satisfy the following Cumulative Profit () constraint:
To understand the above constraint, consider the sum of the agent’s discounted utility from period 1 to as follows:
Under the () constraint, the agent’s cumulative profit from period 1 to for any under any reporting policy is lower bounded by the corresponding value under the truthful reporting policy. This constraint limits the extent to which the agent can underbill his costs (e.g., as a way to cover up overbilling of his costs in the past) and ensures that, for every realization of costs, the agent makes a margin of over the first periods (for every ).
Let denote the set of all feasible reporting policies that the agent can use. Given the reporting policy in response to the mechanism , the agent’s normalized6 expected total discounted utility is expressed as
and the principal’s (normalized) expected total discounted cost is expressed as
To assess the performance of any given mechanism for the principal, we briefly discuss the centralized setting, which is identical to our model except that the principal does not face any information asymmetry, and therefore, knows the true cost of the agent in each period. Since and , it is optimal for the principal to select the agent to execute the task in each period, and never use auditing; that is, and for every , where the superscript “” refers to the centralized setting. In the centralized setting, the agent’s expected total discounted utility is given as , and the principal’s expected total discounted cost is
We seek a class of admissible mechanisms with the following properties: For any , there exists such that for every , there is a member in this class under which:
Property 1 (-incentive compatibility): Truth-telling is an -optimal response of the agent. Formally,
Property 2 (-optimality): Assuming that the agent reports his costs truthfully, the principal’s expected (normalized) total discounted cost under that mechanism is within of the principal’s expected cost in the centralized setting. That is,
The class of mechanisms that satisfies the above properties is near-optimal for the principal for sufficiently large discount factors. In the next section, we introduce a class of mechanisms that achieves these properties.
A class of DA mechanisms
Our class of DA mechanisms is characterized by three parameters, namely, the phase length , and two thresholds and , where . Under the DA mechanism with parameters , the time horizon is partitioned into a sequence of phases, with each phase consisting of periods. The phases are identical and follow the same sequence of events; therefore, we limit our description to the first phase. Let us index the time periods in that phase by .
At the beginning of the phase (i.e., in period 1), the agent is endowed with a score that can increase or decrease over time based on the agent’s reports of his costs, the principal’s allocation and auditing decisions, and the signals generated from the audits conducted by the principal. The agent knows his score in each period as well as how it is updated over time. The principal uses the agent’s score in period to determine her allocation and auditing decisions for that period. Consider any period , and the following three cases:
If , then the principal selects the outside option for executing the task in period . Therefore, and .
If , the principal selects the agent to execute the task and commits to audit the agent’s report after the completion of the task. Thus, and .
If , then the principal assigns the task to the agent, and opts not to audit the agent’s reported cost after the completion of the task. Therefore, and .
At the end of period , the agent’s score for period is updated as follows:
where is the agent’s reported cost for task , if he is selected for that task. A unique feature of (2) is that if the agent is selected for task (i.e., ) and the agent reports his cost truthfully, that is, , then , where the expectation is taken over the realization of . This completes our specification of the DA mechanism.
For a given instance of our problem setting and a given sample path of the DA mechanism with fixed parameters , Figure 1 illustrates the evolution of the agent’s score , where , under three different reporting policies of the agent (that are marked as cases 1, 2, and 3, respectively). The following parameter setting has been used for this illustration: is uniformly distributed over the interval , is normally distributed with mean 0 and standard deviation 0.05, the discount factor is , the phase length is , and the two thresholds are and , respectively. In case 1 of Figure 1, the agent always overbills the principal by a fixed percentage, say 5%, of his true cost, up to the maximum possible cost ; that is, the agent reports his cost as in each period that he is selected. In case 2 of the figure, the agent uses a relatively more sophisticated reporting policy in which, in any period , if the agent’s score is above the threshold , then the agent overbills the principal by reporting his cost as . However, if the agent’s score is between the two thresholds and , then the agent becomes cautious and bills truthfully until his score becomes higher than . Note that if the agent’s score drops below in some period , then the principal does not select the agent (and works with the outside option) in period and for the remainder of that phase. Finally, in case 3 of the figure, the agent reports his cost truthfully in each period.
An illustration of the agent’s score , , under a given sample path of the DA mechanism for three different reporting policies of the agent (marked as cases 1, 2, and 3, respectively).
Given the agent’s reporting policy, we now discuss how the principal’s allocation and auditing decisions evolve in Figure 1 under the given sample path of the DA mechanism. In case 3, where the agent is always truthful, the agent’s score fluctuates around 0 (his initial score in period 1) but is always above for the given sample path, which, in turn, implies that the principal selects the agent and does not audit the agent in each period over the given phase of periods. In case 2, the agent’s score decreases initially with time and then remains within the interval for the remainder of that phase. Thus, the principal selects the agent and does not audit the agent for periods , and selects and audits the agent from period 7 and onward, in the given phase. Finally, in case 1 where the agent always overbills, the principal selects the agent and does not audit the agent for periods , 5, selects and audits the agent for periods 6 and 7, and switches to the outside option from period 8 and onward, in the given phase.
In summary, as the above cases illustrate, the DA mechanism smartly leverages the principal’s ability to use a competitive outside option and the ability to audit the agent’s costs, in order to mitigate the agent’s incentive to overbill. If the agent engaged in overbilling (cases 1 and 2 in Figure 1), his score would decrease over time and, as a result, the principal would increasingly audit the agent’s reported costs to improve her assessment of the agent’s reporting behavior. If the agent continued to overbill, the principal would penalize the agent by delegating tasks to the outside option for the remainder of the phase. On the other hand, if the agent billed truthfully (case 3), the principal would reward the agent by delegating tasks to the agent.
For any , let denote the ceiling function, which is equal to the smallest integer greater than or equal to . We have the following result.
For any , there exists such that for all , strictly positive , , and , and , the DA mechanism with parameters satisfies Properties 1 and 2, where
That is, under the given DA mechanism, it is -optimal for the agent to report his costs truthfully to the principal, and the principal’s expected total discounted cost is within of .
We note that the above result applies for any strictly positive , , and , and . In addition to satisfying the desired properties, our choice of in (3) for the DA mechanism has intuitive interpretations that make them appealing for real-world implementation:
The gap is decreasing in and converges to 0 as converges to infinity. Under the DA mechanism, the principal audits the agent in any given period only when his score in that period is between and . Thus, the probability that the principal audits the agent in any given period is decreasing in the principal’s per-period auditing cost.
The thresholds and are increasing in the phase length . As discussed earlier, if the agent is always truthful, then his score under the DA mechanism remains the same across time, on average. However, due to variations in the agent’s costs and the uncertainties involved in auditing across different tasks, even if the agent were truthful, his score could decrease and fall below and, as a consequence, he could still be (mistakenly) abandoned by the principal.7 By selecting and that are increasing in , the principal ensures that the likelihood of making such a mistake is sufficiently close to 0.
The length of the phase is increasing in . A longer phase length enables the principal to observe the agent’s reporting behavior for a longer duration, thus improving her ability to assess the truthfulness of the agent. Further, a longer phase length also implies a longer suspension (thus, a more stringent penalty) for the agent if he is assessed to be overbilling.
In practice, the auditing noise can depend on the agent’s cost. To incorporate this feature, consider, for example, the auditing signal to be , where, as before, denotes the agent’s actual cost and is a random variable (independent of ) whose mean is zero. It can be shown that our results continue to hold under this extension.
Understanding the role of auditing
In this section, we investigate the role of auditing under DA mechanisms by considering two settings which differ in terms of whether or not the mean of the agent’s cost, that is, , is known to the principal. Our main findings from this section are summarized as follows:
(a) If is known, we show that while auditing is not necessary for achieving Properties 1 and 2, its use can strictly benefit the principal in the following two ways: (i) as the discount factor converges to 1, the agent’s truth-telling regret (i.e., the amount by which the agent could benefit if he used an optimal reporting strategy rather than the truthful reporting strategy) converges to zero at a faster rate, and (ii) it results in a strictly lower expected total cost for the principal under certain conditions; the details are provided in Section 5.1.
(b) If is unknown, we show that it becomes imperative for the principal to use auditing to achieve the two properties. Since the DA mechanism (Section 4) is no longer applicable as it requires (see (2)), we propose a modification, referred to as the DA mechanism, for this setting that achieves Properties 1 and 2; the details are provided in Section 5.2.
Role of auditing when is known
Let us define a subfamily of DA mechanisms, denoted by , by fixing
for any . It is easy to verify that the DA mechanism specified in Theorem 1 with belongs to the family of mechanisms. To demonstrate the value of auditing, for ease of exposition, we restrict our attention to the family of mechanisms and assume that auditing is perfect (i.e., the auditing noise is zero). The assumption of perfect auditing applies only for this subsection, namely Section 5.1. We show the robustness of our insights in this subsection for noisy auditing in Section 6.
Under any mechanism, the principal audits the agent in any given period if and only if his score in that period is between and , where . Since from (4), whether or not the mechanism involves auditing depends only on . If , the mechanism does not involve auditing. As is common in the literature, we use the notation and to denote upper and lower bounds, respectively.8 For simplicity, we express our bounds in terms of (the phase length), which depends on according to (4).
DA Mechanism without Auditing
Consider the mechanism with and , where . We have the following:
The agent’s truth-telling regret is
The principal’s expected total cost is
Using the relationship between and in (4), Theorem 2 results in the following corollary.
For any , there exists such that for all , and , the mechanism with and satisfies Properties 1 and 2: that is, it is -optimal for the agent to report his costs truthfully to the principal, and the principal’s expected total cost is within of .
Corollary 1 confirms that there exists a DA mechanism that achieves Properties 1 and 2, without using auditing. In what follows, we identify sufficient conditions under which the principal strictly prefers to use auditing and also demonstrate the benefits obtained from using auditing. To show that auditing can strictly benefit the principal, it suffices to show the benefit for one specific mechanism that uses auditing relative to any mechanism that does not use auditing. The remainder of our analysis proceeds as follows: First, we obtain lower bounds on the agent’s truth-telling regret and the principal’s expected cost under every mechanism that does not use auditing (see Theorem 3). Then, we obtain upper bounds on the same quantities under a specific mechanism that uses auditing. Finally, we compare the two sets of bounds to establish the benefits of auditing (see Theorem 4).
Lower Bounds without Auditing
For any mechanism with (i.e., the one without auditing since ) and that achieves Properties 1 and 2, we have the following:
The agent’s truth-telling regret is
The principal’s expected total cost is
Theorem 3 shows that, in the absence of auditing, there does not exist a mechanism under which the agent’s truth-telling regret could converge to zero at a rate faster than . This lower bound is tight in the sense that the mechanism identified in Theorem 2 delivers a convergence rate on the agent’s truth-telling regret that is arbitrarily close to . We briefly discuss the technical highlights of the proof of Theorem 3. First, we show that it is without loss of generality to restrict attention to since for all , the mechanism would fail to achieve Property 2, and for all , the mechanism would fail to achieve Property 1. Second, we construct a heuristic reporting policy under which we show that the agent’s truth-telling regret is lower bounded by , and hence by for sufficiently large , since and . To prove this lower bound, we use the () constraint to establish a linkage between our heuristic and the truthful reporting policies—we show that the agent remains active for the same number of periods under both policies.
DA Mechanism with Auditing
Consider the mechanism with (i.e., the one with auditing since ) and , where and is finite. We have the following9:
The agent’s truth-telling regret is
There exists such that for all and , where is defined in (C.10) of online Appendix C.3, the principal’s expected total cost under the given mechanism (i.e., the one with auditing since ) is strictly smaller than the corresponding cost under any mechanism that satisfies Properties 1 and 2 without using auditing.
Theorems 3 and 4 together, generate the following insights:
Without auditing, there does not exist a mechanism under which the agent’s truth-telling regret could converge to zero at a rate faster than . However, with auditing, there exists a mechanism under which the agent’s truth-telling regret converges to zero at a rate arbitrarily close to . Clearly, this improvement in the convergence rate is because of auditing. Intuitively, since auditing generates an informative signal about the agent’s cost, the principal’s ability to deter the agent from deviating from truth-telling is superior with auditing than without auditing.
Without auditing, the principal’s expected total cost is lower bounded by the centralized cost (i.e., ) plus a strictly positive constant which does not depend on the per-period auditing cost . For business environments in which the per-period auditing cost is sufficiently small (i.e., ) and the discount factor is sufficiently large (i.e., ), we show that the principal’s expected total cost is smaller with auditing than without auditing; thus, auditing is strictly preferred by the principal because it endows a stronger incentive on the agent to bill truthfully without compromising on the principal’s total cost. Intuitively, the additional costs incurred by the principal due to auditing are more than compensated by the savings generated in the execution costs.
Role of auditing when is unknown
The DA mechanism (Section 4) requires knowing , irrespective of whether or not the principal uses auditing; see (2). Thus, if is unknown, the DA mechanism is not applicable. One way to address this issue is by using auditing. Since auditing generates an unbiased signal on the agent’s actual cost, the principal can estimate by conducting audits repeatedly over time. In what follows, we propose a modification of the DA mechanism, referred to as the DA mechanism (where the superscript stands for “unknown”) that utilizes auditing to estimate , and demonstrate that it achieves our desired properties. In this manner, in the absence of , using auditing becomes indispensable for the principal.
Similar to the DA mechanism, the time horizon under the DA mechanism is also divided into phases, each of length . However, different from the DA mechanism, every phase of the DA mechanism now consists of two subphases in the following order:
An exploration subphase of length , in which the principal outsources the task in each period of that subphase to the agent and audits the agent’s reported cost. Thus, for . The purpose of the exploration subphase is to learn the distribution of the agent’s cost, and in particular, the mean of that distribution. Let
be the point estimate of obtained in this subphase.10
An exploitation subphase of length , in which the principal’s allocation and auditing decisions are made in the same manner as in the DA mechanism of Section 4 (which required ), except for the following two changes: (a) the value in equation (2) for updating the agent’s score is replaced by obtained from the exploration subphase. (b) The time index goes from to instead of from 1 to .
We show the following result.
For any , there exists such that for all , strictly positive , , and , and , the DA mechanism with parameters
satisfies Properties 1 and 2.
It is worth noting that the convergence rates of Properties 1 and 2 under the DA mechanism (where is unknown) are weaker than the corresponding rates under the DA mechanism (where is known); see Table 2. This signifies the “price” that the principal pays for the lack of knowing (or the inability to use) .
The rates of convergence (with respect to the phase length ) of Properties 1 and 2 under the DA and DA mechanisms, for any and (see online Appendices B and C.4).
DA mechanism
DA mechanism
Property 1
Property 2
Numerical study
Recall that in Theorem 1 of Section 4, we theoretically established the near-optimality of the DA mechanism. This result is “asymptotic” in the sense that for an arbitrarily small , we showed the existence of a sufficiently high discount factor such that our DA mechanism is both -IC and -optimal. Our goal in this section is to demonstrate the excellent performance of our DA mechanism for practically reasonable values of the discount factor. Further, we demonstrate the robustness of our insights from Section 5.1 under noisy auditing.
We now explain the test-bed for our analysis: In practice, the discount factor naturally depends on the duration of a period and the time value of money. In the practical applications that motivated our research, the frequency of billing ranges from a few weeks to a month; for example, 2 to 3 weeks in software development (see, e.g., WSJ, 2023) and 2 to 4 weeks in legal consulting (see, e.g., Giordano, 2022). Accordingly, we consider the length of a time period to be 2 weeks. For the time value of money, we look at annual interest rates for borrowing capital. We use this information to obtain a (crude) estimate of the per-period discount factor for our numerical study as follows: If the duration of a period is weeks and the annual interest rate for lending is , we calculate the per-period discount factor as . The discount factors (roughly) correspond to annual interest rates varying between 7% and 15. The agent’s execution cost follows a uniform distribution, with 10 possible values from the set .11 The cost of using the outside option is set to . We assume the profit margin . The principal’s per-period auditing cost is and the auditing noise follows the normal distribution with mean 0 and standard deviation 0.1. We analyze the performance of the DA mechanism, that is, the one with parameters specified in (3) with , , , and .
Let us define
as the relative percentage loss in the agent’s expected utility if the agent uses the truthful reporting policy under the DA mechanism, instead of an optimal reporting policy, where is defined in (1). A lower value of means that the agent has a stronger incentive to report truthfully. To compute , we need to solve the agent’s decision-making problem under the DA mechanism, which involves finding a reporting policy that maximizes the agent’s total expected discounted utility subject to the () constraint. We can formulate the agent’s problem as a DP recursion whose state-space is multidimensional due to the following reasons: (i) The agent’s decision in any given period depends on his actual cost and his score in that period. (ii) To ensure that the agent’s decision in any given period satisfies the () constraint, the sum of the discounted reported costs until that period must be higher than the sum of the discounted actual costs. Thus, solving the agent’s problem is computationally expensive. To reduce our computational burden, instead of computing defined in (6), we compute upper and lower bounds on as follows:
Computing an upper bound on :
Consider a modification of the agent’s problem which is identical to the problem discussed above, except that the agent’s reporting policy does not need to satisfy the () constraint. Since this modification is a relaxation of the agent’s problem, solving it results in an upper bound, namely , on . Under this relaxation, the state in each period is two-dimensional, consisting of the agent’s actual cost and his score in that period.
Computing a lower bound on :
Consider another modification of the agent’s problem with an additional restriction that the agent cannot understate his costs, that is, for every , the reported cost must be at least the actual cost . Clearly, such a modification is more restrictive and thus, solving it results in a lower bound, namely , on . Furthermore, since the () constraint has become redundant, the state in each period is again reduced to two dimensions and represented by the agent’s actual cost and his score in that period.
The DP recursions for the above two modifications are discussed in online Appendix D.
Next, assuming that the agent reports his costs truthfully to the principal, we define
as the relative percentage gap between the principal’s expected total discounted cost under the DA mechanism relative to the corresponding cost in the centralized setting. A lower value of implies a better cost-performance of the DA mechanism.
We compute , , and numerically. Figure 2 illustrates , , and as a function of the discount factor . We observe that the upper bound on the percentage loss in the agent’s utility from truth-telling, that is, , ranges in the interval 6.9%–9.4, with an average value of . Thus, the agent has a reasonably strong incentive to report his costs truthfully (rather than using a complex, optimal reporting policy). Further, ranges in the interval 3.5%–4.0, with an average value of , showing that the DA mechanism delivers a cost-performance that is reasonably close to the optimum, for practical values of the discount factor.
An illustration of , , and as a function of the discount factor .
Next, we recall that in Section 5.1, assuming perfect auditing, we theoretically established that the use of auditing increases the agent’s incentive to report truthfully, and decreases the principal’s expected total cost, provided that the per-period auditing cost is sufficiently small and the discount factor is sufficiently large. We numerically show that these results continue to hold for noisy auditing.
Figure 3 illustrates , , and as functions of , for a fixed and two different values of . We recall that and , where , represent the two threshold parameters of the DA mechanism and their relative values, together with the score of the agent, determine the principal’s auditing decision. The principal audits the agent in any given period if and only if his score in that period is between and . Thus, if , the principal never audits the agent. From Figure 3, we make two observations: (i) There exists such that the upper bound at is strictly smaller than the lower bound at ; for example, when , (roughly) and when , . As a result, the agent’s incentive to report truthfully is stronger with auditing than without auditing. (ii) The value of at is also strictly smaller than the corresponding value at , and thus, the principal’s expected total cost with auditing is also lower than without auditing.
An illustration of , , and as a function of for different values of , assuming .
Extensions
A competitive setting with multiple tasks and agents
In this section, we analyze an extension in which the principal needs to outsource tasks in each period and has access to a pool of agents. As in the base model (Section 3), each agent can execute at most one task in any given period. Without loss of generality, we assume that ; if , then each agent would be guaranteed to receive a task in each period and thus, there would be no competition among the agents for the principal’s business. We assume that the agents are ex-ante identical, that is, their mean costs of completing a task are identical. The problem setting and notation for this extension remain largely the same as that in the base model, with the main difference being that we now incorporate an index corresponding to agent , .
When there are multiple agents, Property is a natural extension of Property 1 (Section 3) and uses the notion of an -Bayesian Nash equilibrium:
Property (-Bayesian Nash equilibrium): Truthful reporting forms an -Bayesian Nash equilibrium for the agents; that is, for any , given that all agents except agent report their costs truthfully, it is -optimal for agent to report his costs truthfully.
Our main result for the above competitive setting is a mechanism, which we refer to as DA (where the superscript stands for “competition”), that achieves both of our desired properties, namely Properties and 2.
We now define the DA mechanism. For brevity, we only highlight the key features of the DA mechanism that distinguish it from the DA mechanism of the base model. Similar to the DA mechanism, the DA mechanism consists of three parameters, namely, the phase length , and two thresholds and . The time horizon is partitioned into a sequence of phases, with each phase consisting of periods. In every period of any given phase, exactly out of agents are considered to be preferred and each preferred agent receives the allocation of one (unique) task from the principal. While the set of preferred agents will change from one period to another during a phase and across different phases, the number of preferred agents in each period remains equal to .
At the beginning of the time horizon (i.e., in period 1), the principal randomly picks out of agents to be the preferred agents. To explain how the set of preferred agents changes over time, let us consider phase , for instance. Let us index the time periods during that phase as . Let denote the set of preferred agents at the beginning of the phase, that is, in period . The principal endows each preferred agent with a score whose value is initialized to 0 at the beginning of the phase. These scores are monitored and updated by the principal during the phase only up to a point in time, say period , which is the first period in which there is at least one agent in the set whose score falls strictly below . Below, we specify the details of the DA mechanism during phase for periods and for periods .
For every period during phase , every agent remains preferred and executes a (distinct) task for the principal. Further, as in the DA mechanism for the base model, the principal audits agent ’s reported cost in period if the score of that agent is strictly smaller than , that is, . The principal updates agent ’s score for the next period, that is, period , as follows:
where is agent ’s reported cost for period .
Recall from the definition of above that it is the first period during phase when there is at least one agent in the set whose score falls strictly below . Let denote the set of agents whose scores are strictly below in period . Also, let . Clearly, and . A random subset of agents in the set lose their preferred status and are replaced by nonpreferred agents from the set for the remainder of this phase—the precise details of this swapping depend on the relative cardinality of these two sets, and are described formally by the following two cases:
If , then the principal randomly selects agents from the set ; we refer to this set of randomly drawn agents by . For every period until the end of phase , the set of preferred agents consists of all the agents from the sets and . Each of these preferred agents executes a (distinct) task for the principal without any audit until the end of phase .
If , then the principal randomly selects agents from the set ; we refer to this set of randomly drawn agents by . For every period until the end of phase , the set of preferred agents consists of all the agents from the sets and . Each of these preferred agents executes a (distinct) task for the principal without any audit until the end of phase .
After phase ends, each agent who was preferred in the last period of phase is designated as a preferred agent at the beginning (i.e., the first period) of the subsequent phase (i.e., phase ).
This completes our description of the DA mechanism.
For any , there exists such that for all , strictly positive , , and , and , the DA mechanism with parameters
satisfies the following two properties: (a) It is an -Bayesian Nash equilibrium for the agents to be truth-telling. (b) The principal’s expected cost is within of the principal’s expected cost in the centralized setting.
Technical highlights
We briefly highlight the key steps of our analysis of the DA mechanism. In the base model, the principal “prefers” to outsource tasks to the agent until the agent is banned due to the overbilling concern. For the competitive setting, since there are more agents than the number of tasks, the principal has to decide which agents to prefer and when. Whether an agent is preferred in a given period depends not only on his own reporting strategy and preferred status in the past periods, but also on the reporting strategies and preferred status of the other competing agents. Thus, it is challenging to analyze agents’ equilibrium strategies when there is competition among agents for the principal’s business. We briefly highlight features of our DA mechanism that help us overcome these challenges:
Under the DA mechanism, the optimal reporting strategy of an agent who is preferred at the beginning of a phase is independent of the identity of that phase. This property holds because the scores of the preferred agents in any given phase (which form the basis for the outcomes during that phase) are reset to 0 at the beginning of the phase, and the manner in which these scores are updated during the phase is the same across different phases.
In the base model, since the phases were independent, it was sufficient to consider an arbitrary phase to analyze the agent’s optimal reporting strategy. However, for the DA mechanism, the events across different phases are correlated. That is, the past reporting behavior of all the agents determines the set of agents who are preferred by the principal in a given phase, which in turn, influences the principal’s allocation and auditing decisions in that phase.12 Agent , , is preferred at the beginning of phase in one of the following two ways: (i) Agent is preferred at the beginning of phase and remains preferred throughout phase . (ii) Agent is not preferred at the beginning of phase , becomes preferred at some point during phase and remains preferred until the beginning of the next phase. The change in agent ’s status from nonpreferred to preferred in the latter case happens when one of the preferred agents becomes nonpreferred during phase and is replaced by agent . These cases together allow us to develop a recursion to express the probability that agent is preferred at the beginning of phase (see Lemma E.1 in online Appendix E.1), thereby facilitating our analysis of the DA mechanism for the competitive setting.
Inflating costs by performing redundant work
In our analysis thus far, the agent engaged in overbilling after the task’s execution by reporting his cost to be higher than the actual cost. We refer to this type of overbilling as reported-cost overbilling. In this section, we analyze a variant in which the agent unnecessarily incurs an extra cost , over and above , to execute task , and reports the cost incurred correctly as . The principal neither observes nor for any . Thus, the actual cost incurred is inflated (compared to what it should be) but there is no inflation in the reporting. We refer to this as the actual-cost overbilling.13 In Theorem 7, we demonstrate that our DA mechanism continues to remain near-optimal under actual-cost overbilling.
For any , there exists such that for all , strictly positive , , and , and , the DA mechanism with parameters
satisfies the following two properties: (a) It is -optimal for the agent not to incur additional costs to execute tasks. (b) The principal’s expected cost is within of the expected cost in the centralized setting.
Concluding remarks
Our paper is the first to examine the use of two operational levers, namely the dynamic allocation of tasks between the agent and an outside option, and the auditing of the costs reported by the agent, to combat the agent’s incentive to overbill. We propose an easy-to-understand and implementable mechanism, namely the DA mechanism, that intelligently utilizes both levers. We shed light on the role of auditing in repeated interactions, and demonstrate that it is an effective instrument for the principal if either (i) the unit cost of auditing is sufficiently small, or (ii) the principal lacks knowledge of the agent’s cost distribution. Finally, we showcase the robustness of our results for a competitive setting involving many tasks and many agents.
Auditing plays an important role in industries where overbilling is a major concern. For example, in healthcare, systematic auditing can uncover patterns of overbilling behavior including, double-billing, performing unnecessary procedures, and upcoding; this allows regulators to identify clinics that exploit federal reimbursement programs. Similarly, in legal services, performing audits can help in flagging padded invoices, thereby enhancing accountability. In outsourced IT projects, where the information asymmetry between firms and vendors is typically more severe, performing a periodic assessment of reports can detect overstatement of costs and misuse of resources. Across all such industries, coupling auditing with the threat of suspension for a limited duration can help discipline the billing behavior of vendors. For example, healthcare service providers, law firms, or IT contractors exhibiting suspicious billing patterns can be audited more frequently or assigned fewer tasks, whereas those whose reporting behavior is assessed to be reliable continue to receive business with limited oversight. Conditioning business allocation and auditing decisions on service providers’ past billing behavior can effectively mitigate their incentives to overbill.
Our framework, which involves the use of (noisy) auditing over repeated principal–agent interactions, is a potent one and can be extended to study other influential business problems, such as those arising in food supply chains and socially responsible operations. While a majority of the work in these areas has focused on single-shot interactions (see, e.g., the survey by Dawande and Qi, 2021), there are rich opportunities to investigate practical settings that naturally involve repeated interactions. For instance, agricultural producers (farmers) repeatedly interact with intermediaries who help producers in marketing their produce to end consumers. It is common for such intermediaries to routinely inspect (or audit) farmers’ produce for quality-related issues, such as moisture level, presence of unwanted elements (adulteration), and so on. As another example, manufacturing firms repeatedly interact with their suppliers for procuring raw material or components needed for finished products. To ensure socially responsible operations, it is common for such firms to audit their suppliers for any noncompliance (e.g., the use of unsafe working conditions, employment of child labor, etc.) or to monitor supply chain partners for the implementation of environment and social responsibility initiatives; see, for example, Feng et al. (2022).
Under cost-plus billing, the principal reimburses the agent the cost incurred for executing a given task, plus a predetermined profit margin. We have focused on this billing format since it is widely used across major industries and suffers from the issue of overbilling. However, there are business environments where fixed-price billing is relevant; for example, for tasks whose costs are a priori known. In environments where both cost-plus and fixed-price billing can be applied, these two choices present an interesting trade-off for the principal. While cost-plus billing protects agents by guaranteeing a strictly positive utility from completing any given task, it also creates incentives for agents to overbill the principal due to agents’ superior domain knowledge of execution costs. On the other hand, while fixed-price billing eliminates overbilling after the execution of tasks, it leaves agents vulnerable to losses and therefore may also impact the quality of work. This trade-off makes it reasonable for the principal to negotiate the billing format (i.e., cost-plus or fixed-price) with the agents. We hope that our paper will motivate future research to explore such negotiations.
Supplemental Material
sj-pdf-1-pao-10.1177_10591478261451992 - Supplemental material for Combating overbilling in outsourced projects: A dynamic auditing mechanism
Supplemental material, sj-pdf-1-pao-10.1177_10591478261451992 for Combating overbilling in outsourced projects: A dynamic auditing mechanism by Like Bu, Shivam Gupta, Milind Dawande and Ganesh Janakiraman in Production and Operations Management
Footnotes
Acknowledgments
The authors are grateful to the department editor, senior editor, and anonymous reviewers for their constructive suggestions that helped us in significantly improving the paper in content and exposition.
ORCID iDs
Shivam Gupta
Milind Dawande
Ganesh Janakiraman
Like Bu
Funding
The authors received no financial support for the research, authorship, and/or publication of this article.
Declaration of conflicting interests
The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.
Supplemental material
Supplemental material for this article is available online (doi: (doi: )).
Notes
How to cite this article
Bu L, Gupta S, Dawande M and Janakiraman G (2026) Combating overbilling in outsourced projects: A dynamic auditing mechanism. Production and Operations Management x(x): 1–19.
References
1.
AroraPWeiWSolakS (2021) Improving outcomes in child care subsidy voucher programs under regional asymmetries. Production and Operations Management30(12): 4435–4454.
2.
AzevedoEMBudishE (2019) Strategy-proofness in the large. The Review of Economic Studies86(1): 81–116.
BalseiroSRGurkanHSunP (2019) Multiagent mechanism design without money. Operations Research67(5): 1417–1436.
5.
BertsekasD (2012) Dynamic Programming and Optimal Control: Volume I. Vol. 4. Nashua, NH: Athena Scientific.
6.
BudishECachonGPKesslerJB, et al. (2017) Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research65(2): 314–336.
CormenTHLeisersonCERivestRL, et al. (2022) Introduction to Algorithms. Cambridge, MA: MIT Press.
10.
DawandeMQiA (2021) Auditing, inspections, and testing for social responsibility in supply networks. In: Swaminathan JM and Deshpande V (eds) Responsible Business Operations: Challenges and Opportunities. Cham, Switzerland: Springer, 243–259. ISBN 978-3030519568.
11.
DesaiSDKouchakiM (2015) Work-report formats and overbilling: How unit-reporting vs. cost-reporting increases accountability and decreases overbilling. Organizational Behavior and Human Decision Processes130: 79–88.
12.
DrabiakKWolfsonJ (2020) What should health care organizations do to reduce billing fraud and abuse?AMA Journal of Ethics22(3): 221–231.
13.
FangHGongQ (2017) Detecting potential overbilling in Medicare reimbursement via hours worked. American Economic Review107(2): 562–591.
14.
FengQLaiGLuLX (2015) Dynamic bargaining in a supply chain with asymmetric demand information. Management Science61(2): 301–315.
15.
FengQLiCLuM, et al. (2022) Implementing environmental and social responsibility programs in supply networks through multiunit bilateral negotiation. Management Science68(4): 2579–2599.
16.
GaoL (2015) Long-term contracting: The role of private information in dynamic supply risk management. Production and Operations Management24(10): 1570–1579.
17.
GershkovAMoldovanuBStrackP (2018) Revenue-maximizing mechanisms with strategic customers and unknown, Markovian demand. Management Science64(5): 2031–2046.
18.
GiordanoC (2022) Streamline your law firm’s billing process: Best practices to increase profitability. Lawmatics. Available at: https://tinyurl.com/426f53k8 (accessed 13 May 2026).
19.
GorokhABanerjeeSIyerK (2021) From monetary to nonmonetary mechanism design via artificial currencies. Mathematics of Operations Research46(3): 835–855.
20.
GuptaSBansalSDawandeM, et al. (2024) Trust-and-evaluate: A dynamic nonmonetary mechanism for internal capital allocation. Management Science70(11): 7811–7828.
21.
GuptaSChenWDawandeM, et al. (2023b) Three years, two papers, one course off: Optimal nonmonetary reward policies. Management Science69(5): 2852–2869.
22.
GuptaSWangSDawandeM, et al. (2021) Procurement with cost and noncost attributes: Cost-sharing mechanisms. Operations Research69(5): 1349–1367.
LubinBParkesDC (2012) Approximate strategy proofness. Current Science103(9): 1021–1032.
27.
MatsumotoB (2020) Detecting potential overbilling in Medicare reimbursement via hours worked: Comment. American Economic Review110(12): 3991–4003.
28.
MyersonRB (1981) Optimal auction design. Mathematics of Operations Research6(1): 58–73.
29.
NazerzadehHSaberiAVohraR (2013) Dynamic pay-per-action mechanisms and applications to online advertising. Operations Research61(1): 98–111.
30.
OhSÖzerÖ (2013) Mechanism design for capacity planning under dynamic evolutions of asymmetric demand forecasts. Management Science59(4): 987–1007.
31.
ParkerCRuschenaD (2011) The pressures of billable hours: Lessons from a survey of billing practices inside law firms. University of St. Thomas Law Journal9(2): 618–662.
32.
PrendergastC (2022) The allocation of food to food banks. Journal of Political Economy130(8): 1993–2017.
33.
RilkeRMSchurrABarkanR, et al. (2016) One-by-one or all-at-once? Self-reporting policies and dishonesty. Frontiers in Psychology7: 113.
34.
ShekharSLeder-LuisJAkogluL (2023) Unsupervised machine learning for explainable health care fraud detection. Technical report, National Bureau of Economic Research.
WeissDC (2020) Overbilling suit alleges K&L Gates used these techniques to increase fees. ABA Journal. Available at: https://tinyurl.com/yjxtpj29 (accessed 13 May 2026).
ZhangCAtasuAAyerT, et al. (2020) Truthful mechanisms for medical surplus product allocation. Manufacturing & Service Operations Management22(4): 735–753.
40.
ZhangHAydinGParkerRP (2022) Social responsibility auditing in supply chain networks. Management Science68(2): 1058–1077.
41.
ZhangHZeniosS (2008) A dynamic principal–agent model with hidden information: Sequential optimality through truthful state revelation. Operations Research56(3): 681–696.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
