Paper deep dive
Contests with Spillovers: Incentivizing Content Creation with GenAI
Sagi Ohayon, Boaz Taitler, Omer Ben-Porat
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 3/22/2026, 5:08:34 AM
Summary
The paper introduces the 'Content Creation with Spillovers' (CCS) model to address the economic challenge of positive spillovers in GenAI-assisted content creation. It identifies that standard mechanisms like winner-takes-all and Tullock contests fail to guarantee equilibrium in this setting. The authors propose a 'Provisional Allocation' (PRA) mechanism family that ensures a Pareto-dominant Nash equilibrium and develop approximation algorithms for welfare optimization, including solutions for bounded spillovers, tree-structured interactions, and random graphs.
Entities (5)
Relation Signals (3)
GenAI → amplifies → Positive Spillovers
confidence 95% · The rise of GenAI amplifies the economic phenomenon of positive spillovers.
Provisional Allocation (PRA) mechanism → guarantees → Pure Nash Equilibrium (PNE)
confidence 95% · Any PRA p guarantees a Pareto-dominant PNE.
Greedy Cost Selection → optimizes → Social Welfare
confidence 90% · Greedy Cost Selection, a linearithmic time algorithm that achieves approximately optimal results in the average case analysis.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The rise of GenAI amplifies the economic phenomenon of positive spillovers. When creators contribute content that can be reused and adapted by Large Language Models (LLMs), each creator's effort can enhance the content quality of others by enabling easy imitation and recombination of existing content. On the one hand, such spillovers create value for the entire ecosystem; on the other hand, they risk undermining creators' incentives to invest genuine effort, as others may freely benefit from their contributions. To address this problem, we introduce the Content Creation with Spillovers (CCS) model. In our model, each creator chooses an effort level that, together with the efforts of others, determines her content quality. The platform aims to maximize the social welfare of consumers under stable behavior of the creators (pure Nash equilibrium), but can only observe the resulting qualities and not the underlying efforts. Interestingly, simple mechanisms like winner-takes-all and Tullock lead to the non-existence of equilibrium. In response, we propose the parametrized family of Provisional Allocation mechanisms, guaranteeing equilibrium existence and a unique Pareto-dominant equilibrium. While maximizing the social welfare under this family is NP-hard, we develop approximation algorithms that apply to a broad class of spillover structures and provide strong welfare guarantees. Specifically, in the worst-case analysis, we devise efficient algorithms for bounded spillovers and tree-structure spillovers. We also introduce Greedy Cost Selection, a linearithmic time algorithm that achieves approximately optimal results in the average case analysis. Together, our results provide game-theoretic foundations for sustaining human content creation in the era of GenAI.
Tags
Links
- Source: https://arxiv.org/abs/2603.14372v1
- Canonical: https://arxiv.org/abs/2603.14372v1
Trouble viewing inline? Open PDF directly →
Full Text
163,198 characters extracted from source content.
Expand or collapse full text
Contests with Spillovers: Incentivizing Content Creation with GenAI Sagi Ohayon∗† Boaz Taitler∗‡ Omer Ben-Porat§ ∗Equal contribution. †Technion—Israel Institute of Technology. Corresponding author (sagio@campus.technion.ac.il). ‡Technion—Israel Institute of Technology (boaztaitler@campus.technion.ac.il). §Technion—Israel Institute of Technology (omerbp@technion.ac.il) Abstract The rise of GenAI amplifies the economic phenomenon of positive spillovers. When creators contribute content that can be reused and adapted by Large Language Models (LLMs), each creator’s effort can enhance the content quality of others by enabling easy imitation and recombination of existing content. On the one hand, such spillovers create value for the entire ecosystem; on the other hand, they risk undermining creators’ incentives to invest genuine effort, as others may freely benefit from their contributions. To address this problem, we introduce the Content Creation with Spillovers (CCS) model. In our model, each creator chooses an effort level that, together with the efforts of others, determines her content quality. The platform aims to maximize the social welfare of consumers under stable behavior of the creators (pure Nash equilibrium), but can only observe the resulting qualities and not the underlying efforts. Interestingly, simple mechanisms like winner-takes-all and Tullock lead to the non-existence of equilibrium. In response, we propose the parametrized family of Provisional Allocation mechanisms, guaranteeing equilibrium existence and a unique Pareto-dominant equilibrium. While maximizing the social welfare under this family is NP-hard, we develop approximation algorithms that apply to a broad class of spillover structures and provide strong welfare guarantees. Specifically, in the worst-case analysis, we devise efficient algorithms for bounded spillovers and tree-structure spillovers. We also introduce Greedy Cost Selection, a linearithmic time algorithm that achieves approximately optimal results in the average case analysis. Together, our results provide game-theoretic foundations for sustaining human content creation in the era of GenAI. 1 Introduction Online content creation has become a central activity in the digital economy. Individuals and firms produce a wide range of content, including text for posts on social media platforms, long-form articles, and videos for platforms such as YouTube and TikTok. Such content is produced by creators to attract user attention and engagement on these platforms. Because user attention and engagement are limited and often mediated by platform recommendation systems, content creators compete with one another to attract users on online platforms. A large body of literature studies content creation as a competitive environment in which creators vie for users’ attention, engagement, and exposure through recommendation and ranking mechanisms that allocate users based on content performance Hron et al. (2023); Jagadeesan et al. (2023); Ben-Porat et al. (2020); Yao et al. (2024b). In these settings, creators strategically choose their effort levels in order to win users and increase their visibility on the platform. More recently, the widespread adoption of generative AI tools has introduced a new source of interaction between content creators. Many creators now rely on large language models (LLMs) and other generative systems that are trained on, or have direct access to, vast amounts of existing online content. This creates spillovers across creators, whereby the effort of one creator can affect the quality of content produced by others, a phenomenon well studied in economics Mas-Colell et al. (1995). To illustrate, consider two content creators producing material on the same platform. When one creator produces and uploads high-quality content, this content may either be incorporated into the training data of a generative model or be retrieved by the model at inference time through access to online sources. A second creator who relies on such a system to assist with writing or editing can then benefit from the first creator’s effort, producing high(er)-quality content at lower cost. As a result, individual content creation decisions can affect the productivity of other content creators who rely on generative AI tools, linking creators indirectly. While such spillovers can improve individual productivity, they can also distort incentives in competitive environments. When creators compete for user attention and exposure, a creator may benefit from reducing effort and relying on the positive spillovers generated by others, maintaining acceptable content quality at a lower cost. Anticipating this behavior, high-effort creators may, in turn, reduce their own investment, as their effort partially benefits competitors rather than translating into a competitive advantage. This strategic interaction can lead to low-effort outcomes, unstable dynamics, or the absence of equilibrium, undermining content quality. Low-quality content is undesirable from a welfare perspective, as content quality directly affects the utility users derive from consuming content. The low-effort outcomes that can arise in the presence of spillovers therefore undermine social welfare. This raises a central design question: how should systems be designed to account for spillovers and incentivize high levels of content quality? More broadly, can spillover effects be harnessed to reinforce incentives, so that higher quality by one creator increases the incentives of others to improve their own content? 1.1 Our Contribution This paper provides the first game-theoretic foundation for incentive design in GenAI-assisted content creation with positive spillovers. Our contribution is threefold: 1) Modeling Content Creation with Spillovers We introduce the Content Creation with Spillovers (CCS) game, a framework capturing the strategic interaction between a platform and N content creators. Each creator i selects an effort intensity xi∈[0,1]x_i∈[0,1], incurring a convex cost ci(xi)c_i(x_i). The platform cannot observe the effort profile =(x1,…,xN)x=(x_1,…,x_N); instead, the platform observes the resulting quality profile ()=(Q1(),…,QN())∈[0,1]NQ(x)=(Q_1(x),…,Q_N(x))∈[0,1]^N and has to allocate attention accordingly. The key feature of our model is that creator i’s quality Qi()Q_i(x) depends on the efforts of all creators—a phenomenon we call positive spillovers—reflecting scenarios where creators benefit from shared GenAI infrastructure trained on collective content with access to online content. We construct our model by analyzing quality formation in the wild, specifically through LLM scaling laws Kaplan et al. (2020) and graph-based knowledge flows Bramoullé and Kranton (2007), to distill a generalized assumption on spillovers. Informally, we assume the marginal quality gain from one’s own effort is non-decreasing in others’ efforts (see Assumption 1). We observe that in this environment, canonical mechanisms like Winner-Takes-All Hillman and Riley (1989) and Tullock Tullock (1980) are unstable: there exist game instances with no Pure Nash Equilibrium (PNE hereinafter). 2) The Provisional Allocation Mechanism Family Motivated by the instability of standard mechanisms, we propose the family of Provisional Allocation Mechanisms (PRA for shorthand). Every PRA mechanism is fully characterized by allocation shares =(p1,…,pN)∈[0,1]Np=(p_1,…,p_N)∈[0,1]^N with ∑ipi≤1 _ip_i≤ 1. Under any PRA mechanism, creator i’s utility is determined by Ui()=pi⋅Qi()−ci(xi)U_i(x)=p_i· Q_i(x)-c_i(x_i), effectively capping creator i’s share to pip_i. By separating individual rewards from the relative performance of competitors, we align creators’ incentives with those of the ecosystem. We show that: Theorem 1 (Informal; see Theorem 5). Any PRA p guarantees a Pareto-dominant PNE. Furthermore, we provide an axiomatic characterization showing that any mechanism satisfying natural desiderata must possess the PRA structure (see Theorem 6). The existence of such a Pareto-dominant PNE motivates the platform’s incentive-design objective, formalized as the following optimization problem: choose p to maximize SW(¯())SW( x(p)), where ()x(p) is the Pareto-dominant PNE (See Equation 2). 3) Algorithmic Results We study the computational complexity of the above welfare optimization problem over all PRA mechanisms and obtain a negative result. In particular, we prove NP-hardness of finding an optimal mechanism, and show that even approximating the optimum within a constant factor is NP-hard (see Theorem 7 and Corollary 8). On the positive side, we show that: Theorem 2 (Informal; see Theorems 9, 12, and 21). The welfare optimization problem admits efficient approximations in the following cases: • Bounded spillovers: If spillover magnitudes are bounded by a factor β of intrinsic quality, Algorithm 1 runs in polynomial time and achieves a (1+β)(1+β)-approximation. • Hierarchical interactions: If the spillover graph forms a tree, the HOP algorithm (Algorithm 3) computes a near-optimal mechanism in polynomial time. • Random interaction graphs: If spillover coefficients are drawn i.i.d. from a uniform distribution, the Greedy Cost Selection algorithm (Algorithm 2) runs in O(N2)O(N^2) time and is asymptotically optimal, achieving a (1−O(N−1/4))(1-O(N^- 14))-approximation with high probability. Simulations justify the algorithm’ practical advantage. Due to space constraints, we defer some of the proofs to the appendix. 1.2 Related Work We roughly divide all related work into three strands of literature: strategic Content creation, Contest Theory, and economic spillovers. Strategic content creation and GenAI The strategic behavior of content creators in algorithmically mediated platforms has received substantial attention in recent years. A foundational line of work examines how creators compete for attention and adapt their strategies in recommendation systems Ben-Porat et al. (2019); Jagadeesan et al. (2023); Boutilier et al. (2023); Zhu et al. (2023). These works address key challenges such as incentivizing content quality Ghosh and Hummel (2011), improving stability of recommendation systems Adomavicius and Zhang (2012, 2015), and aligning creator incentives with platform-level objectives Van Alstyne et al. (2016). More related to our work, Ben-Porat and Tennenholtz (2018) consider a different mathematical setting but seek mechanisms that satisfy several fairness and stability axioms. We consider a design problem of a similar flavor, but our setting includes effort levels, spillovers, and social welfare optimization, which are absent from their framework. The recent proliferation of Generative AI (GenAI) has introduced new complexity Taitler and Ben-Porat (2025). Several works explore how GenAI alters the competitive dynamics between human creators and AI-generated content. For instance, Yao et al. (2024a) study the competition between human creators and a GenAI agent, characterizing conditions under which symbiosis or conflict arises. Esmaeili et al. (2024) analyze how human creators should strategize their content creation in the presence of GenAI, while Zhao et al. (2026) examine strategic content creation mode choices when creators must decide between human-creation and GAI-creation strategies. Keinan and Ben-Porat (2025) introduce a model where creators strategically decide both their content quality and whether to share their content with a platform’s GenAI system. Unlike these works, which largely focus on creator-platform interactions or creator-AI competition, our model centers on the spillover effects among creators induced by using GenAI and the mechanism design problem of incentivizing effort under equilibrium with such interdependencies. Contest theory Our work draws on the rich literature on contest theory, which examines games in which players invest costly effort to win prizes. The literature has developed several canonical contest success functions (CSFs). The all-pay auction Hillman and Riley (1989) models winner-takes-all scenarios where the highest effort wins with certainty. The Tullock contest Tullock (1980) allocates prizes proportionally to contestants’ efforts, and has been extensively studied for its equilibrium properties Corchón (2007); Chowdhury and Sheremeta (2011). Extensions to the basic framework include CSFs that admit ties Blavatskyy (2010); Jia (2012) and mechanism design approaches that study optimal CSF selection under informational asymmetries Polishchuk and Tonis (2013). Recent work by Yao et al. (2024a) adapts the Tullock framework to model competition between human creators and GenAI, in which user traffic is distributed according to relative content quality. Our mechanism design problem departs from classical contest theory in a fundamental way: we consider settings with positive spillovers, where one creator’s effort can improve the quality of others. As we show in Section 2.3, this spillover structure undermines the stability guarantees that hold in standard contests. Public goods and spillovers A central feature of our model is the presence of positive spillovers, where each creator’s effort benefits not only themselves but also others in the ecosystem. This phenomenon has deep roots in the economics literature on innovation and R&D Cohen and Levinthal (1989); Griliches (1991); Aghion and Jaravel (2015), where knowledge spillovers arise because innovations by one firm can be partially appropriated by competitors. Similar dynamics emerge in the public goods literature, where strategic agents decide how much to contribute to a shared resource Bramoullé and Kranton (2007). Recently, Cheng et al. (2025) study networked digital public goods games with heterogeneous players, capturing the non-exclusivity of digital resources that encourages free-riding. The economic value of data in our setting relates to the broader literature on data economics. Jones and Tonetti (2020) demonstrate that the value of data is driven by a ”scale effect”: the accumulation of information from multiple sources—rather than any single contribution. This insight motivates our social welfare objective, which aggregates quality across all creators. Empirical work on scaling laws for large language models Kaplan et al. (2020); Sun et al. (2017); Hestness et al. (2017); Rosenfeld et al. (2020) confirms that model performance improves predictably with dataset size, providing a concrete foundation for our quality functions. However, a critical caveat is that synthetic data generated by AI systems cannot substitute for human-created content; recent studies show that training on AI-generated data leads to model collapse and degraded performance Shumailov et al. (2023); Alemohammad et al. (2024). This limitation underscores the importance of incentivizing human content creation in GenAI ecosystems—the central challenge our work addresses. 2 Model We study a game representing the content creation ecosystem, involving a mechanism designer (or platform) and strategic content creators. Content creators decide how much effort they want to invest in producing their content, while each creator’s effort might denote to the quality of others due to spillovers. The platform decides how to allocate user attention to them. It can only see creators’ quality product, but their effort remains hidden. We call this game Content Creation with Spillovers (CCS). Formally, the game is defined as a tuple G=⟨,(Qi)i,(ci)i,ℳ⟩G= ,(Q_i)_i,(c_i)_i,M . Players, Strategies and Costs Let =1,…,NN=\1,…,N\ be the set of players (content creators). Each player i∈i selects an effort intensity xi∈[0,1]x_i∈[0,1], where xi=0x_i=0 means no effort and xi=1x_i=1 means maximum capacity. This variable represents the creator’s overall investment intensity, aggregating multiple inputs such as creative labor and time devoted to production. The strategy profile of all players is denoted by =(x1,…,xN)∈[0,1]Nx=(x_1,…,x_N)∈[0,1]^N. Exerting effort incurs a cost, modeled by a function ci:[0,1]→[0,1]c_i:[0,1]→[0,1]. We assume cost functions are normalized to [0,1][0,1], which is standard. We impose some other standard conditions: we assume the cost function ci(⋅)c_i(·) is twice continuously differentiable, convex, strictly increasing, and lastly, it satisfies ci(0)=0c_i(0)=0. Quality and Spillovers The quality of each player i’s content is determined both by the effort of i and by the effort of other, a property we call spillovers. Formally, Given effort profile x, the Quality Function Qi():[0,1]N→[0,1]Q_i(x):[0,1]^N→[0,1] captures how player i’s output quality depends on all creators’ efforts, for example, through shared LLMs trained on other players’ content. To that end, we assume positive spillovers, i.e., for all players i,j∈Ni,j∈ N and all profiles x, ∂Qi∂xj()≥0. ∂ Q_i∂ x_j(x)≥ 0. Note that positive spillovers are free: an increase in any player’s effort weakly improves everyone’s quality, while each player bears costs solely as a function of her own effort. For analytical tractability, we assume QiQ_i is twice continuously differentiable in all arguments. We assume QiQ_i is upper bounded for every i, and w.l.o.g. Qi∈[0,1]Q_i∈[0,1]. Bounded quality represents a normalized metric, such as a predicted probability of user satisfaction, engagement, or a relative relevance grade that the platform can measure. Observability and Contracting We assume a setting of hidden action. While the mechanism possesses data on the ecosystem’s structure, specifically knowing which creators are likely to benefit from each other’s work (through the quality functions Q(⋅)Q(·))—it cannot directly observe the raw effort invested by any creator. Because the platform sees only the final output quality, it cannot contract on effort directly. Thus, rewards can depend only on the quality profile =(Q1,…,QN)Q=(Q_1,...,Q_N). Mechanisms and Utility The platform adopts a mechanism that allocates attention or visibility across creators. Formally, a mechanism is defined by a set of allocation functions ℳ=(M1,…,MN)M=(M_1,…,M_N), where Mi:[0,1]N→[0,1]M_i:[0,1]^N→[0,1] determines the share of total attention captured by player i, as a function of Q. We assume the total attention budget is normalized to 1, such that ∑i∈Mi()≤1 _i M_i(Q)≤ 1 for any profile. Note that we allow for ∑Mi<1Σ M_i<1, representing scenarios where the mechanism chooses to withhold attention (e.g., displaying AI-generated filler content) rather than allocating it to under-performing creators. The utility of player i is the value of their allocated attention minus the cost of effort: Ui()=Mi(Q1(),…,QN())−ci(xi).U_i(x)=M_i(Q_1(x),…,Q_N(x))-c_i(x_i). (1) We define a Pure Nash Equilibrium (PNE) in the standard way Nash (1950). Namely, we say that a profile ∈[0,1]Nx∈[0,1]^N is a PNE if for every player i∈i and every unilateral deviation xi∈[0,1]x_i∈[0,1], it holds that Ui()≥Ui(−i,xi)U_i(x)≥ U_i(x_-i,x_i), where −ix_-i denotes the strategy profiles of all players other than i, and (−i,xi′)(x_-i,x_i ) is the profile obtained by replacing the iith component of x with xi′x_i . Social Welfare We define social welfare as the aggregate quality of content produced in the ecosystem, given a strategy profile x: SW()=∑i=1NQi()SW(x)= _i=1^NQ_i(x). We adopt this summation form for several reasons. First, higher aggregate quality translates directly into higher consumer welfare. This formulation captures the social value without relying on specific platform mechanics, and as shown in Subsection 3.4, already leads to a computationally challenging design problem. Second, since raw effort x is unobservable, the platform cannot directly maximize total labor (i.e., ∑xiΣ x_i). However, given that quality is strictly increasing in effort, maximizing the observable aggregate quality ∑QiΣ Q_i serves as the closest practical proxy. Third, as established by Jones and Tonetti (2020), the economic value of data is driven by a ”scale effect” - the accumulation of information from all sources, rather than the single best contribution. 2.1 Positive Spillovers in the Wild We aspire to conduct a meaningful analysis of the ecosystem without specifying the quality functions Q precisely. To that end, we focus on the essential structure of spillovers. We present the following assumption: Assumption 1 (Effort Complementarities). For every player i∈i , strategy profile x and every other player j∈j , j≠ij≠ i, it holds that ∂2Qi∂xi∂xj()≥0. ∂^2Q_i∂ x_i∂ x_j(x)≥ 0. Assumption 1 suggests that every other player’s effort weakly increases the marginal quality of player i’s own effort. This assumption is motivated by a large body of economics literature Cohen and Levinthal (1989); Griliches (1991); Aghion and Jaravel (2015). To demonstrate that this abstract assumption captures the specific dynamics of the GenAI ecosystem, we present two concrete examples of quality formation: one based on empirical scaling laws, and one based on graph-based spillovers. Example 1. [Scaling Laws Spillovers] Our first example is inspired by scaling laws for LLMS. As demonstrated by a body of literature Sun et al. (2017); Hestness et al. (2017); Rosenfeld et al. (2020); Kaplan et al. (2020), the test loss of an LLM decreases with the training data volume D, and is well approximated by L(D)=(Dc/D)αL(D)= ( D_cD )^α, where α≈0.095α≈ 0.095, and Dc>0D_c>0 is a scaling constant Kaplan et al. (2020). LLM performance is therefore P(D)=1−L(D)=1−(Dc/D)αP(D)=1-L(D)=1- ( D_cD )^α. We interpret creators’ effort as data generation, where the total effective dataset is D=∑j=1Nxj+dD= _j=1^Nx_j+d and d>αd>α representing the amount of pre-existing training data available to the LLM before any creator contributes (a mild assumption, as modern LLMs are trained on vast datasets). The constant DcD_c can be rescaled to match the normalization of x in our model. Using this performance function, we define each player’s quality as Qi()=xi(a+bP())=xi(a+b[1−(Dc∑j=1Nxj+d)α]),Q_i(x)=x_i\! (a+b\,P(x) )=x_i\! (a+b [1- ( D_c _j=1^Nx_j+d )^α ] ), for some a,b≥0a,b≥ 0. Example 2. [Graph Based Spillovers] Our second example is inspired by the framework of Public Goods in Networks Bramoullé and Kranton (2007), and particularly the non-exclusivity of digital resources (like open-source software) encouraging free-riding Cheng et al. (2025). Consider a weighted interaction graph where each node i possesses an intrinsic capability qiq_i, and a directed edge from j to i with weight gijg_ij represents the spillover intensity (where qi,gijq_i,g_ij are non-negative constants). The quality function is given by: Qi()=xi(qi+∑j≠igijxj).Q_i(x)=x_i (q_i+ _j≠ ig_ijx_j ). This decoupled structure intuitively captures the production process: the term xiqix_iq_i reflects the quality a creator generates in isolation, while the term xi∑j≠igijxjx_i _j≠ ig_ijx_j represents the additional value amplified by the ecosystem, which makes sense because a player who invests more might take advantage more of the spillovers. As we formally prove in Appendix A, Lemma 3. The quality functions in Example 1 and Example 2 satisfy Assumption 1. The two examples above illustrate that Assumption 1 is not merely a technical convenience, but rather captures a common structural feature of quality formation in GenAI. Consequently, from here on, we focus our attention on instances satisfying Assumption 1. Remark Throughout the paper, we represent the spillover relationships between players, as embedded in the quality functions (Qi)i(Q_i)_i, using a directed interaction graph. Each vertex i corresponds to a player, and a directed edge (i,j)(i,j) indicates the presence of spillover effects from player i to player j. 2.2 The Platform’s Design Problem Thus far, we have deliberately abstracted from the platform’s objective. Ideally, the platform should offer high social welfare to its consumers under equilibrium. In what follows, we formally define this design problem. Let G denote the class of all game instances with quality functions satisfying effort complementarities (Assumption 1). Further, let (ℳ)G(M) be the subclass of games induced by the mechanism ℳM. We begin by requiring mechanisms to satisfy a minimal stability property. Definition 1. (Stability) A mechanism ℳM is stable if, for every game G∈(ℳ)G (M), G possesses at least one PNE. Conversely, we say a mechanism is unstable if there exists a game G∈(ℳ)G (M) that does not possess a PNE. The role of algorithmic stability has been noted both empirically Adomavicius and Zhang (2012, 2015) and theoretically Jagadeesan et al. (2023); Ben-Porat and Tennenholtz (2018). Given a mechanism is stable, Another goal the designer wants to achieve, subject to being stable, is maximizing Social Welfare (SW()SW(x)). The optimization problem is to choose ℳM that maximizes SWSW subject to the constraint that x is PNE induced by ℳM. Note on Equilibrium Selection We acknowledge that multiple PNEs with varying welfare levels may exist, rendering the optimization constraint currently ill-defined. We formally resolve this ambiguity in the subsequent section by establishing the specific equilibrium selection. 2.3 Failure of Popular Mechanisms Now we move to defining two standard contest formats as mechanisms in this environment, and analyzing their performance. Unfortunately, as we observe, both of them fail to possess Stability. • The Winner-Takes-All mechanism, denoted ℳWTAM^WTA. It is defined s.t. for every i∈i , Mi()=1N()i∈argmax(Q1,…QN)0otherwise. M_i(Q)= cases 1N(Q)&i∈ *arg\,max(Q_1,...Q_N)\\ 0& otherwise cases. and N(Q)=|argmax(Q1,…,QN)|N(Q)=| *arg\,max(Q_1,…,Q_N)|. • The Tullock mechanism, which was introduced in the seminal work of Tullock (1980), denoted by ℳTullM^Tull. is defined s.t. ∀i:Mi()=Tullocki(Q1,…,QN)=Qi∑jQj∀ i:M_i(Q)=Tullock_i(Q_1,…,Q_N)= Q_i _jQ_j.111For completeness, we assume that whenever x generates qualities Q1()=⋯=QN()=0Q_1(x)=·s=Q_N(x)=0, Tullock Mechanism reduces to uniform allocation, following Chowdhury and Sheremeta (2011). Proposition 4. ℳWTAM^WTA and ℳTullM^Tull are unstable. The instability proof of ℳWTAM^WTA is deferred to Appendix A. We now provide a proof sketch demonstrating the instability of ℳTullM^Tull. Proof Sketch of 4. We provide a two–player counterexample defined by Q1(x1,x2)=12x1Q_1(x_1,x_2)= 12x_1, Q2(x1,x2)=x1x2Q_2(x_1,x_2)=x_1x_2, and linear costs c1(x1)=c2(x2)=14xic_1(x_1)=c_2(x_2)= 14x_i. In this setting, Player 1’s effort raises both her own quality and Player 2’s quality, while Player 2’s effort benefits only herself. We demonstrate that no Pure Nash Equilibrium (PNE) exists by exhaustively analyzing the strategy space. First, the profile (0,0)(0,0) is not a PNE because Player 1 strictly prefers any deviation x1′>0x_1 >0, which allows her to capture the entire attention budget at zero competition. Next, consider profiles where Player 1 is active (x1>0x_1>0). If Player 2 is inactive (profile (x1,0)(x_1,0)), she has a profitable deviation to x2≈0.914x_2≈ 0.914. Conversely, if both players are active ((x1,x2)(x_1,x_2) with xi>0x_i>0), Player 1’s payoff becomes strictly decreasing in her own effort, prompting a deviation to x1=0x_1=0. Similarly, no profile of the form (0,x2)(0,x_2) with x2>0x_2>0 is stable; since Q2Q_2 becomes zero when x1=0x_1=0, Player 2’s best response is to cease effort. Since every region of the strategy space admits a profitable deviation, we conclude that no PNE exists. ∎ This motivate the search for stable mechanisms which maximize SW value. 3 Provisional Allocation Mechanisms As established in Proposition 4, popular contest mechanisms often fail to produce stable equilibria in the presence of strong positive spillovers. In this section, we propose a family of mechanisms designed to handle these spillovers robustly and establish the computational complexity of optimizing over a natural subset of this family. 3.1 Provisional Allocation Mechanisms We start with a formal definition of the family of Provisional Allocation mechanisms Definition 2. We say ℳM is a Provisional Allocation Mechanism (PRA) if there exists a vector =(p1,…,pN)∈[0,1]Np=(p_1,…,p_N)∈[0,1]^N satisfying ∑i=1Npi≤1 _i=1^Np_i≤ 1, such that Mi(();)=pi⋅Qi()M_i(Q(x);p)=p_i· Q_i(x) for every i∈[N]i∈[N]. We let ℱPRAF^PRA be the family of all provisional allocation mechanisms. Every member in the family has two critical features: • Monotonically Non-Decreasing: Allocation MiM_i depends on player i’s quality QiQ_i and their assigned fixed portion pip_i. This ensures that an increase in a competitor’s quality QjQ_j affects player MiM_i only through the positive spillover in the quality function Qi()Q_i(x), not through a reduction in market share. • Quality-Scaled Allocation: Since Qi∈[0,1]Q_i∈[0,1], the term piQip_iQ_i represents a fraction of the reserved share pip_i. Therefore, there exist profiles x, for which allocations sum ∑ipiQi() _ip_iQ_i(x) is smaller than 11. Intuitively, low-quality output reduces a player’s realized visibility. The remaining attention is absorbed by baseline or platform-generated content, rather than reallocating it to competitors. 3.2 Game-Theoretic Properties The following theorem establishes that the Provisional Allocation family provides a robust solution to the equilibrium selection problem, guaranteeing stability and Pareto dominance of the selected equilibrium. Theorem 5 (Stability and Selection). For every mechanism ℳ∈ℱPRAM ^PRA, the following properties hold: 1. Stability: The mechanism ℳM is stable. 2. Equilibrium Selection: In every induced game ∈(ℳ)G (M), there exists a specific PNE, named ”greatest equilibrium” and denoted by ¯ x, such that for any other PNE x: (a) SW(¯)≥SW()SW( x)≥ SW(x). (b) Ui(¯)≥Ui()U_i( x)≥ U_i(x) for every player i∈i . (c) ¯ x is reachable via iterated best-response dynamics. Proof Sketch. Parts 1 and 2c follow from the fact that any game G(ℳ)G(M) for ℳ∈ℱPRAM ^PRA is a supermodular game Topkis (1998), as we now show. Parts 2a and 2b are not a direct consequence of supermodularity, and require additional arguments provided below. Definition 3 (Supermodular Game). A game is said to be supermodular if for every player i∈i and any two profiles ,′x,x such that xi≥xi′x_i≥ x_i for every i∈i , it holds that: Ui(xi,−i)−Ui(xi′,−i)≥Ui(xi,−i′)−Ui(xi′,−i′).U_i(x_i,x_-i)-U_i(x _i,x_-i)≥ U_i(x_i,x _-i)-U_i(x _i,x _-i). First, observe that under any mechanism ℳ∈ℱPRAM ^PRA, the utility function is given by Ui()=piQi()−ci(xi)U_i(x)=p_iQ_i(x)-c_i(x_i). By Assumption 1 (Effort Complementarities) and the constant allocation pip_i, the game satisfies the supermodularity condition. Part 1 follows directly from the fundamental theorem of supermodular games (see (Topkis, 1998, Theorem 4.2.1)), which guarantees the existence of a ”greatest” equilibrium ¯ x that dominates all others component-wise, i.e. ¯> x>x for any other PNE x. Part 2c follows from another familiar result of supermodular games, that best-response dynamics starting from the upper bound of the strategy space converge to ¯ x (Vives, 2018, Result 4). Next, we prove Part 2a. Recall that Social Welfare is SW()=∑Qi()SW(x)=Σ Q_i(x). Due to non-negative spillovers, all quality functions QiQ_i are non-decreasing in the efforts of all players. Consequently, SW()SW(x) is monotonic non-decreasing. Therefore, the vector inequality ¯≥ x implies SW(¯)≥SW()SW( x)≥ SW(x). Finally, we prove Part 2b. Let ¯ x be the greatest PNE and x be any other PNE. Since ¯ x is a PNE, player i cannot improve by deviating from x¯i x_i to any other strategy, specifically xix_i (their strategy in the alternative equilibrium), thus: Ui(x¯i,¯−i)≥Ui(xi,¯−i)U_i( x_i, x_-i)≥ U_i(x_i, x_-i). We then compare the right-hand side to Ui()U_i(x). Since ¯≥ x implies ¯−i≥−i x_-i _-i, and QiQ_i is monotonically increasing in the efforts of others (positive spillovers), we have Qi(xi,¯−i)≥Qi(xi,−i)Q_i(x_i, x_-i)≥ Q_i(x_i,x_-i). Given that pi≥0p_i≥ 0, this implies: Ui(xi,¯−i)≥Ui(xi,−i)=Ui()U_i(x_i, x_-i)≥ U_i(x_i,x_-i)=U_i(x). Combining these inequalities yields Ui(¯)≥Ui()U_i( x)≥ U_i(x) for all i. ∎ Since any Provisional Allocation mechanism is fully characterized by its vector p, we denote the greatest equilibrium of a game, induced by p, as ¯() x(p). Consequently, Theorem 5 provides a principled equilibrium selection rule, uniquely identifying the greatest equilibrium profile ¯() x(p) as the outcome of any mechanism p. The designer’s problem becomes well-defined and ensures to yield the stable outcome on which players are most motivated to coordinate. Specifically, the optimization is over the choice of mechanism ℳ∈ℱPRAM ^PRA, or equivalently, over the allocation vector p: maxSW(¯()). _p\;SW\! ( x(p) ). (2) 3.3 Strategic Complementarities as Means of Mitigating Spillovers Our choice of the Provisional Allocation Mechanism is not arbitrary. We now demonstrate that any mechanism aiming to preserve the robust stability properties of supermodular games must necessarily take this form. The following analysis establishes that imposing Strategic Complementarities, the defining condition of supermodular games, logically implies both the monotonicity and the specific separable structure of our mechanism. Motivation: Counteracting the Free-Rider Problem In a generative economy, spillovers pose a significant risk. While better data improves the ecosystem, it creates a ”free-rider” problem: if high-quality content is readily available for costless imitation, creators may reduce their own genuine effort and rely on replication instead. This dynamic threatens to induce a ”Model Collapse” scenario, where the ecosystem floods with derivative synthetic content while genuine innovation stalls. Given the established risks associated with an over-reliance on synthetic data Alemohammad et al. (2024); Jordon et al. (2022); Shumailov et al. (2023), it is critical to design mechanisms that counteract this tendency. Definition 4 (Strategic Complementarities). A game exhibits Strategic Complementarities if the marginal utility of every player i is non-decreasing in the strategy of any other player j. Assuming twice-differentiable utility functions, this is satisfied if and only if: ∂2Ui∂xi∂xj≥0∀j≠i. ∂^2U_i∂ x_i∂ x_j≥ 0 ∀ j≠ i. Theorem 6. Let ℳ=M1,…,MNM=\M_1,…,M_N\ be a mechanism that is twice-differentiable with respect to qualities Q. If ℳM guarantees that every game induced by it satisfies Strategic Complementarities, then ℳM must satisfy the following necessary conditions: 1. Monotonicity in Qualities: The mechanism share MiM_i must be non-decreasing in all quality arguments. That is, ∂Mi∂Qk≥0 ∂ M_i∂ Q_k≥ 0 for all i,k∈i,k . 2. Separable Form: Each component of the mechanism must be of the form Mi()=bi⋅fi()M_i(Q)=b_i· f_i(Q), where bib_i is a constant such that ∑bi≤1Σ b_i≤ 1, and fi:[0,1]N→[0,1]f_i:[0,1]^N→[0,1]. Proof. Since the cost function ci(xi)c_i(x_i) is independent of xjx_j, the condition of strategic complementarities reduces to: ∂2Mi(())∂xi∂xj≥0,∀∈[0,1]N,∀i∈[N],∀j≠i. ∂^2M_i(Q(x))∂ x_i∂ x_j≥ 0, ∈[0,1]^N,∀ i∈[N],∀ j≠ i. (3) Part 1 Since the partial derivatives ∂Mi∂Qk ∂ M_i∂ Q_k depend only on Q and not on how qualities are produced from efforts, and condition (3) must hold for every valid quality profile ()Q(x), the specific effort profile x is immaterial—what matters is that for any target point 0∈[0,1]NQ_0∈[0,1]^N, we can construct a quality profile that evaluates the mechanism’s derivatives at 0Q_0, thereby deriving necessary conditions at an arbitrary point in the quality space. Fix a point 0∈[0,1]NQ_0∈[0,1]^N. Let the quality functions be defined as: Qk()=Q0,k+xlxm,andQr()=Q0,r∀r≠k.Q_k(x)=Q_0,k+x_lx_m, Q_r(x)=Q_0,r ∀ r≠ k. Applying the chain rule to (3) with i=li=l and j=mj=m for this specific instance yields: ∂2Ml∂xl∂xm=∂Ml∂Qk⋅∂2Qk∂xl∂xm+∑r∂2Ml∂Qk∂Qr⋅∂Qr∂xl⋅∂Qk∂xm. ∂^2M_l∂ x_l∂ x_m= ∂ M_l∂ Q_k· ∂^2Q_k∂ x_l∂ x_m+ _r ∂^2M_l∂ Q_k∂ Q_r· ∂ Q_r∂ x_l· ∂ Q_k∂ x_m. Substituting the derivatives of our constructed QkQ_k (where ∂2Qk∂xl∂xm=1 ∂^2Q_k∂ x_l∂ x_m=1, ∂Qk∂xl=xm ∂ Q_k∂ x_l=x_m, and ∂Qk∂xm=xl ∂ Q_k∂ x_m=x_l), and noting that derivatives for r≠kr≠ k vanish: ∂Ml∂Qk+∂2Ml∂Qk2⋅xlxm≥0. ∂ M_l∂ Q_k+ ∂^2M_l∂ Q_k^2· x_lx_m≥ 0. This inequality must hold for all x. Evaluating at =x=0, the second term vanishes, leaving: ∂Ml∂Qk|=0≥0. ∂ M_l∂ Q_k |_Q=Q_0≥ 0. Since 0Q_0, l, and k were chosen arbitrarily, MiM_i must be non-decreasing in all quality arguments for all i. Part 2 Monotonicity implies that MiM_i is non-decreasing in Q. Combined with the non-negative spillovers of the quality functions (∂Q∂x≥0 ∂ Q∂ x≥ 0), the composite function Mi(())M_i(Q(x)) is non-decreasing in x. Consequently, the maximum possible attention portion for every player i is attained at ⋆=(1,…,1)x =(1,…,1). Define: bi≡Mi((⋆)),fi()=Mi()biif bi>0,0if bi=0.b_i≡ M_i(Q(x )), f_i(Q)= cases M_i(Q)b_i&if b_i>0,\\[6.0pt] 0&if b_i=0. cases We verify the required properties. The allocation constraint ∑kMk()≤1 _kM_k(Q)≤ 1 evaluated at ⋆x gives: ∑i=1Nbi=∑i=1NMi((⋆))≤1. _i=1^Nb_i= _i=1^NM_i(Q(x ))≤ 1. For the range of fif_i: if bi=0b_i=0, then 0≤Mi()≤bi=00≤ M_i(Q)≤ b_i=0, so Mi()≡0M_i(Q)≡ 0 and the form holds trivially. If bi>0b_i>0, then Mi()≥0M_i(Q)≥ 0 gives fi()≥0f_i(Q)≥ 0, and monotonicity gives Mi()≤Mi((⋆))=biM_i(Q)≤ M_i(Q(x ))=b_i, so fi()≤1f_i(Q)≤ 1. Thus fi:[0,1]N→[0,1]f_i [0,1]^N→[0,1] and Mi()=bi⋅fi()M_i(Q)=b_i· f_i(Q) with ∑ibi≤1 _ib_i≤ 1. ∎ This result suggests that our proposed mechanism family (Mi=piQiM_i=p_iQ_i) is not merely one possible solution, but essentially the ’basic’ form required to guarantee coordination and prevent best response cycles typical of competitive games with spillovers. 3.4 Hardness Result Having defined and analyzed the family of mechanisms we consider, we now turn to the problem of optimizing SW. We seek the mechanism parameter p that maximizes the greatest PNE’s social welfare of the induced game. As the following theorems show, this optimization problem is not only computationally hard, but also hard to approximate. Theorem 7. SW Optimization Problem (2) is NP-Hard. Proof Sketch. We reduce from the Maximum Clique. Given a graph G=(V,E)G=(V,E) with |V|=N|V|=N, we construct an instance using the graph-based spillover model (Example 2). For each player i∈Vi∈ V, define: Qi()=1N(xi+∑j≠i(i,j)∈Exixj),ci(xi)=xiN.Q_i(x)= 1N (x_i+ _ subarraycj≠ i\\ (i,j)∈ E subarrayx_ix_j ), c_i(x_i)= x_iN. Under any Provisional Allocation mechanism with parameter p, player i’s utility is linear in xix_i, so best responses are binary: xi∈0,1x_i∈\0,1\. The key insight is that any optimal allocation ⋆p induces equilibrium where players form a clique. Specifically, we show (Lemma 16 in Appendix C) that for any allocation where some subset ′⊆N of players exert effort xi=1x_i=1, the allocation constraint forces ′N to be a clique in G, with each active player receiving equal share pi=1/|′|p_i=1/|N |. Consequently, the social welfare becomes SW=|′|2/NSW=|N |^2/N, which is strictly increasing in clique size. Thus, solving Problem (2) requires finding a maximum clique, establishing NP-hardness. ∎ Furthermore, due to the inapproximability of the Max-Clique problem (Håstad, 1999, Theorem, 5.2), we obtain that: Corollary 8. For any ϵ>0ε>0, unless NP=ZPPNP=ZPP, there is no polynomial-time algorithm that approximates Problem (2) within a factor N1−εN^1- . Interestingly, solving Problem (2) is hard even if there are no spillovers and Qi(⋅)Q_i(·) and ci(⋅)c_i(·) are linear. In such a case, the problem reduces to the Knapsack problem, as we prove in Theorem 17. 4 Efficient Algorithms for Structured Instances In this section, we focus on a fixed instance of our game and seek a vector p that induces a non-trivial approximation to the optimal social welfare. To this end, we propose two approaches. The first bounds the spillover effects, while the second focuses on instances that exhibit an underlying tree structure. 4.1 A Crude Approach To handle Problem (2), we first adopt a crude approach that performs well when spillovers are present but can be bounded. We begin by formally characterizing bounded spillovers. Definition 5 (β-Bounded Spillovers). A quality function QiQ_i is said to exhibit β-bounded spillovers for a constant β≥0β≥ 0 if for every strategy profile x, it holds that: Qi(xi,x−i)≤(1+β)Qi(xi,−i),Q_i(x_i,x_-i)\;≤\;(1+β)\,Q_i(x_i,0_-i), where −i0_-i denotes the profile in which all players other than i exert zero effort. This definition captures the idea that while spillovers may amplify a creator’s output, they are bounded by a multiplicative factor relative to what the creator could achieve in isolation. This motivates a naive but robust design principle: instead of directly optimizing the true social welfare, which depends on complex interdependencies, the designer may construct and solve an auxiliary problem, which we call No Spillovers Relaxation (NSR). To ensure computational tractability, we assume a discrete framework. We define the set ℬ(ε)=kε:k=0,1,…,⌊1/ε⌋B( )=\k :k=0,1,…, 1/ \. We restrict our solution to allocations in which (pi)i(p_i)_i are multiples of ε . We now establish the guarantee of this approach with respect to the true Social Welfare (SW) in the game with spillovers. Input: Game parameters ⟨,(Qi)i,(ci)i⟩ ,(Q_i)_i,(c_i)_i , granularity ε>0 >0 Output: Provisional Allocation mechanism p Construct the No Spillovers Relaxation (NSR) problem: max∈ℬ(ε)N∑i∈Qi(yi,−i)s.t.∑i∈pi≤1,yi∈argmaxz∈[0,1]piQi(z,−i)−ci(z)∀i. array[]l _p ( )^N& _i Q_i(y_i,0_-i)\\[6.00006pt] s.t.& _i p_i≤ 1,\\[3.99994pt] & y_i∈ _z∈[0,1]\p_iQ_i(z,0_-i)-c_i(z)\ ∀ i. array Compute an optimal solution p using the dynamic programming approach (Lemma 10); return p; fnum@algorithm1ALGORITHM 1 No Spillovers Relaxation Solver (NSR-Solver) Theorem 9. Suppose all quality functions exhibit β-bounded spillovers. For any ε>0 >0, there exists an algorithm that runs in time O(N/ε2)O(N/ ^2) and outputs a mechanism ^∈ℬ(ε)N p ( )^N such that SW(¯(^))≥11+βmax∈ℬ(ε)NSW(¯()).SW( x( p))≥ 11+β _p ( )^NSW( x(p)). Proof of Theorem 9. We implement the algorithm from the theorem in Algorithm 1. The algorithm constructs an optimization problem that neglects spillovers entirely, maximizing welfare as if each creator operated in isolation, and solves it via dynamic programming. From a runtime perspective, we show a reduction to the Multiple-Choice Knapsack Problem (MCKP) Kellerer et al. (2004) in Appendix C. Our runtime guarantees follow from the fact that MCKP can be solved in pseudo-polynomial time via dynamic programming approach. We show this formally in the following lemma. Lemma 10. The optimal solution p to the NSR problem can be computed in time O(N/ε2)O(N/ ^2). The proof of Lemma 10 is provided in Appendix C. Next, we move to proving the social welfare approximation. For clarity, we adopt the following shorthand notation for the relevant equilibrium profiles: • Let ⋆=argmax∈ℬ(ε)NSW(¯())p = _p ( )^NSW( x(p)) denote the optimal mechanism in the discrete setting. • Let ⋆=¯(⋆)x = x(p ). • Let ^=¯(^) x= x( p). • Let y denote the vector induced by p in the NSR problem. Formally, =(y1,…,yN)y=(y_1,…,y_N) where each component satisfies yi∈argmaxzp^iQi(z,−i)−ci(z)y_i∈ _z\ p_iQ_i(z,0_-i)-c_i(z)\. The proof proceeds in three steps: 1. By the definition of β-bounded spillovers (Definition 5), the welfare of the optimal profile ⋆x is bounded by its isolated value scaled by (1+β)(1+β): SW(⋆)=∑i∈Qi(⋆)≤(1+β)∑i∈Qi(xi⋆,−i).SW(x )= _i Q_i(x )≤(1+β) _i Q_i(x_i ,0_-i). (4) 2. The mechanism p is defined as the maximizer of the no-spillover welfare ∑Qi(yi,−i)Σ Q_i(y_i,0_-i) over all feasible allocations. Since ⋆p is a feasible allocation (∑pi⋆≤1Σ p_i ≤ 1), the no-spillover welfare generated by p must be at least that generated by ⋆p . Recall that xi⋆x_i is supported by ⋆p . In the NSR formulation, the objective is maximized by y. Thus: ∑i∈Qi(xi⋆,−i)≤∑i∈Qi(yi,−i). _i Q_i(x_i ,0_-i)≤ _i Q_i(y_i,0_-i). (5) Combining (4) and (5), we obtain: SW(⋆)≤(1+β)∑i∈Qi(yi,−i).SW(x )≤(1+β) _i Q_i(y_i,0_-i). 3. We compare the profile y to the real equilibrium x. In the no-spillover setting, yiy_i is the best response to p^i p_i assuming zero spillovers. In the real game, player i responds to p^i p_i given non-negative spillovers from others. Due to Strategic Complementarities (Definition 4), the marginal utility of effort is non-decreasing in the efforts of others. Therefore, the equilibrium effort with positive spillovers is at least the effort with zero spillovers: ^≥ x . Since quality functions QiQ_i are monotonically increasing in all effort levels, we have: ∑i∈Qi(^)≥∑i∈Qi()≥∑i∈Qi(yi,−i). _i Q_i( x)≥ _i Q_i(y)≥ _i Q_i(y_i,0_-i). (6) Combining the results from the three steps yields: SW(⋆)≤(1+β)SW(^)⟹SW(^)≥11+βSW(⋆).SW(x )≤(1+β)SW( x) SW( x)≥ 11+βSW(x ). ∎ 4.2 Near-Optimal Mechanism for Trees In this subsection, we leverage the hierarchical structure of tree-based interaction graphs to compute a near-optimal solution to the Problem (2) via dynamic programming. Consider instances where the interaction graph G=(,E)G=(N,E) forms a rooted tree. Each player (except the root) receives spillovers from exactly one parent. Under the graph-based spillover model (Example 2) with linear costs ci(xi)=ci⋅xic_i(x_i)=c_i· x_i, each node’s quality depends only on its own effort and its parent’s effort. Writing xparx_par for the parent’s effort, the quality function takes the form Qi(xi,xpar)=xi(qi+gpar,i⋅xpar)Q_i(x_i,x_par)=x_i(q_i+g_par,i· x_par). Since utility is linear in effort, best responses are binary, which eliminates the need to discretize effort levels. Theorem 11 (Theorem 21). For tree interaction graphs under the graph-based spillover model with linear costs, there exists an algorithm computing an optimal allocation over the discretized allocation set ℬ(ε)=kε:k=0,1,…,⌊1/ε⌋B( )=\k :k=0,1,…, 1/ \ in time O(N/ε2)O(N/ ^2). The algorithm exploits the recursive structure of trees: fixing a node’s effort decouples its children’s subtrees into independent optimization problems coupled only by the shared budget constraint. We define value functions that capture the maximum welfare achievable in each subtree as a function of available budget and parent effort. These are computed bottom-up via dynamic programming, using sequential convolution to optimally allocate budget among children. The optimal allocation is then recovered via top-down extraction. Full details and the proof are provided in Appendix D. 5 Efficient Approximation Guarantees under Random Interaction Graphs In this section, we focus on interaction graphs with linear costs. Namely, we assume that every instance is parameterized by qi∈[0,q⋆],gij∈[0,q⋆],rij∈0,1q_i∈[0,q ],g_ij∈[0,q ],r_ij∈\0,1\ and ci∈[0,1]c_i∈[0,1] for q⋆∈[0,1]q ∈[0,1]. Particularly, the utility function of each agent i is given by Ui(x)=1Npixi(qi+∑j≠ixjgijrij)−1Ncixi.U_i(x)= 1Np_ix_i (q_i+ _j≠ ix_jg_ijr_ij )- 1Nc_ix_i. Our analysis will focus on the random graphs, as we define it in the next subsection. 5.1 Random Interaction Graphs We assume the instance parameters are sampled independently from a distribution, i.e, q~i,g~ij q_i, g_ij from a distribution over the range [0,q⋆][0,q ] with expectation q¯ q. Furthermore, we assume c~i∼Uni([0,1]) c_i ([0,1]) and r~ij∼Bern(r) r_ij (r), where r,q⋆∈[0,1]r,q ∈[0,1] are given exogenously. This model describes a Erdős–Rényi random graph Erdős and Rényi (1959), which captures the setting in which player i affects player j with probability r, and conditional on an interaction, the spillover intensity is drawn uniformly. Definition 6 (Random graph). We define a random graph as a random instance drawn from the joint distribution over q~ii\ q_i\_i, g~iji,j\ g_ij\_i,j, c~ii\ c_i\_i, and r~iji,j\ r_ij\_i,j specified above. Notation When the instance is clear from the context, we keep the notation introduced in previous sections. Additionally, it is convenient to distinguish random quantities induced by a fixed strategy profile over the random parameters of the instance. To this end, we use a tilde to denote random variables. For example, Q~i(x)=xi(q~i+∑j≠ixijg~ijr~ij) Q_i(x)=x_i ( q_i+ _j≠ ix_ij g_ij r_ij ), where Q~i(x) Q_i(x) is a random variable. We use the same notation without the tilde to denote a realization of the corresponding random variable. Additionally, given an effort profile x, we denote by K(x)=∑i=1Nxi=1K(x)= _i=1^N1_x_i=1 the number of players who invest maximal effort. 5.2 The GCS Algorithm Input: N,(rij)ij,(qij)ij,(ci)iN,(r_ij)_ij,(q_ij)_ij,(c_i)_i Output: (pi)i(p_i)_i 1 ←sort((ci)i)N← sort((c_i)_i) where sortsort returns the elements in ascending order ; 2 for k∈N,…1k∈\N,...1\ do 3 pi←0i>kciqi+∑j=1j≠ikrijqijOtherwisep_i← cases0& $i>k$\\ c_iq_i+ _ subarraycj=1\\ j≠ i subarray^kr_ijq_ij& Otherwise cases for every i∈[N]i∈[N] ; 4 if ∑ipi≤1 _ip_i≤ 1 then 5 return (pi)i(p_i)_i ; 6 7 end if 8 9 end for fnum@algorithm2ALGORITHM 2 Greedy Cost Selection (GCS) We now present the GCS algorithm, which is implemented in Algorithm 2. It receives all instance parameters as input and outputs a candidate mechanism. In line 2, the algorithm sorts the players by their costs in ascending order. Line 2 iterates over a parameter k. In each iteration, the value k denotes the number of players the algorithm targets to choose xi(p)=1x_i(p)=1, starting from N and decreasing to 1. Line 2 sets the required portion for each of the first k players in the order to choose xi(p)=1x_i(p)=1. In line 2, we check if those portions are valid, summing to 1 or less. If they are valid, we return the portions in line 2, corresponding to the largest number of players choosing xi(p)=1x_i(p)=1. Intuition The algorithm is surprisingly simple and relies on the following key insight: considering player costs only (and not their qualities) suffices to approximate the optimal social welfare. To see why, consider the following observations. First, notice that the utility of each player is linear in that player’s effort, which leads to the following observation. Observation 1. Fix p, then it holds that xi(p)=0,1x_i(p)=\0,1\ for every player i∈[N]i∈[N]. Next, fix an arbitrary effort profile x and consider the summation in Q~i(x) Q_i(x). This sum has exactly K(x)K(x) terms, all of which are independent random variables. Therefore, as more players invest effort, the quality Q~i Q_i of each such player concentrates around a constant multiple of K(x)K(x). Therefore, 1. the quality Q~i Q_i of each player who invests effort is roughly the same with high probability. 2. To maximize social welfare, we need to maximize the number of players who invest effort. 3. The portion required to incentivize player i to play xi(p)=1x_i(p)=1, given by pi=c~iQ~i(x)p_i= c_i Q_i(x), depends mostly on the cost c~i c_i as the denominator is roughly the same for all players. Therefore, incentivizing the players with the least costs requires the least portion. The next theorem formalized the asymptotic behavior of GCS. Theorem 12. Let p⋆p denote the optimal portions and pap^a be the output of GCS algorithm. For a large enough N, with probability at least 1−4e−Nq¯r1-4e^- N qr it holds that SW(x¯(pa))≥(1−30(q¯r)3N−1/4)SW(x¯(p⋆)),SW( x(p^a))≥ (1- 30 ( qr )^3N^- 14 )SW( x(p )), and the execution time of GCS takes O(N2)O(N^2). Note that Theorem 12 applies only when the number of players is large. We suspect that this is only a byproduct of our proofs. Indeed, later in Section 6 we show empirically that the asymptotic phenomenon captured by Theorem 12 manifests already at small values of N. Next, we provide a proof sketch of the theorem. Proof Sketch of 12. The proof proceeds in three steps. Step 1: reduction to tight portions and lowest costs Following Observation 1, we say a portion p incentivizes a player i if that player chooses xi(p)=1x_i(p)=1. Hence, for any portion that incentivizes a set S⊂NS⊂ N, we may assume w.l.o.g. that every incentivized player receives a tight portion pi=ci/Qi(x¯(p))p_i=c_i/Q_i( x(p)), as increasing any such portion does not change the induced effort profile or social welfare. Ordering players by cost, this implies that if a set of k players can be incentivized for some realized qualities, then the same set of k players would remain incentivizable if their costs were replaced by the k lowest costs. Formally, the feasibility constraint ∑ipi≤1 _ip_i≤ 1 can be upper bounded using the k lowest costs (details in the appendix). Step 2: clean event and bounds on the incentivized set size We define the clean event under which two concentration statements hold simultaneously: (i) Quality concentration: for any portion vector p that incentivizes k players, the realized quality of every incentivized player satisfies Qi(x¯(p))=kq¯r±O(k3/4)Q_i( x(p))=k qr± O(k 34) with high probability. In particular, under the clean event, player qualities are only implicitly depend on p and x. (i) Cost concentration: the sum of the k lowest costs satisfies ∑i=1kc(i)=12(k/N)2N±O(N3/4). _i=1^kc_(i)= 12(k/N)^2N± O(N^3/4). Combining (i) and (i), we analyze the feasibility condition in Line 2, ∑ipi≤1, _ip_i≤ 1, for portions that incentivize exactly k players. We use tight portions pi=ci/Qi(x¯(p))p_i=c_i/Q_i( x(p)), and bound the total cost by the sum of the k lowest order statistics. Combined with the concentration results, this yields explicit upper and lower bounds on the number of players that can be incentivized by any approach that maximizes the number of effort-investing players. In particular, with high probability, there exist integers k¯ k and k¯ k such that any such feasible portion vector incentivizes at most k¯ k players and at least k¯ k players, where k¯≤N(2q¯r+O(N−1/4)),k¯≥N(2q¯r−O(N−1/4)). k≤ N\! (2 qr+O\! (N^-1/4 ) ), k≥ N\! (2 qr-O\! (N^-1/4 ) ). (7) Crucially, these bounds apply to both k⋆k (optimal) and kak^a (algorithmic), since both outcomes must satisfy the same feasibility constraint under the clean event. Step 3: Translating the bounds into a welfare guarantee Let k⋆=K(x¯(p⋆))k =K( x(p )) be the number of incentivized players under p⋆p and ka=K(x¯(pa))k^a=K( x(p^a)) be the number under pap^a. We emphasize that pap^a and p⋆p are defined with respect to the instance, therefore kak^a and k⋆k are random variables. Under the clean event, we can plug the matching lower/upper bounds on total quality as a function of k. Plugging the extreme values ka≥k¯andk⋆≤k¯k^a≥ k k ≤ k into the resulting welfare ratio expression gives SW(x¯(pa))SW(x¯(p⋆))≥ka⋅q⋆r2−(ka)3/4q⋆+k⋆⋅q⋆r2+(k⋆)3/4⋅kak⋆≥ 1−30(q¯r)3N−1/4. SW( x(p^a))SW( x(p ))\;≥\; k^a· q r2-(k^a)^3/4q +k · q r2+(k )^3/4· k^ak \;≥\;1- 30 ( qr )^3N^-1/4. ∎ The proof of Theorem 12 highlights two more insights. First, the bounds on the incentivized players in Inequality (7) provide the asymptotic order of the optimal social welfare. We present it in the next corollary. Corollary 13. The optimal social welfare satisfies SW(x¯(p⋆))=O(N(q¯r)3)SW( x(p ))=O\! (N( qr)^3 ), and in particular it holds that limN→∞SW(x¯(p⋆))=4N(q¯r)3. _N→∞SW( x(p ))=4N( qr)^3. Second, since players’ utilities are linear in their own effort, the portion offered to each player acts as a threshold. Players exert maximal effort whenever their portion passes this threshold, and exert zero effort otherwise. As a result, the equilibrium effort profile induced by the GCS algorithm can be recovered directly from its output. Corollary 14. Let pap^a be the output of the GCS algorithm. For every player i∈Ni∈ N, the equilibrium effort in x¯(pa) x(p^a) satisfies x¯i(pa)=1if pia>00otherwise. x_i(p^a)= cases1&if p^a_i>0\\ 0&otherwise cases. 6 Experimental Validation In this section, we validate the performance of GCS through simulations on random instances drawn from the setting defined above. Algorithmic implementation The implementation uses standard Python scientific computing libraries (NumPy, Matplotlib) and is CPU-based. We consider two algorithms: • Greedy Cost Selection We closely follow the implementation in Algorithm 2. • Equal Allocation (Baseline): This baseline assigns equal portions pi=1/Np_i=1/N to all players. We compute the greatest pure Nash equilibrium via best-response dynamics starting from the maximal profile x=(1,…,1)x=(1,…,1). Empirically, the dynamics converge monotonically to the equilibrium within a small number of iterations. Simulation pipeline For each parameter configuration that we define shortly, we execute the following procedure: 1. Draw 1000 independent game instances with qi,gij∼Uni(0,q⋆)q_i,g_ij (0,q ), costs ci∼Uni(0,1)c_i (0,1) and rij∼Bern(r)r_ij (r). 2. For each instance, we run both Greedy Cost Selection and Equal Allocation. 3. Record the social welfare achieved and the number of active players K(x)K(x) for each algorithm. 4. We present the mean values across all instances, with shaded regions indicating error bars set at three standard deviations. Experimental setup We conducted three sets of experiments: 1. Varying N: Fix q⋆=1q =1 and vary N∈100,200,…,1000N∈\100,200,…,1000\ for r∈0.2,0.5,0.8r∈\0.2,0.5,0.8\. 2. Varying r: Fix q⋆=1q =1 and vary r∈0.05,0.10,…,0.95r∈\0.05,0.10,…,0.95\ for N∈100,500,1000N∈\100,500,1000\. 3. Varying q⋆q : Fix N=100N=100, r=0.5r=0.5, and vary q⋆∈0.05,0.10,…,1.0q ∈\0.05,0.10,…,1.0\. Each plot also includes the reference value N(q⋆r)3/2N(q r)^3/2 from Corollary 13 (since q¯=q⋆2 q= q 2) and the theoretical prediction K(x¯)≈rq⋆NK( x)≈ rq N for the number of incentivized players. Computational resources All experiments were executed on a standard laptop. The entire simulation required approximately 5 hours. 6.1 Results Figure 1: Results for varying N with q⋆=1q =1. Left: Social welfare scales linearly in N. Right: Number of incentivized players grows proportionally to N. Markers indicate theoretical predictions. Equal Allocation shown for r=0.8r=0.8. Figure 2: Results for varying r with q⋆=1q =1. Left: Social welfare. Right: Number of active players. Markers indicate the theoretical predictions N(q⋆r)3/2N(q r)^3/2 and rq⋆Nrq N, respectively. Equal Allocation shown for N=1000N=1000. Figure 3: Results for varying q⋆q with N=100N=100 and r=0.5r=0.5. Left: Social welfare increases with q⋆q . Right: Larger q⋆q enables larger incentivized sets. Figures 1–3 present the results across all three parameter regimes. We report Performance of Greedy Cost Selection Across all experiments, Greedy Cost Selection achieves average welfare that closely tracks N(q⋆r)3/2N(q r)^3/2, empirically validating Theorem 12 for small values of N. Comparison with Equal Allocation The Equal Allocation baseline achieves substantially lower welfare across all parameter configurations. The performance gap widens as r and q⋆q increase, demonstrating the importance of cost-aware allocation: uniform portions fail to concentrate the allocation on players with the highest marginal welfare contribution. Active player dynamics The right panels of Figures 1–3 display the number of active players K(x)K(x) selected by each algorithm. Greedy Cost Selection achieves incentivized sets of size approximately K(x)≈rq⋆NK(x)≈ rq N, matching the theoretical prediction. In contrast, Equal Allocation often activates significantly fewer players, as the uniform allocation cannot provide sufficient incentives for high-cost players to participate, even when their participation would be socially beneficial due to spillover effects. 7 Discussion and Future Work We have presented a novel setting that captures the economic tension of content creation in the era of GenAI. We used a game-theoretic lens to model an environment where creators exhibit positive spillovers. We demonstrated that popular attention-allocation mechanisms fail to sustain stable equilibria in this environment. Instead, we proposed a novel family of mechanisms based on provisional allocation. We proved that this approach induces a supermodular game structure, ensuring robust stability, and provided approximation algorithms for interesting classes of instances to overcome the computational intractability of the design problem. Our analysis relies on structural properties of the spillover functions, encapsulated in Assumption 1, which is inspired by examples of spillovers in the wild. A natural direction for future research is to characterize the stability guarantees when this assumption does not hold. Furthermore, our current definition of social welfare focuses on the user-centric welfare, ∑QiΣ Q_i. It would be interesting to extend our analysis to multi-dimensional objectives, capturing not only effort but also content diversification. Objectives that include platform revenue could also be of interest. Moreover, we remark that our model assumes a fixed volume of user traffic. A promising extension would be to incorporate endogenous participation, allowing user traffic to depend on the ecosystem’s aggregated quality, a feature recently explored by other works Keinan and Ben-Porat (2025); Yao et al. (2024a). Finally, studying how different notions of fairness or diversity, such as preventing dominance by a small set of highly connected players, interact with spillovers and welfare maximization is an important direction for future work. References Adomavicius and Zhang [2012] Gediminas Adomavicius and Jingjing Zhang. Stability of recommendation algorithms. ACM Transactions on Information Systems (TOIS), 30(4):1–31, 2012. Adomavicius and Zhang [2015] Gediminas Adomavicius and Jingjing Zhang. Improving stability of recommender systems: A meta-algorithmic approach. IEEE Transactions on Knowledge and Data Engineering, 27(6):1573–1587, 2015. doi: 10.1109/TKDE.2014.2384502. Aghion and Jaravel [2015] Philippe Aghion and Xavier Jaravel. Knowledge spillovers, innovation and growth. The Economic Journal, 125(583):533–573, 2015. Alemohammad et al. [2024] Sina Alemohammad, Josue Casco-Arias, Mattie Babaei, Hooman andost, Peter Salehi, and N Goldstein, Tom andin. Self-consuming generative models go mad. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=uWlKjX2h9g. Ben-Porat and Tennenholtz [2018] Omer Ben-Porat and Moshe Tennenholtz. A game-theoretic approach to recommendation systems with strategic content providers. Advances in Neural Information Processing Systems, 31, 2018. Ben-Porat et al. [2019] Omer Ben-Porat, Gregory Goren, Itay Rosenberg, and Moshe Tennenholtz. From recommendation systems to facility location games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1772–1779, 2019. Ben-Porat et al. [2020] Omer Ben-Porat, Itay Rosenberg, and Moshe Tennenholtz. Content provider dynamics and coordination in recommendation ecosystems. Advances in Neural Information Processing Systems, 33:18931–18941, 2020. Blavatskyy [2010] Pavlo R Blavatskyy. Contest success function with the possibility of a draw: Axiomatization. Journal of Mathematical Economics, 46(2):267–276, 2010. Boutilier et al. [2023] Craig Boutilier, Martin Mladenov, and Guy Tennenholtz. Modeling recommender ecosystems: Research challenges at the intersection of mechanism design, reinforcement learning and generative models. arXiv preprint arXiv:2309.06375, 2023. Bramoullé and Kranton [2007] Yann Bramoullé and Rachel Kranton. Public goods in networks. Journal of Economic theory, 135(1):478–494, 2007. Cheng et al. [2025] Yukun Cheng, Xiaotie Deng, and Yunxuan Ma. Networked digital public goods games with heterogeneous players and convex costs. In Proceedings of the ACM on Web Conference 2025, pages 1416–1424, 2025. Chowdhury and Sheremeta [2011] Subhasish M Chowdhury and Roman M Sheremeta. A generalized tullock contest. Public Choice, 147(3):413–420, 2011. Cohen and Levinthal [1989] Wesley M Cohen and Daniel A Levinthal. Innovation and learning: the two faces of r & d. The economic journal, 99(397):569–596, 1989. Corchón [2007] Luis C Corchón. The theory of contests: a survey. Review of economic design, 11(2):69–100, 2007. Erdős and Rényi [1959] P. Erdős and A. Rényi. On random graphs i. Publicationes Mathematicae, 6:290–297, 1959. Esmaeili et al. [2024] Seyed A Esmaeili, Kevin Lim, Kshipra Bhawalkar, Zhe Feng, Di Wang, and Haifeng Xu. How to strategize human content creation in the era of genai? arXiv preprint arXiv:2406.05187, 2024. Ghosh and Hummel [2011] Arpita Ghosh and Patrick Hummel. Incentivizing high-quality user-generated content. In Proceedings of the 20th international conference on World wide web, pages 137–146. ACM, 2011. Griliches [1991] Zvi Griliches. The search for r&d spillovers. National Bureau of Economic Research Working Paper Series, (w3768), 1991. Håstad [1999] Johan Håstad. Clique is hard to approximate within n1−ϵn^1-ε. Acta Mathematica, 182:105–142, 1999. Hestness et al. [2017] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint arXiv:1712.00409, 2017. Hillman and Riley [1989] Arye L Hillman and John G Riley. Politically contestable rents and transfers. Economics & Politics, 1(1):17–39, 1989. Hron et al. [2023] Jiri Hron, Karl Krauth, Michael Jordan, Niki Kilbertus, and Sarah Dean. Modeling content creator incentives on algorithm-curated platforms. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=l6CpxixmUg. Jagadeesan et al. [2023] Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt. Supply-side equilibria in recommender systems. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 14597–14608. Curran Associates, Inc., 2023. URL https://proceedings.neurips.c/paper_files/paper/2023/file/2f1486343c2c942a617e4f5b0c64c8-Paper-Conference.pdf. Jia [2012] Hao Jia. Contests with the probability of a draw: a stochastic foundation. Economic record, 88(282):391–406, 2012. Jones and Tonetti [2020] Charles I. Jones and Christopher Tonetti. Nonrivalry and the economics of data. American Economic Review, 110(9):2819–2858, 2020. doi: 10.1257/aer.20191330. Jordon et al. [2022] James Jordon, Lukasz Szpruch, Florimond Houssiau, Mirko Bottarelli, Giovanni Cherubin, Carsten Maple, Samuel Cohen, and Adrian Weller. Synthetic data – what, why and how?, 05 2022. arXiv preprint arXiv:2205.03257. Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. CoRR, abs/2001.08361, 2020. URL https://arxiv.org/pdf/2001.08361.pdf. Keinan and Ben-Porat [2025] Gur Keinan and Omer Ben-Porat. Strategic content creation in the age of genai: To share or not to share? arXiv preprint arXiv:2505.16358, 2025. Kellerer et al. [2004] Hans Kellerer, Ulrich Pferschy, and David Pisinger. The Multiple-Choice Knapsack Problem, pages 317–347. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. ISBN 978-3-540-24777-7. doi: 10.1007/978-3-540-24777-7˙11. URL https://doi.org/10.1007/978-3-540-24777-7_11. Mas-Colell et al. [1995] Andreu Mas-Colell, Michael Dennis Whinston, Jerry R Green, et al. Microeconomic theory, volume 1. Oxford university press New York, 1995. Nash [1950] John F. Nash. Equilibrium points in ¡i¿n¡/i¿-person games. Proceedings of the National Academy of Sciences, 36(1):48–49, 1950. doi: 10.1073/pnas.36.1.48. URL https://w.pnas.org/doi/abs/10.1073/pnas.36.1.48. Polishchuk and Tonis [2013] Leonid Polishchuk and Alexander Tonis. Endogenous contest success functions: a mechanism design approach. Economic Theory, 52(1):271–297, 2013. Rosenfeld et al. [2020] Jonathan S. Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In Proceedings of the 8th International Conference on Learning Representations, ICLR ’20, Addis Ababa, Ethiopia, 2020. OpenReview.net. URL https://openreview.net/forum?id=ryenvpEKDr. Shumailov et al. [2023] Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Yarin Gal, Nicolas Papernot, and Ross Anderson. The curse of recursion: Training on generated data makes models forget. arXiv preprint arXiv:2305.17493, 2023. Sun et al. [2017] Chen Sun, Abhinav Shrivastava, Saurabh Singh, and Abhinav Gupta. Revisiting unreasonable effectiveness of data in deep learning era. In Proceedings of the IEEE international conference on computer vision, pages 843–852, 2017. Taitler and Ben-Porat [2025] Boaz Taitler and Omer Ben-Porat. Collaborating with genai: Incentives and replacements, 2025. URL https://arxiv.org/abs/2508.20213. Topkis [1998] Donald M. Topkis. Supermodularity and complementarity. Princeton University Press, 1998. Tullock [1980] Gordon Tullock. Efficient rent seeking. In James M. Buchanan, Robert D. Tollison, and Gordon Tullock, editors, Toward a Theory of the Rent-Seeking Society, pages 97–112. Texas A&M University Press, College Station, TX, USA, 1980. Van Alstyne et al. [2016] Marshall W Van Alstyne, Geoffrey G Parker, and Sangeet Paul Choudary. Pipelines, platforms, and the new rules of strategy. Harvard business review, 94(4):54–62, 2016. Vives [2018] Xavier Vives. Supermodularity and supermodular games. In The New Palgrave Dictionary of Economics. Palgrave Macmillan, London, UK, 2018. Yao et al. [2024a] Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. Human vs. generative ai in content creation competition: symbiosis or conflict? arXiv preprint arXiv:2402.15467, 2024a. Yao et al. [2024b] Fan Yao, Yiming Liao, Jingzhou Liu, Shaoliang Nie, Qifan Wang, Haifeng Xu, and Hongning Wang. Unveiling user satisfaction and creator productivity trade-offs in recommendation platforms. Advances in Neural Information Processing Systems, 37:86958–86984, 2024b. Zhao et al. [2026] Nenggui Zhao, Youqing Wu, and Kai Li. Human vs. generative ai: Strategic content creation mode choices for competing creators. International Journal of Production Economics, 292:109913, 2026. ISSN 0925-5273. doi: https://doi.org/10.1016/j.ijpe.2026.109913. URL https://w.sciencedirect.com/science/article/pii/S0925527326000046. Zhu et al. [2023] Banghua Zhu, Sai Praneeth Karimireddy, Jiantao Jiao, and Michael I Jordan. Online learning in a creator economy. arXiv preprint arXiv:2305.11381, 2023. Appendix A Proofs Omitted From Section 2 Proof of Lemma 3. First, in Example 1, we verify that QiQ_i satisfies Assumption 1. First, ∂Qi∂xj=xib∂P∂xj=xib[−Dcα⋅(−α)(∑k=1Nxk+d)−α−1]=αbxi∑k=1Nxk+d(Dc∑k=1Nxk+d)α≥ 0, ∂ Q_i∂ x_j=x_ib ∂ P∂ x_j=x_ib [-D_c^α·(-α) ( _k=1^Nx_k+d )^-α-1 ]= α bx_i _k=1^Nx_k+d ( D_c _k=1^Nx_k+d )^α\;≥\;0, So spillovers are non-negative. ∂2Qi∂xi∂xj ∂^2Q_i∂ x_i∂ x_j =∂xi[αbDcαxi(∑k=1Nxk+d)−(α+1)] = ∂ x_i [α bD_c^αx_i ( _k=1^Nx_k+d )^-(α+1) ] =αbDcα[(∑k=1Nxk+d)−(α+1)+xi⋅(−(α+1))(∑k=1Nxk+d)−(α+2)] =α bD_c^α [ ( _k=1^Nx_k+d )^-(α+1)+x_i·(-(α+1)) ( _k=1^Nx_k+d )^-(α+2) ] =αb(∑k=1Nxk+d)2(Dc∑k=1Nxk+d)α((∑k=1Nxk+d)−(α+1)xi) = α b( _k=1^Nx_k+d)^2 ( D_c _k=1^Nx_k+d )^α ( ( _k=1^Nx_k+d )-(α+1)x_i ) =αb(∑k=1Nxk+d)2(Dc∑k=1Nxk+d)α(∑k≠ixk+d−αxi). = α b( _k=1^Nx_k+d)^2 ( D_c _k=1^Nx_k+d )^α ( _k≠ ix_k+d-α x_i ). Since d represents a pre-existing dataset, we assumed d>αd>α. Given that xi∈[0,1]x_i∈[0,1] and α=0.095α=0.095, the term (d−αxi)(d-α x_i) is strictly positive even if ∑k≠ixk=0 _k≠ ix_k=0. Thus, ∑k≠ixk+d−αxi>0⟹∀i,j,i≠j:∂2Qi∂xi∂xj≥0. _k≠ ix_k+d-α x_i>0 ∀ i,j,i≠ j: ∂^2Q_i∂ x_i∂ x_j≥ 0. Next, we do it for Example 2: ∀i,j,i≠j:∂Qi∂xi∂xj=gi,j≥0∀ i,j,i≠ j: ∂ Q_i∂ x_i∂ x_j=g_i,j≥ 0 So Assumption 1 holds strictly on the entire strategy space for both examples. ∎ Proof of Proposition 4. We prove the instability of each mechanism by providing a counterexample instance that admits no PNE. These instances are motivated by Example 2. Part 1: ℳWTAM^WTA is unstable Consider an instance with N=2N=2 players, where players differ in their productivity: Q1()=x1,Q2()=2x2,c1(x1)=0.5x1,c2(x2)=0.5x2.Q_1(x)=x_1, Q_2(x)=2x_2, c_1(x_1)=0.5x_1, c_2(x_2)=0.5x_2. Under the Winner-Takes-All mechanism, the full attention goes to the player with the highest quality. Player 2 wins if and only if 2x2>x12x_2>x_1 (ties occur on a measure-zero set and can be resolved arbitrarily). The utilities are: U1()=1−0.5x1if x1>2x2−0.5x1if x1<2x2,U2()=−0.5x2if x1>2x21−0.5x2if x1<2x2.U_1(x)= cases1-0.5x_1&if x_1>2x_2\\ -0.5x_1&if x_1<2x_2 cases, U_2(x)= cases-0.5x_2&if x_1>2x_2\\ 1-0.5x_2&if x_1<2x_2 cases. Suppose, for contradiction, that a PNE (x1⋆,x2⋆)(x_1 ,x_2 ) exists. We consider all possible cases: • Case 1: Player 1 wins (x1⋆>2x2⋆x_1 >2x_2 ) and x1⋆<1x_1 <1. Since player 2’s utility is U2=−0.5x2⋆U_2=-0.5x_2 , her best response is x2⋆=0x_2 =0. Given x2⋆=0x_2 =0, player 1 wins with any x1>0x_1>0 and maximizes U1=1−0.5x1U_1=1-0.5x_1 by choosing x1x_1 arbitrarily small. However, for any such small x1>0x_1>0, player 2 can deviate to x2′=x1/2+δx_2 =x_1/2+δ for small δ>0δ>0, winning the full attention and obtaining U2=1−0.5(x1/2+δ)>0U_2=1-0.5(x_1/2+δ)>0. This strictly improves upon U2=0U_2=0, contradicting the PNE assumption. • Case 2: Player 2 wins (2x2⋆>x1⋆2x_2 >x_1 ). Since player 1’s utility is U1=−0.5x1⋆U_1=-0.5x_1 , her best response is x1⋆=0x_1 =0. Given x1⋆=0x_1 =0, player 2 wins with any x2>0x_2>0 and maximizes U2=1−0.5x2U_2=1-0.5x_2 by choosing x2x_2 arbitrarily small. However, for any such small x2>0x_2>0, player 1 can deviate to x1′=2x2+δx_1 =2x_2+δ for small δ>0δ>0, winning the full attention and obtaining U1=1−0.5(2x2+δ)=1−x2−0.5δ>0U_1=1-0.5(2x_2+δ)=1-x_2-0.5δ>0 for sufficiently small x2x_2. This strictly improves upon U1=0U_1=0, contradicting the PNE assumption. • Case 3: x1⋆=1x_1 =1. Player 2 can win by choosing any x2>0.5x_2>0.5. Winning yields U2=1−0.5x2>0.5>0U_2=1-0.5x_2>0.5>0. Otherwise, her utility is U2=−0.5x2≤0U_2=-0.5x_2≤ 0. Thus, player 2’s best response is to win with some x2⋆>0.5x_2 >0.5. But then player 1’s utility is U1=−0.5<0U_1=-0.5<0, and player 1 can strictly improve by deviating to x1=0x_1=0, obtaining U1=0U_1=0. This is a contradiction. Since all cases lead to contradiction, no PNE exists. Part 2: ℳTullM^Tull is unstable Consider an instance with N=2N=2 players: Q1()=0.5x1,Q2()=x1x2,c1(x1)=0.25x1,c2(x2)=0.25x2.Q_1(x)=0.5x_1, Q_2(x)=x_1x_2, c_1(x_1)=0.25x_1, c_2(x_2)=0.25x_2. Note that player 1’s effort raises both her own quality and player 2’s quality, while player 2’s effort benefits only herself. Suppose, for contradiction, that a PNE (x1⋆,x2⋆)(x_1 ,x_2 ) exists. We consider all possible cases: • Case 1: (x1⋆,x2⋆)=(0,0)(x_1 ,x_2 )=(0,0). At this profile, the mechanism allocates uniformly, so U1(0,0)=0.5U_1(0,0)=0.5. However, player 1 can deviate to any small x1>0x_1>0. Since Q1=0.5x1>0Q_1=0.5x_1>0 and Q2=0Q_2=0, player 1 captures the full attention U1(x1,0)=1−0.25x1>0.5,U_1(x_1,0)=1-0.25x_1>0.5, which is a contradiction. • Case 2: (x1⋆,0)(x_1 ,0) with x1⋆>0x_1 >0. At this profile, Q1=0.5x1⋆>0Q_1=0.5x_1 >0 and Q2=0Q_2=0, so player 1 receives the full attention. Player 2’s utility is U2=0U_2=0. We show that player 2 has a profitable deviation. For any x1>0x_1>0, player 2’s utility as a function of x2x_2 is: U2(x1,x2)=x1x20.5x1+x1x2−0.25x2=2x21+2x2−0.25x2.U_2(x_1,x_2)= x_1x_20.5x_1+x_1x_2-0.25x_2= 2x_21+2x_2-0.25x_2. Taking the derivative with respect to x2x_2: ∂U2∂x2=2(1+2x2)2−0.25. ∂ U_2∂ x_2= 2(1+2x_2)^2-0.25. Setting this equal to zero: 2(1+2x2)2=0.25⟹(1+2x2)2=8⟹1+2x2=±8, 2(1+2x_2)^2=0.25 (1+2x_2)^2=8 1+2x_2=± 8, yielding two solutions: x2(1)=8−12≈0.914x_2^(1)= 8-12≈ 0.914 and x2(2)=−8−12≈−1.914x_2^(2)= - 8-12≈-1.914. Since effort levels lie in [0,1][0,1], only x2(1)≈0.914x_2^(1)≈ 0.914 is feasible. To verify this is a maximum, observe that ∂U2∂x2>0 ∂ U_2∂ x_2>0 for x2<0.914x_2<0.914 and ∂U2∂x2<0 ∂ U_2∂ x_2<0 for x2>0.914x_2>0.914. Thus, player 2’s unique best response is x2≈0.914x_2≈ 0.914, which yields strictly positive utility, leading to a contradiction. • Case 3: (x1⋆,x2⋆)(x_1 ,x_2 ) with x1⋆,x2⋆>0x_1 ,x_2 >0. When both players are active, player 1’s utility is: U1()=0.5x10.5x1+x1x2−0.25x1=11+2x2−0.25x1.U_1(x)= 0.5x_10.5x_1+x_1x_2-0.25x_1= 11+2x_2-0.25x_1. The derivative with respect to x1x_1 is ∂U1∂x1=−0.25<0 ∂ U_1∂ x_1=-0.25<0, so player 1’s utility is strictly decreasing in her own effort. Thus, player 1 strictly prefers to deviate to x1=0x_1=0, which contradicts our assumption. • Case 4: (0,x2⋆)(0,x_2 ) with x2⋆>0x_2 >0. When x1=0x_1=0, we have Q2=x1x2=0Q_2=x_1x_2=0. Thus, player 2’s quality is zero regardless of her effort, and she pays a cost of 0.25x2⋆>00.25x_2 >0 for no attention. Player 2 strictly prefers to deviate to x2=0x_2=0, again leading to a contradiction. Since all cases lead to contradiction, no PNE exists. ∎ Appendix B Proofs Omitted From Section 3 Definition 7 (Component-Wise Ordering). For two strategy profiles ,′∈[0,1]Nx,x ∈[0,1]^N, we write ≥′x if xi≥xi′x_i≥ x_i for every i∈i . Lemma 15 (Supermodularity of the Induced Game). For every mechanism ℳ∈ℱPAMM ^PAM, every induced game ∈(ℳ)G (M) is a supermodular game. Proof. The strategy space for each player is the compact interval [0,1][0,1], which forms a complete lattice under the standard ordering (Definition 7). It remains to show that the utility function Ui()U_i(x) exhibits increasing differences in (xi,−i)(x_i,x_-i). Under the Provisional Allocation mechanism, the utility is given by: Ui()=piQi()−ci(xi).U_i(x)=p_iQ_i(x)-c_i(x_i). Since the cost function ci(xi)c_i(x_i) depends only on xix_i, the cross-partial derivative of utility with respect to xix_i and any competitor’s effort xjx_j is determined solely by the quality term: ∂2Ui∂xi∂xj=pi∂2Qi∂xi∂xj. ∂^2U_i∂ x_i∂ x_j=p_i ∂^2Q_i∂ x_i∂ x_j. By definition of the mechanism, pi≥0p_i≥ 0. By Assumption 1 (Effort Complementarities), ∂2Qi∂xi∂xj≥0 ∂^2Q_i∂ x_i∂ x_j≥ 0. Consequently, ∂2Ui∂xi∂xj≥0 ∂^2U_i∂ x_i∂ x_j≥ 0 for all j≠ij≠ i. This sufficient condition establishes that the game is supermodular. ∎ Proof of Theorem 5. By Lemma 15, every induced game ∈(ℳ)G (M) is supermodular. We now derive each property from this structure. Part 1 (Stability) and Part 2c (Reachability) These properties follow directly from the fundamental theorems of supermodular games: • Stability: By Topkis’s Theorem (Topkis [1998], Theorem 4.2.1), every supermodular game possesses a non-empty set of pure Nash equilibria, which contains a greatest equilibrium ¯ x (and a least equilibrium). The greatest equilibrium satisfies ¯≥ x (Definition 7) for any other PNE x. • Reachability: As shown by Vives Vives [2018], iterating best-responses starting from the maximal profile =(1,…,1)1=(1,…,1) converges monotonically to the greatest equilibrium ¯ x. Part 2a (Welfare Dominance) We must show SW(¯)≥SW()SW( x)≥ SW(x). Recall that SW()=∑j∈Qj()SW(x)= _j Q_j(x). Differentiating with respect to any effort xkx_k: ∂SW∂xk=∑j∈∂Qj∂xk. ∂ SW∂ x_k= _j ∂ Q_j∂ x_k. By the assumption of non-negative spillovers, ∂Qj∂xk≥0 ∂ Q_j∂ x_k≥ 0 for all j,kj,k. Therefore, the social welfare function is monotonically non-decreasing in the strategy profile. Since ¯≥ x component-wise, it follows immediately that SW(¯)≥SW()SW( x)≥ SW(x). Part 2b (Utility Dominance) Let ¯ x be the greatest PNE and x be any other PNE. We show that Ui(¯)≥Ui()U_i( x)≥ U_i(x) for all i. Since ¯ x is a Nash equilibrium, player i plays a best response to ¯−i x_-i. Therefore, deviating to any other strategy xix_i (where xix_i is player i’s strategy in the alternative equilibrium x) cannot be strictly profitable: Ui(x¯i,¯−i)≥Ui(xi,¯−i).U_i( x_i, x_-i)≥ U_i(x_i, x_-i). (8) Next, consider the term Ui(xi,¯−i)U_i(x_i, x_-i). Since ¯≥ x , we have ¯−i≥−i x_-i _-i. Due to non-negative spillovers, QiQ_i is non-decreasing in −ix_-i, which implies: Qi(xi,¯−i)≥Qi(xi,−i).Q_i(x_i, x_-i)≥ Q_i(x_i,x_-i). Multiplying by pi≥0p_i≥ 0 and subtracting the cost ci(xi)c_i(x_i) (which is identical on both sides) yields: Ui(xi,¯−i)≥Ui(xi,−i)=Ui().U_i(x_i, x_-i)≥ U_i(x_i,x_-i)=U_i(x). (9) Combining (8) and (9), we obtain: Ui(¯)≥Ui(xi,¯−i)≥Ui().U_i( x)≥ U_i(x_i, x_-i)≥ U_i(x). Thus, the greatest equilibrium Pareto-dominates any other equilibrium. ∎ Proof of Theorem 7. We reduce from the Maximum Clique problem. Given a graph G=(V,E)G=(V,E), our goal is to find a maximum cardinality subset V′⊆V V such that (v,v′)∈E(v,v )∈ E for every v,v′∈V′v,v ∈ V . Construction From G=(V,E)G=(V,E), we construct an instance of Problem (2) as follows. Let N=|V|N=|V| be the number of players. Using the graph-based spillover model (Example 2), define the quality function for each player i as: Qi()=1N(xi+∑j≠i(i,j)∈Exixj),Q_i(x)= 1N (x_i+ _ subarraycj≠ i\\ (i,j)∈ E subarrayx_ix_j ), and the cost function as ci(xi)=xi/Nc_i(x_i)=x_i/N. Under the Provisional Allocation mechanism with parameter p, the utility of player i is: Ui()=pi⋅Qi()−ci(xi)=xiN(pi(1+∑j≠i(i,j)∈Exj)−1).U_i(x)=p_i· Q_i(x)-c_i(x_i)= x_iN (p_i (1+ _ subarraycj≠ i\\ (i,j)∈ E subarrayx_j )-1 ). Binary best responses Since UiU_i is linear in xix_i, each player’s best response is binary: xi∈0,1x_i∈\0,1\. Player i chooses xi=1x_i=1 if and only if the coefficient of xix_i in the utility expression is non-negative, i.e., pi(1+∑j≠i(i,j)∈Exj)≥1.p_i (1+ _ subarraycj≠ i\\ (i,j)∈ E subarrayx_j )≥ 1. Equivalently, if n neighbors of player i play xj=1x_j=1, then player i plays xi=1x_i=1 only if pi≥1/(n+1)p_i≥ 1/(n+1). Structure of optimal solutions The following lemma characterizes the equilibrium structure: Lemma 16. Let (pi)i(p_i)_i be a feasible allocation with pi≥0p_i≥ 0 and ∑ipi≤1 _ip_i≤ 1. Then there exists a subset ′⊆N such that: 1. The dominant equilibrium satisfies xi⋆=1x _i=1 if i∈′i and xi⋆=0x _i=0 otherwise. 2. If |′|>0|N |>0, then pi=1/|′|p_i=1/|N | for all i∈′i and pi=0p_i=0 otherwise. 3. The set ′N forms a clique: for every i,j∈′i,j with i≠ji≠ j, we have (i,j)∈E(i,j)∈ E. The proof of Lemma 16 appears below. By this lemma, any feasible allocation induces either no activity (all xi=0x_i=0) or a clique among active players. Since Qi(⋆)=0Q_i(x )=0 for inactive players and Qi(⋆)=|′|/NQ_i(x )=|N |/N for each i∈′i , the social welfare is: SW=∑i∈′Qi(⋆)=|′|⋅|′|N=|′|2N.SW= _i Q_i(x )=|N |· |N |N= |N |^2N. This is strictly increasing in |′||N |. Therefore, the optimal mechanism corresponds to the maximum clique in G, and solving Problem (2) solves Maximum Clique. Since Maximum Clique is NP-hard, so is Problem (2). ∎ Proof of Lemma 16. Part 1 holds trivially since each player’s utility is linear in their own action, forcing best responses to be binary. Parts 2 and 3. Let ⋆x denote the equilibrium profile induced by the allocation (pi)i(p_i)_i, and let ′=i∈:xi⋆=1N =\i :x _i=1\. Assume |′|>0|N |>0. Since Qi(⋆)=0Q_i(x )=0 whenever xi⋆=0x _i=0, only players in ′N have positive quality. Next, let i⋆∈argmaxi∈′Qi(⋆)i ∈ _i Q_i(x ). Define i⋆N_i such that i⋆=j∈:j≠i⋆,(i⋆,j)∈E,xj⋆=1,N_i =\j :j≠ i ,\,(i ,j)∈ E,\,x _j=1\, i.e., the set of neighbors of i⋆i in the graph G who play xj⋆=1x _j=1. By the quality function structure: Qi⋆(⋆)=1N(1+|i⋆|).Q_i (x )= 1N (1+|N_i | ). For i⋆i to choose xi⋆=1x _i =1, the best-response condition requires: pi⋆≥11+|i⋆|.p_i ≥ 11+|N_i |. For any j∈i⋆j _i , since i⋆i maximizes quality among active players, we have Qj(⋆)≤Qi⋆(⋆)Q_j(x )≤ Q_i (x ). The best-response condition for j requires: pj≥1N⋅Qj(⋆)≥1N⋅Qi⋆(⋆)=11+|i⋆|.p_j≥ 1N· Q_j(x )≥ 1N· Q_i (x )= 11+|N_i |. Summing over i⋆∪i⋆\i \ _i : pi⋆+∑j∈i⋆pj≥1+|i⋆|1+|i⋆|=1.p_i + _j _i p_j≥ 1+|N_i |1+|N_i |=1. Since ∑ipi≤1 _ip_i≤ 1, this inequality is tight and pk=0p_k=0 for all k∉i⋆∪i⋆k∉\i \ _i . Any player with pk=0p_k=0 cannot satisfy the best-response condition for xk=1x_k=1, hence xk⋆=0x _k=0. Thus ′=i⋆∪i⋆N =\i \ _i , and pi=1/|′|p_i=1/|N | for all i∈′i , establishing Part 2. For Part 3, the tight inequality chain implies Qj(⋆)=Qi⋆(⋆)Q_j(x )=Q_i (x ) for every j∈′j . Thus each player in ′N has exactly |′|−1|N |-1 neighbors within ′N , meaning every pair of players in ′N shares an edge. ∎ Theorem 17. Problem (2) is NP-hard even under the following simplifying assumptions: 1. There are no spillovers. 2. Both the quality function Qi(xi)Q_i(x_i) and the cost function ci(xi)c_i(x_i) are linear in xix_i. Proof of Theorem 17. We prove NP-hardness by a polynomial-time reduction from the classical 0–1 knapsack optimization problem. Instance of 0–1 knapsack. Let an instance of 0–1 knapsack be given by: Items i=1,…,N,vii=1N⊂ℝ≥0,wii=1N⊂ℝ>0,capacity W>0,Items i=1,…,N, \v_i\_i=1^N _≥ 0, \w_i\_i=1^N _>0, W>0, and the knapsack optimization problem is maxx∈0,1N∑i=1Nvixis.t.∑i=1Nwixi≤W. _x∈\0,1\^N\ _i=1^Nv_ix_i .t. _i=1^Nw_ix_i≤ W. (10) Define normalized weights w~i:=wiW w_i:= w_iW. Then the constraint in (10) is equivalent to ∑i=1Nw~ixi≤1 _i=1^N w_ix_i≤ 1. Constructed instance of (Pq)(Pq). From the knapsack instance we construct an instance of (Pq)(Pq) with N players as follows: Qi(xi):=vixi,ci(xi):=viw~ixi(both linear in xi),Q_i(x_i):=v_ix_i, c_i(x_i):=v_i w_ix_i (both linear in x_i), and the designer’s choice variables are p=(pi)i=1Np=(p_i)_i=1^N with pi≥0p_i≥ 0 and ∑i=1Npi≤1 _i=1^Np_i≤ 1. The mechanism assigns player i payoff share pip_i, so player i’s utility is Ui(xi;pi)=piQi(xi)−ci(xi)=vixi(pi−w~i).U_i(x_i;p_i)=p_iQ_i(x_i)-c_i(x_i)=v_ix_i(p_i- w_i). Players simultaneously choose xi∈0,1x_i∈\0,1\ to maximize their utility given p. Best-response characterization. For each fixed p, the unique best-response of player i is xi⋆(p)=1,if pi≥w~i,0,if pi<w~i.x_i (p)\;=\; cases1,&if p_i≥ w_i,\\[6.0pt] 0,&if p_i< w_i. cases (11) Lemma (threshold form of optimal p). Lemma 18. Let p⋆p be any feasible choice for the designer (i.e., pi⋆≥0p _i≥ 0 and ∑ipi⋆≤1 _ip _i≤ 1). Define the index set S:=i∈1,…,N:pi⋆≥w~i.S:=\i∈\1,…,N\\;:\;p _i≥ w_i\. Define p′∈ℝ≥0Np _≥ 0^N by pi′:=w~i,i∈S,0,i∉S.p _i:= cases w_i,&i∈ S,\\[4.0pt] 0,&i∉ S. cases Then p′p is feasible (∑ipi′≤1 _ip _i≤ 1) and induces the same profile of best-responses as bftp⋆bftp , i.e. x⋆(p′)=x⋆(p⋆)x (p )=x (p ). In particular, for any feasible p⋆p there exists a feasible p′p of this threshold form that yields the same objective value ∑iQi(x⋆(⋅)) _iQ_i(x (·)). Proof of Lemma 18. Let S and p′p be as defined above. First, ∑i=1Npi′=∑i∈Sw~i≤∑i∈Spi⋆≤∑i=1Npi⋆≤ 1, _i=1^Np _i\;=\; _i∈ S w_i\;≤\; _i∈ Sp _i\;≤\; _i=1^Np _i\;≤\;1, where the first inequality uses w~i≤pi⋆ w_i≤ p _i for i∈Si∈ S. Hence p′p is feasible. Second, for each i we compare pi′p _i with w~i w_i: pi′≥w~i⇔i∈S⇔pi⋆≥w~i.p _i≥ w_i i∈ S p _i≥ w_i. Therefore by the best-response rule (11) we have xi⋆(p′)=xi⋆(p⋆)x_i (p )=x_i (p ) for every i. Consequently the induced quality vector is identical, and so the designer’s objective value is the same. This proves the lemma. Equivalence to knapsack. Given Lemma 18, any feasible designer choice p can be replaced (without loss) by a threshold-form p′p that places mass exactly w~i w_i on every player i who is activated, and zero otherwise. Consequently, feasible allocations p correspond one-to-one to subsets S⊆1,…,NS \1,…,N\ satisfying ∑i∈Sw~i≤1 _i∈ S w_i≤ 1; the induced objective value is ∑i=1NQi(xi⋆(p))=∑i∈Svi. _i=1^NQ_i (x_i (p) )\;=\; _i∈ Sv_i. Thus the designer’s optimization problem (Pq)(Pq) on the constructed instance is equivalent to maxS⊆1,…,N∑i∈Svis.t.∑i∈Sw~i≤1, _S \1,…,N\\ _i∈ Sv_i .t. _i∈ S w_i≤ 1, which is exactly the 0–1 knapsack instance (10) (after normalization of weights). Conclusion. Since 0–1 knapsack is NP-hard, the designer’s optimization problem (Pq)(Pq) is NP-hard under the stated linearity and no-externality assumptions. This completes the proof. ∎ Proof of Corollary 8. We proceed by contradiction. Suppose there exists a polynomial-time algorithm that approximates SW problem within a factor of N1−εN^1- . In Theorem 7, we established polynomial reduction from Max-Clique to any of the problems above. Combining this reduction with the hypothesized approximation would yield a polynomial-time N1−εN^1- -approximation for Maximum Clique. This contradicts [Håstad, 1999, Theorem 5.2], which states that unless NP=ZPPNP=ZPP, no such approximation exists. ∎ Appendix C Proofs Omitted From Section 4 Proof of Lemma 10. We show that our allocation problem can be mapped exactly to an instance of the 0-1 Multiple-Choice Knapsack Problem (MCKP) Kellerer et al. [2004]. In the 0-1 MCKP, we are given disjoint classes of items, and we must select exactly one item from each class to maximize total profit subject to a weight capacity constraint. We construct the mapping as follows: • Classes: The classes correspond to the players i∈i (total N classes). • Items: For each class i, the items are indexed by k∈0,1,…,⌊1/ε⌋k∈\0,1,…, 1/ \, where item k corresponds to the allocation pi=kεp_i=k . • Weights: The weight of item k is wik=kw_ik=k. • Profits: The profit of item k in class i is the quality induced by allocation kεk to player i. Specifically, vik=Qi(xi(kε),−i)v_ik=Q_i(x_i(k ),0_-i), where xi(kε)x_i(k ) is the unique optimal effort level player i chooses given allocation pi=kεp_i=k and zero spillovers. • Capacity: The knapsack capacity is C=⌊1/ε⌋C= 1/ . Under this mapping, the NSR problem becomes: max ∑i∈∑k=0⌊1/ε⌋vikzik _i _k=0 1/ v_ik\,z_ik s.t. ∑i∈∑k=0⌊1/ε⌋kzik≤C, _i _k=0 1/ k\,z_ik\;≤\;C, ∑k=0⌊1/ε⌋zik=1,∀i∈, _k=0 1/ z_ik=1, ∀\,i , zik∈0,1,∀i∈,k∈0,…,⌊1/ε⌋. z_ik∈\0,1\, ∀\,i ,\;\;k∈\0,…, 1/ \. This is exactly the 0-1 MCKP formulation: the constraint ∑kzik=1 _kz_ik=1 ensures exactly one allocation level is assigned to each player, and the capacity constraint enforces the budget ∑ipi=∑ikiε≤1 _ip_i= _ik_i ≤ 1. We can therefore solve the NSR problem using standard MCKP algorithms. Running time. Since the problem is equivalent to the 0-1 MCKP, we can solve it exactly using standard dynamic programming approaches. Specifically, the problem can be solved exactly in time O(nitems⋅C)O(n_items· C), where nitemsn_items is the total number of items and C is the knapsack capacity Kellerer et al. [2004]. In our case, the number of classes is m=Nm=N, and the number of items per class is ⌊1/ε⌋+1 1/ +1. Thus, the total number of items is nitems=O(N/ε)n_items=O(N/ ). The dynamic programming algorithm runs in O(nitems⋅C)=O(Nε⋅1ε)=O(Nε2)O(n_items· C)=O( N · 1 )=O( N ^2). ∎ Appendix D Near Optimal Mechanism for Trees In this appendix, we show that when the spillover topology forms a rooted tree, a near-optimal solution can be computed via dynamic programming. We present an algorithm that handles arbitrary branching factors. Setting. Consider instances where the interaction graph G=(,E)G=(N,E) forms a rooted tree. Each player (except the root) receives spillovers from exactly one parent. Under the graph-based spillover model of Example 2 with linear costs ci(xi)=ci⋅xic_i(x_i)=c_i· x_i, each node’s quality depends only on its own effort and its parent’s effort: Qi(xi,xpar)=xi(qi+gpar,i⋅xpar),Q_i(x_i,x_par)=x_i(q_i+g_par,i· x_par), where qi>0q_i>0 is player i’s intrinsic quality and gpar,i≥0g_par,i≥ 0 is the spillover coefficient from i’s parent. The utility of player i is Ui=pi⋅Qi(xi,xpar)−ci⋅xi=xi⋅[pi(qi+gpar,i⋅xpar)−ci].U_i=p_i· Q_i(x_i,x_par)-c_i· x_i=x_i· [p_i(q_i+g_par,i· x_par)-c_i ]. Since utility is linear in xix_i, best responses are binary: xi⋆∈0,1x_i ∈\0,1\. Discretization. Let ε>0 >0 be the granularity parameter. We discretize allocations: ℬ(ε)=kε:k=0,1,…,⌊1/ε⌋B( )=\k :k=0,1,…, 1/ \ with |ℬ(ε)|=O(1/ε)|B( )|=O(1/ ). Effort levels take values in =0,1X=\0,1\. For any x≥0x≥ 0, we define the ε -ceiling ⌈x⌉ε:=⌈x/ε⌉⋅ε x _ := x/ · , the smallest multiple of ε that is at least x. Incentive costs. For each node u, the incentive cost for effort level xu=1x_u=1 given parent effort xparx_par is: ρu(xpar)=cuqu+gpar,u⋅xpar, _u(x_par)= c_uq_u+g_par,u· x_par, representing the minimum allocation to make xu=1x_u=1 incentive-compatible. We round to the discrete grid: ρ^u(xpar)=⌈ρu(xpar)⌉ε. ρ_u(x_par)= _u(x_par) _ . Note that ρ^u(0)≥ρ^u(1) ρ_u(0)≥ ρ_u(1): positive parent effort reduces the allocation needed to incentivize participation. Key insight. The tree structure enables a recursive decomposition. If we fix node u’s effort level xux_u, the children’s subtrees become independent optimization problems coupled only by the shared allocation constraint. This motivates a bottom-up DP computing, for each node, the optimal total quality achievable in its subtree as a function of available allocation and parent effort. Value functions. For each node u with children v1,…,vmv_1,…,v_m, we define two value functions. First, the descendants value: for b∈ℬ(ε)b ( ) and xu∈0,1x_u∈\0,1\, Tu(b,xu):=maxb1,…,bm∈ℬ(ε)b1+⋯+bm≤b∑j=1mVvj(bj,xu),T_u(b,x_u)\;:=\; _ subarraycb_1,…,b_m ( )\\ b_1+·s+b_m≤ b subarray\; _j=1^mV_v_j(b_j,x_u), (12) i.e., the maximum total quality achievable from u’s children’s subtrees when the total allocation to those subtrees is at most b and u exerts effort xux_u. When u is a leaf (m=0m=0), Tu(b,xu)=0T_u(b,x_u)=0 for all b,xub,x_u. Second, the subtree value: for b∈ℬ(ε)b ( ) and xpar∈0,1x_par∈\0,1\, Vu(b,xpar):=maxxu∈0,1ρ^u(xpar)⋅xu≤bQu(xu,xpar)+Tu(b−ρ^u(xpar)⋅xu,xu),V_u(b,x_par)\;:=\; _ subarraycx_u∈\0,1\\\ ρ_u(x_par)· x_u≤ b subarray \Q_u(x_u,x_par)+T_u\! (b- ρ_u(x_par)· x_u,\;x_u ) \, (13) i.e., the maximum total quality in u’s entire subtree (including u itself), given allocation budget b and parent effort xparx_par. To extract the optimal solution, we also store optimal decisions Xu⋆(b,xpar)X_u (b,x_par) and Bu⋆(b,xu,v)B_u (b,x_u,v). Algorithm overview. The algorithm proceeds in two phases. Phase 1 (Bottom-Up DP) processes nodes from leaves to root, computing value functions via subroutine SCBA (Sequential Children Budget Allocation) for aggregating children. Phase 2 (Top-Down Extraction) reconstructs the optimal allocation p⋆p . Input: Tree G with root r, intrinsic qualities (qu)(q_u), spillover coefficients (gpar,u)(g_par,u), costs (cu)(c_u), granularity ε Output: Optimal allocation p⋆∈ℬ(ε)Np ( )^N 1 2ℬ(ε)←kε:k=0,1,…,⌊1/ε⌋B( )←\k :k=0,1,…, 1/ \; 3 foreach (u,xpar)∈×0,1(u,x_par) ×\0,1\ do 4 ρ^u(xpar)←⌈ρu(xpar)⌉ε ρ_u(x_par)← _u(x_par) _ ; 5 6 end foreach 7foreach u∈Gu∈ G in post-order do 8 foreach xu∈0,1x_u∈\0,1\ do 9 Tu(⋅,xu),Bu⋆(⋅,xu,⋅)←SCBA(u,xu,Vv:v∈children(u))T_u(·,x_u),B_u (·,x_u,·)← SCBA (u,\;x_u,\;\V_v:v (u)\ ); 10 11 end foreach 12 foreach (xpar,b)∈0,1×ℬ(ε)(x_par,b)∈\0,1\×B( ) do 13 if b≥ρ^u(xpar)b≥ ρ_u(x_par) then 14 Vu(b,xpar)←maxTu(b,0),Qu(1,xpar)+Tu(b−ρ^u(xpar), 1)V_u(b,x_par)← \T_u(b,0),\;Q_u(1,x_par)+T_u\! (b- ρ_u(x_par),\,1 ) \; 15 Xu⋆(b,xpar)←argmaxX_u (b,x_par)← of above; 16 17 end if 18 else 19 Vu(b,xpar)←Tu(b,0)V_u(b,x_par)← T_u(b,0); 20 Xu⋆(b,xpar)←0X_u (b,x_par)← 0; 21 22 end if 23 24 end foreach 25 26 end foreach 27return Extract(r,Xu⋆u,Bu⋆u,ρ^uu) Extract\! (r,\;\X_u \_u,\;\B_u \_u,\;\ ρ_u\_u ); fnum@algorithm3ALGORITHM 3 Hierarchical Optimal Payment (HOP) Input: Node u, effort level xux_u, value functions Vv:v∈children(u)\V_v:v (u)\ Output: Value function Tu(⋅,xu)T_u(·,x_u) and budget decisions Bu⋆(⋅,xu,⋅)B_u (·,x_u,·) 1 2Tu(b,xu)←0T_u(b,x_u)← 0 for all b∈ℬ(ε)b ( ); 3 Let v1,…,vmv_1,…,v_m be the children of u; 4 for i=1,…,mi=1,…,m do 5 for b∈ℬ(ε)b ( ) in decreasing order do 6 Tu(b,xu)←maxb′∈ℬ(ε):b′≤bTu(b−b′,xu)+Vvi(b′,xu)T_u(b,x_u)← _b ( ):\,b ≤ b \T_u(b-b ,x_u)+V_v_i(b ,x_u) \; 7 Bu⋆(b,xu,vi)←argmaxB_u (b,x_u,v_i)← of above; 8 9 end for 10 11 end for 12return Tu(⋅,xu),Bu⋆(⋅,xu,⋅)T_u(·,x_u),B_u (·,x_u,·); fnum@algorithm4ALGORITHM 4 Sequential Children Budget Allocation (SCBA) Input: Root r, decision tables Xu⋆u∈\X_u \_u , budget tables Bu⋆u∈\B_u \_u , incentive costs ρ^uu∈\ ρ_u\_u Output: Optimal allocation p⋆=(p1,…,pN)p =(p_1,…,p_N) pu←0p_u← 0 for all u∈u ; ExtractRec(r,maxℬ(ε),0) ExtractRec(r, ( ),0); return p⋆p ; Function ExtractRec(u,b,xpar)(u,b,x_par): xu←Xu⋆(b,xpar)x_u← X_u (b,x_par); pu←ρ^u(xpar)⋅xup_u← ρ_u(x_par)· x_u; brem←b−pub_rem← b-p_u; Let v1,…,vmv_1,…,v_m be the children of u; for i=m,…,1i=m,…,1 do bvi←Bu⋆(brem,xu,vi)b_v_i← B_u (b_rem,x_u,v_i); ExtractRec(vi,bvi,xu) ExtractRec(v_i,b_v_i,x_u); brem←brem−bvib_rem← b_rem-b_v_i; end for fnum@algorithm5ALGORITHM 5 Solution Extraction Algorithm details. Algorithm 3 first pre-computes all incentive costs ρ^u(xpar) ρ_u(x_par) for xpar∈0,1x_par∈\0,1\ (Line 3). Then, for each node u in post-order (leaves to root, Line 3), it: 1. Calls SCBA (Algorithm 4, Line 3) to compute Tu(b,xu)T_u(b,x_u): the maximum total quality from u’s descendants given allocation budget b and effort xux_u. The value functions Vv\V_v\ of u’s children, already computed in previous post-order iterations, are passed as input. SCBA uses sequential convolution—processing children one by one, updating TuT_u by considering all ways to split the budget between the current child and previously processed children. The budget loop (Line 4) iterates in decreasing order to ensure correct in-place updates. 2. Computes Vu(b,xpar)V_u(b,x_par) (Lines 3–3 of Algorithm 3): for each pair (xpar,b)(x_par,b), if the budget b is at least ρ^u(xpar) ρ_u(x_par) (Line 3), both effort levels are considered—choosing xu=0x_u=0 yields value Tu(b,0)T_u(b,0), while choosing xu=1x_u=1 contributes quality Qu(1,xpar)=qu+gpar,u⋅xparQ_u(1,x_par)=q_u+g_par,u· x_par, consumes allocation ρ^u(xpar) ρ_u(x_par), and passes positive spillover to descendants. If b<ρ^u(xpar)b< ρ_u(x_par), only xu=0x_u=0 is feasible. After the bottom-up phase, Algorithm 5 reconstructs the optimal allocation via top-down traversal. The decision tables Xu⋆\X_u \, budget tables Bu⋆\B_u \, and incentive costs ρ^u\ ρ_u\ are passed as input. It processes children in reverse order (from vmv_m to v1v_1) to correctly recover the budget splits stored during SCBA. We now establish the correctness of the algorithm through two lemmas: the first shows that SCBA correctly computes the descendants value TuT_u, and the second uses it to show that Algorithm 3 correctly computes the subtree value VuV_u. Lemma 19 (SCBA Correctness). Let u be a node with children v1,…,vmv_1,…,v_m. If VvjV_v_j satisfies (13) for every child vjv_j, then upon termination of SCBA(u,xu,Vv) SCBA(u,x_u,\V_v\) (Algorithm 4), Tu(⋅,xu)T_u(·,x_u) satisfies (12). Proof. We prove by induction on the number of children processed in the outer loop (Line 4 of Algorithm 4) that after processing children v1,…,viv_1,…,v_i, for every b∈ℬ(ε)b ( ): Tu(b,xu)=maxb1,…,bi∈ℬ(ε)b1+⋯+bi≤b∑j=1iVvj(bj,xu).T_u(b,x_u)= _ subarraycb_1,…,b_i ( )\\ b_1+·s+b_i≤ b subarray _j=1^iV_v_j(b_j,x_u). (14) Initialization. Before any child is processed, Tu(b,xu)=0T_u(b,x_u)=0 for all b∈ℬ(ε)b ( ) (Line 4). If m=0m=0 (no children), the claim holds vacuously: the empty sum equals 0, and the only feasible allocation is the empty one. Inductive step. Suppose (14) holds for i−1i-1. In the i-th iteration, the inner loop (Line 4) iterates over budget values b∈ℬ(ε)b ( ) in decreasing order. For each b, Line 4 computes: Tu(b,xu)←maxb′∈ℬ(ε):b′≤bTu(b−b′,xu)+Vvi(b′,xu).T_u(b,x_u)← _b ( ):\,b ≤ b \T_u(b-b ,x_u)+V_v_i(b ,x_u) \. Since b is processed in decreasing order, when we evaluate Tu(b−b′,xu)T_u(b-b ,x_u) on the right-hand side for any b′≤b ≤ b, we have b−b′≤b-b ≤ b. Since all budget values strictly less than b have not yet been updated in the current (i-th) iteration, Tu(b−b′,xu)T_u(b-b ,x_u) still holds the value from iteration i−1i-1. By the inductive hypothesis, this equals the optimum over v1,…,vi−1v_1,…,v_i-1 with budget b−b′b-b . (When b′=0b =0, we have Vvi(0,xu)=0V_v_i(0,x_u)=0, and Tu(b,xu)T_u(b,x_u) retains its previous value, which is also correct.) Therefore, the update computes: Tu(b,xu)=maxb′∈ℬ(ε):b′≤b(maxb1,…,bi−1∈ℬ(ε)∑j=1i−1bj≤b−b′∑j=1i−1Vvj(bj,xu))+Vvi(b′,xu).T_u(b,x_u)= _b ( ):\,b ≤ b \ ( _ subarraycb_1,…,b_i-1 ( )\\ _j=1^i-1b_j≤ b-b subarray _j=1^i-1V_v_j(b_j,x_u) )+V_v_i(b ,x_u) \. Setting bi=b′b_i=b , this equals: Tu(b,xu)=maxb1,…,bi∈ℬ(ε)b1+⋯+bi≤b∑j=1iVvj(bj,xu),T_u(b,x_u)= _ subarraycb_1,…,b_i ( )\\ b_1+·s+b_i≤ b subarray _j=1^iV_v_j(b_j,x_u), completing the inductive step. After all m children, TuT_u satisfies (12). ∎ Lemma 20 (Value Function Correctness). For every node u∈u , the values Vu(b,xpar)V_u(b,x_par) computed in Lines 3–3 of Algorithm 3 satisfy (13) for all (b,xpar)∈ℬ(ε)×0,1(b,x_par) ( )×\0,1\. Proof. We prove by induction on the height of u’s subtree. Base case. For a leaf node u (height 0), node u has no children, so by Lemma 19 applied with m=0m=0, Tu(b,xu)=0T_u(b,x_u)=0 for all b and xux_u. In Lines 3–3: • If b≥ρ^u(xpar)b≥ ρ_u(x_par): Line 3 computes Vu(b,xpar)=max0,Qu(1,xpar)=Qu(1,xpar)V_u(b,x_par)= \0,\;Q_u(1,x_par)\=Q_u(1,x_par), since Qu(1,xpar)=qu+gpar,u⋅xpar>0Q_u(1,x_par)=q_u+g_par,u· x_par>0. This matches (13): the budget suffices to incentivize u, and participation yields positive quality. • If b<ρ^u(xpar)b< ρ_u(x_par): Vu(b,xpar)=0V_u(b,x_par)=0. This matches (13): only xu=0x_u=0 is feasible, contributing Qu(0,xpar)=0Q_u(0,x_par)=0. Inductive step. Let u have subtree height h>0h>0 and children v1,…,vmv_1,…,v_m. By the inductive hypothesis, VvjV_v_j satisfies (13) for every child vjv_j (each having subtree height at most h−1h-1). By Lemma 19, the call to SCBA at Line 3 yields TuT_u satisfying (12) for each xu∈0,1x_u∈\0,1\. Now consider Lines 3–3. For any (xpar,b)∈0,1×ℬ(ε)(x_par,b)∈\0,1\×B( ): • If b≥ρ^u(xpar)b≥ ρ_u(x_par), both effort levels are feasible. Line 3 computes: Vu(b,xpar)=maxTu(b,0)⏟skip u,Qu(1,xpar)+Tu(b−ρ^u(xpar), 1)⏟incentivize u.V_u(b,x_par)= \! \ T_u(b,0)_skip u,\;\; Q_u(1,x_par)+T_u\! (b- ρ_u(x_par),\,1 )_incentivize u \. The first branch corresponds to xu=0x_u=0 (zero quality from u, full budget to descendants); the second to xu=1x_u=1 (quality Qu(1,xpar)Q_u(1,x_par) from u, allocation ρ^u(xpar) ρ_u(x_par) consumed, remaining budget to descendants). Since TuT_u satisfies (12), each branch optimally distributes the available budget among descendants. This matches (13). • If b<ρ^u(xpar)b< ρ_u(x_par), only xu=0x_u=0 is feasible, and Vu(b,xpar)=Tu(b,0)V_u(b,x_par)=T_u(b,0), matching (13). Note that b−ρ^u(xpar)∈ℬ(ε)b- ρ_u(x_par) ( ) whenever b≥ρ^u(xpar)b≥ ρ_u(x_par), since both are multiples of ε . ∎ Theorem 21. Algorithm 3 computes an optimal solution to Problem (2) over allocations in ℬ(ε)NB( )^N, in time O(N/ε2)O(N/ ^2). Proof. Correctness. By Lemma 20, Vr(maxℬ(ε),0)V_r( ( ),0) equals the maximum total quality achievable over all discretized allocations summing to at most maxℬ(ε)≤1 ( )≤ 1, where the root has no parent (effort xpar=0x_par=0). Algorithm 5 reconstructs the optimal allocation by following the stored argmax decisions (see Remark 1 below). Runtime. Let K=|ℬ(ε)|=⌊1/ε⌋+1=O(1/ε)K=|B( )|= 1/ +1=O(1/ ), and let dud_u denote the number of children of node u. Incentive costs. Computing ρ^u(xpar) ρ_u(x_par) for all (u,xpar)∈×0,1(u,x_par) ×\0,1\ requires 2N2N evaluations, each in O(1)O(1) time. SCBA. Consider a single call SCBA(u,xu,⋅) SCBA(u,x_u,·) (Algorithm 4). For each child viv_i, the inner loop iterates over K values of b, and for each b computes a maximum over at most K values of b′b , costing O(K2)O(K^2) per child. With dud_u children, one call costs O(du⋅K2)O(d_u· K^2). Since SCBA is called twice per node (once per xu∈0,1x_u∈\0,1\), the total cost across all SCBA calls is ∑u∈2⋅du⋅K2=2K2∑u∈du=2K2(N−1)=O(NK2). _u 2· d_u· K^2=2K^2 _u d_u=2K^2(N-1)=O(NK^2). Node optimization. In Lines 3–3 of Algorithm 3, for each node u the loop iterates over |0,1|⋅K=2K|\0,1\|· K=2K pairs (xpar,b)(x_par,b), each requiring O(1)O(1) operations (a single comparison and table lookup). The total cost across all nodes is 2NK=O(NK)2NK=O(NK). Extraction. Algorithm 5 visits each node exactly once, performing O(1)O(1) operations per node, for a total of O(N)O(N). Summing all contributions: O(N)+O(NK2)+O(NK)+O(N)=O(NK2)=O(N/ε2)O(N)+O(NK^2)+O(NK)+O(N)=O(NK^2)=O(N/ ^2). ∎ Remark 1 (Extraction Correctness). Algorithm 5 follows stored decisions to reconstruct the optimal allocation. At each node u with budget b and parent effort xparx_par: 1. It retrieves xu=Xu⋆(b,xpar)x_u=X_u (b,x_par) and sets pu=ρ^u(xpar)⋅xup_u= ρ_u(x_par)· x_u (zero if xu=0x_u=0). 2. The remaining budget brem=b−pub_rem=b-p_u is distributed among children. 3. Processing children in reverse order (vm,…,v1v_m,…,v_1): Bu⋆(brem,xu,vm)B_u (b_rem,x_u,v_m) gives vmv_m’s allocation when the total children budget is bremb_rem; after subtracting bvmb_v_m, Bu⋆(brem−bvm,xu,vm−1)B_u (b_rem-b_v_m,x_u,v_m-1) gives vm−1v_m-1’s allocation; and so on. This exactly reverses the sequential convolution in Algorithm 4, recovering the optimal budget split. By construction, the total allocation satisfies ∑ipi≤maxℬ(ε) _ip_i≤ ( ), and the induced total quality equals Vr(maxℬ(ε),0)V_r( ( ),0). Remark 2. The runtime is independent of the maximum branching factor. A node with many children requires more convolutions, but this is offset by those children having fewer children on average. The total runtime is proportional to the number of edges in any tree, which is (N−1N-1). Appendix E Proofs Omitted from Section 5 Proof of Theorem 12. Our proof proceeds in three parts. First, we establish a relationship between the optimal portions p⋆p and an alternative set of portions constructed based on the lowest costs. Next, we show that there exists a high-probability event under which we derive upper and lower bounds on K(x¯(p⋆))K( x(p )). We then show that K(x¯(p))K( x(p)) satisfies the same bounds where p is the output of Algorithm GCS. Finally, we derive the corresponding social welfare guarantee. Step 1 Let S⋆=i∣x¯i(p⋆)=1∀iS =\i x_i(p )=1∀ i\ be the set of incentivized players by the optimal portions. Further assume that the costs of the players in S⋆S are sorted. That is, for every i,j∈S⋆i,j∈ S such that i<ji<j it holds that ci≤cjc_i≤ c_j. Notice that for each player in the induced incentivized set, the optimal portion pi⋆p _i has to satisfy pi⋆≥ciQi(x¯(p⋆)). p _i≥ c_iQ_i( x(p )). Notice that the utility of each player is linear in that player’s effort. Therefore, the effort levels are x¯i(p)∈0,1 x_i(p)∈\0,1\ for every player i∈Ni∈ N. Hence, the portions defined by pi1=ciQi(x¯(p⋆))pi2>ciQi(x¯(p⋆)) casesp^1_i= c_iQ_i( x(p ))\\ p^2_i> c_iQ_i( x(p )) cases incentivizes the same set of players and induces the exact same social welfare. Therefore, throughout our analysis, we consider only portions with strict equality. Next, We denote Rs(i)R_s(i) the index of the i’th player in S⋆S . For example, Rs(i)=jR_s(i)=j describes the player with the j’th least cost in S⋆S . Lastly, we denote (i)(i) the index of the player with the i’th least cost among all N players (and not just in S⋆S ). Then, notice that it holds that pi⋆=ciQi(x¯(p⋆))≥cRs(i)Qi(x¯(p⋆)). p _i= c_iQ_i( x(p ))≥ c_R_s(i)Q_i( x(p )). (15) We note here that if the optimal algorithm can incentivize player i, then reducing the cost of player i while maintaining the same qualities is at least as good as the case where we do not reduce the cost of player i. For convenience, we denote k⋆=K(x¯(p⋆))k =K( x(p )). The portions pi⋆p _i has to satisfy that ∑ipi⋆≤1 _ip _i≤ 1. In other words, we get that ∑i=1k⋆cRs(i)Qi(x¯(p⋆))≤1. _i=1^k c_R_s(i)Q_i( x(p ))≤ 1. Step 2 we denote pap^a the output of Algorithm GCS and ka=K(x¯(p))k^a=K( x(p)) the number of incentivized players. To prove this theorem, we find a clean event with high probability, for which we can estimate k, as well as Qi(x¯(p))Q_i( x(p)). We denote S=i∣x¯i(p)=1S=\i x_i(p)=1\ the set of players incentivized by our algorithm. We further denote αa=kaNα^a= k^aN, α⋆=k⋆Nα = k N the relative sizes of the incentivized sets. We construct an upper bound α¯ α and lower bound α¯ α. We use the following lemma to estimate the qualities. Lemma 22. Let k∈[N]k∈[N] be the number of incentivized players under profile x, then with probability at least 1−2e−2(k−1)k1-2e^- 2(k-1) k it holds that kq¯r−k3/4≤Qi(x)≤q⋆+kq¯r+k3/4. k qr-k 34≤ Q_i(x)≤ q +k qr+k 34. Lemma (22) has two implications: first, it implies that the quality of an incentivized player depends only on the number of incentivized players k, and not on the specific spillover of each player. Second, it implies that the qualities of all incentivized players have an asymptotic value. From this point on, we derive lower and upper bounds on kak^a and k⋆k by analyzing an arbitrary value of k and identifying the conditions under which k is feasible. Moreover, since Lemma 22 implies that player qualities depend only on the number of incentivized players, we denote these qualities by Q throughout the analysis, rather than explicitly tracking the effort profile and the portions. Upper bound Notice that the portion required to incentivize a player is monotonically increasing in the cost and decreasing in the quality. Consequently, in expectation, lower costs and higher qualities allow more players to be incentivized. We use the following lemma to bound the costs. Lemma 23. Let k∈[N]k∈[N], then With probability (1−2e−2N)2(1-2e^-2 N)^2 it holds that 12(kN)2N−2N3/4≤∑i=1kc(i)≤12(kN)2N+5N3/4. 12 ( kN )^2N-2N 34≤ _i=1^kc_(i)≤ 12 ( kN )^2N+5N 34. Therefore, using Lemma 23 and Lemma 22, we get that ∑i=1kc(i)Qi≥∑i=1kc(i)q⋆+kq¯r+k3/4≥∑i=1kc(i)q⋆+kq¯r+k3/4≥12α2N−2N3/4q⋆+αNq¯r+(αN)3/4. _i=1^k c_(i)Q_i≥ _i=1^k c_(i)q +k qr+k 34≥ _i=1^kc_(i)q +k qr+k 34≥ 12α^2N-2N 34q +α N qr+(α N) 34. (16) Inequality (16) together with the condition for feasibility gives us an upper bound for the maximum number of players that can incentivized. 12α¯2N−2N3/4q⋆+α¯Nq¯r+(α¯N)3/4≤1. 12 α^2N-2N 34q + αN qr+( αN) 34≤ 1. After rearrangement, we get that α¯2≤2α¯q¯r+2q⋆N−1+(2α¯3/4+4)N−1/4≤2α¯q¯r+8N−1/4. α^2≤ 2 α qr+2q N^-1+ (2 α 34+4 )N^- 14≤ 2 α qr+8N^- 14. Hence, α¯≤2q¯r+4q¯2r2+32N−1/42=2q¯r+2q¯r1+8(q¯r)2N−1/42. α≤ 2 qr+ 4 q^2r^2+32N^- 142= 2 qr+2 qr 1+ 8 ( qr )^2N^- 142. (17) Notice that (1+4(q¯r)2N−1/4)2=1+8(q¯r)2N−1/4+(8(q¯r)2N−1/4)2≥1+8(q¯r)2N−1/4. (1+ 4 ( qr )^2N^- 14 )^2=1+ 8 ( qr )^2N^- 14+ ( 8 ( qr )^2N^- 14 )^2≥ 1+ 8 ( qr )^2N^- 14. Plugging this inequality into Inequality (17) results in α¯≤2q¯r+2q¯r(1+4(q¯r)2N−1/4)22=4q¯r+8q¯rN−1/42=2q¯r+4q¯rN−1/4. α≤ 2 qr+2 qr (1+ 4 ( qr )^2N^- 14 )^22= 4 qr+ 8 qrN^- 142=2 qr+ 4 qrN^- 14. (18) Lower bound Similar to before, we now look for the lowest number of players in the average case that can be incentivized. We use Lemma 23 and Lemma 22 again to get that ∑i=1kcikq¯r−k3/4=∑i=1kcikq¯r−k3/4≤12(kN)2N+5N3/4kq¯r−k3/4=12α2N+5N3/4αNq¯r−(αN)3/4=α2+10N−1/42αq¯r−2α3/4N−1/4 _i=1^k c_ik qr-k 34= _i=1^kc_ik qr-k 34≤ 12 ( kN )^2N+5N 34k qr-k 34= 12α^2N+5N 34α N qr-(α N) 34= α^2+10N^- 142α qr-2α 34N^- 14 Next, we use the following lemma. Lemma 24. For every N≥(12(q⋆r)2)4N≥ ( 12 (q r )^2 )^4 it holds that α2+10N−1/42αq¯r−2α3/4N−1/4≤α2q¯r+12(q¯r)3N−1/4. α^2+10N^- 142α qr-2α 34N^- 14≤ α2 qr+ 12 ( qr )^3N^- 14. Therefore, if there exists α¯ α such that α¯2q¯r+12(q¯r)3N−1/4≤1 α2 qr+ 12 ( qr )^3N^- 14≤ 1, then it must be a lower bound for α. Notice that as N increases, the term N−1/4N^- 14 becomes negligible and at the limit we get the term α¯2q¯r=k¯2Nq¯r α2 qr= k2N qr. Next, observe that as N becomes bigger, the discretization 1N 1N becomes smaller. Thus, we can increase k¯ k (hence increase ∑iQi _iQ_i) when N increases until we approach k2Nq¯r→1 k2N qr→ 1 as N→∞N→∞. In other words, we get that k¯=⌊2Nq¯r(1−12(q¯r)3N−1/4)⌋≥2Nq¯r(1−12(q¯r)3N−1/4)−1. k= 2N qr (1- 12 ( qr )^3N^- 14 ) ≥ 2N qr (1- 12 ( qr )^3N^- 14 )-1. Multiplying both sides by 1/N1/N results in α¯≥2q¯r−q¯r24(q¯r)3N−1/4−N−1≥2q¯r−(24(2q¯r)2+1)N−1/4≥2q¯r−(7q¯r)2N−1/4. α≥ 2 qr- qr 24 ( qr )^3N^- 14-N^-1≥ 2 qr- ( 24 (2 qr )^2+1 )N^- 14≥ 2 qr- ( 7 qr )^2N^- 14. (19) Notice that from Inequality (15), both Inequality (18) and Inequality (19) applies to k⋆k . Furthermore, since pap^a is feasible, it also applies to kak^a. Therefore, 2q¯r−(7q¯r)2N−1/4≤α⋆≤2q¯r+4q¯rN−1/42q¯r−(7q¯r)2N−1/4≤α≤2q¯r+4q¯rN−1/4. cases2 qr- ( 7 qr )^2N^- 14≤α ≤ 2 qr+ 4 qrN^- 14\\ 2 qr- ( 7 qr )^2N^- 14≤α≤ 2 qr+ 4 qrN^- 14 cases. (20) Step 3 to find the total qualities, the worst case is if the algorithm incentivizes k=⌊N(2q¯r−(7q¯r)2N−1/4)⌋,k= N (2 qr- ( 7 qr )^2N^- 14 ) , while in the optimal case we get that k⋆=⌈N(2q¯r+4q¯rN−1/4)⌉.k = N (2 qr+ 4 qrN^- 14 ) . Using Lemma 22, we get that SW(x¯(p1))SW(x¯(p⋆))≥kq¯r−k3/4q⋆+kq¯r+k3/4k⋆. SW( x(p^1))SW( x(p ))≥ k qr-k 34q +k qr+k 34 kk . To get our guarantee, we use the following lemma. Lemma 25. For every N>(100(q⋆r)3)4N> ( 100 (q r )^3 )^4 it holds that kq¯r−k3/4q⋆+k⋆q¯r+k⋆3/4k⋆≥1−30(q¯r)3N−1/4. k qr-k 34q +k qr+k 34 kk ≥ 1- 30 ( qr )^3N^- 14. Hence, SW(x¯(pa))≥(1−30(q¯r)3N−1/4)SW(x¯(p⋆)). SW( x(p^a))≥ (1- 30 ( qr )^3N^- 14 )SW( x(p )). Lastly, we finish this proof with a bound for the probability of the clean event (1−2e−2k−1k)(1−2e−2N)2. (1-2e^-2 k-1 k ) (1-2e^-2 N )^2. Lemma 26. For every N≥(100(q¯r)3)4N≥ ( 100 ( qr )^3 )^4 it holds that (1−2e−Nq¯r)(1−2e−2N)2≥1−4e−Nq¯r. (1-2e^- N qr ) (1-2e^-2 N )^2≥ 1-4e^- N qr. This concludes the proof of Theorem 12 ∎ Proof of Lemma 23. Let c(i)c_(i) be the i’th least cost. Then, for any incentivized set of size k it holds that ∑i=1kci≥∑i=1kc(i). _i=1^kc_i≥ _i=1^kc_(i). Next, we use the empirical distribution function Fn(t)=1N∑i=1Nci<tF_n(t)= 1N _i=1^N1_\c_i<t\. Notice that the cdf of cic_i is F(t)=tF(t)=t. Using the DKW inequality, for every ε>0 >0, we get that Pr(|1N∑i=1Nci<t−t|>ε)=Pr(|Fn(t)−F(t)|>ε)≤Pr(supt|Fn(t)−F(t)|>ε)≤2e−2Nε2.Pr ( | 1N _i=1^N1_\c_i<t\-t |> )=Pr( |F_n(t)-F(t) |> )≤ Pr ( _t |F_n(t)-F(t) |> )≤ 2e^-2N ^2. In other words, with probability at least 1−2e−2Nε21-2e^-2N ^2, we get that |1N∑i=1Nci<t−t|≤ε | 1N _i=1^N1_\c_i<t\-t |≤ (21) Next, our goal is to find t such that ∑i=1Nci<t=k _i=1^N1_\c_i<t\=k. Notice that by definition, it holds that kN≤Fn(c(k))<k+1N. kN≤ F_n (c_(k) )< k+1N. Let α=kNα= kN. Therefore, rearranging Inequality (21) and plugging the bounds of Fn(c(k))F_n (c_(k) ) in gives us that α−ε≤c(k)<α+1N+ε. α- ≤ c_(k)<α+ 1N+ . Now, we estimate ∑i=1kc(i) _i=1^kc_(i). It holds that ∑i=1Nci⋅ci≤α−ε≤∑i=1kc(i)≤∑i=1Nci⋅ci≤α+1N+ε _i=1^Nc_i·1_ \c_i≤α- \≤ _i=1^kc_(i)≤ _i=1^Nc_i·1_ \c_i≤α+ 1N+ \ (22) Therefore, we can use Hoeffding’s inequality to estimate each side. Let zi(t)=ci⋅ci≤tz_i(t)=c_i·1_ \c_i≤ t \. Then it holds that [zi(t)]=∫c=01c⋅c≤tc=∫c=0tcc=t22. [z_i(t)]= _c=0^1c·1_ \c≤ t \dc= _c=0^tcdc= t^22. Hence, Pr(|∑i=1Nzi(t))−Nt22|≥Nδ)≤2e−2Nδ2/t≤2e−2Nδ2 Pr ( | _i=1^Nz_i(t))-N t^22 |≥ Nδ )≤ 2e^-2Nδ^2/t≤ 2e^-2Nδ^2 In other words, with probability at least 1−2e−2Nδ21-2e^-2Nδ^2, we get that ∑i=1Nci⋅ci≤α+1N+ε≤N((α+1N+ε)22+δ)∑i=1Nci⋅ci≤α−ε≥N((α−ε)22−δ) cases _i=1^Nc_i·1_ \c_i≤α+ 1N+ \≤ N ( (α+ 1N+ )^22+δ )\\ _i=1^Nc_i·1_ \c_i≤α- \≥ N ( (α- )^22-δ ) cases We now choose ε=δ=N−14 =δ=N^- 14, resulting in ∑i=1Nci⋅ci≤α+1N+ε≤N((α+2N−1/4)22+N−1/4)∑i=1Nci⋅ci≤α−ε≥N((α−N−1/4)22−N−1/4) cases _i=1^Nc_i·1_ \c_i≤α+ 1N+ \≤ N ( (α+2N^- 14 )^22+N^- 14 )\\ _i=1^Nc_i·1_ \c_i≤α- \≥ N ( (α-N^- 14)^22-N^- 14 ) cases Opening the parentheses results in ∑i=1Nci⋅ci≤α+1N+ε≤N(α22+5N−1/4)∑i=1Nci⋅ci≤α−ε≥N(α22−2N−1/4) cases _i=1^Nc_i·1_ \c_i≤α+ 1N+ \≤ N ( α^22+5N^- 14 )\\ _i=1^Nc_i·1_ \c_i≤α- \≥ N ( α^22-2N^- 14 ) cases Finally, we plug it into Inequality (22) and get that with probability at least (1−2e−2N)2 (1-2e^-2 N )^2 it holds that α22N−2N3/4≤∑i=1kc(i)≤α22N+5N3/4. α^22N-2N 34≤ _i=1^kc_(i)≤ α^22N+5N 34. This concludes the proof of Lemma 23. ∎ Proof of Lemma 22. Given an incentivized set of size k, we denote by Wi=∑j=1j≠ikrijgijW_i= _ subarraycj=1\\ j≠ i subarray^kr_ijg_ij. Let zij=rijgijz_ij=r_ijg_ij, then [zij]=q¯rE[z_ij]= qr. Therefore, by Heoffding’s inequality, it holds that Pr(|Wi−(k−1)q¯r|≥(k−1)ε)≤2e−2(k−1)ε2. Pr ( |W_i-(k-1) qr |≥(k-1) )≤ 2e^-2(k-1) ^2. Now we can bound the quality of each player. Let rir_i be a random variable sampled from Bern(r)Bern(r) distribution. Therefore, we can get a lower bound using: Qi=qi+Wi≥qiri+Wi Q_i=q_i+W_i≥ q_ir_i+W_i Hence, with probability at least 1−2e−2kε21-2e^-2k ^2 it holds that Qi≥kq¯r−kε. Q_i≥ k qr-k . (23) Next, for an upper bound, we use Qi≤q⋆+wiQ_i≤ q +w_i. Therefore, with probability at least 1−2e−2(k−1)ε21-2e^-2(k-1) ^2 it holds that Qi≤q⋆+(k−1)q¯r+(k−1)ε≤q⋆+kq¯r+kε Q_i≤ q +(k-1) qr+(k-1) ≤ q +k qr+k (24) Combining the two bounds from Inequality (23) and Inequality (24) results in kq¯r−kε≤Qi≤q⋆+kq¯r+kε. k qr-k ≤ Q_i≤ q +k qr+k . Finally, we choose ε=k−1/4 =k^- 14 to get that with probability 1−2e−2(k−1)k1-2e^-2 (k-1) k kq¯r−k3/4≤Qi≤q¯+kq¯r+k3/4. k qr-k 34≤ Q_i≤ q+k qr+k 34. This concludes the proof of Lemma 22. ∎ Proof of Lemma 24. This proof has 2 steps: first, we find a lower bound for alpha in order to bound the denominator. The second step then uses the bound from the first step and shows the distance from 2αq¯r 2α qr. Step 1 we look for a lower bound for α. Notice that for α=q¯rα= qr, the condition to make the incentivized set feasible is (q¯r)2+10N−1/42(q¯r)2−2(q¯r)3/4N−1/4≤1. ( qr )^2+10N^- 142 ( qr )^2-2 ( qr ) 34N^- 14≤ 1. After rearrangement, we get that (q¯r)2−N−1/4(10+2(q¯r)3/4)≥0. ( qr )^2-N^- 14 (10+2 ( qr ) 34 )≥ 0. (25) Observe that q¯r≤1 qr≤ 1, therefore it holds that (q¯r)2−N−1/4(10+2(q¯r)3/4)≥(q¯r)2−12N−1/4 ( qr )^2-N^- 14 (10+2 ( qr ) 34 )≥ ( qr )^2-12N^- 14 Therefore, to satisfy Inequality (25), it is sufficient to demand (q¯r)2−12N−1/4≥0 ( qr )^2-12N^- 14≥ 0 Which holds for every N≥(12(q¯r)2)4N≥ ( 12 ( qr )^2 )^4. In other words, let N1=(12(q¯r)2)4N_1= ( 12 ( qr )^2 )^4, then for every N≥N1N≥ N_1 it holds that α≥q¯rα≥ qr. Step 2 to show our claim, it is enough to show that α2+10N−1/42αq¯r−2α3/4N−1/4−α2q¯r<D⋅N−1/4 α^2+10N^- 142α qr-2α 34N^- 14- α2 qr<D· N^- 14 where D∈ℝ≥0D _≥ 0. Indeed, α2+10N−1/42αq¯r−2α3/4N−1/4−α2q¯r α^2+10N^- 142α qr-2α 34N^- 14- α2 qr =α2+10N−1/42αq¯r−2α3/4N−1/4−α22αq¯r = α^2+10N^- 142α qr-2α 34N^- 14- α^22α qr =2αq¯r(α2+10N−1/4)−α2(2αq¯r−2α3/4N−1/4)2αq¯r(2αq¯r−2α3/4N−1/4) = 2α qr (α^2+10N^- 14 )-α^2 (2α qr-2α 34N^- 14 )2α qr (2α qr-2α 34N^- 14 ) =20αq¯rN−1/4+2α11/4N−1/42αq¯r(2αq¯r−2α3/4N−1/4) = 20α qrN^- 14+2α 114N^- 142α qr (2α qr-2α 34N^- 14 ) =20q⋆rN−1/4+2α7/4N−1/42q¯r(2αq¯r−2α3/4N−1/4) = 20q rN^- 14+2α 74N^- 142 qr (2α qr-2α 34N^- 14 ) ≤6N−1/4q¯r(αq¯r−α3/4N−1/4) ≤ 6N^- 14 qr (α qr-α 34N^- 14 ) Notice that this expression is positive and maximal when the denominator is positive and minimal. Therefore, αq¯r−α3/4N−1/4≥(q¯r)2−N−1/4 α qr-α 34N^- 14≥ ( qr )^2-N^- 14 We now choose N such that our last term is at least (q¯r)22 ( qr )^22, that is (q¯r)2−N−1/4≥(q¯r)22 ( qr )^2-N^- 14≥ ( qr )^22 Which holds for every N≥N2=(2(q¯r)2)4N≥ N_2= ( 2 ( qr )^2 )^4. To get N⋆N , we take an upper bound over this N1N_1 and N2N_2 N⋆=(12(q¯r)2)4. N = ( 12 ( qr )^2 )^4. Therefore, for any N≥N⋆N≥ N it holds that α2+10N−1/42αq¯r−2α3/4N−1/4≤α2q¯r+12(q¯r)3N−1/4. α^2+10N^- 142α qr-2α 34N^- 14≤ α2 qr+ 12 ( qr )^3N^- 14. This concludes the proof of Lemma 24. ∎ Proof of Lemma 25. We first rearrange the expression: kq¯r−k3/4q⋆+k⋆q¯r+k⋆3/4k⋆=(k⋆)21−1q¯rk−1/41+1q¯r(q⋆k⋆−1+k⋆−1/4) k qr-k 34q +k qr+k 34 kk = ( kk )^2 1- 1 qrk^- 141+ 1 qr (q k ^-1+k ^- 14 ) First, we handle the expression (k⋆)2 ( kk )^2. For that, we use the following lemma. Lemma 27. For any N>(8(q⋆r)2)4N> ( 8 (q r )^2 )^4, it holds that k⋆≥1−26(q¯r)3N−1/4. kk ≥ 1- 26 ( qr )^3N^- 14. Using the binomial series expansion (1−x)2=1+R0(x)(1-x)^2=1+R_0(x) where x=26(q¯r)3x= 26 ( qr )^3 and R0(x)R_0(x) is the Lagrange remainder, defined by R0(x)=2(1−ε)xR_0(x)=2(1- )x for ε∈[0,x] ∈[0,x]. Notice that for N>(52(q¯r)3)4N> ( 52 ( qr )^3 )^4 , we get that R0(x)≥xR_0(x)≥ x and (k⋆)2≥1−26(q¯r)3N−1/4 ( kk )^2≥ 1- 26 ( qr )^3N^- 14 Next, we handle the nominator 1−2q⋆rk−1/41- 2q rk^- 14. For that, we use the following result: Lemma 28. For every N≥(100(q¯r)3)4N≥ ( 100 ( qr )^3 )^4 it holds that k−1/4≤(Nq¯r)−1/4(1+72(q¯r)3N−1/4).k^- 14≤ (N qr )^- 14 (1+ 7^2 ( qr )^3N^- 14 ). Next, we handle the denominator 1+1q¯r(q⋆k⋆−1+1q⋆k⋆−1/4)1+ 1 qr (q k ^-1+ 1q k ^- 14 ). Lemma 29. For every N>(2(q¯r)2)4N> ( 2 ( qr )^2 )^4 it holds that 11+1q¯r(q⋆k⋆−1+k⋆−1/4)≥1−1(q¯r)2N−1/4. 11+ 1 qr (q k ^-1+k ^- 14 )≥ 1- 1 ( qr )^2N^- 14. Plugging those results gives us that kq¯r−k3/4q⋆+k⋆q¯r+k⋆3/4k⋆ k qr-k 34q +k qr+k 34 kk ≥(1−26(q¯r)3N−1/4)(1−1q¯r(Nq¯r)−1/4(1+72(q¯r)3N−1/4))(1−1(q¯r)2N−1/4) ≥ (1- 26 ( qr )^3N^- 14 ) (1- 1 qr (N qr )^- 14 (1+ 7^2 ( qr )^3N^- 14 ) ) (1- 1 ( qr )^2N^- 14 ) Notice that (1−26(q¯r)3N−1/4)(1−1(q¯r)2N−1/4)≥1−27(q¯r)3N−1/4 (1- 26 ( qr )^3N^- 14 ) (1- 1 ( qr )^2N^- 14 )≥ 1- 27 ( qr )^3N^- 14 Furthermore, for N≥(72(q¯r))4N≥ ( 7^2 ( qr ) )^4 it holds that 1−1q¯r(Nq¯r)−1/4(1+72(q¯r)3N−1/4)≥1−2(q¯r)3N−1/41- 1 qr (N qr )^- 14 (1+ 7^2 ( qr )^3N^- 14 )≥ 1- 2 ( qr )^3N^- 14 Hence, kq¯r−k3/4q⋆+k⋆q¯r+k⋆3/4k⋆ k qr-k 34q +k qr+k 34 kk ≥(1−27(q¯r)3N−1/4)(1−2(q¯r)3N−1/4) ≥ (1- 27 ( qr )^3N^- 14 ) (1- 2 ( qr )^3N^- 14 ) ≥1−30(q¯r)3N−1/4. ≥ 1- 30 ( qr )^3N^- 14. This concludes the proof of Lemma 25. ∎ Proof of Lemma 27. We start by rearranging the expression k⋆ kk . k⋆≥N(2q¯r−(7q¯r)2N−1/4)−1N(2q¯r+4q¯rN−1/4)+1=1−722(q¯r)3N−1/4−12q¯rN−11+2(q¯r)2N−1/4+12q¯rN−1 kk ≥ N (2 qr- ( 7 qr )^2N^- 14 )-1N (2 qr+ 4 qrN^- 14 )+1= 1- 7^22 ( qr )^3N^- 14- 12 qrN^-11+ 2 ( qr )^2N^- 14+ 12 qrN^-1 (26) Next, for any N>(4(q¯r)2)4N> ( 4 ( qr )^2 )^4, we can expand the denominator using the Taylor series 11−x=1+x+O(x2) 11-x=1+x+O(x^2) for x=−(2(q¯r)2N−1/4+12q¯rN−1).x=- ( 2 ( qr )^2N^- 14+ 12 qrN^-1 ). This results in 11+2(q¯r)2N−1/4+12q¯rN−1=1−2(q¯r)2N−1/4+O(N−1/2) 11+ 2 ( qr )^2N^- 14+ 12 qrN^-1=1- 2 ( qr )^2N^- 14+O(N^- 12) (27) Plugging Equation (27) into Inequality (26) gives us that k⋆ kk ≥(1−722(q¯r)3N−1/4−12q¯rN−1)(1−2(q¯r)2N−1/4+O(N−1/2)) ≥ (1- 7^22 ( qr )^3N^- 14- 12 qrN^-1 ) (1- 2 ( qr )^2N^- 14+O(N^- 12) ) =1−(722(q¯r)3+2(q¯r)2)N−1/4+O(N−1/2) =1- ( 7^22 ( qr )^3+ 2 ( qr )^2 )N^- 14+O(N^- 12) ≥1−26(q¯r)3N−1/4. ≥ 1- 26 ( qr )^3N^- 14. This concludes the proof of Lemma 27. ∎ Proof of Lemma 28. We begin with the lower bound on k. For every N≥1q¯rN≥ 1 qr it holds that k≥N(2q¯r−(7q¯r)2N−1/4)−1≥Nq¯r(1−72(q¯r)3N−1/4) k≥ N (2 qr- ( 7 qr )^2N^- 14 )-1≥ N qr (1- 7^2 ( qr )^3N^- 14 ) Therefore, it holds that k−1/4≤(Nq¯r(1−72(q¯r)3N−1/4))−1/4=(Nq¯r)−1/4(1−72(q¯r)3N−1/4)−1/4 k^- 14≤ (N qr (1- 7^2 ( qr )^3N^- 14 ) )^- 14= (N qr )^- 14 (1- 7^2 ( qr )^3N^- 14 )^- 14 Next, we use the binomial series expansion (1−x)−1/4=1+R0(x),(1-x)^- 14=1+R_0(x), where R1(x)R_1(x) is the Lagrange remainder, given by R0(x)≤14(1−x)−54xR_0(x)≤ 14 (1-x )^- 54x Therefore, for any N≥(100(q¯r)3)4N≥ ( 100 ( qr )^3 )^4 it holds that x=72(q¯r)3N−1/4<12x= 7^2 ( qr )^3N^- 14< 12. Hence, R0(x)≤1425/4x=123/4x≤xR_0(x)≤ 142 54x= 12 34x≤ x k−1/4 k^- 14 ≤(Nq¯r)−1/4(1+72(q¯r)3N−1/4) ≤ (N qr )^- 14 (1+ 7^2 ( qr )^3N^- 14 ) This concludes the proof of Lemma 28. ∎ Proof of Lemma 29. We start by getting lower bounds for (k⋆)−1 (k )^-1 and (k⋆)−1/4 (k )^- 14. We use the following results. Lemma 30. It holds that k⋆−14≥(4q¯r)−1/4(N−1/4−14(q⋆r)2N−1/2)k⋆−1≥(4q¯r)−1(N−1−1(q⋆r)2N−5/4) casesk ^- 14≥ (4 qr )^- 14 (N^- 14- 14 (q r )^2N^- 12 )\\ k ^-1≥ (4 qr )^-1 (N^-1- 1 (q r )^2N^- 54 ) cases Therefore, we get that 11+1q¯r(q⋆k⋆−1+k⋆−1/4) 11+ 1 qr (q k ^-1+k ^- 14 ) ≥11+1q¯r(q⋆(4q¯r)−1(N−1−1(q¯r)2N−5/4)+(4q¯r)−1/4(N−1/4−14(q¯r)2N−1/2)) ≥ 11+ 1 qr (q (4 qr )^-1 (N^-1- 1 ( qr )^2N^- 54 )+ (4 qr )^- 14 (N^- 14- 14 ( qr )^2N^- 12 ) ) ≥11+1q¯r((4q¯r)−1N−1+(4q¯r)−1/4N−1/4) ≥ 11+ 1 qr ( (4 qr )^-1N^-1+ (4 qr )^- 14N^- 14 ) ≥11+1(q¯r)2N−1/4 ≥ 11+ 1 ( qr )^2N^- 14 Next, we use the Taylor expansion for 11−x=∑n=0∞xn=1+R0(x) 11-x= _n=0^∞x^n=1+R_0(x), where x=−1(q¯r)2N−1/4x=- 1 ( qr )^2N^- 14 and R0(x)R_0(x) is the Lagrange remainder. In our case, R0(x)≥x(1−x)2R_0(x)≥ x (1-x )^2. Hence, for N>(2(q¯r)2)4N> ( 2 ( qr )^2 )^4, we get that x<0.5x<0.5 and 11+1q¯r(q⋆k⋆−1+k⋆−1/4)≥1−(23)21(q¯r)2N−1/4≥1−1(q¯r)2N−1/4. 11+ 1 qr (q k ^-1+k ^- 14 )≥ 1- ( 23 )^2 1 ( qr )^2N^- 14≥ 1- 1 ( qr )^2N^- 14. This concludes the proof of Lemma 29. ∎ Proof of Lemma 30. We start from the upper bound of k⋆k , namely k⋆≤N(2q¯r+4q¯rN−1/4)+1 k ≤ N (2 qr+ 4 qrN^- 14 )+1 For N>⌈12q¯r⌉N> 12 qr it holds that k⋆≤N(2q¯r+4q¯rN−1/4)+1≤4q¯rN(1+1(q¯r)2N−1/4). k ≤ N (2 qr+ 4 qrN^- 14 )+1≤ 4 qrN (1+ 1 ( qr )^2N^- 14 ). Therefore, (k⋆)−1≥(4q¯rN)−1(1+1(q¯r)2N−1/4)−1(k⋆)−1/4≥(4q¯rN)−1/4(1+1(q¯r)2N−1/4)−1/4. cases(k )^-1≥ (4 qrN )^-1 (1+ 1 ( qr )^2N^- 14 )^-1\\ (k )^- 14≥ (4 qrN )^- 14 (1+ 1 ( qr )^2N^- 14 )^- 14 cases. (28) For the binomial series (1+x)−1/4=1−14x+O(x2)(1+x)^- 14=1- 14x+O(x^2), we get that (1+1(q¯r)2N−1/4)−1/4=1−141(q¯r)2N−1/4+O(N−1/2). (1+ 1 ( qr )^2N^- 14 )^- 14=1- 14 1 ( qr )^2N^- 14+O(N^- 12). Similarly, for the series (1+x)−1=1−x+O(x2)(1+x)^-1=1-x+O(x^2), we get that (1+1(q¯r)2N−1/4)−1/4=1−1(q¯r)2N−1/4+O(N−1/2). (1+ 1 ( qr )^2N^- 14 )^- 14=1- 1 ( qr )^2N^- 14+O(N^- 12). Plugging those results into Inequalities (28) then gives us our results. This concludes the proof of Lemma 30. ∎ Proof of Lemma 26. First, we use the following lemma. Lemma 31. For every N≥(100(q¯r)3)4N≥ ( 100 ( qr )^3 )^4 it holds that 1−2e−2k−1k≥1−2e−q¯rN. 1-2e^-2 k-1 k≥ 1-2e^- qrN. Therefore, the probability for the clean event is lower bounded by (1−2e−q¯rN)(1−2e−2N)2. (1-2e^- qrN ) (1-2e^-2 N )^2. Next, we use the binomial series (1−x)2=1−2x+R1(x)(1-x)^2=1-2x+R_1(x) for x=2e−2Nx=2e^-2 N and R1(x)R_1(x) is the Lagrange remainder, which for some ε∈[0,x] ∈[0,x] is given by R1(x)=12(d2dx2(1−ε)2)x2=x2;R_1(x)= 12 ( d^2dx^2(1- )^2 )x^2=x^2; therefore, we get that (1−x)2=1−2x+x2≥1−2x,(1-x)^2=1-2x+x^2≥ 1-2x, and (1−2e−2N)2=1−4e−2N. (1-2e^-2 N )^2=1-4e^-2 N. Plugging everything into our clean event probability, we obtain (1−2e−Nq¯r)(1−2e−2N)2 (1-2e^- N qr ) (1-2e^-2 N )^2 ≥(1−2e−Nq¯r)(1−4e−2N) ≥ (1-2e^- N qr ) (1-4e^-2 N ) =1−2e−Nq¯r−4e−2N+8e−(q⋆r+2)N =1-2e^- N qr-4e^-2 N+8e^-( q r+2) N ≥1−2e−Nq¯r−4e−2N. ≥ 1-2e^- N qr-4e^-2 N. Lastly, for every N≥(ln22−q¯r)2N≥ ( 22- qr )^2, the above inequality asserts that (1−2e−Nq¯r)(1−2e−2N)2≥1−4e−Nq¯r. (1-2e^- N qr ) (1-2e^-2 N )^2≥ 1-4e^- N qr. This concludes the proof of Lemma 26. ∎ Proof of Lemma 31. We begin by forming a lower bound for the expression 2k−1k2 k-1 k. Notice that this expression is minimal for the minimal value of k, that is for k=⌊α¯N⌋k= αN . Plugging that in gives us that 2k−1k≥2N(2q¯r−(7q¯r)2N−1/4)−2(N(2q¯r−(7q¯r)2N−1/4)−1)1/2. 2 k-1 k≥ 2 N (2 qr- ( 7 qr )^2N^- 14 )-2 (N (2 qr- ( 7 qr )^2N^- 14 )-1 ) 12. First, we handle the nominator. Notice that for every N≥2q⋆rN≥ 2q r it holds that N(2q¯r−(7q¯r)2N−1/4)−2≥N(q¯r−(7q¯r)2N−1/4). N (2 qr- ( 7 qr )^2N^- 14 )-2≥ N ( qr- ( 7 qr )^2N^- 14 ). Next, the denominator can be written as (N(2q¯r−(7q¯r)2N−1/4)−1)−1/2≥(2q¯rN)−1/2. (N (2 qr- ( 7 qr )^2N^- 14 )-1 )^- 12≥ (2 qrN )^- 12. Plugging the nominator and denominator back in gives us that 2k−1k 2 k-1 k ≥2N(q¯r−(7q¯r)2N−1/4)(2q¯rN)−1/2. ≥ 2N ( qr- ( 7 qr )^2N^- 14 ) (2 qrN )^- 12. (29) Hence, for every N≥(100(q¯r)3)4N≥ ( 100 ( qr )^3 )^4 it holds that 1−72(q⋆r)3N−1/4>121- 7^2 (q r )^3N^- 14> 12 and 2k−1k≥2Nq¯r12(2q¯rN)−1/2=q¯rN. 2 k-1 k≥ 2N qr 12 (2 qrN )^- 12= qrN. Finally, plugging this into 1−2e−2k−1k1-2e^-2 k-1 k gives us that 1−2e−2k−1k≥1−2e−q¯rN. 1-2e^-2 k-1 k≥ 1-2e^- qrN. This concludes the proof of Lemma 31. ∎