LLM Detection as an Intervention: Downstream Impact under Strategic User Behavior Meena Jagadeesan1,3 , Tatsunori Hashimoto1 , and Jon Kleinberg2 1
Stanford University Cornell University 3 University of Pennsylvania 2
arXiv:2607.19300v1 [cs.AI] 21 Jul 2026
July 22, 2026
Abstract As LLM adoption becomes more widespread, there is a growing interest in detecting LLMgenerated content, for example through LLM detection tools and through heuristics based on language patterns. Detectors operate as an intervention that steers not only the detected attribute itself, but also downstream metrics such as LLM usage and output quality. In this work, we demonstrate how imperfect LLM detectors lead to counterintuitive impacts on these downstream metrics, by distorting how users are incentivized to use LLMs in their workflow. We develop a stylized model which captures how users strategically choose how much to use the LLM and how to post-process content to reduce the detected attribute. Using this model, we show that LLM detection can counterintuitively lead humans to increase their LLM usage. Moreover, even when reducing the detected attribute improves output quality, we find that introducing an LLM detector can lead users to produce lower quality outputs. In contrast, we show that detectors result in a clean “rise-then-fall” pattern for the detected attribute, which we empirically reproduce for word frequencies on arXiv abstracts. Altogether, our work illustrates how LLM detection can distort LLM usage and output quality, uncovering failure modes when LLM detectors operate as an intervention on these downstream metrics.
1
Introduction
As large language models (LLMs) get deployed at larger scale, content is increasingly scrutinized for whether it is LLM-generated or human-generated. This has led to the deployment of LLM detection tools [Mitchell et al., 2023, Verma et al., 2024, Hans et al., 2024, Adam et al., 2026] such as GPTZero and Pangram1 in academic conferences [ICLR 2026 Program Chairs, 2026] and in education [Prothero, 2024], among other domains (Example 1). Beyond these automated tools, LLM detection is performed implicitly by society using heuristics based on language patterns (e.g., increased usage of specific words such as “delve” [Liang et al., 2025, Juzek and Ward, 2025] and stylistic patterns such as em-dashes [Wu, 2025]). Society-based detection can harm authors, for example by leading to negative perceptions of content quality [Knight et al., 2023] (Example 2). LLM detection, whether performed by institutions or by society, operates as an intervention on several downstream metrics. One such metric is LLM usage: for example, educators may deploy LLM detectors in an attempt to reduce LLM usage. Another such metric is output quality: 1
See https://gptzero.me and https://www.pangram.com/.
1
academic research institutions may deploy LLM detectors in order to increase the quality of academic publications. Yet another metric is the attribute that the detector directly penalizes. For example, the frequency of specific word patterns on arXiv [Liang et al., 2025, Geng and Trotta, 2024] empirically exhibits a “rise-then-fall” pattern, dramatically increasing after the release of ChatGPT, but then subsequently dropping in frequency in the following months [Geng and Trotta, 2025, Leiter et al., 2024], perhaps due to society becoming aware of LLM-sounding words. However, the link between LLM detection and these downstream metrics is complicated by user incentives: imperfect LLM detectors fundamentally distort how users are incentivized to integrate LLMs into their workflow. Automated and heuristic LLM detectors routinely misclassify content [Liang et al., 2023, Weber-Wulff et al., 2023] and are non-robust to small perturbations [Krishna et al., 2023, Sadasivan et al., 2025], and correctness is inherently ambiguous under human-LLM collaboration [Zhang et al., 2024]. To avoid detection, users may be incentivized to post-process LLM-generated content2 or even their own human-generated content [Wu, 2025], for example by removing instances of LLM-sounding words (Example 2). Users may also be incentivized to change how much work they delegate to the LLM, for example by deciding to perform some tasks (e.g., reference generation) manually to avoid detection (Example 1). In this work, we study this distortion of user incentives, and show how imperfect LLM detection can lead to counterintuitive impacts on downstream metrics. In our stylized model (Section 2), outputs are embedded in D-dimensions: the LLM detector flags outputs using a threshold-based classifier on the first dimension (detected attribute), but quality depends on all D dimensions. If an output is flagged by the LLM detector, the user who authored it incurs a penalty. Each user chooses how much work to allocate to an LLM, which determines the convex combination between their own natural human-generated output and their fully LLM-generated output. The user also decides how much to post-process content by reducing the detected attribute (which may help them avoid being flagged by the detector). They optimize for their utility which is a combination of output quality, the detection penalty, production costs, and post-processing costs. Using this model, we prove that LLM detection can distort both LLM usage and output quality, even though it has a clean impact on the metric that it optimizes. • LLM usage: Introducing an LLM detector can lead some users to increase their LLM usage relative to the no-detector baseline (Section 3; Figure 1a). Specifically, we show sufficient conditions under which there exist users who increase LLM usage under detection (Theorem 1), as well as necessary conditions (Theorem 2) that match in the case where quality is linear in LLM usage. While one may expect that detection would lead users to reduce LLM usage to lower the detected attribute, our result shows the opposite can occur. The intuition is that post-processing can remove some quality-reducing characteristics produced by the LLM, which may incentivize users to selectively take greater advantage of those characteristics where LLM-generated content may be higher quality than human-generated content (Example 3). • Output quality: Introducing an LLM detector can lead users to produce lower-quality outputs relative to the baseline, even when the detected attribute is quality-reducing (Section 4; Figure 1b). We prove sufficient conditions under which there exist users who produce lower-quality outputs under detection (Theorem 3). While one may expect the LLM detector to improve quality when detection penalizes a quality-reducing characteristic, our result shows that detection can counterintuitively reduce quality. The intuition is that detection can lead users to under-use the LLM, and thereby lose the (non-detected) dimensions in which LLM use can increase quality 2
https://www.quetext.com/blog/top-prompts-humanize-ai-generated-text
2
(Example 4).3 • Detected attribute: Our model reproduces the empirically observed “rise-then-fall” pattern for the detected attribute [Geng and Trotta, 2025, Leiter et al., 2024] (Section 5; Figure 1c). We prove the detected attribute always weakly increases when the user is given access to an LLM and then weakly decreases with the detector (Theorem 4). From an empirical perspective, we provide more systematic empirical validation of this pattern. Moving beyond the specific word lists studied in Geng and Trotta [2025] and Leiter et al. [2024], we show the “rise-then-fall” pattern has increased in prevalence in the LLM era relative to prior time windows over the past decade (Figure 2). Altogether, our work illustrates the unintended impacts of LLM detection, when accounting for how it shapes user workflow decisions. More broadly, these distortion results uncover key failure modes when institutions deploy detectors to intervene on LLM usage and output quality.
1.1
Related Work
Our model builds on the literature on strategic classification and human-AI collaboration. Strategic classification. A vast theoretical literature on strategic classification studies how users strategically change their features to improve their classification outcomes (see [Rosenfeld, 2024, Podimata, 2025] for surveys). One line of work focuses on how users can “game” the classifier to shift the features of their input without improving their true outcome (e.g., [Hardt et al., 2016, Dong et al., 2018, Hu et al., 2019, Milli et al., 2019, Ghalme et al., 2021, Bechavod et al., 2022]). The typical focus is on classifiers that perform well under gaming. Another line of work focuses on how users can take actions that not only change their features but also “improve” their true outcome (e.g., [Kleinberg and Raghavan, 2020, Alon et al., 2020]), investigating how to account for and disentangle gaming and improvement (e.g., [Miller et al., 2020, Shavit et al., 2020, Haghtalab et al., 2020, Ahmadi et al., 2022]). Our model of post-processing directly builds on the model for gaming in Hardt et al. [2016]. Similar to the improvement models, we capture how changing the detected attribute affects quality. A distinguishing feature of our work is that we combine post-processing with human-AI collaboration, showing how this joint decision fundamentally shapes user incentives and detector performance along downstream metrics. More broadly, our work contributes to a growing literature on the strategic behaviors in the context of LLMs. This includes the strategic LLM usage on online platforms [Yao et al., 2024, Ali et al., 2025, Keinan and Ben-Porat, 2026], the strategic impacts of LLMs in markets [Lucier et al., 2026, Fish et al., 2024], and strategic LLM manipulations in hiring [Cohen et al., 2025]. Our work also fits into a broader research perspective of viewing predictions as interventions in social systems [Liu et al., 2025]. Human-AI collaboration. A vast theoretical literature on human-AI collaboration studies how to design and evaluate human-AI teams. These works consider many models: for example, models based on presenting subsets (e.g., [Straitouri et al., 2023, Donahue et al., 2024, Hullman et al., 2025]), delegation (e.g., [Lai et al., 2022, Greenwood et al., 2025]), and learning over time (e.g., [Collina et al., 2025, Noorani et al., 2026]). A key desideratum is complementarity (e.g., [Bansal et al., 2021, Donahue et al., 2022, Rastogi et al., 2022]), which captures that the human-LLM team must perform better than either agent can perform in isolation. Our model takes a simplified view of human-AI 3
The conditions in Theorem 3 do not satisfy the necessary conditions in Theorem 2, meaning that LLM detection weakly decreases LLM usage.
3
collaboration as interpolation; a distinguishing feature is that we combine human-AI collaboration with post-processing. Our model exhibits complementarity in idealized cases, but we show LLM detection can compromise complementarity (Figure 1b; Theorem 3).
2
Model
We develop a stylized model which captures the following key features of user incentives under LLM detection. First, the detector is correlated with some, but not all, aspects of output quality. Second, users can assign fractional parts of the task to the LLM. Third, users can post-process their outputs to try to avoid detection. Finally, users are heterogeneous in terms of ability level and production costs.
2.1
Output Detection and Quality
We embed outputs z into RD . Outputs are detected as being LLM-generated on the basis of one of the dimensions, which we take without loss of generality to be the first dimension. We consider threshold-based detectors of the form F (z) = 1[z1 > ν], which predict whether a given z ∈ RD was generated by an LLM. The other D − 1 dimensions thus capture attributes of the content that contribute to content quality (and may be affected by LLM use) but are independent of detection. The user faces a penalty β > 0 from being detected. The case of no LLM detector can be embedded into this model as either having zero penalty (β = 0) or having an infinite threshold (ν = ∞), or both. P Quality is measured by a separable function Q(z) := D i=1 Qi (zi ). Each Qi is twice continuously differentiable and concave. Moreover, Q1 is weakly increasing or weakly decreasing, capturing whether the detected attribute is positively or negatively correlated with quality.
2.2
User Types
Each user is specified by a type t = (ht , ℓt , γ t ) where4 : • The human-generated output ht ∈ RD captures what the user would generate without the LLM. • The LLM-generated output ℓt ∈ RD captures what the user would generate if they fully automate output generation using the LLM. • The human-generated production cost γ t ≥ 0 captures how much more expensive it is to produce t human-generated content LLM-generated content ℓt . t ht than t The type space is T = (h , ℓ , γ ) ∈ RD × RD × R≥0 | ℓt1 > ht1 , which assumes that the detected attribute is higher for the LLM-generated output than for the human-generated output.
2.3
User Workflow Decisions
Each user decides how to allocate work to the LLM vs. to themselves, and how to post-process their output to avoid detection. They derive value from quality, but face penalty β > 0 from detection. Work allocation. The user chooses a fraction α ∈ [0, 1] of the task to outsource to the LLM, which produces outputs according to the convex combination mt (α) = α · ℓt + (1 − α) · ht . The user pays production cost γ t · (1 − α) that scales with the fraction of the task that they allocate to themselves. For notational convenience, let mti (α) = (mt (α))i for i ∈ [D]. 4
Quality Q(ht ) is affected by the user’s ability, and Q(ℓt ) − Q(ht ) captures the quality change from using the LLM.
4
Post-processing. For post-processing, users can decide to decrease any of the coordinates of their output mt (α) to produce a final output z ′ ∈ RD , facing a cost for these adjustments. This postprocessing produces gaming costs that are specified by a function C : z, z ′ ∈ RD | zi′ ≤ zi ∀i ∈ [D] → R≥0 , where C(z, z ′ ) captures the cost of post-processing output z into an output z ′ with weakly P ′ lower coordinates. Gaming costs are separable (C(z, z ′ ) = D i=1 Ci (zi , zi )). We consider two cases: (a) finite costs C where each Ci is finite and twice-continuously differentiable up to the boundary, and (b) infinite costs C ∞ where Ci (zi , zi′ ) = ∞ when zi ̸= zi′ . In the case of finite costs, we place the following additional assumptions on each component: (A1) For any zi ̸= zi′ , costs exceed quality improvements (i.e., Ci (zi , zi′ ) > Qi (zi′ ) − Qi (zi )). This means that post-processing is not incentivized if detection penalties are zero (Lemma 5). (A2) Ci (zi , zi′ ) is strictly decreasing in zi′ and strictly increasing in zi . (A3) Ci (zi , zi′ ) is nonnegative, and is 0 if and only if zi′ = zi . (A4) For any zi′ , the costs Ci (zi , zi′ ) approaches ∞ as zi → ∞. (A5) For any zi′′ , it holds that the utility supzi ≥zi′′ (Qi (zi′ ) − Ci (zi , zi′ )) approaches −∞ as zi′ → −∞. Utility-optimization. Users derive utility from quality, pay costs for production and postprocessing, and face a penalty if they are detected. Given a work allocation α and final output z such that zi ≤ mti (α) for all i ∈ [D], the utility of a user with type t is: U t (α, z; β, ν, Q, C) :=
Q(z) | {z }
output quality
− β · 1[z1 > ν] − γ t · (1 − α) − | | {z } {z } detection penalty
production costs
C(mt (α), z) | {z }
.
post-processing costs
The user chooses a work allocation and post-processed output to maximize their utility: (αt (β, ν; Q, C), z t (β, ν; Q, C)) := argmaxα∈[0,1],z∈RD |∀i∈[D]:zi ≤mti (α) U t (α, z; β, ν, Q, C). We show this optimization program is well-defined in Appendix C. We assume users first tiebreak in favor of lower values of αt , and then tiebreak in favor of lower values of z1t . Let (αt (∅; Q, C), z t (∅; Q, C)) := (αt (0, ∞; Q, C), z t (0, ∞; Q, C)) capture the case of no LLM detector.
2.4
Illustrative Examples
We discuss how to instantiate our model in the context of two illustrative examples. Example 1. Institutions such as schools [Prothero, 2024], academic conference committees [ICLR 2026 Program Chairs, 2026], and grant agencies5 increasingly use tools such as GPTZero or Pangram to detect if authors are producing LLM-generated content. Let z1 denote characteristics used for detection: for example, if the detection process focuses on hallucinated references, then first attribute z1 may capture the estimated number of hallucinated references. Such detectors are often non-robust to superficial changes such as paraphrasing [Krishna et al., 2023], and may misclassify content written by non-native English writers [Liang et al., 2023]. Authors may thus post-process their LLM-generated content or human-generated content, facing a time-based cost C for doing so. Authors may also opt to manually perform steps in the research process, such as reference generation or writing, which affects their production cost γ t · (1 − α). 5
See https://grants.nih.gov/grants/guide/notice-files/NOT-OD-25-132.html.
5
(a) LLM usage
(b) Output quality
(c) Detected attribute
Figure 1: Impact of LLM detector on LLM usage (left), output quality (middle), and the detected attribute (right). Quality is linearly decreasing in the detected dimension (i.e., the detector targets quality-reducing characteristics), and linearly increasing in the other dimension. The plot shows how the presence of the LLM detector can lead users to increase their LLM usage relative to the no-detector baseline (Theorem 1; Example 3), can lead users to produce lower-quality content than the no-detector baseline (Theorem 3; Example 4), and leads to a clean “rise-then-fall” pattern for the detected attribute (Theorem 4; Figure 2). Example 2. Society also implicitly forms opinions about whether content is LLM-generated by using heuristics. Detection may be performed based on stylistic quirks: let z1 denote the frequency of stylistically LLM-sounding words such as “delve” [Juzek and Ward, 2025, Liang et al., 2025] or stylistic patterns such as em-dashes [Wu, 2025]. Alternatively, detection may be done based on polish: let z1 denote the level of polish of the content (e.g., lack of typos). The penalty β captures the implicit reputational cost to the authors, coming from perceived correlations between LLM usage and author identity [Lepp and Smith, 2025], content quality [Knight et al., 2023], or authenticity. If detection is based on stylistic quirks, authors may manually remove some of these quirks in LLM-generated content, or even in fully human-generated content if they happen to naturally adopt the same patterns [Phillips, 2025]. They may also post-process content by prompting an LLM to avoid these patterns.6 If detection is based on polish, then authors may introduce typos into outputs using automated tools.7 Authors may also opt to use models for brainstorming rather than for writing, which affects their production cost γ t · (1 − α).
3
Impact on LLM Usage
At first glance, it may seem that introducing an LLM detector would weakly decrease LLM usage αt (β, ν; Q, C) relative to the no-detector baseline αt (∅; Q, C). Since we assume that the detected attribute for a user’s LLM-generated content is strictly larger than the detected attribute for the user’s human-generated content (ℓt1 > ht1 ), LLM detection may seem to lead users to reduce their LLM usage in order to lower the detected attribute. Our results in this section illustrate how this argument breaks down: we find that introducing an LLM detector can counterintuitively lead some users to increase their LLM usage. 6 7
See https://www.quetext.com/blog/top-prompts-humanize-ai-generated-text See https://sinceerly.com
6
3.1
Sufficient condition for increase in LLM usage
The following result shows sufficient conditions under which there exists some user type t that increases their LLM usage relative to the no-detector baseline. Theorem 1. Fix ν < ∞, Q, C. If the costs C are finite and there exists z1u > z1l > ν such that: ′ u ′ ′ l ′ max Q (z ) − C (z , z ) − max Q (z ) − C (z , z ) > Q′1 (z1l ) · (z1u − z1l ), (1) 1 1 1 1 1 1 1 1 1 1 ′ ′ z1 ≤ν
z1 ≤ν
then there exists a type t ∈ T and a penalty threshold β̄ > 0 such that the presence of the detector strictly increases LLM usage: αt (β, ν; Q, C) > αt (∅; Q, C) for all β > β̄. Theorem 1 (Figure 1a) shows conditions under which the presence of the detector strictly increases LLM usage for some user type. The condition (1) is based on the after-post-processing utility maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )). This captures a user’s utility from dimension 1 if they start with content z1 , decide to post-process their content to fall below the boundary, and then optimally post-process their content to maximize their utility. The after-post-processing utility is always weakly decreasing in z1 , because costs increase from being further away from the boundary (Lemma 4). This means that the left-hand-side is always negative, so the condition is violated when the quality Q1 is weakly increasing in z1 . When Q1 is weakly decreasing, can be restated as the condition ′ u ′ ′ l ′ ′ l u ′ ′ | maxz1 ≤ν (Q1 (z1 ) − C1 (z1 , z1 )) − maxz1 ≤ν Q1 (z1 ) − C1 (z1 , z1 ) | < |Q1 (z1 ) · (z1 − z1l )|: this requires the after-post-processing utility decreases at a slower rate than quality on the interval [z1l , z1u ]. k3 To see that (1) is achievable, let Q1 (z1 ) = k1 − k2 z1 , let C1 (z1 , z1′ ) = k2 (z1 − z1′ ) + 1+e z1 (1 − ′ ′ 2 −(z −z ) 1 1 e ) + k4 (z1 − z1 ) , and let ν = 0. As long as k2 is sufficiently large, k3 is sufficiently small, and k4 is sufficiently small, this setup satisfies (1) (Proposition 1 in Appendix D.2). Observe that the quality is linear and weakly decreasing in the detected attribute z1 , and the costs have a linear structure with exponential and quadratic perturbations. Proof sketch of Theorem 1. The intuition is as follows and is depicted in Figure 1a.8 When the penalty β is sufficiently high, users post-process their content to avoid detection. Users choose their work allocation α taking into account that they will post-process their content. Since (1) ensures that Q1 is weakly decreasing, post-processing removes quality-reducing characteristics arising from LLM usage. When the LLM-generated content is higher quality than human-generated content along other characteristics (as captured by the second dimension), the user can take greater advantage of the LLM performing well along these characteristics under detection, without suffering from the quality-reducing characteristics. The condition (1) guarantees that the after-post-processing utility decreases sufficiently slowly that assigning more work to the LLM is worth it. The proofs in Appendix D.1 formalize this intuition. We construct a user type where ℓt1 = z1u and ht1 = z1l . We can set the second dimension so that the quality of the LLM-generated output slightly exceeds the quality of the human-generated output (i.e., Q2 (ℓt2 ) > Q2 (ht2 ) with a small gap). We set the production costs (γ t ≈ −Q′1 (z1l )(z1u − z1l )) to ensure that the user will not use the LLM in the no-detector baseline (i.e., αt (∅; Q; C) = 0). The condition in (1) ensures that when there is a detector, the user achieves greater utility from fully allocating their work to the LLM (i.e., α = 1) than from not using the LLM (i.e., α = 0), so the user will at least partially use the LLM. 8
We focus on an intuitive 2-d construction from Theorem 8, rather than the 1-d construction from the proof of Theorem 1.
7
Illustrative example. To help distill the intuition from the proof, we provide an illustrative example. Example 3. While LLMs exhibit stylistic quirks (e.g., overusage of the word “delve” and em-dash) or make errors in terms of references or facts, human authors also exhibit some of these characteristics to a lesser degree. Without a detector, even when the LLM is slightly more skilled at producing interesting arguments than many authors, authors may decide to produce outputs themselves to reduce stylistic quirks and errors. When the detector catches not only the LLM-generated content but also the human-generated content produced by the author [Wu, 2025, Phillips, 2025, Liang et al., 2023], authors may post-process all content to remove stylistic quirks and to correct errors. Given that they have to do this post-processing anyway, authors may be incentivized to use an LLM to take advantage of its interesting arguments. Implications for institutions. Theorem 1 highlights that while institutions (e.g., educators) may deploy LLM detectors in an effort to reduce LLM usage, this can backfire and lead some users to use the LLM more. Due to the availability of post-processing as an option for users, this result holds even in the extreme case where penalty becomes arbitrarily severe (β → ∞), so institutions cannot even rely on severe penalties to reduce incentives for LLM usage.
3.2
Necessary condition for increase in LLM usage
To complement Theorem 1, we derive necessary conditions under which there exists a user type that increases their LLM usage relative to the no-detector baseline.9 Theorem 2. Fix β > 0, ν < ∞, Q, C. If there exists a type t ∈ T such that the presence of the detector strictly increases LLM usage αt (β, ν; Q, C) > αt (∅; Q, C), then gaming costs C are finite and there exist z1u > z1l > ν such that: ′ u ′ ′ l ′ max Q (z ) − C (z , z ) − max Q (z ) − C (z , z ) > Q1 (z1u ) − Q1 (z1l ). (2) 1 1 1 1 1 1 1 1 1 1 ′ ′ z1 ≤ν
z1 ≤ν
The condition (2) in Theorem 2 has a similar structure to the condition (1) from the sufficient condition, but the right-hand side is changed from the first-order approximation Q′1 (z1l )(z1u − z1l ) to the difference Q1 (z1u ) − Q1 (z1l ). These conditions are equivalent when Q1 is linear, meaning that Theorems 1 and 2 fully characterize when there exists a user type where detection leads to greater LLM usage. However, these conditions can differ slightly in the nonlinear case.10 We defer the proof to Appendix D.3. Proof sketch of Theorem 2. The intuition for Theorem 2 is as follows. It is easier to show the contrapositive: if gaming costs are infinite or if (2) is not satisfied, then the presence of the detector weakly decreases LLM usage for all user types. Intuitively, when gaming costs are infinite, then the users do not post-process their content, so the only way that they can avoid detection is through reducing LLM usage, and LLM detection thus leads to reduced LLM usage. When gaming costs are finite, if (2) is not satisfied, the after-post-processing utility maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) decreases sufficiently quickly in z1 that it is not worth it to take greater advantage of any characteristics where the LLM-generated content outperforms human-generated content. 9
Note that the necessary condition is more general, since it provides a penalty-independent condition that applies to every value of β, rather than only for sufficiently large β. 10 As a sanity check, recall that since Q1 is assumed to be concave, we know that Q′1 (z1l )(z1u − z1l ) ≥ Q1 (z1u ) − Q1 (z1l ), meaning that the sufficient condition implies the necessary condition as expected.
8
The proof, which is formalized in Appendix D.3, leverages a partial characterization of the optimal user workflow decisions for general user types (Appendix C). Two key technical complexities arise: (1) users may be incentivized to post-process beyond the threshold, and (2) the set of work allocations where post-processing is incentivized may not be an interval. We nonetheless are able to show the optimal work allocation falls within a restricted set of possible values (Theorem 7). In contrast, the case where gaming costs are infinite (C = C ∞ ) is cleaner because there is no post-processing (Theorem 6). Clean cases where LLM detection weakly decreases LLM usage. As a consequence of Theorem 2, we can derive several cases where LLM detection does not increase LLM usage for any user. Corollary 1. Fix Q, β, ν, and C. Suppose that at least one of the following conditions holds: 1. Gaming costs C = C ∞ are infinite. 2. Quality Q1 is weakly increasing. ∂ 2 C (z ,z ′ ) 3. Gaming costs C satisfy the mixed partial condition ∂z11 ∂z1 ′ 1 ≤ 0 for all z1′ ≤ z1 . 1
For any type t, the detector weakly decreases LLM usage: αt (β, ν; Q, C) ≤ αt (∅; Q, C). Implications for institutions. Corollary 1 provides conditions under which institutions do not need to worry about whether LLM detection will backfire in terms of LLM usage. The first condition illustrates the benefits of robust LLM detectors, but does not reflect current detectors which are vulnerable to post-processing (e.g., [Krishna et al., 2023]). The second condition illustrates potential benefits of detecting using quality-improving characteristics. While this condition is unlikely to be met when detecting on the basis of stylistic quirks or factual errors, it may be met by detection on the basis of document polish.11 The third condition is more technical, and may be difficult to control via detector design.
4
Impact on Quality
When the detected attribute is negatively correlated with output quality (i.e., Q1 is weakly decreasing in z1 ), one may expect the LLM detector to improve quality since it penalizes quality-reducing characteristics. However, the results in this section show how this argument breaks down. Specifically, we show that even when the clean cases from Corollary 1 do apply, LLM detection can still distort output quality, leading users to produce lower-quality content than the no-detector baseline. Decrease in output quality. The following result constructs sufficient conditions under which there exist user types who produce strictly lower-quality outputs than in the no-detector baseline. Theorem 3. Fix β > 0, ν < ∞, Q, and C, and suppose that at least one of the three conditions in Corollary 1 holds. If gaming costs C are finite, then suppose also that ∇1 (C1 (ν, ν)) > max(0, −Q′1 (ν)). Suppose also D ≥ 2, that there exists a dimension 2 ≤ i′ ≤ D such that Qi′ is non-constant. Then, the presence of the detector decreases quality for some user type tD : that is Q(z tD (β, ν; Q, C)) < Q(z tD (∅; Q, C)). 11
That being said, there may be practical barriers to adopting detectors which penalize LLM characteristics which improve quality.
9
Theorem 3 (Figure 1b) illustrates how introducing an LLM detector can hurt output quality, even when Q1 is weakly decreasing. The conditions in Theorem 3 build on the clean cases from Corollary 1 where LLM detection weakly reduces LLM usage. When gaming costs are finite, we place the additional condition that the marginal costs of post-processing are sufficiently large close to the boundary. As a concrete example, note that for any linear quality function Q1 which is weakly decreasing in the detected attribute, it is easy to see the conditions in Theorem 3 are satisfied for linear costs C1 (z1 , z1′ ) = (−Q′1 (ν) + ϵ) · (z1 − z1′ ) for any ϵ > 0 as well as for infinite costs C = C ∞ . Proof sketch of Theorem 3. The intuition is as follows and is depicted in Figure 1b. The idea is that quality increase from post-processing can be offset by decrease in LLM usage. Specifically, suppose that the LLM-generated content is higher quality than human-generated content on nondetected characteristics (as captured by the second dimension). We take this quality gap to be small enough that users strictly reduce LLM usage under detection. The quality gap needs to be large enough that users create LLM-generated content in the no-detector baseline, and the gap also needs to be large enough that reducing LLM usage reduces output quality enough to offset any quality increase from post-processing. The proof is in Appendix E. Illustrative examples. To distill the intuition underpinning Theorem 3, we provide illustrative examples for how the detector can lead to decreased quality. First, we consider the case where the quality is negatively correlated with the detected attribute, where the intuition for the quality decrease is more subtle. Example 4. Like in Example 3, consider detectors based on stylistic quirks (e.g., overusage of the word “delve”) or errors in terms of references or facts; however, suppose that the detector is much more conservative and does not flag content produced with a sufficient level of human collaboration (even though it flags fully LLM-generated content). Without a detector, if the LLM is sufficiently more skilled at producing interesting arguments than the human author, the author may produce LLMgenerated content. With detection, if post-processing is costly, authors may instead be incentivized to use the LLM less, leading to content with less interesting arguments but also a lesser degree of stylistic quirks. If the quality reduction from losing interesting arguments is sufficiently large relative to the quality gain from mitigating stylistic quirks, detection would reduce content quality. Next, we turn to the case where quality is positively correlated with the detected attribute. In this case, the intuition is simpler: the quality decrease can come directly from post-processing. Example 5. Content generated by LLMs tends to be highly polished relative to human-generated content. When polish is used for detection, users may be incentivized to reduce the polish of their LLMgenerated outputs, for example using automated tools to introduce typos.12 This type of post-processing can lead users to produce lower-quality outputs than if there had not been a detector. Implications for institutions. Theorem 3 illustrates that institutions cannot assume that detection will translate to improvements in downstream output quality, regardless of whether the detector penalizes quality-reducing or quality-increasing attributes. In Appendix E, we also show that there exist types where LLM detection increases quality and where LLM detection leads to no change in quality relative to the no-detector baseline. This illustrates that detection has a heterogeneous impact on quality across users. 12
See https://sinceerly.com/.
10
(a) Counts of rise-then-fall (RTF) patterns
(b) Word frequency curve
Figure 2: Empirical analysis of word frequencies on arXiv abstracts (Section 5.2). The top 100 words with the greatest change in each 3-year time window are computed. The left figure counts the number of style words and topic words exhibiting a “rise-then-fall” (RTF) pattern, and the total number of style words, over five trials with 2 standard errors. The right figure illustrates 4 example style words from the 2022-2025 window exhibiting the “rise-then-fall pattern”. The full word list is deferred to Appendix G. These results show how the “rise-then-fall” pattern became significantly more prevalent in the LLM era (2022-2025), relative to prior time windows.
5
Impact on Detected Attribute
In contrast with the distortion from Section 3 and Section 4, we show that LLM detection has a clean impact on the detected attribute, reproducing an empirical “rise-then-fall” pattern.
5.1
Theoretical Analysis
We prove that the detected attribute always weakly increases when LLMs are introduced into the world, and then always weakly decreases when an LLM detector is deployed. We also construct a user type for which both of these inequalities are strict. Theorem 4. Fix β > 0, ν < ∞, Q, and C. For any type t, the presence of the LLM weakly increases the detected attribute (i.e., ht1 ≤ z1t (∅; Q, C)), and the presence of the detector weakly decreases the detected attribute (i.e., z1t (∅; Q, C) ≥ z1t (β, ν; Q, C)). There exists a type t for which both of these inequalities are strict. Theorem 4 shows that the detected attribute always follows a clean pattern, thus confirming that LLM detection does not distort the metric that it optimizes. We defer the proof to Appendix F.
5.2
Empirical Analysis: Word Frequency on ArXiv Abstracts
To complement Theorem 4, we empirically show that the LLM era exhibits a significantly greater prevalence of the rise-then-fall pattern for style words in arXiv papers [arXiv.org submitters, 2024]. Our analysis builds on the analysis in Liang et al. [2025], Geng and Trotta [2025].
11
Setup. We summarize the empirical setup, deferring details to Appendix G.13 In each of 5 trials, we sample 3000 abstracts per month from the cs category on arXiv between 1/1/2013 and 12/31/2025 [arXiv.org submitters, 2024]. We pre-process each abstract to build a vocabulary V . We build nine, 3-year time windows of the form [10/1/s, 9/30/(s + 3)], where s ∈ {2014, 2015, . . . , 2022}. For each time interval s: s which captures the • Top 100 words: For every word w ∈ V , we compute a reference probability rw s fraction of words in [10/1/(s), 9/30/(s + 1)] which are equal to w. Let Ntotal be the number of s words in [10/1/(s + 1), 9/30/(s + 2)], and let N (w) be the number of instances of word w ∈ V . s s ) = N s (w)]. We then select For each word, we compute the likelihood ℓs (w) := P[Bin(Ntotal , rw s the 100 words with the lowest values of ℓ (w). This produces a set W s of words.14
• Classification: For each word w ∈ W s , we use an LLM judge to classify the word as “style” (J(w) = S) or “topic” (J(w) = T ). We also determine whether the word fits a “rise-then-fall” pattern in the interval [10/1/s, 9/30/(s + 3)] looking at the gap between the start (and end) versus the maximum and the number of sign changes. Let Rs (w) = 1 if w fits the rise-then-fall pattern in this interval, and let Rs (w) = 0 otherwise. For each value of s, we compute the number of words in different subcategories based on the value of Rs (w) and J(w). Results. Figure 2a shows that the number of style words in the top 100 words fitting the “risethen-fall” pattern substantially increases in the 2022-2025 relative to every other window in the preceding eight three-year time windows. This illustrates that high prevalence of the “rise-then-fall” pattern is unique to the LLM era. Moreover, the number of topic “rise-then-fall” words changes much less dramatically, highlighting how this trend is unique to style words. As an illustrative example, we depict the shape of these curves in 2022-2025 for one trial in Figure 2b. Ablations and full word lists are deferred to Appendix G. Our analysis differs from prior work [Geng and Trotta, 2025] in two ways: (1) we systematically study this pattern across all words with a high degree of change, moving beyond the word lists identified in Liang et al. [2025], and (2) we compare the prevalence of the “rise-then-fall” pattern in 2022-2025 to prior windows. One possible driver of this rise-then-fall pattern is that users strategically change their workflow decisions in response to LLM detection, along the lines of our theoretical analysis (Theorem 4). However, we note our analysis does not disentangle a causal claim. Other factors may have contributed to the rise-then-fall pattern, including newer LLMs using these words less frequently.
6
Discussion
We study how LLM detection affects downstream metrics, when taking into account user incentives. Using a stylized model, we show LLM detection can counterintuitively increase LLM usage, and prove sufficient conditions and necessary conditions for this phenomenon which are matching when quality is linear. We also show that LLM detection can lead to reduced output quality, even when the detected attributes are quality-reducing. In contrast, LLM detection has a clean impact on the metric that it optimizes, and our model reproduces an empirically observed “rise-then-fall” pattern. 13
The code is available at https://github.com/mjagadeesan/detection-analysis-empirical. This builds on a prior approach [Kleinberg, 2016, Monroe et al., 2008]. Specifically, like these works, we consider s a reference distribution with words sampled i.i.d. from a categorical distribution {rw }w∈V , and we compute the s probability ℓ (w) of the next year’s observed word count for w under this distribution. 14
12
Our findings reveal key failure modes when current detection practices are used as an intervention to steer these downstream metrics. Specifically, our results show that detection through qualityreducing characteristics can induce the opposite effect on LLM usage and output quality that an institution may have intended. This effect persists even when the penalty becomes arbitrarily severe. On the flip side, our results suggest that detecting via quality-improving characteristics would ensure that detection weakly decreases LLM usage, although it would not remove the distortion in output quality. Model discussion and limitations. Our model captures key aspects of user incentives under LLM detection, including detection quality effects, fractional work allocation, post-processing, and user heterogeneity. However, our model is stylized and makes several simplifications. For example, we assume that quality Q and gaming costs C are separable across dimensions. Moreover, we assume that users exactly know the detection boundary, following standard assumptions from strategic classification (e.g., [Hardt et al., 2016]). Finally, we assume that post-processing costs are identical for human-generated and LLM-generated content. An interesting direction for future work would be to relax these assumptions and incorporate further practical complexities into our model.
7
Acknowledgments
We would like to thank Luke Bailey and Sanmi Koyejo for useful feedback on the paper. MJ was partially supported by a SAIL postdoctoral fellowship. TH was supported by a grant by HAI, DSO labs, gifts from Open Philanthropy, Amazon, Schmidt Sciences, the Tianqiao and Chrissy Chen Foundation and a grant under the NSF CAREER IIS-2338866, ONR N00014-24-1-2609, and DARPA Cooperative Agreement HR00112520013. JK was supported in part by a Simons Collaboration grant, AFOSR grant FA9550-23-1-0410, and a grant from the MacArthur Foundation. This work does not necessarily reflect the position or policy of the government and no official endorsement should be inferred.
References George Alexandru Adam, Alexander Cui, Edwin Thomas, Emily Napier, Nazar Shmatko, Jacob Schnell, Jacob Junqi Tian, Alekhya Dronavalli, Edward Tian, and Dongwon Lee. Gptzero: Robust detection of llm-generated texts. CoRR, abs/2602.13042, 2026. doi: 10.48550/ARXIV.2602.13042. URL https://doi.org/10.48550/arXiv.2602.13042. Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On classification of strategic agents who can both game and improve. In L. Elisa Celis, editor, 3rd Symposium on Foundations of Responsible Computing, FORC 2022, Cambridge, MA, USA, June 6-8, 2022, LIPIcs, pages 3:1– 3:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi: 10.4230/LIPICS.FORC.2022.3. URL https://doi.org/10.4230/LIPIcs.FORC.2022.3. S. Nageeb Ali, Nicole Immorlica, Meena Jagadeesan, and Brendan Lucier. Flattening supply chains: When do technology improvements lead to disintermediation? CoRR, abs/2502.20783, 2025. doi: 10.48550/ARXIV.2502.20783. URL https://doi.org/10.48550/arXiv.2502.20783. Tal Alon, Magdalen Dobson, Ariel D. Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 13
2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1774–1781. AAAI Press, 2020. doi: 10.1609/AAAI.V34I02.5543. URL https://doi.org/10.1609/aaai.v34i02.5543. arXiv.org submitters. arxiv dataset, 2024. URL https://www.kaggle.com/dsv/7548853. Gagan Bansal, Tongshuang Wu, Joyce Zhou, Raymond Fok, Besmira Nushi, Ece Kamar, Marco Túlio Ribeiro, and Daniel S. Weld. Does the whole exceed its parts? the effect of AI explanations on complementary team performance. In Yoshifumi Kitamura, Aaron Quigley, Katherine Isbister, Takeo Igarashi, Pernille Bjørn, and Steven Mark Drucker, editors, CHI ’21: CHI Conference on Human Factors in Computing Systems, Virtual Event / Yokohama, Japan, May 8-13, 2021, pages 81:1–81:16. ACM, 2021. doi: 10.1145/3411764.3445717. URL https://doi.org/10.1145/ 3411764.3445717. Yahav Bechavod, Chara Podimata, Zhiwei Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Proceedings of Machine Learning Research, pages 1691–1715. PMLR, 2022. URL https://proceedings.mlr.press/v162/bechavod22a.html. Lee Cohen, Connie Hong, Jack Hsieh, and Judy Hanwen Shen. Two tickets are better than one: Fair and accurate hiring under strategic LLM manipulations. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025, Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025. URL https://proceedings.mlr.press/v267/cohen25a.html. Natalie Collina, Surbhi Goel, Varun Gupta, and Aaron Roth. Tractable agreement protocols. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1532–1543. ACM, 2025. doi: 10.1145/3717823.3718222. URL https://doi.org/10.1145/3717823.3718222. Kate Donahue, Alexandra Chouldechova, and Krishnaram Kenthapadi. Human-algorithm collaboration: Achieving complementarity and avoiding unfairness. In FAccT ’22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 21 - 24, 2022, pages 1639–1656. ACM, 2022. doi: 10.1145/3531146.3533221. URL https: //doi.org/10.1145/3531146.3533221. Kate Donahue, Sreenivas Gollapudi, and Kostas Kollias. When are two lists better than one?: Benefits and harms in joint decision-making. In Michael J. Wooldridge, Jennifer G. Dy, and Sriraam Natarajan, editors, Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2024, February 20-27, 2024, Vancouver, Canada, pages 10030–10038. AAAI Press, 2024. doi: 10.1609/AAAI.V38I9.28866. URL https://doi.org/10.1609/aaai.v38i9.28866. Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Éva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 55–70. ACM, 2018. doi: 10.1145/3219166.3219193. URL https://doi.org/10. 1145/3219166.3219193. 14
Sara Fish, Yannai A. Gonczarowski, and Ran I. Shorrer. Algorithmic collusion by large language models. CoRR, abs/2404.00806, 2024. doi: 10.48550/ARXIV.2404.00806. URL https://doi. org/10.48550/arXiv.2404.00806. Mingmeng Geng and Roberto Trotta. Is chatgpt transforming academics’ writing style? CoRR, abs/2404.08627, 2024. Mingmeng Geng and Roberto Trotta. Human-llm coevolution: Evidence from academic writing. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar, editors, Findings of the Association for Computational Linguistics, ACL 2025, Vienna, Austria, July 27 August 1, 2025, Findings of ACL, pages 12689–12696. Association for Computational Linguistics, 2025. Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, pages 3672–3681. PMLR, 2021. URL http:// proceedings.mlr.press/v139/ghalme21a.html. Sophie Greenwood, Karen Levy, Solon Barocas, Hoda Heidari, and Jon M. Kleinberg. Designing algorithmic delegates: the role of indistinguishability in human-ai handoff. In Itai Ashlagi and Aaron Roth, editors, Proceedings of the 26th ACM Conference on Economics and Computation, EC 2025, Stanford University, Stanford, CA, USA, July 7-10, 2025, pages 306–336. ACM, 2025. doi: 10.1145/3736252.3742533. URL https://doi.org/10.1145/3736252.3742533. Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. In Christian Bessiere, editor, Proceedings of the TwentyNinth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 160–166. ijcai.org, 2020. doi: 10.24963/IJCAI.2020/23. Abhimanyu Hans, Avi Schwarzschild, Valeriia Cherepanova, Hamid Kazemi, Aniruddha Saha, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Spotting llms with binoculars: Zeroshot detection of machine-generated text. In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Proceedings of Machine Learning Research, pages 17519–17537. PMLR / OpenReview.net, 2024. URL https://proceedings.mlr.press/v235/hans24a.html. Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, and Mary Wootters. Strategic classification. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 111–122. ACM, 2016. doi: 10.1145/2840728.2840730. URL https://doi.org/10.1145/2840728.2840730. Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In danah boyd and Jamie H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 2019, Atlanta, GA, USA, January 29-31, 2019, pages 259–268. ACM, 2019. doi: 10.1145/3287560.3287597. URL https://doi.org/10. 1145/3287560.3287597. Jessica Hullman, Yifan Wu, Dawei Xie, Ziyang Guo, and Andrew Gelman. Conformal prediction and human decision making. CoRR, abs/2503.11709, 2025. doi: 10.48550/ARXIV.2503.11709. URL https://doi.org/10.48550/arXiv.2503.11709. 15
ICLR 2026 Program Chairs. A retrospective on the iclr 2026 review process. https://blog.iclr. cc/2026/03/31/a-retrospective-on-the-iclr-2026-review-process/, 2026. Tom S. Juzek and Zina B. Ward. Why does chatgpt "delve" so much? exploring the sources of lexical overrepresentation in large language models. In Owen Rambow, Leo Wanner, Marianna Apidianaki, Hend Al-Khalifa, Barbara Di Eugenio, and Steven Schockaert, editors, Proceedings of the 31st International Conference on Computational Linguistics, COLING 2025, Abu Dhabi, UAE, January 19-24, 2025, pages 6397–6411. Association for Computational Linguistics, 2025. Gur Keinan and Omer Ben-Porat. Strategic content creation with genai: To share or not to share? In Hakim Hacid, Yoelle Maarek, Francesco Bonchi, Ido Guy, and Emine Yilmaz, editors, Proceedings of the ACM Web Conference 2026, WWW 2026, Dubai, United Arab Emirates, originally scheduled for April 13-17, 2026, rescheduled for June 29 - July 3, 2026, pages 169–180. ACM, 2026. doi: 10.1145/3774904.3792308. URL https://doi.org/10.1145/3774904.3792308. Jon Kleinberg. Temporal dynamics of on-line information streams. In Data stream management: Processing high-speed data streams, pages 221–238. Springer, 2016. Jon M. Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Trans. Economics and Comput., 8(4):19:1–19:23, 2020. doi: 10.1145/3417742. URL https://doi.org/10.1145/3417742. Samsun Knight, Yakov Bart, and Minwen Yang. Generative ai and the perceived quality of usergenerated content: Evidence from online reviews. Northeastern U. D’Amore-McKim School of Business Research Paper, (4621982), 2023. Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL http://papers.nips.cc/paper_files/paper/2023/hash/ 575c450013d0e99e4b0ecf82bd1afaa4-Abstract-Conference.html. Vivian Lai, Samuel Carton, Rajat Bhatnagar, Q. Vera Liao, Yunfeng Zhang, and Chenhao Tan. Human-ai collaboration via conditional delegation: A case study of content moderation. In Simone D. J. Barbosa, Cliff Lampe, Caroline Appert, David A. Shamma, Steven Mark Drucker, Julie R. Williamson, and Koji Yatani, editors, CHI ’22: CHI Conference on Human Factors in Computing Systems, New Orleans, LA, USA, 29 April 2022 - 5 May 2022, pages 54:1–54:18. ACM, 2022. doi: 10.1145/3491102.3501999. URL https://doi.org/10.1145/3491102.3501999. Christoph Leiter, Jonas Belouadi, Yanran Chen, Ran Zhang, Daniil Larionov, Aida Kostikova, and Steffen Eger. NLLG quarterly arxiv report 09/24: What are the most influential current AI papers? CoRR, abs/2412.12121, 2024. Haley Lepp and Daniel Scott Smith. “you cannot sound like gpt": Signs of language discrimination and resistance in computer science publishing. In Proceedings of the 2025 ACM conference on fairness, accountability, and transparency, pages 3162–3181, 2025. Weixin Liang, Mert Yüksekgönül, Yining Mao, Eric Wu, and James Zou. GPT detectors are biased against non-native english writers. Patterns, 4(7):100779, 2023. doi: 10.1016/J.PATTER.2023. 100779. URL https://doi.org/10.1016/j.patter.2023.100779. 16
Weixin Liang, Yaohui Zhang, Zhengxuan Wu, Haley Lepp, Wenlong Ji, Xuandong Zhao, Hancheng Cao, Sheng Liu, Siyu He, Zhi Huang, et al. Quantifying large language model usage in scientific papers. Nature Human Behaviour, pages 1–11, 2025. Lydia T. Liu, Inioluwa Deborah Raji, Angela Zhou, Luke Guerdan, Jessica Hullman, Daniel Malinsky, Bryan Wilder, Simone Zhang, Hammaad Adam, Amanda Coston, Benjamin Laufer, Ezinne Nwankwo, Michael Zanger-Tishler, Eli Ben-Michael, Solon Barocas, Avi Feller, Marissa Gerchick, Talia Gillis, Shion Guha, Daniel E. Ho, Lily Hu, Kosuke Imai, Sayash Kapoor, Joshua Loftus, Razieh Nabi, Arvind Narayanan, Ben Recht, Juan Carlos Perdomo, Matthew J. Salganik, Mark P. Sendak, Alexander Tolbert, Berk Ustun, Suresh Venkatasubramanian, Angelina Wang, and Ashia Wilson. Bridging prediction and intervention problems in social systems. CoRR, abs/2507.05216, 2025. doi: 10.48550/ARXIV.2507.05216. URL https://doi.org/10.48550/arXiv.2507.05216. Brendan Lucier, Nicole Immorlica, Markus Mobius, Aleksandrs Slivkins, Daniel G. Goldstein, Jake M. Hofman, Sonia Jaffe, and David M. Rothschild. Agentic markets: Equilibrium effects of improving consumer search. CoRR, abs/2603.25893, 2026. doi: 10.48550/ARXIV.2603.25893. URL https://doi.org/10.48550/arXiv.2603.25893. John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, pages 6917–6926. PMLR, 2020. URL http://proceedings.mlr.press/v119/miller20b.html. Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classification. In danah boyd and Jamie H. Morgenstern, editors, Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* 2019, Atlanta, GA, USA, January 29-31, 2019, pages 230–239. ACM, 2019. doi: 10.1145/3287560.3287576. URL https://doi.org/10.1145/ 3287560.3287576. Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D. Manning, and Chelsea Finn. Detectgpt: Zero-shot machine-generated text detection using probability curvature. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learning Research, pages 24950–24962. PMLR, 2023. URL https://proceedings.mlr.press/v202/mitchell23a.html. Burt L Monroe, Michael P Colaresi, and Kevin M Quinn. Fightin’words: Lexical feature selection and evaluation for identifying the content of political conflict. Political Analysis, 16(4):372–403, 2008. Sima Noorani, Shayan Kiyani, Hamed Hassani, and George J. Pappas. Multi-round human-ai collaboration with user-specified requirements. CoRR, abs/2602.17646, 2026. doi: 10.48550/ ARXIV.2602.17646. URL https://doi.org/10.48550/arXiv.2602.17646. Brian Phillips. Stop ai-shaming our precious, kindly em dashes—please. The Ringer, 2025. URL https://www.theringer.com/2025/08/20/pop-culture/ em-dash-use-ai-artificial-intelligence-chatgpt-google-gemini. Chara Podimata. Incentive-aware machine learning; robustness, fairness, improvement & causality. CoRR, abs/2505.05211, 2025. doi: 10.48550/ARXIV.2505.05211. URL https://doi.org/10. 48550/arXiv.2505.05211. 17
Arianna Prothero. More teachers are using ai-detection tools. here’s why that might be a problem. Education Week, 2024. URL https://www.edweek.org/technology/ more-teachers-are-using-ai-detection-tools-heres-why-that-might-be-a-problem/ 2024/04. Charvi Rastogi, Liu Leqi, Kenneth Holstein, and Hoda Heidari. A unifying framework for combining complementary strengths of humans and ML toward better predictive decision-making. CoRR, abs/2204.10806, 2022. doi: 10.48550/ARXIV.2204.10806. URL https://doi.org/10.48550/ arXiv.2204.10806. Nir Rosenfeld. Strategic ML: how to learn with data that ’behaves’. In Luz Angelica CaudilloMata, Silvio Lattanzi, Andrés Muñoz Medina, Leman Akoglu, Aristides Gionis, and Sergei Vassilvitskii, editors, Proceedings of the 17th ACM International Conference on Web Search and Data Mining, WSDM 2024, Merida, Mexico, March 4-8, 2024, pages 1128–1131. ACM, 2024. doi: 10.1145/3616855.3636453. URL https://doi.org/10.1145/3616855.3636453. Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected? stress testing AI text detectors under various attacks. Trans. Mach. Learn. Res., 2025, 2025. URL https://openreview.net/forum?id=OOgsAZdFOt. Yonadav Shavit, Benjamin L. Edelman, and Brian Axelrod. Causal strategic linear regression. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, pages 8676–8686. PMLR, 2020. URL http://proceedings.mlr.press/v119/shavit20a.html. Eleni Straitouri, Lequn Wang, Nastaran Okati, and Manuel Gomez Rodriguez. Improving expert predictions with conformal prediction. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learning Research, pages 32633–32653. PMLR, 2023. URL https://proceedings.mlr.press/ v202/straitouri23a.html. Vivek Verma, Eve Fleisig, Nicholas Tomlin, and Dan Klein. Ghostbuster: Detecting text ghostwritten by large language models. In Kevin Duh, Helena Gómez-Adorno, and Steven Bethard, editors, Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), NAACL 2024, Mexico City, Mexico, June 16-21, 2024, pages 1702–1717. Association for Computational Linguistics, 2024. doi: 10.18653/V1/2024.NAACL-LONG.95. URL https://doi.org/10.18653/v1/2024.naacl-long.95. Debora Weber-Wulff, Alla Anohina-Naumeca, Sonja Bjelobaba, Tomáš Foltỳnek, Jean Guerrero-Dib, Olumide Popoola, Petr Šigut, and Lorna Waddington. Testing of detection tools for ai-generated text. International Journal for Educational Integrity, 19(1):1–39, 2023. Daniel Wu. Some people think ai writing has a tell — the em dash. writers disagree. The Washington Post, 2025. URL https://www.washingtonpost.com/technology/2025/04/09/ ai-em-dash-writing-punctuation-chatgpt/. Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. Human vs. generative AI in content creation competition: Symbiosis or conflict? In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, 18
editors, Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Proceedings of Machine Learning Research, pages 56885–56913. PMLR / OpenReview.net, 2024. URL https://proceedings.mlr.press/v235/yao24b.html. Qihui Zhang, Chujie Gao, Dongping Chen, Yue Huang, Yixin Huang, Zhenyang Sun, Shilin Zhang, Weiye Li, Zhengyan Fu, Yao Wan, et al. Llm-as-a-coauthor: Can mixed human-written and machine-generated text be detected? In Findings of the Association for Computational Linguistics: NAACL 2024, pages 409–436, 2024.
A
LLM usage
Claude Opus 4.7 assisted us in writing code. GPT-5.4, Claude Opus 4.7, and Opus 4.6 were consulted to help gather related work, brainstorm proof ideas, and provide feedback on the writing and ideas in the paper. We also use LLM judges in our empirical analysis. All outputs were verified by the (human) authors of this paper.
B
Key objects and auxiliary lemmas
The following work allocation objects emerge in our analysis. Let α∗ ∈ [0, 1] be the minimum optimizer of maxα∈[0,1] Q(mt (α)) − γ t · (1 − α) , which we know exists because this is a continuous function over a compact set. If ht1 ≤ ν < ℓt1 , we let αgame ∈ [0, 1] be the unique value where mt1 (α) = ν. Otherwise, we define αgame := ∞. When gaming costs are finite, we also define several other objects. The function G. One key object is the function G : {z1 ≥ ν : z1 ∈ R} → R: G(z1 ) = argmaxz1′ ≤ν Q1 (z1′ ) − C1 (z1 , z1′ ) , where we tiebreak in favor of lower values. To see that G(z1 ) is well-defined, note that by (A5), we know that Q1 (z1′ ) − k1 (z1 , z1′ ) → −∞ as z1′ → −∞. The function G(z1 ) captures the post-processing decision that the user will make, should they decide to post-process their content. The sets S(β) and At (β). Another key object is the set: ′ ′ S(β) := z1 > ν | Q1 (z1 ) − max Q1 (z1 ) − C1 (z1 , z1 ) ≤ β . ′ z1 ≤ν
which captures the values for which it is worthwhile for the user to post-process their content to avoid detection. At a high-level, the user must factor not only explicit gaming costs but also the change in quality from post-processing. We also define an additional type-dependent function At (β) that reparameterizes the set S(β) into work allocation. We let: At (β) := α ∈ [0, 1] | mt1 (α) ∈ S(β) capture the set of work allocations that are in the post-processing region.
19
Domain truncation property and implicit definition V (w1 ). Finally, we also show the following domain truncation property which will enable us to apply Berge’s maximum theorem. Suppose that we have an upper bound w1 > ν on z1 . Then, we show we can also truncate the domain z1′ as follows. By (A5), we know that supz1 ≥ν (Q1 (z1′ ) − C1 (z1 , z1′ )) → −∞ as z1′ → −∞. We can thus truncate the domain to z1′ ≥ V (w1 ) where V (w1 ) ≤ ν is defined to guarantee that: for all z1′ < V (w1 ) : sup Q1 (z1′ ) − C1 (z1 , z1′ ) < inf (Q1 (ν) − C1 (z1 , ν)) . (3) z1 ∈[ν,w1 ]
z1 ≥ν
This means that: max Q1 (z1′ ) − C1 (z1 , z1′ ) = ′ max ′ z1 ≤ν
z1 ∈[V (w1 ),ν]
Q1 (z1′ ) − C1 (z1 , z1′ )
for all z1 ∈ [ν, w1 ]. Throughout the analysis, we will use the fact that we can apply Berge’s maximum theorem to maxz1′ ∈[V (w1 ),ν] (Q1 (z1′ ) − C1 (z1 , z1′ )) whenever we have an upper bound on z1 . For ease of notation, we will use this general fact without explicitly rederiving the threshold V (w1 ) on each instance.
B.1
Auxiliary lemmas
We prove a useful lemma about the structure of At (β). Lemma 1. Fix β > 0, ν < ∞, Q, and finite costs C. If Āt (β) denotes the closure of At (β), then: Āt (β) \ At (β) ⊆ {αgame } . Proof. Using the definition of S(β), we know that: ′ t ′ At (β) = α ∈ [0, 1] | mt1 (α) > ν, Q1 (mt1 (α)) − max Q (z ) − C (m (α), z ) ≤ β . 1 1 1 1 1 ′ z1 ≤ν
Consider any α ∈ [0, 1] such that α ̸∈ At (β) ∪ {αgame }. It suffices to show that there exists an t open ball around α that does not intersect At (β). By definition, we know that either m1 (α) ≤ ν or t ′ t ′ Q1 (m1 (α)) − maxz1′ ≤ν Q1 (z1 ) − C1 (m1 (α), z1 ) > β. We divide into these two cases. Case 1: mt1 (α) ≤ ν. Since we know by assumption α = ̸ αgame , we know that mt1 (α) < ν. If we take a sufficiently small open ball around Bϵ (α), we know that every α′ ∈ Bϵ (α) satisfies mt1 (α′ ) < ν. This means that Bϵ (α) ∩ At (β) = ∅ as desired. Case 2: Q1 (mt1 (α))−maxz1′ ≤ν Q1 (z1′ ) − C1 (mt1 (α), z1′ ) > β. We know that the function Q1 (mt1 (α))− maxz1′ ≤ν Q1 (z1′ ) − C1 (mt1 (α), z1′ ) is continuous in α. Thus, the pre-image of the open set (β, ∞) is open. This means that the set t ′ t ′ α ∈ [0, 1] | Q1 (m1 (α)) − max Q1 (z1 ) − C1 (m1 (α), z1 ) > β ′ z1 ≤ν
is open as desired. We prove the following structural property of G. Lemma 2. Fix finite costs C and suppose that Q1 is weakly increasing. Then, it holds that G(z1 ) = ν for all z1 ≥ ν. 20
Proof. This holds because C1 (z1 , z1′ ) is weakly decreasing in z1′ and Q1 (z1′ ) is weakly increasing in z1′ . We prove the following structural property of G. Lemma 3. Fix finite costs C such that for all z1 ≥ ν.
∂ 2 C1 (z1 ,z1′ ) ≤ 0 for all z1′ ≤ z1 . Then, it holds that G(z1 ) = ν ∂z1 ∂z1′
Proof. The case of z1 = ν follows immediately from (A1). We consider z1 > ν for the remainder of the analysis. It suffices to show that Q1 (z1′ ) − C1 (z1 , z1′ ) < Q1 (ν) − C1 (z1 , ν) for all z1′ < ν, which we can rewrite as Q1 (z1′ ) − Q1 (ν) < C1 (z1 , z1′ ) − C1 (z1 , ν). Note that by (A1), we know that Q1 (z1′ ) − Q1 (ν) < C1 (ν, z1′ ). This means that it suffices to show that: C1 (ν, z1′ ) ≤ C1 (z1 , z1′ ) − C1 (z1 , ν). Using (A3), this can be rewritten as: C1 (ν, z1′ ) − C1 (ν, ν) ≤ C1 (z1 , z1′ ) − C1 (z1 , ν), which can be rewritten as: Z ν − z1′
Z ν ∇2 C1 (ν, y)dy ≤ −
z1′
∇2 C1 (z1 , y)dy,
which can be rewritten as: Z ν z1′
(∇2 C1 (z1 , y) − ∇2 C1 (ν, y))dy ≤ 0.
We know this holds by the assumption that
∂ 2 C1 (z1 ,z1′ ) ≤ 0. ∂z1 ∂z1′
We prove that maxz ′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) is weakly decreasing in z1 . Lemma 4. Fix finite costs C. For any ν, it holds that maxz ′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) is weakly decreasing in z1 for z1 ≥ ν. Proof. For any z1′ ≤ z1 ≤ z1′′ , it holds that (Q1 (z1′ ) − C1 (z1 , z1′ )) ≥ (Q1 (z1′ ) − C1 (z1′′ , z1′ )) by (A2). This means that maxz ′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) ≥ maxz ′ ≤ν (Q1 (z1′ ) − C1 (z1′′ , z1′ )) as desired.
C
Characterization of user workflow decisions
In this section, we characterize user workflow decisions by analyzing the utility-optimization program maxz U t (α, z; β, ν, Q, C) (and showing it is well-defined). Outline. We perform this analysis for three cases: no detector (Appendix C.1), detector with infinite gaming costs (Appendix C.2), and detector with finite gaming costs (Appendix C.3). We characterize properties of these user workflow decisions. For each case, we analyze the utility-optimization program in two stages: (1) for each fixed value of α, we analyze the indirect utility maxz U t (α, z; β, ν, Q, C), and (2) we analyze the value of α that maximizes maxα∈[0,1] maxz U t (α, z; β, ν, Q, C). 21
C.1
No detector
The following result characterizes user workflow decisions for the case of no detector. Theorem 5. Fix Q and C. The optimization program maxα∈[0,1],z U t (α, z; ∅, Q, C) is well-defined, and the optimal value is given by: maxα∈[0,1],z U t (α, z; ∅, Q, C) = max Q(mt (α)) − γ t · (1 − α) . α∈[0,1]
Moreover, it holds that αt (∅; Q, C) = α∗ , and z t (∅; Q, C) = mt (α∗ ). To prove Theorem 5, we first analyze the indirect utility function. We show this is well-defined and that users will never post-process their content. Lemma 5. Fix Q and C. For any α ∈ [0, 1], the optimization program for the indirect utility maxz∈RD (U t (α, z; ∅, Q, C)) is well-defined and has a unique optimum at z ∗ = mt (α). The optimal value is given by: max (U t (α, z; ∅, Q, C)) = Q(mt (α)) − γ t · (1 − α). z∈RD
Proof. For any value of z, we know that: U t (α, z; ∅, Q, C) = Q(z) − γ t · (1 − α) − C(mt (α), z) = −γ t · (1 − α) +
D X
Qi (z) − Ci (mti (α), zi )
i=1 t
≤(1) −γ · (1 − α) +
D X
Qi (mti (α))
i=1 t
t
= Q(m (α)) − γ · (1 − α) = U t (α, mt (α); ∅, Q, C). where (1) follows from assumption (A1). This implies that mt (α) is an optimizer of maxz (U t (α, z; ∅, Q, C). We also see that the optimal value is given by: U t (α, mt (α); ∅, Q, C) = Q(mt (α)) − γ t · (1 − α). Now, we show that mt (α) is the unique optimizer. If z ∗ is an optimizer of maxz (U t (α, z; ∅, Q, C) of maxz (U t (α, z;P β, ν, Q, C), then we know that equality PD mustthold in the above chain of equations. D ∗ t ∗ This means that i=1 Qi (z ) − Ci (mi (α), zi ) = i=1 Qi (mi (α)). Applying (A1), this means that zi∗ = mti (α) for all 1 ≤ i ≤ D. We prove Theorem 5. Proof of Theorem 5. Using Lemma 5, we know that for any α ∈ [0, 1], it holds that: maxz U t (α, z; ∅, Q, C) = Q(mt (α)) − γ t · (1 − α). This function is continuous in α, and the optimization is over a compact set [0, 1], meaning that it achieves its optimum. We know that αt (∅; Q, C) = α∗ since both are tiebroken in favor of lower values by definition. The fact that z t (∅; Q, C) = mt (αt (∅; Q, C)) now follows from Lemma 5. 22
C.2
Detector in the case of infinite gaming costs
The following result characterizes user workflow decisions in the case of infinite gaming costs. Theorem 6. Fix β > 0, ν < ∞, and Q. Suppose that gaming costs C = C ∞ are infinite. The optimization program maxα∈[0,1],z U t (α, z; β, ν, Q, C ∞ ) is well-defined. Moreover, if mt1 (α∗ ) ≤ ν, it holds that αt (β, ν; Q, C ∞ ) = α∗ ; otherwise, it holds that αt (β, ν; Q, C ∞ ) ∈ {α∗ , αgame }. Finally, it holds that z t (β, ν; Q, C ∞ ) = mt (αt (β, ν; Q, C ∞ )). To prove Theorem 6, we analyze the indirect utility function. We show this is well-defined and that users will never post-process their content. Lemma 6. Fix β > 0, ν < ∞, and Q. Suppose that gaming costs C ∞ are infinite. For any α ∈ [0, 1], the optimization program for the indirect utility maxz U t (α, z; β, ν, Q, C ∞ ) is well-defined, and the optimum is uniquely achieved at z ∗ = mt (α). The optimal value is given by: maxz U t (α, z; β, ν, Q, C ∞ ) = Q(mt (α)) − β · 1[mt1 (α) > ν] − γ t · (1 − α). Proof. First, for any value of α, we claim that maxz (U t (α, z; β, ν, Q, C ∞ )) is uniquely maximized at z ∗ = mt (α). For any value of z, note that: U t (α, z; β, ν, Q, C ∞ ) := Q(z) − β · 1[z1 > ν] − γ t · (1 − α) − C ∞ (mt (α), z). This expression is equal to −∞ if z ̸= mt (α), and it is finite when z = mt (α). This proves the desired claim. This implies that maxz U t (α, z; β, ν, Q, C ∞ ) = Q(mt (α)) − β · 1[mt1 (α) > ν] − γ t · (1 − α) as desired. We prove Theorem 6. Proof of Theorem 6. By Lemma 6, we know that for any α ∈ [0, 1] it holds that: maxz U t (α, z; β, ν, Q, C) = Q(mt (α)) − β · 1[mt1 (α) > ν] − γ t · (1 − α). To optimize over α, we split into cases. Case 1: ht1 < ℓt1 ≤ ν. This means that mt1 (α)) ≤ ν for all α ∈ [0, 1]. Then we know that maxz U t (α, z; β, ν, Q, C ∞ ) = Q(mt (α))−γ t ·(1−α) for all α ∈ [0, 1]. The function Q(mt (α))−γ t ·(1− α) is a continuous function of α on a compact set [0, 1], meaning that maxα∈[0,1],z U t (α, z; β, ν, Q, C ∞ ) is well-defined. Using the tie-breaking rule specified in Section 2.3, it holds that αt (β, ν; Q, C ∞ ) = α∗ . The fact that z t (β, ν; Q, C ∞ ) = mt (αt (β, ν; Q, C ∞ )) follows from Lemma 6. Case 2: ν < ht1 < ℓt1 . This means that mt1 (α)) > ν for all α ∈ [0, 1]. Then we know that maxz U t (α, z; β, ν, Q, C ∞ ) = Q(mt (α))−γ t ·(1−α)−β for all α ∈ [0, 1]. By an analogous argument, we know that maxα∈[0,1],z U t (α, z; β, ν, Q, C ∞ ) is well-defined. The optimizer of Q(mt (α))−γ t ·(1−α)−β is the same as the optimizer of Q(mt (α)) − γ t · (1 − α), since these functions are just off by a constant shift. Using the tie-breaking rule specified in Section 2.3, it thus holds that αt (β, ν; Q, C) = α∗ . The fact that z t (β, ν; Q, C ∞ ) = mt (αt (β, ν; Q, C ∞ )) follows from Lemma 6. 23
Case 3: ht1 ≤ ν < ℓt1 . In this case, the value αgame denotes the unique value such that mt1 (αgame )) = ν. We further know that mt1 (α)) < ν for α < αgame and mt1 (α)) > ν for α > αgame . This means that: ( Q(mt (α)) − γ t · (1 − α) if 0 ≤ α ≤ αgame t ∞ maxz U (α, z; β, ν, Q, C ) = . Q(mt (α)) − γ t · (1 − α) − β if αgame < α ≤ 1. First, we show that maxα∈[0,1],z U t (α, z; β, ν, Q, C) is well-defined. A useful intermediate step is to show that maxα∈[0,1],z U t (α, z; β, ν, Q, C) = max max Q(mt (α)) − γ t · (1 − α) , max Q(mt (α)) − γ t · (1 − α) − β . α∈[0,αgame ]
α∈[αgame ,1]
This almost follows from the equation above; the only aspect we need to verify is that we can replace (αgame , 1] by [αgame , 1] in the second term. If maxα∈[αgame ,1] Q(mt (α)) − γ t · (1 − α) − β is achieved for α ∈ (αgame , 1], then we are done. If not, then we know that: sup Q(mt (α)) − γ t · (1 − α) − β = Q(mt (αgame )) − γ t · (1 − αgame ) − β α∈(αgame ,1]
< Q(mt (αgame )) − γ t · (1 − αgame ) ≤ maxα∈[0,αgame ] Q(mt (α)) − γ t · (1 − α) , so the first branch dominates anyway. This shows the intermediate step. Using the intermediate t t step, we show that maxα∈[0,αgame ] Q(m (α)) − γ · (1 − α) is well-defined. Note that the functions Q(mt (α)) − γ t · (1 − α) and Q(mt (α)) − γ t · (1 − α) − β are continuous functions of α, and in the intermediate step, we optimize these functions over compact sets. We now claim that αt (β, ν; Q, C) ∈ {α∗ , αgame } always, and αt (β, ν; Q, C) = α∗ if α∗ ≤ αgame . Using the characterization ( Q(mt (α)) − γ t · (1 − α) if 0 ≤ α ≤ αgame t maxz U (α, z; β, ν, Q, C) = , Q(mt (α)) − γ t · (1 − α) − β if αgame < α ≤ 1. we know that either (1) αt (β, ν; Q, C) lies on the boundary {0, 1, αgame }, or (2) αt (β, ν; Q, C) does not lie on the boundary {0, 1, αgame } and the derivative of Q(mt (α)) − γ t · (1 − α) − β or Q(mt (α)) − γ t · (1 − α) is 0 at αt (β, ν; Q, C). We handle the cases separately. • For (1), to show that αt (β, ν; Q, C) ∈ {α∗ , αgame }, it suffices to show that αt (β, ν; Q, C) ∈ {0, 1} \ {αgame } implies that αt (β, ν; Q, C) = α∗ . If αt (β, ν; Q, C) = 0 and αt (β, ν; Q, C) ̸= αgame , then the right derivative of Q(mt (α)) − γ t · (1 − α) at α = 0 must be non-positive, and by concavity, this means that Q(mt (α)) − γ t · (1 − α) is non-increasing, so α∗ = 0 as well. If αt (β, ν; Q, C) = 1 and αt (β, ν; Q, C) ̸= αgame , then the left derivative of Q(mt (α)) − γ t · (1 − α) at α = 1 must be non-negative, and by concavity, this means that Q(mt (α)) − γ t · (1 − α) is non-decreasing. Moreover, by the tie-breaking rule, it must hold that the inequality Q(mt (α)) − γ t · (1 − α) < Q(ℓt ) is strict for sufficiently large α < 1. Using concavity again, this means that Q(mt (α)) − γ t · (1 − α) is strictly increasing. Thus, it holds that α∗ = 1 as well. This proves the desired claim. We further show that if α∗ ≤ αgame , then it holds that αt (β, ν; Q, C) = α∗ . This follows from the fact that maxz∈RD (U t (α, z; β, ν, Q, C)) is point-wise weakly dominated by the function Q(mt (α)) − γ t · (1 − α) with equality at α∗ , and tiebreaking favors lower values of the work allocation. 24
• For (2), we use the concavity of Q, and the fact that the derivative of Q(mt (α)) − γ t · (1 − α) − β is the same as the derivative of Q(mt (α)) − γ t · (1 − α) everywhere. If αt (β, ν; Q, C) = α∗ , we are done. Assume for sake of contradiction that αt (β, ν; Q, C) ̸= α∗ . Then, we would know that the derivative of Q(mt (α)) − γ t · (1 − α) − β is 0 both at αt (β, ν; Q, C) and at α∗ . However, by the concavity of Q, this means that the derivative of Q(mt (α)) − γ t · (1 − α) − β is 0 along the full interval between αt (β, ν; Q, C) and α∗ . By assumption, there is a local ball around αt (β, ν; Q, C) that does not intersect {0, 1, αgame }, which means that slightly reducing αt (β, ν; Q, C) would yield the same utility but be lower, which is a contradiction given the tiebreaking rule. The fact that z t (β, ν; Q, C) = mt (αt (β, ν; Q, C)) follows from Lemma 6.
C.3
Detector in the case of finite gaming costs
The following result characterizes user workflow decisions in the case of finite gaming costs. Theorem 7. Fix β > 0, ν < ∞, Q, and finite costs C. The program maxα∈[0,1],z U t (α, z; β, ν, Q, C) is well-defined. Moreover, if mt1 (α∗ ) ≤ ν, it holds that αt (β, ν; Q, C) = α∗ ; otherwise, it holds that αt (β, ν; Q, C) ∈ {α∗ , αgame } ∪ At (β). Finally, it holds that zit (β, ν; Q, C) = mti (αt (β, ν; Q, C)) for i ≥ 2, and it holds that: ( G(mt1 (αt (β, ν; Q, C))) if αt (β, ν; Q, C) ∈ At (β) z1t (β, ν; Q, C) = mt1 (αt (β, ν; Q, C)) else. To prove Theorem 7, we first analyze the indirect utility. We show the optimization program for the indirect utility is well-defined, users will never post-process their content along dimensions that are not used in the detection classifier, and users post-process in a structured manner. Lemma 7. Fix β > 0, ν < ∞, Q, and finite costs C. For any α ∈ [0, 1], the optimization program for the indirect utility maxz∈RD (U t (α, z; β, ν, Q, C)) is well-defined, and the optimal value maxz∈RD (U t (α, z; β, ν, Q, C)) is given by: t (α)) − γ t · (1 − α) Q(m P Qi (mti (α)) + maxz1′ ≤ν Q1 (z1′ ) − C1 (mt1 (α), z1′ ) − γ t · (1 − α) i≥2 Q(mt (α)) − β − γ t · (1 − α)
if (mt1 (α)) ≤ ν if (mt1 (α)) ∈ S(β) else.
Moreover, any optimizer z ∗ satisfies zi∗ = mti (α) for i ≥ 2. Finally, the optimizer z ∗ with minimum first dimension (as per the tiebreaking rule in Section 2.3) satisfies: ( G(mt1 (α)) if mt1 (α) ∈ S(β) ∗ z1 = mt1 (α) else. Proof. Let z̃ denote the content where the 1st coordinate is given by z̃1 = G(mt1 (α)) if mt1 (α) ∈ S(β) and z̃1 = mt1 (α) otherwise, and the other coordinates are given by z̃i = mti (α) for all i ≥ 2. Given
25
any value of z, we know that: U t (α, z; β, ν, Q, C) = Q(z) − γ t · (1 − α) − β · 1[z1 > ν] − C(mt (α), z) = −γ t · (1 − α) + Q1 (z1 ) − β · 1[z1 > ν] − C1 (mt1 (α), z1 ) +
X
Qi (z) − Ci (mti (α), zi )
i≥2
≤(1) −γ
t
· (1 − α) + Q1 (z1 ) − β · 1[z1 > ν] − C1 (mt1 (α), z1 ) +
X
Qi (mti (α)
i≥2
= −γ t · (1 − α) + Q1 (z1 ) − β · 1[z1 > ν] − C1 (mt1 (α), z1 ) +
X
(Qi (z̃i ))
i≥2
≤(2) −γ t · (1 − α) + Q1 (z̃1 ) − β · 1[z̃1 > ν] − C1 (mt1 (α), z̃1 ) +
X
(Qi (z̃i ))
i≥2
= Q(z̃) − γ t · (1 − α) − β · 1[z̃1 > ν] − C(mt (α), z̃) = U t (α, z̃; β, ν, Q, C) where (1) follows from (A1). We observe that (2) follows from the following two facts. The first is that if mt1 (α) ̸∈ S(β), then by (A1): Q1 (z1 ) − β · 1[z1 > ν] − C1 (mt1 (α), z1 ) ≤ Q1 (mt1 (α)) − β · 1[mt1 (α) > ν]. The second is that if mt1 (α) ∈ S(β), then: Q1 (z1 )−β ·1[z1 > ν]−C1 (mt1 (α), z1 ) ≤ Q1 (G(mt1 (α)))−β ·1[G(mt1 (α)) > ν]−C1 (mt1 (α), G(mt1 (α))). (2) follows from these two facts. This proves that z̃ is an optimizer of maxz∈RD (U t (α, z; β, ν, Q, C)). Using the definition of G, we see that the optimal value is given by: Q(mt (α)) − γ t · (1 − α) if (mt1 (α)) ≤ ν P t ′ t ′ t if (mt1 (α)) ∈ S(β) i≥2 Qi (mi (α)) + maxz1′ ≤ν Q1 (z1 ) − C1 (m1 (α), z1 ) − γ · (1 − α) Q(mt (α)) − β − γ t · (1 − α) else. as desired. Now, consider any optimizer z ∗ . Then we know that equality must hold in the above chain of equalities. For (1), this means that X X Qi (z ∗ ) − Ci (mti (α), zi∗ ) = Qi (mti (α)). i≥2
i≥2
Applying (A1), this means that zi∗ = mti (α) for all i ≥ 2. For (2), we know that: Q1 (z1∗ ) − β · 1[z1∗ > ν] − C1 (mt1 (α), z1∗ ) = Q1 (z̃1 ) − β · 1[z̃1 > ν] − C1 (mt1 (α), z̃1 ) ≥ max Q1 (z1 ) − β · 1[z > ν] − C1 (mt1 (α), z1 ) , z1
where the last step follows from the analysis above that we showed for every value of z1 . Let’s now assume that z ∗ tiebreaks in favor of lower values. Based on the definitions of G and S(β), we know that z̃1 is the maximizer of maxz1 Q1 (z1 ) − β · 1[z > ν] − C1 (mt1 (α), z1 ) with lowest value, meaning that z1∗ = z̃1 as desired. 26
We prove Theorem 7. Proof of Theorem 7. Using Lemma 7 and applying a partial reparameterization, we know that the optimal value maxz∈RD (U t (α, z; β, ν, Q, C)) is given by: Q(mt (α)) − γ t · (1 − α) if mt1 (α) ≤ ν P t ′ t ′ t if α ∈ At (β) i≥2 Qi (mi (α)) + maxz1′ ≤ν Q1 (z1 ) − C1 (m1 (α), z1 ) − γ · (1 − α) Q(mt (α)) − β − γ t · (1 − α) else. Since the functions Q, C, and mt are continuous, we know that this function is continuous in α (we use Berge’s maximum theorem to ensure continuity of maxz1′ ≤ν Q1 (z1′ ) − C1 (mt1 (α), z1′ ) ). The optimization is over a compact set [0, 1], meaning that it achieves its optima. The characterization of z t (β, ν; Q, C) follows from Lemma 7 coupled with the fact that At (β) is a reparameterization of S(β). If mt1 (α∗ ) ≤ ν, we show that αt (β, ν; Q, C) = α∗ . This follows from the fact that maxz∈RD (U t (α, z; β, ν, Q, C)) is point-wise dominated by the function Q(mt (α)) − γ t · (1 − α) with equality at α∗ , and tiebreaking favors lower values of the work allocation. For the remainder of the analysis, we can assume that mt1 (α∗ ) > ν. We wish to show that t α (β, ν; Q, C) ∈ At (β) ∪ {αgame , α∗ }. It suffices to show any α ∈ [0, 1] such that α ̸∈ At (β) ∪ {αgame , α∗ } is not equal to αt (β, ν; Q, C). We split into cases. Case 1: α ∈ (0, 1) such that α ̸∈ At (β) ∪ {αgame , α∗ }. By Lemma 1, we know that the set At (β) ∪ {αgame } is closed. This means that there is a ball around α which is fully contained in either the first branch (mt1 (α) ≤ ν) or the third branch (mt1 (α) > ν, α ̸∈ At (β)). The function maxz∈RD (U t (α, z; β, ν, Q, C)) is differentiable on these branches. We now use the concavity of Q, and the fact that the derivative of Q(mt (α)) − γ t · (1 − α) − β is the same as the derivative of Q(mt (α)) − γ t · (1 − α) everywhere. If the derivative is nonzero, then we can find a local improvement, meaning that α ̸= αt (β, ν; Q, C) as desired. Suppose the derivative is zero. By assumption, we know that α ̸= α∗ . However, by the concavity of Q, this means that the derivative of Q(mt (α)) − γ t · (1 − α) − β is 0 along the full interval between α and α∗ . However, this is a contradiction given the tiebreaking rule. Case 2: α = 0 and α ̸∈ At (β) ∪ {αgame , α∗ }. By Lemma 1, we know that the set At (β) ∪ {αgame } is closed. This means that there exists ϵ > 0 such that around α + ϵ′ for 0 ≤ ϵ′ < ϵ which is fully contained in either the first branch (mt1 (α) ≤ ν) or the third branch (mt1 (α) > ν, α ̸∈ At (β)). The function maxz∈RD (U t (α, z; β, ν, Q, C)) is differentiable on these branches. We now use the concavity of Q, and the fact that the derivative of Q(mt (α)) − γ t · (1 − α) − β is the same as the derivative of Q(mt (α)) − γ t · (1 − α) everywhere. If the derivative is positive, then we can find a local improvement, meaning that α ̸= αt (β, ν; Q, C) as desired. Suppose the derivative is nonpositive. By assumption, we know that 0 ̸= α∗ . However, by the concavity of Q, this means that the derivative of Q(mt (α)) − γ t · (1 − α) − β is nonpositive along the full interval between [0, α∗ ]. However, this would mean that α∗ = 0, due to the tiebreaking rule, which is a contradiction. Case 3: α = 1 and α ̸∈ At (β) ∪ {αgame , α∗ }. By Lemma 1, we know that the set At (β) ∪ {αgame } is closed. This means that there exists ϵ > 0 such that around α − ϵ′ for 0 ≤ ϵ′ < ϵ which is fully contained in either the first branch (mt1 (α) ≤ ν) or the third branch (mt1 (α) > ν, α ̸∈ At (β)). The function maxz∈RD (U t (α, z; β, ν, Q, C)) is differentiable on these branches. We now use the concavity of Q, and the fact that the derivative of Q(mt (α)) − γ t · (1 − α) − β is the same as the 27
derivative of Q(mt (α)) − γ t · (1 − α) everywhere. If the derivative is negative, then we can find a local improvement, meaning that α = ̸ αt (β, ν; Q, C) as desired. Suppose the derivative is nonnegative. By assumption, we know that 1 ̸= α∗ . However, by the concavity of Q, this means that the derivative of Q(mt (α)) − γ t · (1 − α) − β is nonnegative along the full interval between [α∗ , 1]. However, the tiebreaking rule would mean that αt (β, ν; Q, C) = α∗ ̸= 1, which is a contradiction.
D
Proofs for Section 3
D.1
Proof of Theorem 1
We prove Theorem 1, and we also state and prove a variant for 2-dimensional settings that matches the presented proof intuition more closely. Proof of Theorem 1. Suppose that (1) is satisfied. First, we claim that Q1 is weakly decreasing. Assume for sake of contradiction that Q1 is weakly increasing (recall that we assumed one of the two holds). This means that: max (Q1 (z1′ ) − C1 (z1u , z1′ )) − max (Q1 (z1′ ) − C1 (z1l , z1′ )) =(A) (Q1 (ν) − C1 (z1u , ν)) − (Q1 (ν) − C1 (z1l , ν)) ′ ′ z1 ≤ν
z1 ≤ν
= C1 (z1l , ν) − C1 (z1u , ν) <(B) 0 ≤(C) Q′1 (z1l )(z1u − z1l ). where (A) follows from Lemma 2, (B) follows from assumption (A2), and (C) follows from the fact that Q1 is weakly increasing. This violates (1), which is a contradiction. Let t be such that ht1 = z1l , ℓt1 = z1u , hti = ℓti for all i ≥ 2. Let γ t = −Q′1 (z1l ) · (z1u − z1l ), which we know is nonnegative since Q1 is weakly decreasing. Let ′ ′ β̄ = sup Q1 (z1 ) − max (Q1 (z1 ) − C1 (z1 , z1 ) ′ z1 ∈[z1l ,z1u ]
z1 ≤ν
which we know is finite because it is the supremum of a continuous function (continuous by Berge’s maximum theorem) on a compact set. We claim that α∗ = 0. By concavity, it suffices to show that the derivative at α = 0 is nonpositive. Note that: D X Q(mt (α)) − γ t (1 − α) = Q1 (mt1 (α)) − γ t (1 − α) + Qi (hti ). i=2
Taking a derivative, we obtain:
Q′1 (ht1 )(ℓt1 − ht1 ) + γ t = 0.
This coupled with the tiebreaking rule means that α∗ = 0. We claim that for β > β̄, it holds that α ∈ At (β) for all α ∈ [0, 1]. We know that: ′ t ′ ′ ′ Q1 (mt1 (α)) − max (Q (z ) − C (m (α), z )) ≤ sup Q (z ) − max (Q (z ) − C (z , z ) 1 1 1 1 1 1 1 1 1 1 1 1 ′ ′ z1 ≤ν
z1 ∈[z1l ,z1u ]
= β̄ < β, 28
z1 ≤ν
as desired. Now, we claim that maxz (U t (1, z; β, ν, Q, C)) > maxz (U t (0, z; β, ν, Q, C)). We know that: max(U t (1, z; β, ν, Q, C)) − max(U t (0, z; β, ν, Q, C)) z z ′ u ′ ′ l ′ =(A) max (Q1 (z1 ) − C1 (z1 , z1 )) − max (Q1 (z1 ) − C1 (z1 , z1 )) + γ t z1′ ≤ν z1′ ≤ν ′ u ′ ′ l ′ = max (Q1 (z1 ) − C1 (z1 , z1 )) − max (Q1 (z1 ) − C1 (z1 , z1 )) − Q′1 (z1l ) · (z1u − z1l ) ′ ′ z1 ≤ν
z1 ≤ν
>(B) 0, where (A) uses Lemma 7, (B) uses (1). By Theorem 5, we know that αt (∅; Q, C) = α∗ . By the above, we know that αt (β, ν; Q, C) ̸= 0. This means that αt (β, ν; Q, C) > 0 = α∗ = αt (∅; Q, C) as desired. The proof intuition in the main body and depicted in Figure 1a actually shows a slightly more complex construction, which relies on slightly stronger assumptions. We state this alternate result below. We believe this construction conveys more practical intuition, even though the underlying result is less general. Theorem 8. Consider the same setup as Theorem 1. Let’s additionally assume that D ≥ 2 and Q2 is non-constant. If gaming costs C are finite and there exists z1u > z1l > ν satisfying (1), then there exists a penalty threshold β̄ > 0 and a type t of the form Q2 (ℓt2 ) > Q2 (ht2 ) and Q1 (ℓt1 ) < Q1 (ht1 ) such that αt (β, ν; Q, C) > αt (∅; Q, C) for all β > β̄. Proof. First, we claim that Q1 is weakly decreasing. Assume for sake of contradiction that Q1 is weakly increasing (recall that we assumed one of the two holds). This means that: max (Q1 (z1′ ) − C1 (z1u , z1′ )) − max (Q1 (z1′ ) − C1 (z1l , z1′ )) =(A) (Q1 (ν) − C1 (z1u , ν)) − (Q1 (ν) − C1 (z1l , ν)) ′ ′ z1 ≤ν
z1 ≤ν
= C1 (z1l , ν) − C1 (z1u , ν) <(B) 0 ≤(C) Q′1 (z1l )(z1u − z1l ). where (A) follows from Lemma 2, (B) follows from assumption (A2), and (C) follows from the fact that Q1 is weakly increasing. This violates (1), which is a contradiction. We will let ϵ1 > 0 and ϵ2 > 0 be sufficiently small parameters that we will set later. Let t be such that ht1 = z1l , ℓt1 = z1u , hti = ℓti for all i > 2. Furthermore, let t be such that Q′2 (ht2 ) ̸= 0 (this exists because Q2 is non-constant by assumption). Let ′ ′ β̄ = sup Q1 (z1 ) − max (Q1 (z1 ) − C1 (z1 , z1 ) ′ z1 ∈[z1l ,z1u ]
z1 ≤ν
which we know is finite because it is the maximum of a continuous function (continuous by Berge’s maximum theorem) on a compact set. Let ℓt2 = ht2 + ϵ1 · sign(Q′2 (ht2 )). (If ϵ1 is positive and falls below some positive threshold ϵ̄1 , we know that Q2 (ℓt2 ) > Q2 (ht2 ).) Let γ t = −Q′1 (z1l ) · (z1u − z1l ) − ϵ2 , which we know is nonnegative since Q1 is weakly decreasing. 29
If |Q′2 (ht2 )| · ϵ1 − ϵ2 ≤ 0, we claim that α∗ = 0. By concavity, it suffices to show that the derivative at α = 0 is nonpositive. Note that: X Q(mt (α)) − γ t (1 − α) = Q1 (mt1 (α)) + Q2 (ht2 ) − γ t (1 − α) + Qi (hti ). i>2
Taking a derivative, we obtain: Q′1 (ht1 )(ℓt1 − ht1 ) + Q′2 (ht2 ) · (ℓt2 − ht2 ) + γ t = |Q′2 (ht2 )| · ϵ1 − ϵ2 ≤ 0. This coupled with the tiebreaking rule means that α∗ = 0. We claim that for β > β̄, it holds that α ∈ At (β) for all α ∈ [0, 1]. We know that: t ′ t ′ ′ ′ Q1 (m1 (α)) − max (Q1 (z1 ) − C1 (m1 (α), z1 )) ≤ sup Q1 (z1 ) − max (Q1 (z1 ) − C1 (z1 , z1 ) ′ ′ z1 ≤ν
z1 ∈[z1l ,z1u ]
z1 ≤ν
= β̄ < β, as desired. Now, we claim that maxz (U t (1, z; β, ν, Q, C)) > maxz (U t (0, z; β, ν, Q, C)). For ϵ2 below some positive threshold ϵ̄2 , we know that: max(U t (1, z; β, ν, Q, C)) − max(U t (0, z; β, ν, Q, C)) z z l ′ ′ u ′ ′ =(A) max (Q1 (z1 ) − C1 (z1 , z1 )) − max (Q1 (z1 ) − C1 (z1 , z1 )) + γ t + Q2 (ℓt2 ) − Q2 (ht2 ) z1′ ≤ν z1′ ≤ν ′ u ′ ′ l ′ >(B) max (Q (z ) − C (z , z )) − max (Q (z ) − C (z , z )) − Q′1 (z1l ) · (z1u − z1l ) − ϵ2 1 1 1 1 1 1 1 1 1 1 ′ ′ z1 ≤ν
z1 ≤ν
>(C) 0, where (A) uses Lemma 7, and (B) uses that ϵ1 is sufficiently small, and (C) uses that ϵ2 is sufficiently small and uses (1). By Theorem 5, we know that αt (∅; Q, C) = α∗ . By the above, we know that αt (β, ν; Q, C) ̸= 0. This means that αt (β, ν; Q, C) > 0 = α∗ = αt (∅; Q, C) as desired. We can satisfy the conditions on ϵ1 as follows. Let ϵ2 = ϵ̄2 /2, and let ϵ1 = min(ϵ̄1 /2, ϵ2 /|Q′2 (ht2 )|).
D.2
Statement and Proof of Proposition 1
Proposition 1. Fix k1 ∈ R, k2 > e−2 , and 0 < k3 < 4k2 , and k4 > 0. Let ν = 0, Q1 (z1 ) = k1 −k2 z1 , and let k3 −(z1 −z1′ ) C1 (z1 , z1′ ) = k2 (z1 − z1′ ) + (1 − e ) + k4 (z1 − z1′ )2 . z 1+e 1 √ Then the assumptions in Section 2 are satisfied. For any z1u > z1l > ln(1 + 2), if k4 is sufficiently small, the condition (1) holds. Proof. First, we see that Q1 is weakly decreasing and continuously differentiable. For (A1), note that: C1 (z1 , z1′ ) = k2 (z1 − z1′ ) +
k3 ′ (1 − e−(z1 −z1 ) ) + k4 (z1 − z1′ )2 ≥ Q1 (z1′ ) − Q1 (z1 ) z 1 1+e 30
as desired. Equality holds only when z1′ = z1 . For (A2), we take a derivative with respect to z1 to obtain: ′
k2 −
′
k3 (2ez1 + e−z1 +z1 ) k3 k3 · ez1 + + 2k4 (z1 − z1′ ) ≥ k2 − > 0. (1 + ez1 )2 (1 + ez1 )2 4
We take a derivative with respect to z1′ to obtain: −k2 −
k3 ′ e−(z1 −z1 ) ) + 2k4 (z1′ − z1 ) < 0. z 1 1+e
For (A3), we see that: C1 (z1 , z1′ ) = k2 (z1 − z1′ ) +
k3 −(z1 −z1′ ) (1 − e ) + k4 (z1 − z1′ )2 ≥ 0 z 1+e 1
since each term is nonnegative because z1 ≥ z1′ . Equality is achieved if and only if z1 = z1′ . For (A4), note that k2 (z1 − z1′ ) → ∞ as z1 → ∞, and the other terms are nonnegative. For (A5), we see that Q1 (z1′ ) − C1 (z1 , z1′ ) = k1 − k2 z1′ − k2 (z1 − z1′ ) − = k1 − k2 z1 −
k3 ′ (1 − e−(z1 −z1 ) ) − k4 (z1 − z1′ )2 z 1 1+e
k3 ′ (1 − e−(z1 −z1 ) ) − k4 (z1 − z1′ )2 . z 1 1+e
Note that for any zi′′ , it holds that the utility supzi ≥zi′′ (−k4 (z1 − z1′ )2 ) → −∞ as zi′ → −∞. Now, observe that: k3 ′ ′ −(z1 −z1′ ) ′ 2 max Q1 (z1 ) − C1 (z1 , z1 ) = max k1 − k2 z1 − (1 − e ) − k4 (z1 − z1 ) 1 + e z1 z1′ ≤ν z1′ ≤ν k3 −(z1 −z1′ ) ′ 2 (1 − e ) + k (z − z ) . = k1 − k2 z1 − min 4 1 1 z1′ ≤ν 1 + ez1 ′
k3 −(z1 −z1 ) )+k (z −z ′ )2 is decreasing with z ′ , so it is minimized at z ′ = ν = 0. Note that 1+e z1 (1−e 4 1 1 1 1 Thus we obtain: k3 ′ ′ −z1 2 max Q1 (z1 ) − C1 (z1 , z1 ) = k1 − k2 z1 − (1 − e ) + k4 z1 . 1 + e z1 z1′ ≤ν
Now, observe that: ′ u ′ ′ l ′ max Q (z ) − C (z , z ) − max Q (z ) − C (z , z ) 1 1 1 1 1 1 1 1 1 1 ′ ′ z1 ≤ν
z1 ≤ν
k3 k3 l −z1u )− (1 − e−z1 ) + k4 (z1l )2 − k4 (z1u )2 = −k2 (z1u − z1l ) − u (1 − e l z 1+e 1 1 + e z1 l
u
= Q′1 (z1l )(z1u − z1l ) −
k3 (1 − e−z1 ) k3 (1 − e−z1 ) + + k4 (z1l )2 − k4 (z1u )2 u l z 1 + e z1 1 1+e
√ . By taking a derivative, we can see that f ′ (x) < 0 for x ≥ ln(1 + 2). This u l √ −z1 −z1 means that for z1u > z1l > ln(1 + 2), it holds that − k3 (1−ezu ) + k3 (1−ezl ) > 0. We can take k4 −x)
Let f (x) = k3 (1−e 1+ex
1+e 1
sufficiently small so that the overall expression is positive. 31
1+e 1
D.3
Proof of Theorem 2
To prove Theorem 2, we first prove a series of lemmas. The first case is infinite gaming costs. Lemma 8. Fix β > 0, ν < ∞, and Q. Suppose that gaming costs C = C ∞ are infinite. If mt1 (α∗ ) > ν, then it holds that: αt (β, ν; Q, C) ≤ α∗ . Proof. By Theorem 6, we know that αt (β, ν; Q, C) ∈ {α∗ , αgame }. If αt (β, ν; Q, C) = α∗ , then we are done. If αt (β, ν; Q, C) = αgame , then we know that αgame < ∞ and this case would imply that α∗ ≥ αgame = αt (β, ν; Q, C) as desired. The second case is that maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for all z1 > ν. Lemma 9. Fix β > 0, ν < ∞, and finite costs C. Suppose that maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for all z1 > ν. If mt1 (α∗ ) > ν, then it holds that: αt (β, ν; Q, C) ≤ α∗ . Proof. By Theorem 7, we know that αt (β, ν; Q, C) ∈ {α∗ , αgame } ∪ At (β). If αt (β, ν; Q, C) = αgame , then we know that αgame < ∞ and that thus mt1 (α∗ ) > ν = mt1 (αgame ), which means that α∗ ≥ αgame = αt (β, ν; Q, C) as desired. Otherwise, we know that αt (β, ν; Q, C) ∈ At (β). Assume for sake of contradiction that αt (β, ν; Q, C) > α∗ . We first claim that A′ := At (β) ∩ {α ∈ [0, 1] | α ≥ α∗ } is nonempty and closed, meaning that min A′ exists. The fact that it is nonempty follows from the fact that αt (β, ν; Q, C) > α∗ . Now, we show it is closed. Using Lemma 1, we know that Āt (β) \ At (β) ⊆ {αgame }. Since the intersection of two closed sets is closed, we know that Āt (β) ∩ {α ∈ [0, 1] | α ≥ α∗ } is closed. Since mt1 (α∗ ) > ν, we know that αgame ̸∈ Āt (β) ∩ {α ∈ [0, 1] | α ≥ α∗ }, which means that A′ = At (β) ∩ {α ∈ [0, 1] | α ≥ α∗ } = Āt (β) ∩ {α ∈ [0, 1] | α ≥ α∗ } , so A′ is closed. First, we claim that αt (β, ν; Q, C) = min A′ . We know that: max U t (αt (β, ν; Q, C), z; β, ν, Q, C) z X =(A) Qi (mti (αt (β, ν; Q, C))) i≥2
+ max Q1 (z1′ ) − C1 ((mt1 (αt (β, ν; Q, C))), z1′ ) − γ t · (1 − αt (β, ν; Q, C)) ′ z1 ≤ν = Q(mt (αt (β, ν; Q, C))) − γ t · (1 − αt (β, ν; Q, C)) + max Q1 (z1′ ) − C1 ((mt1 (αt (β, ν; Q, C))), z1′ ) − Q1 (mt1 (αt (β, ν; Q, C))) ′ z1 ≤ν ≤(B) Q(mt (min A′ )) − γ t · (1 − min A′ ) ′ t t ′ + max Q (z ) − C ((m (α (β, ν; Q, C))), z ) − Q1 (mt1 (αt (β, ν; Q, C))) 1 1 1 1 1 z1′ ≤ν ′ t ′ ′ t ′ Q (z ) − C ((m (min A )), z ) − Q (m (min A )) = max U t (min A′ , z; β, ν, Q, C) − max 1 1 1 1 1 1 1 z z1′ ≤ν + max Q1 (z1′ ) − C1 ((mt1 (αt (β, ν; Q, C))), z1′ ) − Q1 (mt1 (αt (β, ν; Q, C))) ′ z1 ≤ν
32
where (A) uses Lemma 7, and (B) uses the fact that αt (β, ν; Q, C) ≥ min A′ ≥ α∗ and Q(mt (α)) − γ t (1 − α) is concave and maximized at α∗ . Becauseof the tiebreaking rule, it now suffices to show that maxz1′ ≤ν Q1 (z1′ ) − C1 ((mt1 (αt (β, ν; Q, C))), z1′ ) − Q1 (mt1 (αt (β, ν; Q, C))) is upper bounded by maxz1′ ≤ν Q1 (z1′ ) − C1 (mt1 (min A′ ), z1′ ) − Q1 (mt1 (min A′ )). This follows from the assumption that maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for all z1 > ν. Next, we claim that maxz U t (min A′ , z; β, ν, Q, C) ≤ maxz U t (α∗ , z; β, ν, Q, C). By assumption, we know that min A′ ̸= α∗ and so ((min A′ ) − ϵ) ̸∈ At (β) for sufficiently small ϵ > 0. We know that: t t t ′ t ′ A (β) = α ∈ [0, 1] | m1 (α) > ν, Q1 (m (α)) − max Q1 (z1 ) − C1 (m1 (α), z1 ) ≤ β . ′ z1 ≤ν
′ Using that mt1 (min A′ )) > mt1 (α∗ ) > ν by assumption, we know that mt1 ((min A ) − ϵ) > ν for t ′ t ′ sufficiently small ϵ > 0. Since Q1 (m (α)) − maxz1′ ≤ν Q1 (z1 ) − C1 (m (α), z1 ) is continuous in α (the continuity of the max follows from Berge’s maximum theorem), this altogether means that t ′ ′ t ′ ′ Q1 (m (min A )) − maxz1′ ≤ν Q1 (z1 ) − C1 (m (min A ), z1 ) = β. Thus, using Lemma 7, we know that:
max U t (min A′ , z; β, ν, Q, C) z
′ t ′ ′ = Q(mt (min A′ )) − γ t · (1 − min A′ ) − Q1 (mt1 (min A′ )) + max Q (z ) − C (m (min A ), z ) 1 1 1 1 1 z1′ ≤ν = Q(mt (min A′ )) − γ t · (1 − min A′ ) − β ≤(C) Q(mt (α∗ )) − γ t · (1 − α∗ ) − β =(D) max U t (α∗ , z; β, ν, Q, C) z
where (C) uses the fact that min A′ > α∗ and Q(mt (α)) − γ t (1 − α) is concave and maximized at α∗ , and (D) uses the fact that α∗ ̸∈ At (β) since min A′ ̸= α∗ . However, based on the tiebreaking rule, this would mean that αt (β, ν; Q, C) = α∗ , which is a contradiction. We prove Theorem 2. Proof of Theorem 2. Note that the condition that there does not exist z1u > z1l > ν such that (2) holds is equivalent to the condition that maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for all z1 > ν. It suffices to prove that if gaming costs C are infinite or maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ ))− Q1 (z1 ) is weakly decreasing in z1 for all z1 > ν, then the presence of the detector weakly decreases LLM usage for all types t and all penalties β > 0. We split into cases based on the value of mt1 (α∗ ). Case 1: mt1 (α∗ ) ≤ ν. In this case, we know that αt (β, ν; Q, C) = α∗ in the case of finite gaming costs (by Theorem 7) and infinite gaming costs (by Theorem 6). This, coupled with Theorem 5, implies that: αt (β, ν; Q, C) = α∗ = αt (∅; Q, C) as desired. Case 2: mt1 (α∗ ) > ν. We know that: αt (β, ν; Q, C) ≤(A) α∗ =(B) αt (∅; Q, C) where (A) follows from Lemma 8 for the case of infinite costs and Lemma 9 for the case where maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for all z1 > ν, and (B) follows from Theorem 5.
33
D.4
Proof of Corollary 1
Besides Theorem 2, another key lemma is the following structural property of maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ). ∂ 2 C (z ,z ′ )
Lemma 10. Fix Q and finite costs C. Suppose that either (1) Q1 is increasing, or (2) ∂z11 ∂z1 ′ 1 ≤ 0 1 for all z1′ ≤ z1 . Then, it holds that maxz1′ ≤ν (Q1 (z1′ ) − C(z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for z1 > ν. Proof. We split into two cases: (1) Q1 is weakly increasing, and (2)
∂ 2 C(z1 ,z1′ ) ≤ 0 for all z1′ ≤ z1 ∂z1 ∂z1′
Case 1: Q1 is weakly increasing. By Lemma 2, we know that G(z1 ) = ν for all z1 ≥ ν. This means that for z1′′ ≤ z1 , it holds that: max Q1 (z1′ ) − C1 (z1 , z1′ ) − Q1 (z1 ) ′ z1 ≤ν ≤(A) max Q1 (z1′ ) − C1 (z1′′ , z1′ ) − Q1 (z1 ) ′ z1 ≤ν ′ ′′ ′ ≤(B) max Q (z ) − C (z , z ) − Q1 (z1′′ ) 1 1 1 1 1 ′ z1 ≤ν
where (A) follows from Lemma 4, and (B) follows from the fact that Q1 is weakly increasing. ∂ 2 C (z ,z ′ )
1 1 1 ≤ 0 for all z1′ ≤ z1 . By Lemma 3, we know that G(z1 ) = ν for all z1 ≥ Case 2: ∂z1 ∂z1′ ν. This means that it suffices to show that Q1 (ν) − C1 (z1 , ν) − Q1 (z1 ) is weakly decreasing in z1 . This is differentiable and we take the derivative to obtain −∇1 C1 (x, ν) − Q′1 (x). Since Q1 (x) − C1 (y, x) − Q1 (y) < 0 for x < y by (A1) and since C1 (x, x) = 0 for all x, we know that the function y 7→ Q1 (x) − C1 (y, x) − Q1 (y) is uniquely maximized at y = x in the domain y ≥ x. Since we know that C1 is continuously differentiable up to the boundary, this means that −∇1 C1 (x, x) − Q′1 (x) ≤ 0. Now, we use the mixed partial condition to conclude that:
−∇1 C1 (x, ν) − Q′1 (x) ≤ −∇1 C1 (x, x) − Q′1 (x) ≤ 0 as desired. Corollary 1 now follows from Theorem 2 and Lemma 10. Proof of Corollary 1. If gaming costs C = C ∞ are infinite, then the result follows directly from ∂ 2 C (z ,z ′ ) Theorem 2. If gaming costs C satisfy the mixed partial condition ∂z11 ∂z1 ′ 1 ≤ 0 for all z1′ ≤ z1 or if 1 Q1 is weakly increasing, then by Lemma 10, we know that maxz1′ ≤ν (Q1 (z1′ ) − C1 (z1 , z1′ )) − Q1 (z1 ) is weakly decreasing in z1 for z1 > ν. This means that there does not exist z1u > z1l > ν such that (2) holds. By Theorem 2, this means that the presence of the detector weakly decreases LLM usage.
E
Additional material and Proofs for Section 4
E.1
Additional result
We show an analogue of Theorem 3 for quality increases and quality staying constant. 34
Theorem 9. Consider the setup of Theorem 3. The presence of the detector increases quality for some user type tI : that is, Q(z tI (β, ν; Q, C)) > Q(z tI (∅; Q, C)). It also induces no change in quality for some user type tN : that is, Q(z tN (β, ν; Q, C)) = Q(z tN (∅; Q, C)). Together, Theorem 3 and Theorem 9 illustrate that LLM detection can have a highly heterogeneous impact on output quality across users. This casts doubt about whether LLM detection is an effective intervention to improve output quality.
E.2
Proofs
To prove Theorem 3 and Theorem 9, we handle the infinite cost and finite cost cases separately. E.2.1
Infinite costs
We split into sublemmas for quality increase, quality decrease, and constant quality. Lemma 11. Fix β > 0, ν < ∞, Q, and infinite costs C = C ∞ . Suppose also D ≥ 2, that there exists a dimension 2 ≤ i′ ≤ D such that Qi′ is non-constant. Then, the presence of the detector increases quality for some user type tI , Q(z tI (β, ν; Q, C)) > Q(z tI (∅; Q, C)). Proof. We let hti I = ℓti I for all i = ̸ 1, i′ . Since Qi′ is non-constant and twice-differentiable concave, for every value ϵ, there exists bi′ (ϵ) and ai′ (ϵ) such that supzi ∈conv(ai′ (ϵ),bi′ (ϵ))) Q′′i′ (zi ) ·(bi′ (ϵ)−ai′ (ϵ))2 < ϵ and Qi′ (ai′ (ϵ)) ∈ (Qi′ (bi′ (ϵ)), Qi′ (bi′ (ϵ)) + ϵ). Let tI be such that ht1I = ν − 1, and let ℓt1I = ν + ϵ1 for an ϵ1 > 0 that we will set later. We let tI 1 ℓi′ = bi′ (ϵ2 ) and we let hti′I = bi′ (ϵ2 ) + (ai′ (ϵ2 ) − bi′ (ϵ2 )) · 1+ϵ ϵ1 for ϵ2 > 0 we will set later. We will t I construct γ later. 1 Utility without the detector. For γ tI > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · 1+ϵ ϵ1 , ∗ we claim that α = 1. By concavity, it suffices to show that the derivative at α = 1 is positive. By the definition of α∗ X Q(mtI (α)) − γ tI (1 − α) = Q1 (mt1I (α)) + Qi′ (mti′I (α)) − γ tI (1 − α) + Qi (ℓt ).
i̸=i′ ,1
Taking a derivative, we obtain: Q′1 (ℓt1I )(ℓt1I − ht1I ) + Q′i′ (ℓti′I )(ℓti′I − hti′I ) + γ tI = Q′1 (ν + ϵ1 )(1 + ϵ1 ) + Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) ·
1 + ϵ1 + γ tI ϵ1
>0 as desired. Quality analysis. If Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) > 0, then we claim that 1 Q(mtI (αgame ) > Q(mtI (1). Note that αgame = 1+ϵ . We know that: 1 Q(mtI (αgame )) − Q(mtI (1)) = Q1 (ν) + Qi′ (ai′ (ϵ2 )) − Q1 (ν + ϵ1 ) − Qi′ (bi′ (ϵ2 )) > 0.
35
ϵ1 Utility under detection. If Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) − γ tI · 1+ϵ + β > 0, 1 t game t I I then we claim that maxz U (α , z; β, ν, Q, C) > maxz U (1, z; β, ν, Q, C). By Lemma 6, we also know that:
max U tI (αgame , z; β, ν, Q, C) − max U tI (1, z; β, ν, Q, C) z
z
tI
= Q(m (α
game
tI
)) + β − Q(m (1)) − γ tI (1 − αgame )
= β + Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) − γ tI ·
ϵ1 1 + ϵ1
> 0. Guarantees under conditions. Suppose that γ tI > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − 1 ′ ′ ′ ′ ′ ′ ′ ′ ai′ (ϵ2 )) · 1+ϵ ϵ1 , Qi (ai (ϵ2 )) − Qi (bi (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) > 0, and Qi (ai (ϵ2 )) − Qi (bi (ϵ2 )) + ϵ1 t t ∞ I I Q1 (ν) − Q1 (ν + ϵ1 ) − γ · 1+ϵ1 + β > 0. By Theorem 6, we know that α (β, ν; Q, C ) ∈ {1, αgame }, and the above arguments show that αtI (β, ν; Q, C ∞ ) = αgame . Moreover, Theorem 6 also tells us that z tI (β, ν; Q, C ∞ ) = mtI (αgame ). Moreover, by Theorem 5, we know that αtI (∅; Q, C ∞ ) = α∗ , , and the above arguments show that α∗ = 1. Moreover, Theorem 5 also tells us that z tI (∅; Q, C ∞ ) = mtI (α∗ ). Putting this together, and combining with the above arguments, we see that Q(z tI (β, ν; Q, C ∞ )) = Q(mtI (αtI (β, ν; Q, C ∞ ))) > Q(mtI (αtI (∅; Q, C ∞ ))) = Q(z tI (∅; Q, C ∞ )) as desired. Condition analysis. It now suffices to construct ϵ1 , ϵ2 and γ tI that satisfy Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) − γ tI ·
ϵ1 +β >0 1 + ϵ1
and Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) > 0 and γ tI > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) ·
1 + ϵ1 . ϵ1
We can rewrite these as: γ tI ·
ϵ1 < β + Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) 1 + ϵ1
and Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν) and
γ tI ·
ϵ1 > −ϵ1 · Q′1 (ν + ϵ1 ) + Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )). 1 + ϵ1
We can construct γ tI ≥ 0 as long as: β + Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) > −ϵ1 · Q′1 (ν + ϵ1 ) + Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )). and Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν).
36
This is equivalent to: Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν) and β + Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) − Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν) − ϵ1 · Q′1 (ν + ϵ1 ). Since Qi′ is concave, we know that: Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) − Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) = Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) + Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) − Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) + Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) ≥ −0.5
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 )))
Q′′i′ (zi ) · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 .
Thus it suffices to have that: Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν) and β − 0.5
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 )))
Q′′i′ (zi ) · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 > Q1 (ν + ϵ1 ) − Q1 (ν) − ϵ1 · Q′1 (ν + ϵ1 ).
Parameter settings. We can set ϵ2 = β, which means that supzi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))) Q′′i′ (zi ) · (bi′ (ϵ2 )−ai′ (ϵ2 ))2 < β and Qi′ (ai′ (ϵ2 )) > Qi′ (bi′ (ϵ2 )). As ϵ1 → 0, we know that Q1 (ν+ϵ1 )−Q1 (ν) → 0 and Q1 (ν + ϵ1 ) − Q1 (ν) − ϵ1 · Q′1 (ν + ϵ1 ) → 0. Thus, we can choose ϵ1 sufficiently small to satisfy the desired expressions. Lemma 12. Fix β > 0, ν < ∞, Q, and infinite costs C = C ∞ . Suppose also D ≥ 2, that there exists a dimension 2 ≤ i′ ≤ D such that Qi′ is non-constant. Then, the presence of the detector decreases quality for some user type tD such that Q(z tD (β, ν; Q, C)) < Q(z tD (∅; Q, C)). Proof. We let hti D = ℓti D for all i = ̸ 1, i′ . Since Qi′ is non-constant and twice-differentiable concave, for every value ϵ, there exists bi′ (ϵ) and ai′ (ϵ) such that supzi ∈conv(ai′ (ϵ),bi′ (ϵ))) Q′′i′ (zi ) ·(bi′ (ϵ)−ai′ (ϵ))2 < ϵ and Qi′ (ai′ (ϵ)) ∈ (Qi′ (bi′ (ϵ)), Qi′ (bi′ (ϵ)) + ϵ). Let tD be such that ht1D = ν − 1, and let ℓt1D = ν + ϵ1 for an ϵ1 > 0 that we will set later. We 1 let ℓti′D = ai′ (ϵ2 ) and we let hti′D = ai′ (ϵ2 ) + (bi′ (ϵ2 ) − ai′ (ϵ2 )) · 1+ϵ ϵ1 for ϵ2 > 0 we will set later. We will construct γ tD later. 1 Utility without the detector. For γ tD > −Q′1 (ν +ϵ1 )(1+ϵ1 )−Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 )−bi′ (ϵ2 ))· 1+ϵ ϵ1 , ∗ we claim that α = 1. By concavity, it suffices to show that the derivative at α = 1 is positive. By the definition of α∗ X Qi (ℓt ). Q(mtD (α)) − γ tD (1 − α) = Q1 (mt1D (α)) + Qi′ (mti′D (α)) − γ tD (1 − α) +
i̸=i′ ,1
37
Taking a derivative, we obtain: Q′1 (ℓt1D )(ℓt1D − ht1D ) + Q′i′ (ℓti′D )(ℓti′D − hti′D ) + γ tD = Q′1 (ν + ϵ1 )(1 + ϵ1 ) + Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) ·
1 + ϵ1 + γ tD ϵ1
>0 as desired. Quality analysis. If Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) < 0, then we claim that 1 Q(mtD (αgame )) < Q(mtD (1). Note that αgame = 1+ϵ . We know that: 1 Q(mtD (αgame )) − Q(mtD (1)) = Q1 (ν) + Qi′ (bi′ (ϵ2 )) − Q1 (ν + ϵ1 ) − Qi′ (ai′ (ϵ2 )) < 0. ϵ1 Utility under detection. If Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) − γ tD · 1+ϵ + β > 0, 1 t game t then we claim that maxz U D (α , z; β, ν, Q, C) > maxz U D (1, z; β, ν, Q, C). By Lemma 6, we also know that:
max U tD (αgame , z; β, ν, Q, C) − max U tD (1, z; β, ν, Q, C) z
z
tD
= Q(m
(α
game
tD
)) + β − Q(m
(1)) − γ tD (1 − αgame )
= β + Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) − γ tD ·
ϵ1 1 + ϵ1
> 0. Guarantees under conditions. Suppose that γ tD > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − 1 ′ ′ ′ ′ ′ ′ ′ ′ bi′ (ϵ2 )) · 1+ϵ ϵ1 , Qi (bi (ϵ2 )) − Qi (ai (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) < 0, and Qi (bi (ϵ2 )) − Qi (ai (ϵ2 )) + ϵ1 t t ∞ D D Q1 (ν) − Q1 (ν + ϵ1 ) − γ · 1+ϵ1 + β > 0. By Theorem 6, we know that α (β, ν; Q, C ) ∈ {1, αgame }, and the above arguments show that αtD (β, ν; Q, C ∞ ) = αgame . Moreover, Theorem 6 also tells us that z tD (β, ν; Q, C ∞ ) = mtD (αgame ). Moreover, by Theorem 5, we know that αtD (∅; Q, C ∞ ) = α∗ , , and the above arguments show that α∗ = 1. Moreover, Theorem 5 also tells us that z tD (∅; Q, C ∞ ) = mtD (α∗ ). Putting this together, and combining with the above arguments, we see that Q(z tD (β, ν; Q, C ∞ )) = Q(mtD (αtD (β, ν; Q, C ∞ )) < Q(mtD (αtD (∅; Q, C ∞ )) = Q(z tD (∅; Q, C ∞ )) as desired. Condition analysis. It now suffices to construct ϵ1 , ϵ2 and γ tD that satisfy Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) − γ tD ·
ϵ1 +β >0 1 + ϵ1
and Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) < 0 and γ tD > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) ·
1 + ϵ1 . ϵ1
We can rewrite these as: ϵ1 γ tD · < β + Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) 1 + ϵ1 38
and Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) < Q1 (ν + ϵ1 ) − Q1 (ν) and
γ tD ·
ϵ1 > −ϵ1 · Q′1 (ν + ϵ1 ) + Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )). 1 + ϵ1
We can construct γ tD ≥ 0 as long as: β + Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) + Q1 (ν) − Q1 (ν + ϵ1 ) > −ϵ1 · Q′1 (ν + ϵ1 ) + Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )). and −β + Q1 (ν + ϵ1 ) − Q1 (ν) < Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) < Q1 (ν + ϵ1 ) − Q1 (ν). This is equivalent to: β − (Q1 (ν + ϵ1 ) − Q1 (ν)) > Qi′ (ai′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > − (Q1 (ν + ϵ1 ) − Q1 (ν)) . and β + Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) − Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν) − ϵ1 · Q′1 (ν + ϵ1 ). Since Qi′ is concave, we know that: Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) − Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) = Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) − Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) + Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) ≥ −0.5
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 )))
Q′′i′ (zi ) · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 .
Parameter settings. We can set ϵ2 = β/2, which means that supzi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))) Q′′i′ (zi ) · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 < β/2 and Qi′ (ai′ (ϵ2 )) ∈ (Qi′ (bi′ (ϵ2 )), Qi′ (bi′ (ϵ2 )) + β/2). As ϵ1 → 0, we know that Q1 (ν + ϵ1 ) − Q1 (ν) → 0 and Q1 (ν + ϵ1 ) − Q1 (ν) − ϵ1 · Q′1 (ν + ϵ1 ) → 0. Thus, we can choose ϵ1 sufficiently small to satisfy the desired expressions. Lemma 13. Fix β > 0, ν < ∞, Q, and infinite costs C = C ∞ . Then, the presence of the detector keeps quality the same for some user type tN Q(z tN (β, ν; Q, C)) = Q(z tN (∅; Q, C)). Proof. Let tN be such that ht1N < ℓt1N < ν, and let hti N = ℓti N for all i ≥ 2. By Theorem 6, we know that αtN (β, ν; Q, C ∞ ) = α∗ and z tN (β, ν; Q, C ∞ ) = mtN (α∗ ). By Theorem 5, we know that αtN (∅; Q, C ∞ ) = α∗ and z tN (∅; Q, C ∞ ) = mtN (α∗ ). This implies that Q(z tN (β, ν; Q, C ∞ )) = Q(z tN (∅; Q, C ∞ )) as desired. E.2.2
Finite costs
We split into sublemmas for quality increase, quality decrease, and constant quality.
39
Lemma 14. Fix β > 0, ν < ∞, Q, and finite costs C. Suppose that the second or third condition in Corollary 1 holds. Suppose also that ∇1 (C1 (ν, ν)) > max(0, −Q′1 (ν)). Suppose also D ≥ 2, that there exists a dimension 2 ≤ i′ ≤ D such that Qi′ is non-constant. Then, the presence of the detector increases quality for some user type tI , Q(z tI (β, ν; Q, C)) > Q(z tI (∅; Q, C)). Proof. We let hti I = ℓti I for all i = ̸ 1, i′ . By applying the assumptions in the lemma along with Lemma 3 in the mixed-partial case and Lemma 2 in the weakly-increasing Q1 case, we know that G(z1 ) = ν for all z1 ≥ ν. Define the type such that ht1I = ν − 1, and let ℓt1I = ν + ϵ1 for an ϵ1 > 0 that we will set later. 1 We will also later construct 0 < ϵ3 < ϵ1 and γ tI . Let ᾱ3 = 1+ϵ . Let κ = ∇1 (C1 (ν, ν)). 3 1 We will use the following fact. For any 0 ≤ ϵ < ϵ1 , let α = 1+ϵ . For any ϵ4 > 0, if ϵ1 is sufficiently small, and letting κ = ∇1 (C1 (ν, ν)), it holds that: tI tI ′ ′ min Q1 (m1 (α)) − max Q1 (z1 ) − C1 (m1 (α), z1 ) , β z1′ ≤ν =(B) min Q1 (mt1I (α)) − Q1 (ν) + C1 (mt1I (α), ν) , β =(C) Q1 (mt1I (α)) − Q1 (ν) + C1 (mt1I (α), ν) = Q1 (mt1I (α)) − Q1 (ν) + C1 (mt1I (α), ν) − C1 (ν, ν) ! ϵ1 − ϵ − Q1 (ν) + inf (∇1 C1 (x, ν)) · mt1I (α) − ν ≥ Q1 ν + t 1+ϵ x∈[ν,m1I (α)] ϵ1 − ϵ ≥(D) Q1 ν + − Q1 (ν) + (κ − ϵ4 ) · mt1I (α) − ν) 1+ϵ ϵ1 − ϵ ϵ1 − ϵ − Q1 (ν) + (κ − ϵ4 ) · . = Q1 ν + 1+ϵ 1+ϵ where (B) uses the fact that G(z1 ) = ν for all z1 ≥ ν, and (C) uses that ϵ1 is sufficiently small coupled with the continuity of Q1 and assumption (A3) and the continuity of C1 in its first argument, and (D) also uses that ϵ1 is sufficiently small coupled with the assumption that C is twice continuously differentiable. Since Qi′ is non-constant and concave, there exists an interval I on which Q′i′ has constant nonzero sign. Thus, for all sufficiently small ϵ2 > 0, we can choose ai′ (ϵ2 ), bi′ (ϵ2 ) ∈ I such that |ai′ (ϵ2 ) − bi′ (ϵ2 )| = ϵ2 ,
Qi′ (ai′ (ϵ2 )) > Qi′ (bi′ (ϵ2 )).
Moreover, there exist constants 0 < k1 < k2 < ∞ and k3 < ∞ such that, for all sufficiently small ϵ2 , k1 ≤ |Q′i′ (z)| ≤ k2 ,
|Q′′i′ (z)| ≤ k3
for all z ∈ conv(ai′ (ϵ2 ), bi′ (ϵ2 )). 1 We let ℓti′I = bi′ (ϵ2 ) and we let hti′I = bi′ (ϵ2 ) + (ai′ (ϵ2 ) − bi′ (ϵ2 )) · 1+ϵ ϵ1 for ϵ2 > 0. 1 Utility with no detection. For γ tI > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · 1+ϵ ϵ1 , ∗ we claim that α = 1. By concavity, it suffices to show that the derivative at α = 1 is positive. By the definition of α∗ X Q(mtI (α)) − γ tI (1 − α) = Q1 (mt1I (α)) + Qi′ (mti′I (α)) − γ tI (1 − α) + Qi (ℓt ).
i̸=i′ ,1
40
Taking a derivative, we obtain: Q′1 (ℓt1I )(ℓt1I − ht1I ) + Q′i′ (ℓti′I )(ℓti′I − hti′I ) + γ tI = Q′1 (ν + ϵ1 )(1 + ϵ1 ) + Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) ·
1 + ϵ1 + γ tI ϵ1
>0 as desired. 1) ′ (ϵ2 ) − bi′ (ϵ2 )) −Qi′ (bi′ (ϵ2 )) > · (a Quality analysis. If Q1 (ν)−Q1 (ν+ϵ1 )+Qi′ bi′ (ϵ2 ) + (1−ᾱ3ϵ)(1+ϵ i 1 0, then we claim that Q(z tI (α)) > Q(mtI (1)) for all α ∈ {αgame } ∪ ([αgame , ᾱ3 ] ∩ At (β)). By Lemma 7, we know that: Q(z tI (α)) − Q(mtI (1)) = Q1 (argmaxz1′ ≤ν Q1 (z1′ ) − C1 (mtI (α), z1′ )) − Q1 (ν + ϵ1 ) (1 − α)(1 + ϵ1 ) + Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) ϵ1 (1 − ᾱ3 )(1 + ϵ1 ) ≥(B) Q1 (ν) − Q1 (ν + ϵ1 ) + Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) ϵ1 >0 where (B) uses the fact that G(z1 ) = ν for all z1 ≥ ν. 1 1) game + t ′ (ϵ2 ) − bi′ (ϵ2 )) −γ I Utility with detection. If Qi′ (ai′ (ϵ2 ))−Qi′ bi′ (ϵ2 ) + ϵ(1+ϵ − α · (a i 1+ϵ ϵ1 (1+ϵ) 1 −ϵ (κ − ϵ4 ) · ϵ1+ϵ > 0 for all 0 < ϵ < ϵ3 , then we claim that maxz U tI (αgame , z; β, ν, Q, C) ≥ 1 maxz U tI (α, z; β, ν, Q, C) for all α ≥ ᾱ3 . By Lemma 7, we also know that if we write α = 1+ϵ , then:
max U tI (αgame , z; β, ν, Q, C) − max U tI (α, z; β, ν, Q, C) z z ′ tI ′ = Q(mtI (αgame )) + min Q1 (mt1I (α)) − max (Q (z ) − C (m (α), z )), β 1 1 1 1 ′ z1 ≤ν
− Q(mtI (α)) − γ tI (α − αgame ) (1 − α)(1 + ϵ1 ) ϵ1 − ϵ ≥ Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) + Q1 (ν) − Q1 ν + ϵ1 1+ϵ + min Q1 (mt1I (α)) − max (Q1 (z1′ ) − C1 (mtI (α), z1′ )), β − γ tI (α − αgame ) z1′ ≤ν ϵ(1 + ϵ1 ) 1 tI game ≥ Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − γ −α ϵ1 (1 + ϵ) 1+ϵ ϵ1 − ϵ + (κ − ϵ4 ) · 1+ϵ ≥ 0, where the last inequality holds by assumption for 0 < ϵ < ϵ3 and by continuity for ϵ = 0 and ϵ = ϵ3 .
41
Guarantees under conditions. Suppose that γ tI > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − (1−ᾱ3 )(1+ϵ1 ) 1 ′ ′ ai′ (ϵ2 )) · 1+ϵ · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > 0, ϵ1 , Q1 (ν) − Q1 (ν + ϵ1 ) + Qi bi (ϵ2 ) + ϵ1 and 1 1) t game + (κ − ϵ ) · ϵ1 −ϵ > 0. By ′ (ϵ2 ) − bi′ (ϵ2 )) − γ I Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + ϵϵ(1+ϵ · (a − α 4 i 1+ϵ 1+ϵ 1 (1+ϵ) Theorem 7, we know that αtI (β, ν; Q, C) ∈ {1, αgame } ∪ At (β), and the above arguments coupled with the tiebreaking rule show that αtI (β, ν; Q, C) ∈ {αgame } ∪ ([αgame , ᾱ3 ] ∩ At (β)). Moreover, by Theorem 5, we know that αtI (∅; Q, C) = α∗ , and the above arguments show that α∗ = 1. Moreover, Theorem 5 also tells us that z tI (∅; Q, C) = mtI (α∗ ). Putting this together, and combining with the above arguments, we see that Q(z tI (β, ν; Q, C)) > Q(mtI (αtI (∅; Q, C))) = Q(z tI (∅; Q, C)) as desired. Condition analysis. It now suffices to construct ϵ1 , ϵ2 , ϵ3 and γ tI that satisfy the following for all 0 ≤ ϵ < ϵ3 : 1 + ϵ1 γ tI > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (bi′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · , ϵ1 (1 − ᾱ3 )(1 + ϵ1 ) Q1 (ν) − Q1 (ν + ϵ1 ) + Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > 0 ϵ1 ϵ(1 + ϵ1 ) Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ 1 − αgame + (κ − ϵ4 ) · >0 −γ tI 1+ϵ 1+ϵ This is equivalent to ϵ1 − ϵ ϵ1 − ϵ ϵ1 − ϵ > −Q′1 (ν + ϵ1 ) · + Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) · , (1 + ϵ1 )(1 + ϵ) (1 + ϵ) ϵ1 (1 + ϵ) ϵ3 (1 + ϵ1 ) Q1 (ν) − Q1 (ν + ϵ1 ) + Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > 0 ϵ1 (1 + ϵ3 ) ϵ(1 + ϵ1 ) Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ −γ tI · + (κ − ϵ4 ) · >0 (1 + ϵ1 )(1 + ϵ) 1+ϵ
γ tI ·
We can construct γ tI ≥ 0 as long as: ϵ1 − ϵ ϵ1 − ϵ + Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) · (1 + ϵ) ϵ1 (1 + ϵ) ϵ(1 + ϵ1 ) ϵ1 − ϵ < Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) + (κ − ϵ4 ) · . ϵ1 (1 + ϵ) 1+ϵ ϵ3 (1 + ϵ1 ) Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )) > Q1 (ν + ϵ1 ) − Q1 (ν) ϵ1 (1 + ϵ3 ) ϵ(1 + ϵ1 ) ϵ1 − ϵ Qi′ (ai′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) + (κ − ϵ4 ) · > 0. ϵ1 (1 + ϵ) 1+ϵ −Q′1 (ν + ϵ1 ) ·
42
We can rewrite the first inequality as: −Q′1 (ν + ϵ1 ) ·
ϵ1 − ϵ (1 + ϵ)
ϵ1 − ϵ < Qi′ (ai′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) ϵ1 (1 + ϵ) −Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) ·
ϵ1 − ϵ ϵ1 − ϵ + (κ − ϵ4 ) · . ϵ1 (1 + ϵ) 1+ϵ
Using concavity, the right-hand-side can be lower bounded by: ϵ1 − ϵ Qi′ (ai′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ + (κ − ϵ4 ) · − Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) · ϵ1 (1 + ϵ) 1+ϵ ϵ1 − ϵ ≥ Q′i′ (ai′ (ϵ2 )) · · (ai′ (ϵ2 ) − bi′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ + (κ − ϵ4 ) · − Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) · ϵ1 (1 + ϵ) 1+ϵ ϵ − ϵ ϵ1 − ϵ 1 = (Q′i′ (ai′ (ϵ2 )) − Q′i′ (bi′ (ϵ2 ))) · (ai′ (ϵ2 ) − bi′ (ϵ2 )) · + (κ − ϵ4 ) · ϵ1 (1 + ϵ) 1+ϵ ϵ − ϵ ϵ1 − ϵ 1 |Q′′i′ (zi )| · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 · ≥− sup + (κ − ϵ4 ) · . ϵ1 (1 + ϵ) 1+ϵ zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 )) The first inequality is thus implied by: (κ − ϵ4 ) · ϵ1 + ϵ1 Q′1 (ν + ϵ1 ) >
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
|Q′′i′ (zi )| · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 .
The second inequality is implied by: ϵ3 (1 + ϵ1 ) ϵ3 (1 + ϵ1 ) ′ Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) (ai′ (ϵ2 ) − bi′ (ϵ2 )) > ϵ1 Q′1 (ν). ϵ1 (1 + ϵ3 ) ϵ1 (1 + ϵ3 ) The third inequality is equivalent to: ϵ1 − ϵ ϵ1 − ϵ · (bi′ (ϵ2 ) − ai′ (ϵ2 )) + (κ − ϵ4 ) · > 0. Qi′ (ai′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + ϵ1 (1 + ϵ) 1+ϵ This is implied by: −Q′i′ (ai′ (ϵ2 )) ·
ϵ1 − ϵ ϵ1 − ϵ · (bi′ (ϵ2 ) − ai′ (ϵ2 ) + (κ − ϵ4 ) · > 0. ϵ1 (1 + ϵ) 1+ϵ
This is equivalent to: Q′i′ (ai′ (ϵ2 )) · (ai′ (ϵ2 ) − bi′ (ϵ2 )) + (κ − ϵ4 ) · ϵ1 > 0.
43
Parameter settings. Our goal is to construct parameters that satisfy the following three conditions: (κ − ϵ4 ) · ϵ1 + ϵ1 Q′1 (ν + ϵ1 ) > sup |Q′′i′ (zi )| · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 (4) zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
ϵ3 (1 + ϵ1 ) ϵ3 (1 + ϵ1 ) ′ (ai′ (ϵ2 ) − bi′ (ϵ2 )) > ϵ1 Q′1 (ν) Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) ϵ1 (1 + ϵ3 ) ϵ1 (1 + ϵ3 )
(5)
Q′i′ (ai′ (ϵ2 )) · (ai′ (ϵ2 ) − bi′ (ϵ2 )) + (κ − ϵ4 ) · ϵ1 > 0.
(6)
We can take ϵ4 <pmin((κ + Q′1 (ν))/4, κ/2). Then we satisfy (6). If we take ϵ2 such that (ai′ (ϵ2 ) − bi′ (ϵ2 )) = o( (κ + Q′ (ν))ϵ1 ) and make ϵ1 sufficiently small, this satisfies (4). If we take ϵ2 such that (ai′ (ϵ2 ) − bi′ (ϵ2 )) = Ω(ϵ1 ), take ϵ3 sufficiently close to ϵ1 , and take ϵ1 sufficiently small, 3/4 then we satisfy (5). We can achieve both conditions on ϵ2 by making it scale with ϵ1 and making ϵ1 sufficiently small. Lemma 15. Fix β > 0, ν < ∞, Q, and finite costs C. Suppose that the second or third condition in Corollary 1 holds. Suppose also that ∇1 (C1 (ν, ν)) > max(0, −Q′1 (ν)). Suppose also D ≥ 2, that there exists a dimension 2 ≤ i′ ≤ D such that Qi′ is non-constant. Then, the presence of the detector decreases quality for some user type tD such that Q(z tD (β, ν; Q, C)) < Q(z tD (∅; Q, C)). Proof. We let hti D = ℓti D for all i = ̸ 1, i′ . By applying the assumptions in the lemma along with Lemma 3 in the mixed-partial case and Lemma 2 in the weakly-increasing Q1 case, we know that G(z1 ) = ν for all z1 ≥ ν. Let ht1D = ν − 1, and let ℓt1D = ν + ϵ1 for an ϵ1 > 0 that we will set later. We will also later 1 construct 0 < ϵ3 < ϵ1 and γ tD . Let ᾱ3 = 1+ϵ . Let κ = ∇1 (C1 (ν, ν)). 3 1 We will use the following fact. For any 0 ≤ ϵ < ϵ1 , let α = 1+ϵ . For any ϵ4 > 0, if ϵ1 is sufficiently small, and letting κ = ∇1 (C1 (ν, ν)), it holds that: tD tD ′ ′ min Q1 (m1 (α)) − max Q1 (z1 ) − C1 (m1 (α), z1 ) , β z1′ ≤ν =(B) min Q1 (mt1D (α)) − Q1 (ν) + C1 (mt1D (α), ν) , β =(C) Q1 (mt1D (α)) − Q1 (ν) + C1 (mt1D (α), ν) = Q1 (mt1D (α)) − Q1 (ν) + C1 (mt1D (α), ν) − C1 (ν, ν) ! ϵ1 − ϵ ≥ Q1 ν + − Q1 (ν) + inf (∇1 C1 (x, ν)) · mt1D (α) − ν t 1+ϵ x∈[ν,m1D (α)] ϵ1 − ϵ ≥(D) Q1 ν + − Q1 (ν) + (κ − ϵ4 ) · mt1D (α) − ν) 1+ϵ ϵ1 − ϵ ϵ1 − ϵ = Q1 ν + − Q1 (ν) + (κ − ϵ4 ) · . 1+ϵ 1+ϵ where (B) uses the fact that G(z1 ) = ν for all z1 ≥ ν, and (C) uses that ϵ1 is sufficiently small along with the continuity of Q1 , assumption (A3), and the continuity of C1 in its first argument, and (D) also uses that ϵ1 is sufficiently small along with the assumption that C is twice continuously differentiable. 44
Since Qi′ is non-constant and concave, there exists an interval I on which Q′i′ has constant nonzero sign. Thus, for all sufficiently small ϵ2 > 0, we can choose ai′ (ϵ2 ), bi′ (ϵ2 ) ∈ I such that |ai′ (ϵ2 ) − bi′ (ϵ2 )| = ϵ2 , and
Qi′ (ai′ (ϵ2 )) > Qi′ (bi′ (ϵ2 )),
Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) > 0.
Moreover, there exist constants 0 < k1 < k2 < ∞ and k3 < ∞ such that, for all sufficiently small ϵ2 , k1 ≤ |Q′i′ (z)| ≤ k2 ,
|Q′′i′ (z)| ≤ k3
for all z ∈ conv(ai′ (ϵ2 ), bi′ (ϵ2 )). Moreover, we choose the parametrization so that the map ϵ2 7→ Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) extends continuously to ϵ2 = 0, has value 0 at ϵ2 = 0, and is strictly positive for all sufficiently small ϵ2 > 0. 1 Let ℓti′D = ai′ (ϵ2 ) and we let hti′D = ai′ (ϵ2 ) + (bi′ (ϵ2 ) − ai′ (ϵ2 )) · 1+ϵ ϵ1 for ϵ2 > 0. 1 Utility with no detector. For γ tD > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) · 1+ϵ ϵ1 , ∗ we claim that α = 1. By concavity, it suffices to show that the derivative at α = 1 is positive. By the definition of α∗ X Q(mtD (α)) − γ tD (1 − α) = Q1 (mt1D (α)) + Qi′ (mti′D (α)) − γ tD (1 − α) + Qi (ℓt ).
i̸=i′ ,1
Taking a derivative, we obtain: Q′1 (ℓt1D )(ℓt1D − ht1D ) + Q′i′ (ℓti′D )(ℓti′D − hti′D ) + γ tD = Q′1 (ν + ϵ1 )(1 + ϵ1 ) + Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) ·
1 + ϵ1 + γ tD ϵ1
>0 as desired. 1) ′ ′ Quality analysis. If Q1 (ν)−Q1 (ν+ϵ1 )+Qi′ ai′ (ϵ2 ) + (1−ᾱ3ϵ)(1+ϵ · (b (ϵ ) − a (ϵ )) −Qi′ (ai′ (ϵ2 )) < i 2 i 2 1 0, then we claim that Q(z tD (α)) < Q(mtD (1)) for all α ∈ {αgame } ∪ ([αgame , ᾱ3 ] ∩ At (β)). By Lemma 7, we know that: Q(z tD (α)) − Q(mtD (1)) = Q1 (argmaxz1′ ≤ν Q1 (z1′ ) − C1 (mtD (α), z1′ )) − Q1 (ν + ϵ1 ) (1 − α)(1 + ϵ1 ) + Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) ϵ1 (1 − ᾱ3 )(1 + ϵ1 ) ≤(B) Q1 (ν) − Q1 (ν + ϵ1 ) + Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) ϵ1 <0 where (B) uses the fact that G(z1 ) = ν for all z1 ≥ ν. 45
1) ′ (ϵ2 ) − ai′ (ϵ2 )) Utility under detection. If Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + ϵ(1+ϵ · (b + (κ − ϵ4 ) · i ϵ1 (1+ϵ) ϵ1 −ϵ 1 tD game > 0 for all 0 < ϵ < ϵ , then we claim that max U tD (αgame , z; β, ν, Q, C) ≥ 3 z 1+ϵ −γ 1+ϵ − α 1 maxz U tD (α, z; β, ν, Q, C) for all α ≥ ᾱ3 . If we let α = 1+ϵ , then by Lemma 7, we know that:
max U tD (αgame , z; β, ν, Q, C) − max U tD (α, z; β, ν, Q, C) z z tD tD game ′ tD ′ = Q(m (α )) + min Q1 (m1 (α)) − max (Q1 (z1 ) − C1 (m (α), z1 )), β ′ z1 ≤ν
− Q(m
tD
(α)) − γ
tD
game
(α − α ) ϵ(1 + ϵ1 ) ≥ Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) ϵ1 (1 + ϵ) 1 ϵ1 − ϵ tD game −γ + (κ − ϵ4 ) · −α 1+ϵ 1+ϵ ≥ 0, where the last inequality holds by assumption for 0 < ϵ < ϵ3 and by continuity for ϵ = 0 and ϵ = ϵ3 . Guarantees under conditions. Suppose that γ tD > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − (1−ᾱ3 )(1+ϵ1 ) 1 ′ ′ bi′ (ϵ2 )) · 1+ϵ · (bi′ (ϵ2 ) − ai′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) < 0, ϵ1 , Q1 (ν) − Q1 (ν + ϵ1 ) + Qi ai (ϵ2 ) + ϵ1 and ϵ1 −ϵ 1 1) game > 0 tD ′ ′ Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + ϵ(1+ϵ · (b (ϵ ) − a (ϵ )) + (κ − ϵ ) · − α − γ 4 i 2 i 2 1+ϵ 1+ϵ ϵ1 (1+ϵ) for all 0 ≤ ϵ < ϵ3 . By Theorem 7, we know that αtD (β, ν; Q, C) ∈ {1, αgame } ∪ At (β), and the above arguments coupled with the tiebreaking rule show that αtD (β, ν; Q, C) ∈ {αgame } ∪ ([αgame , ᾱ3 ] ∩ At (β)). Moreover, by Theorem 5, we know that αtD (∅; Q, C) = α∗ , and the above arguments show that α∗ = 1. Moreover, Theorem 5 also tells us that z tD (∅; Q, C) = mtD (α∗ ). Putting this together, and combining with the above arguments, we see that Q(z tD (β, ν; Q, C)) < Q(mtD (αtD (∅; Q, C))) = Q(z tD (∅; Q, C)) as desired. Condition analysis. It now suffices to construct ϵ1 , ϵ2 , ϵ3 and γ tD that satisfy the following for all 0 ≤ ϵ < ϵ3 : 1 + ϵ1 , ϵ1 (1 − ᾱ3 )(1 + ϵ1 ) Q1 (ν) − Q1 (ν + ϵ1 ) + Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) < 0 ϵ1 ϵ(1 + ϵ1 ) Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ 1 tD game +(κ − ϵ4 ) · −γ > 0. −α 1+ϵ 1+ϵ γ tD > −Q′1 (ν + ϵ1 )(1 + ϵ1 ) − Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) ·
This is equivalent to γ tD ·
ϵ1 − ϵ ϵ1 − ϵ ϵ1 − ϵ > −Q′1 (ν + ϵ1 ) · + Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · , (1 + ϵ1 )(1 + ϵ) (1 + ϵ) ϵ1 (1 + ϵ) 46
ϵ3 (1 + ϵ1 ) Q1 (ν) − Q1 (ν + ϵ1 ) + Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) < 0 ϵ1 (1 + ϵ3 ) ϵ(1 + ϵ1 ) Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ − γ tD · > 0. +(κ − ϵ4 ) · 1+ϵ (1 + ϵ1 )(1 + ϵ) We can construct γ tD ≥ 0 as long as: ϵ1 − ϵ ϵ1 − ϵ + Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · (1 + ϵ) ϵ1 (1 + ϵ) ϵ(1 + ϵ1 ) ϵ1 − ϵ < Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + . · (bi′ (ϵ2 ) − ai′ (ϵ2 )) + (κ − ϵ4 ) · ϵ1 (1 + ϵ) 1+ϵ ϵ3 (1 + ϵ1 ) Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) − Qi′ (ai′ (ϵ2 )) < Q1 (ν + ϵ1 ) − Q1 (ν) ϵ1 (1 + ϵ3 ) ϵ(1 + ϵ1 ) ϵ1 − ϵ Qi′ (bi′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + · (bi′ (ϵ2 ) − ai′ (ϵ2 )) + (κ − ϵ4 ) · > 0. ϵ1 (1 + ϵ) 1+ϵ −Q′1 (ν + ϵ1 ) ·
We can rewrite the first inequality as: −Q′1 (ν + ϵ1 ) ·
ϵ1 − ϵ (1 + ϵ)
ϵ1 − ϵ < Qi′ (bi′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ + (κ − ϵ4 ) · . −Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · ϵ1 (1 + ϵ) 1+ϵ Using concavity, the right-hand side can be lower bounded by: ϵ1 − ϵ Qi′ (bi′ (ϵ2 )) − Qi′ bi′ (ϵ2 ) + · (ai′ (ϵ2 ) − bi′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ ′ + (κ − ϵ4 ) · − Qi′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · ϵ1 (1 + ϵ) 1+ϵ ϵ − ϵ 1 ≥ Q′i′ (bi′ (ϵ2 )) · · (bi′ (ϵ2 ) − ai′ (ϵ2 )) ϵ1 (1 + ϵ) ϵ1 − ϵ ϵ1 − ϵ + (κ − ϵ4 ) · − Q′i′ (ai′ (ϵ2 ))(bi′ (ϵ2 ) − ai′ (ϵ2 )) · ϵ1 (1 + ϵ) 1+ϵ ϵ1 − ϵ ϵ1 − ϵ ′ ′ = (Qi′ (bi′ (ϵ2 )) − Qi′ (ai′ (ϵ2 ))) · (bi′ (ϵ2 ) − ai′ (ϵ2 )) · + (κ − ϵ4 ) · ϵ1 (1 + ϵ) 1+ϵ ϵ1 − ϵ ϵ1 − ϵ ≥− sup |Q′′i′ (zi )| · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 · + (κ − ϵ4 ) · . ϵ1 (1 + ϵ) 1+ϵ zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 )) The first inequality is thus implied by: sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
|Q′′i′ (zi )| · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 < ϵ1 (κ − ϵ4 ) + ϵ1 Q′1 (ν + ϵ1 )
47
We can rewrite the second inequality as: ϵ3 (1 + ϵ1 ) · (bi′ (ϵ2 ) − ai′ (ϵ2 )) > Q1 (ν) − Q1 (ν + ϵ1 ) Qi′ (ai′ (ϵ2 )) − Qi′ ai′ (ϵ2 ) + ϵ1 (1 + ϵ3 ) The second inequality is implied by: ϵ3 (1 + ϵ1 ) ′ · (ai′ (ϵ2 ) − bi′ (ϵ2 )) > −ϵ1 Q′1 (ν + ϵ1 ). Qi′ (ai′ (ϵ2 )) ϵ1 (1 + ϵ3 ) We can rewrite the third inequality as: ϵ1 − ϵ ϵ1 − ϵ > Qi′ bi′ (ϵ2 ) + (κ − ϵ4 ) · · (ai′ (ϵ2 ) − bi′ (ϵ2 )) − Qi′ (bi′ (ϵ2 )). 1+ϵ ϵ1 (1 + ϵ) The third inequality is implied by: ϵ1 − ϵ ϵ1 − ϵ ′ (κ − ϵ4 ) · > Qi′ (bi′ (ϵ2 )) (ai′ (ϵ2 ) − bi′ (ϵ2 )), 1+ϵ ϵ1 (1 + ϵ) which can be written as: ϵ1 (κ − ϵ4 ) > Q′i′ (bi′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )). which is implied by: −ϵ1 · Q′1 (ν + ϵ1 ) + (ϵ1 · Q′1 (ν + ϵ1 ) − ϵ1 · Q′1 (ν)) + ϵ1 (κ + Q′1 (ν) − ϵ4 ) > Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) +
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
|Q′′i′ (zi )| · (ai′ (ϵ2 ) − bi′ (ϵ2 ))2 .
which is implied by: −ϵ1 · Q′1 (ν + ϵ1 ) − ϵ21 ·
sup z1 ∈[ν,ν+ϵ1 ]
> Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) +
|Q′′ (z1 )| + ϵ1 (κ + Q′1 (ν) − ϵ4 )
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
|Q′′i′ (zi )| · (ai′ (ϵ2 ) − bi′ (ϵ2 ))2 .
Parameter settings. Our goal is to construct parameters that satisfy the following three conditions: sup |Q′′i′ (zi )| · (bi′ (ϵ2 ) − ai′ (ϵ2 ))2 < ϵ1 (κ − ϵ4 ) + ϵ1 Q′1 (ν + ϵ1 ) (7) zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
Q′i′ (ai′ (ϵ2 ))
− ϵ1 · Q′1 (ν + ϵ1 ) − ϵ21 ·
ϵ3 (1 + ϵ1 ) ϵ1 (1 + ϵ3 ) sup z1 ∈[ν,ν+ϵ1 ]
(8)
|Q′′ (z1 )| + ϵ1 (κ + Q′1 (ν) − ϵ4 )
> Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )) + Let
· (ai′ (ϵ2 ) − bi′ (ϵ2 )) > −ϵ1 Q′1 (ν + ϵ1 )
sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
|Q′′i′ (zi )| · (ai′ (ϵ2 ) − bi′ (ϵ2 ))2
(9)
p(ϵ2 ) := Q′i′ (ai′ (ϵ2 ))(ai′ (ϵ2 ) − bi′ (ϵ2 )).
By construction, p(ϵ2 ) > 0 for all sufficiently small ϵ2 > 0, p(ϵ2 ) → 0 as ϵ2 → 0, and, since |Q′i′ | is bounded above and below on the chosen interval, p(ϵ2 ) = Θ(|ai′ (ϵ2 ) − bi′ (ϵ2 )|). 48
Choose ϵ4 > 0 small enough that max(0, −Q′1 (ν)) < κ − ϵ4 . Then choose a constant ρ satisfying max(0, −Q′1 (ν)) < ρ < κ − ϵ4 . For each sufficiently small ϵ1 , choose ϵ2 so that p(ϵ2 ) = ρϵ1 . This is possible by the continuity of p and the fact that p(ϵ2 ) = Θ(ϵ2 ) locally. In particular, ai′ (ϵ2 ) − bi′ (ϵ2 ) = O(ϵ1 ), and hence the curvature term sup zi ∈conv(ai′ (ϵ2 ),bi′ (ϵ2 ))
|Q′′i′ (zi )| (ai′ (ϵ2 ) − bi′ (ϵ2 ))2
is O(ϵ21 ). We now verify (7)–(9). Since ϵ1 (κ − ϵ4 ) + ϵ1 Q′1 (ν + ϵ1 ) = ϵ1 (κ + Q′1 (ν) − ϵ4 ) + O(ϵ21 ), and κ + Q′1 (ν) − ϵ4 > 0, condition (7) holds for sufficiently small ϵ1 . Condition (8) holds because ϵ3 is chosen sufficiently close to ϵ1 , so the multiplicative factor converges to 1, and p(ϵ2 ) = ρϵ1 > −ϵ1 Q′1 (ν + ϵ1 ) for sufficiently small ϵ1 , where we use that ρ > −Q′1 (ν) and Q′1 (ν + ϵ1 ) → Q′1 (ν). Finally, condition (9) holds because its left-hand side is lower bounded as ϵ1 (κ + Q′1 (ν) − ϵ4 ) − ϵ1 Q′1 (ν + ϵ1 ) − O(ϵ21 ) = ϵ1 (κ − ϵ4 ) − O(ϵ21 ), while its right-hand side is upper bounded as p(ϵ2 ) + O(ϵ21 ) = ρϵ1 + O(ϵ21 ), and ρ < κ − ϵ4 was chosen with slack. Lemma 16. Fix β > 0, ν < ∞, Q, and finite costs C. Suppose that the second or third condition in Corollary 1 holds. Then, the presence of the detector keeps quality the same for some user type tN Q(z tN (β, ν; Q, C)) = Q(z tN (∅; Q, C)). Proof. Let tN be such that ht1N < ℓt1N < ν, and let hti N = ℓti N for all i ≥ 2. By Theorem 7, we know that αtN (β, ν; Q, C) = α∗ and z tN (β, ν; Q, C) = mtN (α∗ ). By Theorem 5, we know that αtN (∅; Q, C) = α∗ and z tN (∅; Q, C) = mtN (α∗ ). This implies that Q(z tN (β, ν; Q, C)) = Q(z tN (∅; Q, C)) as desired.
49
E.3
Proofs from lemmas
The desired results follow from these lemmas. Proof of Theorem 3. This follows from Lemma 15 and Lemma 12. Proof of Theorem 9. This follows from Lemma 11, Lemma 13, Lemma 14, and Lemma 16.
F
Proofs for Section 5
F.1
Proof of Theorem 4
We split into two lemmas. Lemma 17. Fix β > 0, ν < ∞, Q, and C. For any type t ∈ T , it holds that: ht1 ≤ z1t (∅; Q, C) and z1t (∅; Q, C) ≥ z1t (β, ν; Q, C). Proof. First, we apply Theorem 5 to see that z1t (∅; Q, C) = mt1 (α∗ ). Moreover, using the assumption on the type space that ht1 < ℓt1 , we know that mt1 (α) is increasing in α. We show that ht1 ≤ z1t (∅; Q, C). This follows from the fact that: z1t (∅; Q, C) = mt1 (α∗ ) ≥ mt1 (0) = ht1 as desired. Now, we show that z1t (∅; Q, C) ≥ z1t (β, ν; Q, C). We split into two cases: infinite gaming costs and finite gaming costs. Case 1: Infinite gaming costs. Using Theorem 6, we know that z1t (β, ν, Q, C ∞ ) = mt1 (αt (β, ν, Q, C ∞ )). We split into subcases: mt1 (α∗ ) ≤ ν and mt1 (α∗ ) > ν. Case 1a: mt1 (α∗ ) ≤ ν. Using Theorem 6, we know that αt (β, ν, Q, C ∞ ) = α∗ , which means that: z1t (∅; Q, C) = mt1 (α∗ ) = mt1 (αt (β, ν, Q, C ∞ )) = z1t (β, ν, Q, C ∞ ) as desired. Case 1b: mt1 (α∗ ) > ν. Using Theorem 6, we know that αt (β, ν, Q, C ∞ ) ∈ {α∗ , αgame }. If t α (β, ν, Q, C ∞ ) = α∗ , this again means that z1t (∅; Q, C) = mt1 (α∗ ) = mt1 (αt (β, ν, Q, C ∞ )) = z1t (β, ν, Q, C ∞ ). If αt (β, ν, Q, C ∞ ) = αgame , then we know that αgame < ∞. Since αgame < ∞, then we know that mt1 (αgame ) = ν. This would mean that: z1t (∅; Q, C) = mt1 (α∗ ) > ν = mt1 (αgame ) = mt1 (αt (β, ν, Q, C ∞ )) = z1t (β, ν, Q, C ∞ ).
50
Case 2: Finite gaming costs. We split into subcases: mt1 (α∗ ) ≤ ν and mt1 (α∗ ) > ν. Case 2a: mt1 (α∗ ) ≤ ν. Using Theorem 7, we know that αt (β, ν; Q, C) = α∗ and z1t (β, ν; Q, C) = t m1 (αt (β, ν; Q, C)), which means that: z1t (∅; Q, C) = mt1 (α∗ ) = mt1 (αt (β, ν; Q, C)) ≥ z1t (β, ν; Q, C) as desired. Case 2b: mt1 (α∗ ) > ν. Using Theorem 7, we know that αt (β, ν; Q, C) ∈ {α∗ , αgame } ∪ At (β). If αt (β, ν; Q, C) = α∗ , this again means that z1t (∅; Q, C) = mt1 (α∗ ) = mt1 (αt (β, ν; Q, C)) ≥ z1t (β, ν; Q, C). If αt (β, ν, Q) = αgame , then we know that αgame < ∞. Since αgame < ∞, then we know that mt1 (αgame ) = ν. This would mean that: z1t (∅; Q, C) = mt1 (α∗ ) > ν = mt1 (αgame ) = mt1 (αt (β, ν; Q, C)) ≥ z1t (β, ν; Q, C). If αt (β, ν; Q, C) ∈ At (β) and αt (β, ν; Q, C) ̸= α∗ , then we know by Theorem 7 that mt1 (α∗ ) > ν, which means that: z1t (∅; Q, C) = mt1 (α∗ ) > ν ≥ G(mt1 (αt (β, ν, Q, C))) = z1t (β, ν; Q, C). as desired. Lemma 18. Fix β > 0, ν < ∞, Q, C. There exists a type t ∈ T such that ht1 < z1t (∅; Q, C) and z1t (∅; Q, C) > z1t (β, ν; Q, C). Proof. We construct t so that hti = ℓti for i ̸= 1, so the two outputs only differ along the first coordinate. We take ht1 = ν − 1 and ℓt1 = ν + ϵ where ϵ > 0. First, we show that for sufficiently large γ t it holds that z t (∅; Q, C) = ℓt for any 0 < ϵ < 1/2. Using Theorem 5, we know that z t (∅; Q, C) = mt (α∗ ), so it suffices to show that α∗ = 1. Recall that α∗ is the minimum optimizer of maxα∈[0,1] (Q(mt (α)) − γ t (1 − α)). Since the objective Q(mt (α)) − γ t (1 − α) is concave, it suffices to show that the derivative as α → 1 is strictly positive. Note that this is equal to 3 Q′1 (ℓt1 ) · (ℓt1 − ht1 ) + γ t ≥ γ t − · sup Q′1 (ν + ϵ) . 2 0<ϵ<1/2 This is strictly positive for sufficiently large γ t , as desired. For γ t satisfying the above, note that: ht1 < z1t (∅; Q, C) = ℓt1 , which proves the first inequality. Next, for any fixed value of γ t , we show that for sufficiently small ϵ > 0 it holds that t (α (β, ν; Q, C), z t (β, ν; Q, C)) ̸= (1, ℓt ). It suffices to show that U t (αgame , mt (αgame ), β, ν, Q, C) > U t (1, ℓt , β, ν, Q, C). For any ϵ > 0, it holds that: U t (αgame , mt (αgame )) − U t (1, ℓt , β, ν, Q, C) = Q(mt (αgame )) − Q(ℓt ) + β − γ t (1 − αgame ) ϵ = Q1 (ν) − Q1 (ν + ϵ) + β − γ t · 1+ϵ ′ t ≥(A) β − ϵ · Q1 (ν) − γ · ϵ where (A) uses the concavity of Q1 . For sufficiently small ϵ > 0, we see that this is strictly positive. Now, taking values of γ t and ϵ that satisfy the above, we split into two cases: (1) αt (β, ν; Q, C) ̸= 1 and (2) αt (β, ν; Q, C) = 1 and z t (β, ν; Q, C)) ̸= ℓt ). 51
Window 2014-17 2015-18 2016-19 2017-20 2018-21 2019-22 2020-23 2021-24 2022-25
Style (RTF) 0.0 ± 0.0 0.0 ± 0.0 0.6 ± 0.8 0.0 ± 0.0 0.2 ± 0.4 0.4 ± 0.5 0.0 ± 0.0 0.2 ± 0.4 26.4 ± 1.4
Topic (RTF) 5.6 ± 1.0 4.2 ± 0.7 7.2 ± 0.4 4.0 ± 0.6 3.8 ± 1.7 6.2 ± 1.6 5.4 ± 1.2 10.2 ± 1.2 9.2 ± 1.6
Style (All) 13.6 ± 1.0 10.6 ± 1.5 16.8 ± 3.5 18.2 ± 2.7 10.4 ± 2.2 15.2 ± 2.7 18.4 ± 1.7 24.0 ± 2.1 55.4 ± 1.6
Figure 3: Numerical values shown in Figure 2a. Case 1: αt (β, ν; Q, C) ̸= 1. In this case, we know that: z1t (β, ν; Q, C) ≤ mt1 (αt (β, ν; Q, C)) < ℓt1 = z1t (∅; Q, C), which proves the second inequality. Case 2: αt (β, ν; Q, C) = 1 and z t (β, ν; Q, C) ̸= ℓt . By Theorems 6 and 7, we know that zit (β, ν; Q, C) = mti (αt (β, ν; Q, C)) for all i ≥ 2. Thus, the assumptions of this case mean that z1t (β, ν; Q, C)) ̸= ℓt1 , which by the definition of post-processing means that z1t (β, ν; Q, C)) < ℓt1 . Putting this together, we obtain that: z1t (β, ν; Q, C)) < ℓt1 = z1t (∅; Q, C), which proves the second inequality. Theorem 4 follows from these lemmas. Proof of Theorem 4. The first part follows from Lemma 17, and the second part follows from Lemma 18.
G
Additional details, ablations, and full word lists for Section 5.2
We provide additional empirical details in Appendix G.1, ablations in Appendix G.2, and full word lists in Appendix G.3.
G.1
Details of empirical setup
Details of building vocabulary V . We only consider non-stop words that are at least 3 letters long. For each trial, we then build a vocabulary V consisting of the 10,000 words with highest frequency across the sampled dataset with the papers in each month from 1/1/2013 to 12/31/2025. Details of LLM judge configuration. We use the latest version of GPT-5.4-mini as of May 4th, 2026. We set the temperature to be the default value. We take the judge prompt to be “"""You are an expert linguist analyzing word frequency changes in academic computer science papers (arXiv CS abstracts). A word’s usage frequency changed significantly over a time period. Classify it as either: 52
Figure 4: Variation of Figure 2a where the judge is GPT-5-nano-2025-08-07. - "topic": The frequency change is primarily because the word relates to a research topic, method, dataset, tool, technology, or domain-specific concept that became more or less popular (e.g., "transformer", "bert", "diffusion", "covid", "blockchain", "federated", "adversarial", "pruning"). - "style": The frequency change primarily reflects a change in writing style, rhetoric, word choice, or language patterns not tied to a specific research topic (e.g., "delve", "comprehensive", "notably", "leveraging", "crucial", "showcasing", "underscores", "innovative"). Respond with ONLY "topic" or "style". No other text."""”. Details of “rise-then-fall” classification. Given a word w and an interval indexed by s, we compute the maximum frequency of the word across any quarter in [10/1/s, 9/30/(s + 3)]. We require that the maximum frequency is at least R = 1.5 times the frequency in the first quarter, that the final frequency is at most F = 0.95 times the maximum frequency, and that the number of sign changes is at most C = 4. All experiments are run on 1 CPU.
G.2
Ablations
We show ablations where we adjust the parameters of the rise-then-fall classification: the rise threshold (Figure 5), the fall threshold (Figure 6), and the max number of sign changes (Figure 7). We also show ablations where we take GPT-5-nano-2025-08-07 to be the judge (Figure 4). Our results readily generalize across these settings.
53
(a) R = 1.1
(b) R = 3.0
Figure 5: Variation of Figure 2a where rise-then-fall classification takes the rise threshold to 1.1 (left) and 3 (right), rather than 1.5.
(a) F = 0.8
(b) F = 0.98
Figure 6: Variation of Figure 2a where rise-then-fall classification takes the fall threshold to 0.8 (left) and 0.98 (right), rather than 0.95.
54
(a) C = 2
(b) C = 6
Figure 7: Variation of Figure 2a where rise-then-fall classification takes the number of sign changes C is set to 2 (left) and 6 (right), rather than 4.
G.3
Lists of words
We show a list of rise-then-fall style words, rise-then-fall topic words, and non-rise-then-fall style words, taking one of the trials as an illustrative example (Table 1).
55
Window 20142017
RTF style (none)
RTF topic leaky, microservices, pandemic, relu, stdp
20152018
(none)
aoi, celeba, lstm, rnn, train
20162019
(none)
autonomous, convolutional, deep, generative, loss, unet, urllc
20172020
(none)
bert, capsules, mask, ntk
20182021
explanations
20192022
(none)
20202023
(none)
coronavirus, counterfactual, distancing, pandemic, vln contrastive, coronavirus, federated, gnns, nerfs, pandemic, swin, vit gnns, masked, metaverse, peft
20212024
(none)
aigc, chatgpt, denoising, isac, llm, llms, masked, metaverse, rlhf
20222025
additionally, addressing, advancement, advancements, capabilities, challenges, delves, effectively, encompassing, enhance, enhances, enhancing, ensuring, facilitating, innovative, integrating, intricate, leveraging, notably, potential, significant, thereby, underscores, utilizing
aigc, clip, hallucinations, instruction, lmms, mamba, mistral, prompting, rag
hpo,
Non-RTF style adequacy, attentive, benefiting, caption, crafting, essays, footprints, informativeness, learn, listeners, localizes, necessitating, trained argumentative, cer, frozen, individualized, irl, isa, paraphrases, regressing, tasks, trained abusive, audits, bells, bound, driving, duplicates, https, ideological, memorability, methods, models, slip, sota, supervisions, tasks, tee, tees, trained, whistles achievable, asc, bound, bounds, capacity, experiments, explanations, however, https, learn, methods, models, number, optimal, problem, rate, schemes, tasks, trained, users contextualized, data, downstream, experiments, however, https, methods, models, problem, sota, tasks, vos downstream, existing, explanations, extensive, https, methods, models, number, order, paper, pretext, problem, research, shifts, sota, tasks, tod downstream, existing, extensive, global, however, https, methods, models, number, order, paper, problem, scenarios, shifts, sota, tasks, tod, word, works additionally, address, advancements, art, based, capabilities, comprehensive, diverse, downstream, effectiveness, enhance, enhancing, existing, extensive, however, https, issue, limitations, models, number, paper, performance, potential, problem, sota, tasks, various, word across, address, comprehensive, crucial, diverse, enabling, findings, highlighting, insights, integration, introduce, introduces, large, models, offering, offers, one, particularly, pivotal, problem, proposed, remarkable, show, showcasing, struggle, tailored, underscore, underscoring, used, various, within
Table 1: Full list of rise-then-fall style words, rise-then-fall topic words, and non-rise-then-fall words within the top 100 words with most greatest change. The list is generated from one of the trials, following the empirical setup in Section 5.2.
56