extfieldsofstudy:
Computer Science
Mathematics

text:
Information Gathering with Peers: Submodular Optimization with Peer-Prediction Constraints

We study a problem of optimal information gathering from multiple data providers that need to be incentivized to provide accurate information. This problem arises in many real world applications that rely on crowdsourced data sets, but where the process of obtaining data is costly. A notable example of such a scenario is crowd sensing. To this end, we formulate the problem of optimal information gathering as maximization of a submodular function under a budget constraint, where the budget represents the total expected payment to data providers. Contrary to the existing approaches, we base our payments on incentives for accuracy and truthfulness, in particular, {\em peer-prediction} methods that score each of the selected data providers against its best peer, while ensuring that the minimum expected payment is above a given threshold. We first show that the problem at hand is hard to approximate within a constant factor that is not dependent on the properties of the payment function. However, for given topological and analytical properties of the instance, we construct two greedy algorithms, respectively called PPCGreedy and PPCGreedyIter, and establish theoretical bounds on their performance w.r.t. the optimal solution. Finally, we evaluate our methods using a realistic crowd sensing testbed.

Introduction
The recent success of various machine learning techniques can partly be attributed to the existence of large sets of labeled data that can readily be used for training purposes. In the past decade, the predominant form of obtaining useful data is through crowdsourcing approaches, where human subjects either directly label data or have private devices that provide measurements about spatially distributed phenomena.
One of the most important aspects of data is its accuracy, which can only be established if data providers (e.g. crowdparticipants) report accurate information. To incentivize accurate reporting, a data collector can provide incentives that compensate data providers for their effort. In its simplest form, this type of data elicitation process can be modeled as a three step protocol: Figure 1: An example of crowdsourcing with incentives: Crowd-sensors (air-quality eggs 1 ) report air-quality measurements and a data collector rewards them with monetary payments. An edge (black line) indicates that there is a sufficient correlation between the measurements of two sensors to verify accuracy.
• Data providers report the acquired data to a data collector; • The data collector pays to the data providers a value that compensates for the cost of effort.
An example scenario is shown in Figure 1. The problem, however, arises if the data providers are susceptible to moral hazard, that is, deviation to reporting heuristically without obtaining the data in the first place. In fact, such a behavior is expected for a rational participant who aims to maximize their utility, since heuristic reporting typically carries no cost of effort. To avoid this problem, the data collector can design payment functions τ that are dependent on the accuracy of the reported information, for example, by installing random spot-checks that validate some of the reports (Gao, Wright, and Leyton-Brown 2016). While this approach has often been used in standard microtask crowdsourcing, it is often too costly to apply it in a more complex elicitation setting. Consider, for example, a crowd-sensing scenario shown in Figure 1, where sensors measure spatially distributed phenomenon that is highly localized. To apply a spot-checking procedure, the data collector would need to have mobile sensors that would change their locations at each time-step. Furthermore, due to the localized nature of the measured phenomenon, the density of the spot-check sensor network has to be relatively large.
Instead of evaluating data providers against trusted reports, Dasgupta and Ghosh (2013), Jurca and Faltings (2011), Radanovic, Faltings, andJurca (2016), Shnayder et al. (2016), Witkowski et al. (2017), and Baillon (2017), propose peer-prediction mechanisms for incentivizing distributed information sources. Peer-prediction mechanisms reward data providers by measuring consistency among their reports-thus, if a data provider believes that others are honest, she is also incentivized to report truthfully. 1 The most important condition to hold when applying a peerprediction mechanism is that a data provider and her peer have correlated private information. Furthermore, this correlation, when expressed through expected payments, should be greater than the cost of effort. The latter property can always be achieved by scaling, provided that a considered peer-prediction method provides strict incentives for truthfulness. The scaling approach, however, neglects potential budget concerns that are important when collecting large data sets.

Overview of Our Approach
We, therefore, focus on the limited budget concern in a distributed data collection process that uses peer-prediction incentives. There are two important aspects to this problem: • which data providers to select given that we only have a limited budget to spend on incentives-thus, only those data providers who received incentives can be considered to be reliable; • how to ensure that all of the selected data providers have a proper peer-this constrains the selection problem to always include a proper peer of each data provider that is to be selected. To quantify the usefulness of each data provider, we adopt a submodular utility function, which can, for example, measure the information gain of the data collector for obtaining the reports of the selected data-providers. We will insist that each data provider can be scored against a peer report with resulting expected payment being greater than a given threshold. Furthermore, the total expected payment should be bounded by a budget, while a data provider should be always scored against the best peer among the selected data providers. Our main contributions are: • A formal model of information gathering with budget and peer-prediction constraints that is based on submodular maximization. • Showing that the studied optimization problem is hard to approximate within a constant factor independent of the properties of the applied payment function. • Novel algorithms for maximizing submodular functions with peer-prediction constraints that have provable guarantees for given topological and analytical properties of payments.
1 Peer-predictions are in general susceptible to collusion, but in many cases one can establish relatively strong incentive properties for a wide variety of reporting strategies (Kong and Schoenebeck 2016). We do not focus on collusion resistance, so we use standard peer-predictions in our setting.
• Experimental evaluation of the proposed algorithms on a crowd-sensing test-bed. Notice that we do not focus on a particular peer-prediction mechanism, but rather we allow a wide range of possible mechanisms (those that are robust in terms of the number of peers and produce bounded expected payments); thus, we complement the prior work on peer-predictions by examining orthogonal aspects of elicitation without direct verification. We provide the proofs to our formal claims in the extended version of the paper (Radanovic et al. 2017).

Problem Statement
We now formalize the problem addressed in this paper. We model data providers as nodes in a graph, whereas the underlying peer-prediction dependencies are modeled via edges whose weights are defined by the expected payments. The overall goal is to select a set of nodes that maximize a submodular utility function, while satisfying the constraint that the cost of the data collector (i.e., the total expected payment to nodes) is within a predefined budget. The following subsections provide more precise modeling details.

Set of Nodes and the Utility Function
We consider a set of nodes (e.g., a population of people or sensors deployed in a city) denoted by set V = {v 1 , v 2 , . . . , v |V | }, of size |V |. Hereafter, we denote a generic node by v. We associate a function over the set of nodes f : 2 V → R ≥0 that quantifies their utility (e.g., informativeness). That is, given a set of selected nodes S, the utility achieved from this set is equal to f (S). Furthermore, for given set S, and a node v ∈ V \S, we define the marginal utility of adding v to S as follows: (1) Here, the function f is assumed to be submodular and monotone. Submodularity is an intuitive notion of diminishing returns, stating that, for any sets S ⊆ S ⊆ V , and any given node v / ∈ S , it holds that f (v|S) ≥ f (v|S ). Monotonicity requires that the function f increases as we add more elements to set S. That is, for any sets S ⊆ S ⊆ V , it holds that f (S) ≤ f (S ). These conditions are relatively general, and are satisfied by many realistic, as well as complex utility functions for information gathering (Krause and Guestrin 2011; Krause and Golovin 2012; Singla and Krause 2013;Singla et al. 2014;Tschiatschek, Singla, and Krause 2017). W.l.o.g., we assume that function f is normalized, i.e., f (∅) = 0.

Peer-prediction Constraints (PPC)
The nodes in general exhibit dependencies with other nodes. We consider a particular form of constraints that is associated with information elicitation via peer-prediction mechanisms (Miller, Resnick, and Zeckhauser 2005). A canonical peer-prediction τ : V × V → R scores the information reported by node v using the information of a peer node v p . Mechanism τ (v, v p ) is said to be proper if node v's best response to accurate reporting of node v p is to report accurately, where the quality of a response is measured in terms of node v's expected payoff over possible (accurate) reports of node v p . 2 We denote node v's expected payoff for accurate reporting by E(τ (v, v p )). To establish the properness of τ , one needs to ensure that peer v p provides statistically correlated information to that of node v, so that the expected payoff E(τ (v, v p )) is strictly greater than the cost of accurate reporting (which models, for example, participants' effort exertion). Therefore, node v has only a limited number of peers defined as nodes that lead to the expected payoff E(τ (v, v p )) ≥ τ min , where τ min > 0 is a problem specific threshold dependent on the cost of accurate reporting. We will further require that the same holds for node v's peers, i.e., E(τ (v p , v)) ≥ τ min , and assume that mechanism τ provides bounded payments, so that E(τ (v, v p )) ≤ τ max . Notice that as τ min increases, a node is expected to have a smaller number of peers, which makes the problem of selecting an optimal set of nodes more constrained. In Section 'Experimental Evaluation', we confirm this observation by showing the drop in the obtained utility.
Example: Output Agreement (OA). Arguably the simplest peer prediction method is the output agreement of von Ahn and Dabbish (2004), which gives a strictly positive payment only for matching reports. In our experiments, reported information can in general take real values. In that case, as explained by Waggoner and Chen (2014), the OA mechanism can be defined as: where d is Euclidian distance between reported values of v and v p . Note that more complex designs are also allowed by our framework, such as the one proposed in (Faltings, Li, and Jurca 2014). For more information on the properties of different minimal peer-predictions and their relationships, we refer the reader to (Frongillo and Witkowski 2016).
With this in mind, we can model the dependencies among nodes using an undirected graph G = (V, E), where edges are defined as We require that each node in a selected set S has a neighboring node G that is also in S, which implies that we can properly evaluate the reported information of each selected node. We denote the set of neighboring nodes to node v as N v , i.e., N v = {u ∈ V : {v, u} ∈ E}. W.l.o.g. we can assume that every node in G has at least one peer node v p , i.e., |N v | ≥ 1. Namely, nodes that do not have a peer cannot be incentivized to report accurately in our setting, so they bring 0 utility in terms of f . Finally, let us denote by ω the maximum number of peers that a node in graph G has, i.e., ω(G) = max v∈V |N v |.

Cost of Incentivizing Accuracy
Given a selected set of nodes S, an information elicitation procedure needs to spend a certain amount of budget, hereafter denoted by B, to incentivizing accurate reporting. To quantify the cost of accurate elicitation, one needs to specify a peer selection procedure when a node v has multiple peers. We take the approach of selecting the best peer, that 2 Therefore, properness is here defined as Bayes-Nash incentive compatibility in game-theoretic sense.
is the peer that has the most correlated information to that of the considered node according to the expected payoffs-this leads to the strongest incentives in terms of the separation between the expected payoffs for accurate and inaccurate reporting. With this choice of peer selection procedure, we can define the cost of selecting nodes S as function c : 2 V φ → R: Here, 2 V φ contains only sets S such that each node v ∈ S has a peer node v p ∈ S, which makes c well defined.

Optimization Problem
Our goal is to select a feasible set S ∈ 2 V φ that maximizes the utility f (S) given budget B, i.e., c(S) ≤ B. More precisely, the budget denotes the total expected payment that a data collector is willing to provide for incentivizing accurate reporting. We therefore pose the following optimization problem: Ignoring the computational constraints, we denote the optimal solution to this problem as OPT.

Methodology
Instead of operating directly on optimization problem (4), we reformulate it so that the budget constraint is expressed through a cost function defined over all subsets of nodes 2 V , not just the feasible set 2 V φ . We first show that the new optimization problem is equivalent to (4). Unfortunately, it is hard to approximate without any dependency on the structure of the cost function. We then relax it to an optimization problem that uses a modular approximation to the cost function, but operates with reduced budget to satisfy the original budget constraint. This relaxation is the basis for our algorithms developed in the next section, and is sound if the cost function of the original problem has certain topological and analytical constraints. The following subsections explain our methodology in more details.

Expansion of the Cost Function
We start by expanding the domain of cost function c to power-set 2 V , which will provide us with better insights on the computational complexity of the original problem. In particular, we consider the following expansion c e : 2 V → R: where S p is a set of all nodes in S who also have a peer in S, i.e., S p = {v ∈ S : ∃v p ∈ S s.t. v p ∈ N v }. In other words, cost function c e acts as if all the nodes in S who have a peer in S are rewarded as usual, while those that do not have a peer in S are rewarded with the expected payoff they obtain when scored against the worst peer. Notice that c e (S) = c(S) for all S ∈ 2 V φ , which makes the expansion sound. We denote by c e (v|S) the marginal increase of cost c e for adding an element v to S, i.e., c e (v|S) = c e (S ∪ {v}) − c e (S).
We establish the monotonicity of cost function c e with the following lemma; notice, however, that the cost function is not necessarily sub/super-modular. Lemma 1. Cost function c e defined by (5) is monotone. Furthermore: c e ({v}) ≤ c e (v|S), for all S ∈ 2 V \{v}.

Hardness Result
To prove the complexity of our initial problem, we adapt optimization problem (4) to use the extended cost function c e . In particular, we consider the optimization problem defined as: Clearly, any feasible solution to the problem (6) is also a feasible solution to the original problem due to the constraint S ∈ 2 V φ , while the optimality alignment is ensured by having the same objective value. Now, to show the hardness result for approximating OPT, we reduce the maximum clique problem to optimization problem (6) in a computationally efficient way, thus, obtaining: Theorem 1. For any > 0, it is NP-hard to find a solution S to optimization problem (6) (and thus (4)) such that Consider an arbitrary undirected unweighted graph G = (V, E ) for which we wish to compute the maximum clique. To reduce the maximum clique problem to (6): 1) define function f as f (S) = |S|, which is clearly monotone and submodular; 2) define payment function as: ∈ E , and τ (v, v p ) = τ (v p , v) = τ min otherwise; 3) set budget B to B = |V |·τ min ; 4) and set τ max > B. Notice that such an arrangement induces a fully connected graph G. Furthermore, we defined deterministic payment functions τ (v, v p ) and τ (v p , v), but one can use E(τ (v, v p )) and E(τ (v p , v)) instead. Points 2 and 4 ensure that any solution to optimization problem (6) is a clique in graph G ; otherwise, the budget constraints would be violated in solving (6). Likewise, points 2 and 3 ensure that any clique is permitted as a potential solution w.r.t. the budget constraint. Finally, point 1 ensures that we search for a clique with the maximum number of vertices. Since the reduction is computationally efficient (polynomial in the graph size, i.e. |V | and E), optimization (4) is at least as hard as the maximum clique problem. Using the fact that the maximum clique problem is hard to approximate within factor 1 |V | 1− (Hastad 1999), we obtain the claim.

Structural Properties of the Cost Function
To cope with the computational hardness of the problem at hand, we identify two structural properties of cost function c e (or equivalently, the structural properties of payment function τ ). The first one is related to topological properties of graph G, and can be quantified with the maximum number of peers that a node in the graph can have. As explained earlier in this section, we denote this number by ω.
The second property is similar to the notion of curvature of a submodular function (Iyer, Jegelka, and Bilmes 2013), but now defined over cost function c e that is not necessarily sub/super-modular. In particular, we define the slope α of cost function c e as: The slope of cost function c e , as defined above, measures how much marginal gains of c e change as we add more to initially empty set of selected nodes. 3 Intuitively, it measures the deviation of c e from modularity. A specific case of our interest is when α = 0, which indicates that c m is modular and, thus, can be decomposed into a sum of costs c m dependent only on one vertex, i.e., v∈S c m (v). In the next subsection, we discuss how to utilize modular approximations of c e when c e itself is not modular. First, let us upper bound the slope α using the fact that payments are bounded.

Relaxed Optimization Problem
To make use of the structural constraints of cost function c e , let us consider a relaxed version of optimization problem (6) with budget constraints defined via a modular lower bound to cost function c e , denoted by c M . As we show in the next section, for such a relaxation, one can develop a greedy approach that has provable approximation guarantees on the quality of the obtained solution relative to OPT. More precisely, consider the modular function c M : 2 V → R defined via a cost function c m : V → R: where c m (v) = min vp∈Nv E(τ (v, v p )).
Clearly, c M (S) lower bounds c e (S) as it calculates the expected payoffs of nodes in S when they are scored against their worst peers (not necessarily in S). Now, we relax optimization problem (6) to: In order to make the relaxation sound, any selected set S * in problem (8) should also be feasible in problem (6) (and thus (4)). We can ensure this by reducing the available budget, i.e., by making B appropriately smaller than B. Using the slope of cost c e , we can obtain that the following budget reduction satisfies our requirement.
Lemma 3. Any feasible solution S to optimization problem (8) is also a feasible solution to optimization problem (6) (and thus (4)) for B ≤ (1 − α) · B, where α is the slope of cost function c e .

Algorithm
We now present a new greedy algorithm for solving the optimization problem with peer-prediction constraints (PPC), called PPCGreedy (Algorithm 1). It is similar to standard greedy approaches for submodular maximization with budget constraints (e.g., Nushi et al. (2015)), but it additionally ensures that a tentative output S * at a certain iteration is an element of 2 V φ . To do so, it initially constructs a set of couples Z that contains all the peer pairs and selects at each iteration t either a node that already has a peer in the selected set or a pair of nodes that are peers. The selection procedure makes a choice z * that maximizes the ratio between the utility gain and the cost increase, while not exceeding a given budget B = (1 − α) · B. If there are multiple choices that maximize this ratio, the selection procedure selects one of them, whereas if there is no choice that fits the budgets constraints, z * is set to N U LL, which ends the search and outputs the current solution S * .

Analysis
We will now show the main property of our algorithm: its near optimality when cost function c e has a low slope α, i.e., when the difference between τ max and τ min is small. Notice that parameters τ max and τ min are controllable through our design of a peer-prediction method τ and the requirements on minimal expected payments, which implies that α can be tuned. For all practical reasons, it is also reasonable to assume that (1−α)·B τmax > 2, which simply states that our algorithm is always able to initially select any pair of nodes. Theorem 2. Let the maximal relative difference between modular costs of two peer nodes be bounded by r, i.e., r ≥ max v∈V,vp∈Nv cm(v) cm(vp) , and let γ = max v∈V cm(v) B ∈ (0, 1 2 ). Then, the output S * of Algorithm 1 has the following guarantees on the utility: Proof (Sketch). The proof of the theorem is non-trivial, so we outline only its basic steps (see (Radanovic et al. 2017) for more details). Using the fact that f is submodular, while Algorithm 1 is greedy in terms of f /c M ratio, we show that: where S t is equal to S * at time-step t, whileŌPT is the optimum solution to optimization problem (8) when budget B = B. Now, following the the proofs of related results for submodular maximization under budget constraints (e.g., Sviridenko (2004), Nushi et al. (2015)), and adapting them to our setting, we obtain that: As we argue in the full proof, f (ŌPT) ≥ f (OPT) becausē OPT is obtained for the same budget as OPT, but the cost c M that lower bounds c. Together with the above inequality, this implies the statement of the theorem.
We see that the quality of the approximation ratio depends on the structural properties of the cost function, including slope α, the maximum cost discrepancy between two nodes measured by r, and the maximum fraction of the budget assigned to a node, measured by γ. As α approaches its maximum value, i.e., α → 1, the approximation ration goes to 0. This is consistent with the hardness result presented in Section 'Methodology', which shows the necessity of imposing structural constraints. One can reach a similar conclusion by analyzing r as it goes to its maximal value, i.e., r → ∞.
To see this more clearly, we can express the results of the theorem in terms of the original optimization problem and the structural properties of payment function τ . Using the bound on slope α (Lemma 2), the boundedness of payments, which imply r ≤ τmax τmin , we obtain: Corollary 1. Assuming B > 2 · ω·τ 2 max τmin , the output S * of Algorithm 1 has the following guarantees on the utility: Therefore, whenever the maximum payment τ max or the number of possible peers ω go to large values, the approximation factor becomes negligible. Notice that the number of Algorithm 2: Algorithm PPCGREEDYITER 1 Output: selected set S * ; 2 Initialize: t = 1; S * = ∅; budget B 0 = B + ; B 1 = B ; ; end 9 Output: S * possible peers ω is dependent on τ min , so we can alternatively say that for small values of τ min , i.e., τ min ≈ 0, the quality of the obtained greedy solution is relatively low. In practice, however, we can often avoid these corner cases by adjusting the payment function, and thus τ max and τ min .

More Efficient Budget Expenditure
The PPCGreedy algorithm, as described by Algorithm 1 does not necessarily spend the full budget on incentivizing nodes. This is because we use a reduced budget B when running the main steps of the algorithm. One can achieve a better budget efficiency by iteratively calling PPCGreedy method, as shown in Algorithm 2, that we refer to as PPC-GreedyIter. It is important to note that in the sub-procedure P P CGreedy we take into account the current set of selected nodes S * when examining the feasibility of a solution and evaluating the utility and cost functions. The budget reduction in the P P CGreedy subroutine can, on the other hand, be done with the same (initial) α. The procedure terminates when no new node is added, which is equivalent to the budget not changing between two consecutive iterations.
The utility function f is always evaluated with the selected set of nodes S * from previous iterations, in the algorithm denoted by f (· ∪ S * ). The same is true for cost function c, denoted by c(· ∪ S * ), and its modular approximation c M . Due to monotonicity of f , this means that the reached solution is always as good as the one obtained by PPCGreedy. Furthermore, the cost of the solution is within the budget constraints: this is because c e ({v}) ≤ c e (v|S) (Lemma 1), so the slope α defined on c e (·) upper bounds the one defined on c(· ∪ S * ), which implies that the subroutine P P CGreedy makes a proper budget reduction. Therefore, the results of Theorem 2 and Corollary 1 are preserved.

Experimental Evaluation
To evaluate our approach, we use a crowd sensing test-bed of Singla (2017), constructed from real measurements of CO 2 and user locations across an urban area. The concentrations of CO 2 in the city of Zurich were acquired with a NODE+ 4 sensor. These measurements were used to fit a Gaussian variogram whose parameters indicate that the relevant correlation range between two measurement locations is about R = 236 meters. We use this distance to define a disk coverage function-for a set of points of interest, we count how many of these are within R meters away from the set of selected points. More formally, given a set of points S that represent the location of the selected sensors and set of points S poi that represent locations for which we would like to obtain CO 2 measurements, the objective function f is defined as: f (S) = s∈Spoi 1 min s ∈S d(s,s )≤R . Here, 1 cond is an indicator variable, evaluating to 1 when cond is satisfied, and is 0 otherwise, while d(s, s ) measures the distance in meters between locations s and s . The function f is a coverage function, which is monotone and submodular (Krause and Golovin 2012).
Points of interest S poi are predefined, and in total, there are 300 of them. These were obtained using a publicly available data (OpenStreetMap 5 ), from which we randomly selected 300 locations from an area in the center of New York City. To identify the locations of available crowd-sensors, i.e., the ground set V , we use the population statistics of the test-bed, which give us the likelihood of a user appearing in one of the 300 points. This statistics is inferred from a publicly accessible dataset (Strava 6 ) that contains the mobility patterns of cyclists for a period of 6 days. We sample from the likelihood 1000 points to obtain sensing locations and then we perturb them by 50 meters.
As a peer prediction scoring rule, we use the output agreement mechanism as described in Section Problem Statement. The expected score of this mechanism for two points s and s in truthful reporting regime is equal to E(d(s, s ) 2 ). We approximate the expected value of OA for two sensors s and s by using the variogram of the test-bed. More precisely, given the range parameter R = 236, we estimate the expected payoff between two sensors as: E(τ (s 1 , s 2 )) = 1 − e − d(s 1 ,s 2 ) 2 a·R 2 , where a is set to 1 3 . Results. We test our approaches, PPCGreedy and PPC-GreedyIter, against two other baselines: (a) a random selection (denoted by Random) that satisfies peer-prediction constraints, (b) a greedy approach (denoted by Greedy) that assumes it suffices to reward each sensor with τ min , without providing incentives for accurate reporting. Clearly, the latter baseline represents an optimistic approach whose performance upper bounds that of the proposed algorithms, while the former one is likely to lower bound their performance. In all the cases, the expected budget is at most B.
We perform two different tests. In the first test, we vary the total available budget B from 5 to 25 at steps of size 5. At the same time, we keep the minimal expected payment to τ min = 0.5. As we can see from Figure 2a, as the total budget increases, all the methods perform better. However, the increase is more notable for non-random algorithms. The performance of PPCGreedyIter is generally better than the one of PPCGreedy, and this is due to the spent budget - (b) Performance as we vary the minimum payments. Figure 2: Experimental results show how the utility f ( S * ) changes as we increase budget B or the minimum expected payments τ min . S * is the output of different methods. Increasing B is beneficial as it allows more sensors to be selected. On the other hand, as we increase τ min , the sensors have less peers and they need to be payed more. Random is run 10 times and we show the means and standard deviations.
as explained in the previous section, PPCGreedy is only the first step of PPCGreedyIter, which further iteratively runs PPCGreedy on the remaining budget.
In the second test, we vary the minimal expected payment τ min , which now takes values in {0.1, 0.25, 0.5, 0.75, 0.9}. Budget B is set to 15. The results are given in Figure 2b. Except for Random, a general trend is that increasing the minimal payments leads to lower performance, which is not surprising given that the number of peers and the budget per sensor decrease in that case. Random in general performs much worse than other techniques for all values of τ min . Moreover, notice that the discrepancy in performance between PPCGreedy, PPCGreedyIter, and Greedy, increases with τ min . Initially, all the non-random algorithms find an optimum of function f , achieving the utility equal to 300.

Related Work
Information elicitation. A standard incentives for quality are typically categorized into gold standard techniques, such as proper scoring rules (Gneiting and Raftery 2007) or prediction markets (Chen and Pennock 2007), or peer-prediction techniques, such as the classical peerprediction (Miller, Resnick, and Zeckhauser 2005) or Bayesian truth serums (Prelec 2004;Witkowski and Parkes 2012;. We focus in this paper on peer-prediction techniques due to the scalability of elicitation without verification for acquiring large amounts of highly distributed information. Recently, several peerpredictions were proposed for various crowdsourcing scenarios. These included micro-task crowdsourcing (Dasgupta and Ghosh 2013), opinion polling (Jurca and Faltings 2011), information markets (Baillon 2017), peer grading (Shnayder et al. 2016), and most importantly for this work, crowdsensing (Radanovic, Faltings, and Jurca 2016). The proposed mechanisms for these domains follow the standard principles of the classical peer-prediction, e.g., incentivizing participants by comparing their reports and placing higher scores for a priori less likely matches. However, they also often extend the design of the original methods by making them more robust in terms of the required number of participants and the knowledge about them, the heterogeneity of users and tasks, or susceptibility to collusive behaviors (Faltings and Radanovic 2017). We analyze orthogonal charac-teristics important for deploying such mechanisms in practice, i.e., budget and cost acquisition constraints. Although the prior work (e.g., Liu and Chen (2016)) does study metamechanisms that make peer-predictions proper in terms of effort exertion, it is often based on scaling techniques, which either ignore budget limitations or the cost of effort.
Submodular function maximization. From the technical side, the most important aspect relates to submodular function maximization. While there is a sizeable literature on this topic (e.g., Krause and Guestrin (2011), Krause and Golovin (2012)), we mostly focus on the prior work that is closely related to the techniques used in this paper. Our basic objective is a subset selection under budget (knapsack) constraints (e.g., Sviridenko (2004)), and we base our algorithmic techniques on a simple greedy approach (Nushi et al. 2015). Notice that we additionally have a graph based constraint, which is in spirit similar to , although we are solving a different optimization problem. Arguably, this paper is most related to submodular maximization with submodular budget constraints ; contrary to this work, our budget constraints are not necessarily sub/super-modular. It is also worth mentioning the hardness results that relate to the ones obtained in this paper, such as the inapproximability of the maximum of a submodular non-monotone, possibly negative, profit function (Feige et al. 2008).

Conclusion
In this paper, we have introduced an information elicitation model for data collection from distributed sources when the incentive mechanism is based on peer-predictions. We have shown that optimal information gathering is computationally infeasible in that even approximating the optimal solution is NP-hard. However, given structural constraints on peer-prediction incentives, we have proposed two greedy methods that achieve good performance relative to the optimum, and have tested their performance empirically on a realistic crowd-sensing test-best.


text:
Partition-based Caching in Large-Scale SIC-Enabled Wireless Networks

Existing designs for content dissemination do not fully explore and exploit potential caching and computation capabilities in advanced wireless networks. In this paper, we propose two partition-based caching designs, i.e., a coded caching design based on Random Linear Network Coding and an uncoded caching design. We consider the analysis and optimization of the two caching designs in a large-scale successive interference cancelation (SIC)-enabled wireless network. First, under each caching design, by utilizing tools from stochastic geometry and adopting appropriate approximations, we derive a tractable expression for the successful transmission probability in the general file size regime. To further obtain design insights, we also derive closed-form expressions for the successful transmission probability in the small and large file size regimes, respectively. Then, under each caching design, we consider the successful transmission probability maximization in the general file size regime, which is an NP-hard problem. By exploring structural properties, we successfully transform the original optimization problem into a Multiple-Choice Knapsack Problem (MCKP), and obtain a near optimal solution with 1/2 approximation guarantee and polynomial complexity. We also obtain closed-form asymptotically optimal solutions. The analysis and optimization results show the advantage of the coded caching design over the uncoded caching design, and reveal the impact of caching and SIC capabilities. Finally, by numerical results, we show that the two proposed caching designs achieve significant performance gains over some baseline caching designs.

I. INTRODUCTION
The rapid proliferation of smart mobile devices has triggered an unprecedented growth of the global mobile data traffic. Recently, caching at base stations (BSs) has been proposed as a promising approach for massive content delivery by reducing the distance between popular files and their requesters [1]- [3]. As the cache size is limited in general, designing caching strategies appropriately is a prerequisite for efficient content dissemination. The performance of a caching design is highly affected by the file diversity it provides. In [4]- [7], the authors consider large-scale wireless network models where the stochastic nature of geographic locations of BSs and users is characterized using stochastic geometry. In particular, in [4], the authors consider caching the most popular files at each BS, which does not provide file diversity. In [5], the authors consider random caching with files being stored at each BS in an i.i.d. manner, which may store multiple copies of a file at one BS and yield storage waste. In [6], [7], the authors consider random caching and multicasting on the basis of file combinations consisting of different files, and analyze and optimize the joint design. Note that the random caching designs in [5]- [7] can provide file diversity. However, in [5]- [7], a file transmission may not make full use of the file diversity provided by the random caching designs, when the serving BS of the file is not close to the file requester. In addition, the caching designs proposed in [4]- [7] require storing entire files at each BS, which may restrict file diversity and limit the potential of caching.
To further improve file diversity, in [8]- [12], files are partitioned into multiple subfiles, and each BS stores an uncoded or coded subfile of a file. For instance, in [8] and [9], the authors propose network coding-based caching designs, and analyze the cache miss probability [8] and minimize the occupied storage space [9], respectively. In [10] and [11], the authors propose MDS code-based caching designs, and minimize the backhaul rate [10] and average delay [11], respectively. In [12], the authors propose a partition-based uncoded caching design, and analyze the successful content delivery probability. Note that the network coding-based caching designs in [8], [9] are restricted to a single file and cannot be directly applied to practical networks with multiple files. In addition, the coded caching designs in [8]- [11] do not consider the delivery of the cached files, and hence may not yield good user experience. Compared to coded caching designs, the uncoded caching design in [12] may not sufficiently exploit storage resources. But [12] considers the delivery of the cached files, where successive interference cancelation (SIC) is employed at each user to decode all the uncoded subfiles of its desired file transmitted at the same time over the same frequency band. Given computational capability at users, applying SIC can facilitate the exploitation of file diversity, and hence improve the performance of the caching design.
SIC is a promising technique to improve the performance of wireless networks with relatively small additional computational complexity. The idea of SIC is to decode multiple signals sequentially by subtracting interference due to the decoded signals before decoding other signals.
The use of SIC hinges on the imbalance of the received powers of different signals, which come from transmitters at different locations in some cases. Conventional performance analysis of SIC is for wireless networks with transmitters residing at given locations [13]. To capture the impact of the spatial distribution of transmitters, recent studies attempt to reveal the gain of SIC in large-scale wireless networks utilizing tools from stochastic geometry [14]- [17]. In this context, approximations are often used due to the well-acknowledged challenge in tracking the problem directly. For instance, in [14], the authors characterize the performance of SIC using a guardzone based approximation, where the interferers inside a guard-zone centered at the receiver are assumed canceled, and the size of the guard-zone is used to model the SIC capability. In [15], the authors consider SIC based on power order, i.e., from the stronger signals to the weaker signals, and derive tractable bounds on the successful decoding probability. In [16] and [17], the authors consider SIC based on distance order, i.e., from the nearer transmitters to the farther transmitters, and obtain closed-form expressions for the coverage probabilities in heterogeneous networks and D2D networks, respectively, assuming independence between decoding events. Note that [13]- [17] focus on performance analysis of SIC in large-scale wireless networks without caching capability.
In summary, further studies are required to understand the fundamental impacts of communication, caching and computation (e.g., SIC) capabilities on network performance. In this paper, we shall shed some light on the essential problem. We consider multiple files and a large-scale SIC-enabled wireless network with random channel fading as well as stochastic locations of BSs and users. Our main contributions are summarized below.
• First, we propose two general partition-based caching designs, i.e., a coded caching design based on Random Linear Network Coding (RLNC) [18] and an uncoded caching design, which incorporate any deterministic and identical (same at all BSs) caching of entire files as a special case. Correspondingly, we transmit multiple coded or uncoded subfiles of a requested file at the same time over the same frequency band, and adopt SIC to decode February 7, 2017 DRAFT these subfiles for recovering the requested file.
• Then, we analyze the successful transmission probability. The challenge in analyzing partitionbased caching and SIC is commonly recognized. By utilizing tools from stochastic geometry and adopting appropriate approximations, under each caching design, we derive a tractable expression for the successful transmission probability in the general file size regime. We also show that the coded caching design outperforms the uncoded caching design in the general file size regime. To further obtain design insights, under each caching design, we derive closed-form expressions for the successful transmission probabilities in the small and large file size regimes, respectively, utilizing series expansion of some special functions.
These expressions reveal the impacts of caching and SIC capabilities. From the asymptotic analysis, we know that under each caching design, the successful transmission probability increases linearly as the file size decreases to zero, and decreases exponentially to zero as the file size increases to infinity.
• Next, we consider the successful transmission probability maximization by optimizing a design parameter. In the general file size regime, under each caching design, by exploring structural properties of the optimization problem which is NP-hard, we successfully transform the original optimization problem into a Multiple-Choice Knapsack Problem (MCKP), and obtain a near optimal solution with 1 2 approximation guarantee and polynomial complexity [19]. Under the coded caching design, we also obtain closed-form asymptotically optimal solutions in the small and large file size regimes, respectively. Under the uncoded caching design, we obtain a near optimal solution in the small file size regime and a closed-form asymptotically optimal solution in the large file size regime, respectively. From the asymptotic optimization results, we know that in the small file size regime, the optimal successful transmission probability under the coded caching design increases with the cache size and the SIC capability. While, in the large file size regime, the optimal successful transmission probabilities under both caching designs increase with the cache size and are not affected by the SIC capability. The asymptotic optimization results also demonstrate the advantage of the coded caching design over any deterministic and identical caching of entire files in the small file size regime.
• Finally, by numerical results, we show that the proposed coded caching design achieves a significant performance gain in the successful transmission probability in the general file size regime over the proposed uncoded caching design and some baseline caching designs.

A. Network Model
We consider a large-scale wireless network, as shown in Fig. 1. The locations of the base stations (BSs) are spatially distributed as a two-dimensional homogeneous Poisson point process We focus on a typical user u 0 , which we assume without loss of generality (w.l.o.g.) to be located at the origin. The BSs are labeled in ascending order of distance from u 0 . Let d i denote the distance between BS i ∈ Φ b and u 0 . Thus, we have d 1 ≤ d 2 ≤ · · · .
We consider the downlink transmission. Each BS has one transmit antenna and transmits with power P over bandwidth W . User u 0 has one receive antenna. Consider a discrete-time system with time being slotted. The duration of each time slot is T seconds. We study one slot of the network. We consider both path loss and small-scale fading. Specifically, due to path loss, transmitted signals with distance d are attenuated by a factor d −α , where α > 2 is the path loss exponent. For small-scale fading, we assume Rayleigh fading, i.e., each small-scale channel Let N {1, 2, · · · , N} denote the set of N files in the network. For ease of illustration, we assume that all files have the same size of S bits. Each file is of certain popularity. User u 0 randomly requests one file, which is file n ∈ N with probability a n ∈ (0, 1), where n∈N a n = 1.
Thus, the file popularity distribution is given by a (a n ) n∈N , which is assumed to be known apriori. In addition, w.l.o.g., we assume a 1 > a 2 . . . > a N .

B. Caching Designs
The network consists of cache-enabled BSs. In particular, each BS is equipped with a cache of size K ≥ 1 (in files), i.e., KS (in bits). Assume each BS cannot store all files in N due to the limited storage capacity, i.e., K < N. Now, we propose two caching designs, i.e., a coded caching design based on Random Linear Network Coding (referred to as RLNC caching design) [18] and an uncoded caching design (referred to as UC caching design), as illustrated in Fig. 1. Both are partition-based and are parameterized by s (s n ) n∈N , where s n ∈ {0} ∪ 1 m m ∈ N + , n ∈ N represents the amount of storage (in files) allocated to file n ∈ N at each BS. Here, N + denotes the set of positive integers. In particular, for any file n ∈ N , consider the following three cases.
(i) If s n = 0, file n is not stored at any BS. (ii) If s n = 1, file n is stored at each BS. (iii) If s n ∈ { 1 m |m = 2, 3, · · · }, file n is partitioned into 1 sn subfiles, each of s n S bits. In Case (i) and Case (ii), the two caching designs coincide. In Case (iii), the two caching designs differentiate with each other as follows.
• RLNC Caching Design in Case (iii): Each BS forms a random linear combination of all the 1 sn subfiles of file n (i.e., a coded subfile of file n which is of s n S bits) using RLNC, and stores it in its cache. We consider RLNC over a large field, and assume that file n can be decoded from any 1 sn coded subfiles of file n stored in the network [18]. • UC Caching Design in Case (iii): Each BS selects a random subfile from the 1 sn subfiles of file n according to the uniform distribution, and stores it in its cache.
The design parameter s of a feasible RLNC or UC caching design satisfies the following constraint n∈N s n ≤ K.
(1) caching designs, as illustrated in Fig. 1. The file transmission under the RLNC caching design is determined by parameter s only. While, the file transmission strategy under the UC caching design depends on parameter s and another parameter m (m n ) n∈N , where m n ∈ { 1 sn , 1 sn + 1, · · · } represents the number of (nearest) BSs serving the request for file n. Specifically, consider the following three cases. (i) If s n = 0, u 0 cannot obtain file n from a cache of the network under either caching design. 1 In this case, we set m n = 0 for the UC cachign design. (ii) If s n = 1, the nearest BS transmits file n to u 0 under both caching designs. In this case, we set m n = 1 for the UC cachign design. (iii) If s n ∈ { 1 m |m = 2, 3, · · · }, each of the 1 sn nearest BSs transmits the stored coded subfile of file n to u 0 under the RLNC caching design, and each of the m n nearest BSs transmits the stored uncoded subfile of file n to u 0 under the UC caching design.
Note that in Cases (ii) and (iii), the subfile transmission of each serving BS is over the whole bandwidth and time slot.
In Case (iii), for the RLNC caching design, file n can be decoded from the 1 sn coded subfiles of file n stored in the 1 sn nearest BSs; for the UC caching design, file n may not be successfully decoded from the m n uncoded subfiles of file n stored in the m n nearest BSs, as the m n subfiles may not cover the 1 sn different subfiles (due to the random placement of the 1 sn different subfiles under the UC caching design). For the UC caching design, let I j n ∈ N + denote the nearest BS storing the jth subfile of file n, where j ∈ {1, 2, · · · , 1 sn }, and denote I u n max I 1 n , I 2 n , · · · , I 1 sn n ∈ { 1 sn , 1 sn + 1, · · · }. Note that I j n , j ∈ {1, 2, · · · , 1 sn } and I u n are random variables with the randomness induced by the random subfile placement, and the probability mass functions (p.m.f.s) of I j n , j ∈ {1, 2, · · · , 1 sn } and I u n depend on s n . In particular, if I u n ≤ m n , file n can be decoded from the subfiles of file n stored in the m n nearest BSs; otherwise file n cannot be decoded. For ease of illustration, we also set I u n = ∞ in Case (i) (i.e., s n = 0) and I u n = 1 in Case (ii) (i.e., s n = 1). In this paper, we consider an interference-limited network and neglect the background thermal noise. We assume all BSs are active for serving their own users. Thus, the received signals of u 0 under the RLNC caching design and the UC caching design, denoted as y c n and y u n respectively, are given by where d i is the distance between BS i and u 0 , h i d ∼ CN (0, 1) is the small-scale channel between BS i and u 0 , x i is the transmit signal from BS i. The first sums in (2) and (3) represent the desired signals, and the second sums in (2) and (3) represent the interferences.
To extract multiple signals under each caching design, we adopt SIC. As in [16], we consider the distance-based decoding and cancelation order. 2 In particular, when decoding the signal from BS i, all signals from the nearer BSs in {1, 2, · · · , i − 1} need to be successfully decoded and canceled, where i ∈ {1, 2, · · · , 1 sn } for the RLNC caching design and i ∈ {1, 2, · · · , I u n } for the UC caching design. 3 The signal-to-interference ratio (SIR) of the signal from BS i after successfully decoding and canceling the signals from the nearer BSs in {1, 2, · · · , i − 1} is given where T , u 0 can successfully decode (and cancel) the signal from BS i. Due to the limited computational capability and the delay constraint, as in [16], we assume that u 0 has limited SIC capability M, which is a system parameter. That is, u 0 can perform decoding and cancelation at most M times to obtain its desired signals.
M} . Given SIC capability M, for the two proposed caching designs to be meanful, we require where (5) is for the RLNC caching design, and (6) is for the UC caching design. Note that when M = 1, (5) and (6)

D. Performance Metric
Requesters are mostly concerned about whether their desired files can be successfully received.
Therefore, in this paper, we consider the successful transmission probability of a file randomly requested by u 0 as the network performance metric. According to the file transmission and reception discussed in Section II-C, the successful transmission probabilities of file n ∈ N requested by u 0 under the RLNC caching design and the UC caching design, denoted as q c n (s n ) and q u n (s n , m n ) respectively, are given by where SIR i is given by (4). According to the total probability theorem, the successful transmission probabilities of a file randomly requested by u 0 under the RLNC caching design and the UC caching design, denoted as q c (s) and q u (s, m) respectively, are given by 4 q c (s) = n∈N a n q c n (s n ), s ∈ S N , q u (s, m) = n∈N a n q u n (s n , m n ), (s, m) ∈ U N .

III. PERFORMANCE ANALYSIS AND OPTIMIZATION OF RLNC CACHING DESIGN
In this section, we consider the performance analysis and optimization of the RLNC caching design. First, we analyze the successful transmission probabilities in the general file size regime, the small file size regime and the large file size regime, respectively. Then, we optimize the successful transmission probabilities in these regions.
As in [16], for the tractability of the analysis, we assume the independence between the events W log(1 + SIR j ) > snS T , j ∈ {1, 2, · · · , i}. Then, we have the following lemma.
where B ′ (x, y, z) Therefore, we have the successful transmission probability under the RLNC caching design, as summarized below.

Theorem 1 (Performance of RLNC in General File Size Regime):
The successful transmission probability q c (s) under the RLNC caching design is given by where q c n (s n ) is given by (10). From Theorem 1, we can see that q c (s) is a decreasing function of S. The impact of s on q c (s) is not obvious. Fig. 2 plots q c (s) versus S at different s. To further obtain design insights, in the following, we analyze the asymptotic successful transmission probabilities in the small file size regime and the large file size regime, respectively.

2) Performance Analysis in Small File Size Regime:
Utilizing series expansion of some special functions, from Theorem 1, we derive the asymptotic successful transmission probability in the small file size regime (i.e., S → 0) as follows.  1 General Here, 1[·] denotes the indicator function.
Proof: Please refer to Appendix B.
From Lemma 2, we know that lim S→0 q c (s) = n∈N a n 1 [s n = 0], and q c 0 (s) increases linearly to n∈N a n 1 [s n = 0] as S decreases to 0. In addition, s affects the asymptotic behavior of q c 0 (s) by affecting lim S→0 q c (s) and the coefficient of S. Fig. 3 (a) plots q c 0 (s) versus S in the small file size regime. We see from Fig. 3 (a) that when S decreases, the gap between each "General" curve, which is plotted using Theorem 1, and the corresponding "Asymptotic" curve, which is plotted using Lemma 2, decreases. Thus, Fig. 3 (a) verifies Lemma 2.

3) Performance Analysis in Large File
Size Regime: Utilizing series expansion of some special functions, from Theorem 1, we derive the asymptotic successful transmission probability in the large file size regime (i.e., S → ∞) as follows.

Lemma 3 (Performance of RLNC in Large File Size Regime):
Here, s max max{s n |n ∈ N } and B(x, y) From Lemma 3, we know that lim S→∞ q c (s) = 0, and q c ∞ (s) decreases exponentially to 0 as S increases to ∞. In addition, s affects the asymptotic behavior of q c ∞ (s) via s max only. Fig. 3 (b) plots q c ∞ (s) versus S in the large file size regime. We see from Fig. 3 (b) that when S increases, the gap between each "General" curve, which is plotted using Theorem 1, and the corresponding "Asymptotic" curve, which is plotted using Lemma 3, decreases. Thus, Fig. 3 verifies Lemma 3.

B. Performance Optimization of RLNC Caching Design 1) Performance Optimization in General File Size Regime:
The caching design affects the successful transmission probability q c (s) via design parameter s. We would like to maximize q c (s) by carefully optimizing s.

Problem 1 (RLNC Caching Design in General File Size Regime):
where q c (s) is given by (11). Let s * denote the optimal solution.
When M = 1, we have s n ∈ {0, 1} for all n ∈ N , and the proposed RLNC caching design degenerates to deterministic and identical caching of entire files. Based on structural properties of q c (s), we know that the optimal caching design is to store the most K popular entire files at each BS. When M ≥ 2, Problem 1 is a challenging discrete optimization problem with a complex objective function. The number of possible choices for s is given by O (M + 1) N .
Thus, a brute-force solution to Problem 1, i.e., exhaustive search, is not acceptable when N and M are large. In the following, we consider M ≥ 2. We aim to obtain a low-complexity solution with superior performance, by carefully exploiting structural properties of Problem 1. First, we convert Problem 1 into an MCKP, which is a generalization of the ordinary knapsack problem. In particular, there are N mutually disjoint classes C 1 , C 2 , · · · , C N , each containing M +1 items, to be packaged into a knapsack of capacity K. Item m ∈ M {1, 2, · · · , M} in class C n represents that the amount of storage allocated to file n is 1 m , and item M + 1 in class C n represents that the amount of storage allocated to file n is 0. The profit p n,m and weight w n,m of item m ∈ M + {1, 2, · · · , M + 1} in class C n are given by Note that w n,m , n ∈ N are the same for all m ∈ M + . Let x n,m ∈ {0, 1} represent whether item m in class C n is packaged into the knapsack, where x n,m = 1 indicates that item m in class C n is packaged into the knapsack. Thus, the profit sum is given by and the weight sum is given by n∈N m∈M+ w n,m x n,m .
Therefore, Problem 1 can be transformed into the following MCKP, which chooses exactly one item from each class such that the profit sum in (16) is maximized without exceeding the capacity K in the corresponding weight sum in (17). where q c (x) is given by (16). Let x * denote the optimal solution.

Problem 2 (Equivalent Problem of Problem 1 (MCKP)):
MCKP is an NP-hard problem, which can be easily shown by reduction from the ordinary knapsack problem. Like other Knapsack Problem variants, MCKP can be solved optimally using two approaches, i.e., the branch-bound method and dynamic programming, with non-polynomial complexity [20]. The increase in the number of items will cause the optimization complexity to increase rapidly. Thus, approximate solutions of polynomial complexity are widely adopted. For instance, the dynamic programming-based approximate solution proposed in [21] can achieve a performance that is no less than 1 − ǫ times the optimal value with running time polynomial to 1 ǫ , where ǫ ∈ (0, 1). Due to the integer requirement (i.e., both the weights and the profits must be positive integers), the dynamic programming-based approximate solution in [21] cannot be applied to Problem 2. In addition, the greedy solution proposed in [19] can achieve a performance that is no less than 1 2 times the optimal value with complexity O((M + 1)Nlog((M + 1)N)). In the following, we adopt the greedy method in [19] to obtain a near optimal solution to Problem 2 with 1 2 approximation guarantee. Before adopting the greedy solution in [19], we first introduce some key definitions.
Definition 1: [19] If two items i and j in the same class C n satisfy w n,i ≤ w n,j and p n,i ≥ p n,j , then item j is dominated by item i. If three items i, j, k in the same class C n with w n,i < w n,j < w n,k and p n,i < p n,j < p n,k satisfy p n,k −p n,j w n,k −w n,j ≥ p n,j −p n,i w n,j −w n,i , then item j is LP-dominated by items i and k.
By (14) and (15) Based on these optimality properties, a greedy method is proposed in [19] to solve MCKP. We adopt this greedy method to solve Problem 2, as summarized in Algorithm 1. The complexity of + 1)N)). The feasible solution x † to Problem 2 obtained by Algorithm 1 achieves a performance that is no less than 1 2 times the optimal value to Problem 2, i.e., q c (x † ) ≥ q c * 2 . Note that Step 1 can be conducted using the prune and search method proposed in [22]. In Step 2, as an initialization, we choose the lightest item M + 1 for each class. In 5: while W + w n,m ≤ K do 6: Set x n,m = 1, x n,m + = 0, and update W = W + w n,m − w n,m + and P = P + p n,m − p n,m + .

7:
Update l = l + 1. Let n, m be the indices satisfying λ n,m = λ(l).  Construct a feasible solution x (x i,j ) i∈N ,j∈M+ to Problem 2 by setting x n,m = 1, x i,j = 0 for i ∈ N , i = n or j ∈ M + , j = m.
14: end if optimal solution to Problem 2. Otherwise, x † is a feasible solution to Problem 2 with worst-case performance 1 2 .

2) Performance Optimization in Small File Size Regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q c 0 (s) in the small file size regime.

Problem 3 (RLNC Caching Design in Small File Size Regime):
where q c 0 (s) is given by (12). By exploring structural properties of q c 0 (s), we can obtain the optimal caching design in the small file size regime.

Lemma 4 (Optimal Solution to Problem 3):
Suppose KM ≤ N. There exists S 0 > 0, such that for all S < S 0 , the optimal solution to Problem 3 is given by and the optimal value to Problem 3 is given by Proof: Please refer to Appendix D.
Lemma 4 indicates that in the small file size regime, when KM ≤ N, it is optimal to allocate the storage of each BS equally to the most KM popular files. That is, each of the most KM popular files is partitioned into M subfiles (each of S M bits), and each BS stores a coded subfile of each of the most KM popular files. The reason is as follows. In the small file size regime, the probability that u 0 can decode the signal from each of the M nearest BSs is high, and allocating the storage of each of the M nearest BSs equally to KM files maximizes the number of files that can be successfully decoded by u 0 . Thus, storing the most KM popular files obviously maximizes the successful transmission probability. In addition, Lemma 4 reveals that in the small file size regime, the optimal successful transmission probability increases with the product of the cache size and SIC capability, i.e., KM.

3) Performance Optimization in Large File Size Regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q c ∞ (s) in the large file size regime.

Problem 4 (RLNC Caching Design in Large File Size Regime):
where q c ∞ (s) is given by (13). By exploring structural properties of q c ∞ (s), we can obtain the optimal caching design in the large file size regime.

Lemma 5 (Optimal Solution to Problem 4):
There exists S ∞ > 0, such that for all S > S ∞ , the optimal solution to Problem 4 is given by and the optimal value to Problem 4 is given by Proof: Please refer to Appendix E.
Lemma 5 indicates that in the large file size regime, it is optimal to allocate the storage of each BS equally to the most K popular files. That is, each BS stores each of the most K popular (entire) files. The reason is as follows. In the large file size regime, the probability that u 0 can decode the signal from any BS besides the nearest one is very small. Allocating the storage of the nearest BS to K uncoded files maximizes the number of files that can be successfully decoded by u 0 . Storing the most K popular files obviously maximizes the successful transmission probability. In addition, Lemma 5 reveals that in the large file size regime, the optimal successful transmission probability increases with cache size K and is not affected by SIC capability M.
Now, we use a numerical example to compare the optimal solution obtained by exhaustive search and the proposed near optimal solution obtained by Algorithm 1 in both successful transmission probability and computational complexity. We also use this example to verify the asymptotically optimal solutions obtained in Lemmas 4 and 5 in the asymptotic file size regimes. Fig. 4 plots the successful transmission probability versus file size S. We can see that the successful transmission probability of the proposed near optimal solution is very close to that of the optimal solution. While, the average computation time for the optimal solution is 3136 times of that for the near optimal solution. This demonstrates the applicability and effectiveness of the near optimal solution. In addition, we can see that the successful transmission probabilities of the asymptotically optimal solutions obtained by Lemmas 4 and 5 approach those of the optimal solutions in the small and large file size regimes, respectively, verifying Lemmas 4 and 5.

IV. PERFORMANCE ANALYSIS AND OPTIMIZATION OF UC CACHING DESIGN
In this section, we consider the performance analysis and optimization of the UC caching design. First, we analyze the successful transmission probabilities in the general file size regime, the small file size regime and the large file size regime, respectively. Then, we optimize the successful transmission probabilities in these regions.

A. Performance Analysis of UC Caching Design 1) Performance Analysis in General File Size Regime:
According to the total probability theorem, from (8) where h(s n , i) is given by (9). To calculate q u n (s n , m n ), it remains to calculate the p.m.f. of I u n . Collecting 1 sn different subfiles of file n under the UC caching design can be viewed as a classical Coupon Collector's Problem, where 1 sn distinct objects (i.e., coupons) are repeatedly drawn (with replacement) from an urn with probability s n of picking an object at each trial until each of the 1 sn objects is picked at least once. In particular, 1 sn different subfiles of file n can be regarded as 1 sn different objects in the Coupon Collector's Problem. The subfile of file n stored at BS i ∈ {1, 2, · · · , m n } can be regarded as the object drawn at the i-th trial in the Coupon Collector's Problem. Recovering file n (i.e., obtaining 1 sn different subfiles of file n) from the subfiles of file n stored at the i nearest BSs is equivalent to collecting all 1 sn types of objects within i trials in the Coupon Collector's Problem. Thus, I u n can be regarded as the minimum number of trials needed to get all 1 sn distinct objects in the Coupon Collector's Problem. From the results of the Coupon Collector's Problem [23], we have From (8), (9), (22) and (23)   Therefore, we have the successful transmission probability under the UC caching design, as summarized below.

Theorem 2 (Performance of UC in General File Size Regime):
The successful transmission probability q u (s, m) under the UC caching design is given by where q u n (s n , m n ) is given by (24). From Theorem 2, we can see that q u (s, m) is a decreasing function of S and an increasing function of m n for all n ∈ N . The impact of s on q u (s, m) is not obvious. By comparing Theorem 1 and Theorem 2, we have the following corollary.

Corollary 1 (Performance Comparison between RLNC and UC Caching Designs):
Given any caching design parameter s ∈ S N , the successful transmission probability under the RLNC caching design is greater than or equal to that under the UC caching design, i.e., q c (s) ≥ q u (s, m) for all m such that (s, m) ∈ U N , where the equality holds when s n ∈ {0, 1} for all n ∈ N .
2) Performance Analysis in Small File Size Regime: From Theorem 2, we derive the asymptotic successful transmission probability in the small file size regime (i.e., S → 0) as follows. Here, p(·, ·) is given by (23).
Proof: Lemma 6 can be proved in a similar way to Lemma 2. We omit the details due to page limitation.
From Lemma 6, we know that lim S→0 q u (s, m) = n∈N a n mn i= 1 sn p (s n , i), which represents the success probability of collecting all different subfiles of a randomly requested file, and q u 0 (s, m) increases linearly to n∈N a n mn i= 1 sn p (s n , i) as S decreases to 0. In addition, s affects the asymptotic behavior of q u 0 (s, m) by affecting lim S→0 q u (s, m) and the coefficient of S. Fig. 6 (a) plots q u 0 (s, m) versus S in the small file size regime. We see from Fig. 6 (a) that when S decreases, the gap between each "General" curve, which is plotted using Theorem 2, and the corresponding "Asymptotic" curve, which is plotted using Lemma 6, decreases. Thus, Fig. 6 (a) verifies Lemma 6.

3) Performance Analysis in Large File
Size Regime: From Theorem 2, we derive the asymptotic successful transmission probability in the large file size regime (i.e., S → ∞) as follows.

Lemma 7 (Performance of UC in Large File Size Regime):
For all (s, m) ∈ U N , we have q u (s, m) Here, p(·, ·) is given by (23).
Proof: Lemma 7 can be proved in a similar way to Lemma 3. We omit the details due to page limitation.
Note that q u ∞ (s) does not depend on m. From Lemma 7, we know that lim S→∞ q u (s, m) = 0, and q u ∞ (s) decreases exponentially to 0 as S increases to ∞. In addition, s affects the asymptotic behavior of q u ∞ (s) in the form of s max only. By comparing Lemma 3 and Lemma 7, we can see that in the large file size regime, the successful transmission probability under the UC caching design is p(s max , 1 smax ) of that under the RLNC caching design. Fig. 6 (b) plots q u ∞ (s) versus S in the large file size regime. We see from Fig. 6 (b) that when S increases, the gap between each "General" curve, which is plotted using Theorem 2, and the corresponding "Asymptotic" curve, which is plotted using Lemma 7, decreases. Thus, Fig. 6 (b) verifies Lemma 7. W = 10MHz, T = 1ms, M = 3, and a n = n −γ n∈N n −γ with γ = 1.

B. Performance Optimization of UC Caching Design
Note that q u (s, m) is an increasing function of m n for all n ∈ N . In the following, to study the optimal successful transmission probability under the UC caching design, we set Specifically, in the general file size regime, we focus on optimizing q u (s) n∈N a n q u n (s n , m n ) over s ∈ S N , where m is given by (28). In the small file size regime, we focus on optimizing q u 0 (s) q u 0 (s, m) over s ∈ S N , where m is given by (28). In the large file size regime, we focus on optimizing q u ∞ (s) over s ∈ S N . 1) Performance Optimization in General File Size Regime: The caching design affects the successful transmission probability q u (s) via design parameter s. We would like to maximize q u (s) by carefully optimizing s.

Problem 5 (UC Caching Design in General File Size Regime):
where q u (s) is given by (25). Let s * denote the optimal solution.
When M = 1, we have s n ∈ {0, 1} for all n ∈ N , and the proposed UC caching design degenerates to deterministic and identical caching of entire files. Based on structural properties of q u (s), we know that the optimal caching design is to store the most K popular entire files at each BS. When M ≥ 2, as Problem 1, Problem 5 can also be converted into an MCKP and solved with 1 2 approximation guarantee using the greedy method in [19].

2) Performance Optimization in Small File Size Regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q u 0 (s) in the small file size regime.
Problem 6 (UC Caching Design in Small File Size Regime): where q u 0 (s) is given by (26). Similarly, Problem 6 can also be converted into an MCKP and solved with 1 2 approximation guarantee using the greedy method in [19].

3) Performance optimization in large file size regime:
In this part, we consider the optimization of the asymptotic successful transmission probability q u ∞ (s) in the large file size regime.

Problem 7 (UC Caching Design in Large File Size Regime):
where q u ∞ (s) is given by (27). By exploring structural properties of q u ∞ (s), we can obtain the optimal caching design in the large file size regime.
Lemma 8 (Optimal Solution to Problem 7): There exists S ∞ > 0, such that for all S > S ∞ , the optimal solution to Problem 7 is given by and the optimal value to Problem 7 is given by Lemma 8 indicates that in the large file size regime, it is optimal to allocate the storage of each BS equally to the most K popular files. That is, each BS stores each of the most K popular files. Note that the optimal UC caching design is the same as the optimal RLNC caching design in the large file size regime. This indicates that the advantage of the RLNC caching design over the UC caching design vanishes in the large file size regime.

V. NUMERICAL RESULTS
In this section, we compare the proposed near optimal RLNC caching design with the proposed near optimal UC caching design and three baselines in the existing literature. Baseline 1 refers to the caching design in which the most K popular entire files are stored at each BS (i.e., s n = 1 for n ∈ {1, 2, · · · , K}, and s n = 0 for n ∈ {K + 1, K + 2, · · · , N}) [4]. Baseline 2 refers to the random caching design in which all files in N are randomly stored at each BS with equal caching probability K N [24]. Baseline 3 refers to the random caching design in which file n ∈ N is stored at a BS with caching probability T n = min{a n K + µ, 1}, where c satisfies n∈N min{a n K +µ, 1} = K. 7 Under Baselines 1, 2 and 3, u 0 requesting file n is associated with the nearest BS which stores file n [6]. In the simulation, the popularity follows Zipf distribution, i.e., a n = n −γ n∈N n −γ , where γ is the Zipf exponent. We choose N = 1000, α = 4, W = 10MHz and T = 1ms. Fig. 7 illustrates the successful transmission probability versus different system parameters.
We can observe that the proposed RLNC caching design significantly outperforms the proposed UC caching design and the three baseline designs, and its performance increases much faster with the SIC capability and the cache size. This is because the proposed RLNC caching design wisely exploits SIC capability and storage resource. In addition, the two proposed partition-based caching designs have better performance than the three baseline designs, which focus on storing entire files. This is because the partition-based caching designs achieve higher file diversities than the caching designs storing entire files.
Specifically, Fig. 7 (a) illustrates the successful transmission probability versus the file size S. We can see that the performance gaps between the proposed RLNC caching design and the other caching designs are relative large at small S. This is because when S is small, the success probability of sequentially decoding multiple signals using SIC is relatively large, and hence, the benefit of high file diversity offered by the proposed RLNC caching design can be seen more clearly. under the three baseline designs, which store entire files, the successful transmission probability of an entire file from the nearest BS does not change with M. In addition, note that when M = 1, the successful transmission probabilities of the proposed RLNC and UC caching designs and Baseline 1 are the same. This is because as discussed in Sections III-B1 and IV-B1, the optimal RLNC and UC caching designs degenerate to Baseline 1, when M = 1. Fig. 7 (c) illustrates the successful transmission probability versus the cache size K. We can see that the performance of all the caching designs increases with K. This is because as K increases, each BS can store more files, and the probability that a randomly requested file can be obtained from the nearby BSs increases. Fig. 7 (d) illustrates the successful transmission probability versus the Zipf exponent γ. We can see that the performance of the proposed RLNC and UC caching designs, Baseline 1 and Baseline 3 increases with γ. This is because when γ increases, the probability that a requested file is a popular one increases. These popularity-aware caching designs store more popular files in the network, while Baseline 2 allocates the same storage resource to all the files.

VI. CONCLUSION
In this paper, we proposed two partition-based caching designs, i.e., a RLNC caching design and an UC caching design, and analyzed and optimized the two caching designs in a large-scale SIC-enabled wireless network. First, by utilizing tools from stochastic geometry and adopting appropriate approximations, we analyzed the successful transmission probabilities in the general file size regime and the two asymptotic file size regimes. We also showed that the RLNC caching design outperforms the UC caching design in the general file size regime, and the successful transmission probability of each proposed caching design decreases linearly with the file size in the small file size regime, and decreases exponentially with the file size in the large file size regime. Then, for each proposed caching design, by exploring structural properties, we successfully transformed the original caching optimization problem, which is NP-hard, into an MCKP problem, and obtained a near optimal solution with 1 2 approximation guarantee and polynomial complexity in the general file size regime. We also obtained closedform asymptotically optimal solutions. The asymptotic optimization results show that in the small file size regime, the optimal successful transmission probability under the RLNC caching design increases with the cache size and the SIC capability. While, in the large file size regime, the optimal successful transmission probability of each proposed caching design increases with the cache size and is not affected by the SIC capability.
APPENDIX A: PROOF OF LEMMA 1 First, the conditional probability of successfully decoding the subfile of file n stored at BS j after successfully decoding and canceling the signals from the nearer BSs in {1, 2, · · · j − 1}, conditioned on d j = x, is given by where (a) is obtained based on (4), and (b) is obtained by noting that |h j | 2 d ∼ exp (1). To calculate p n,j,d j (s n , x) using (31), we only need to calculate L I j (s, x). The expression of L I j (s, x) is calculated as follows where (c) is obtained by utilizing the probability generating functional of PPP [25, Page 235], and (d) is obtained by first replacing s − 1 α r with t, and then replacing 1 1+t −α with w. Substituting s = 2 snS W T − 1 x α into (32), we have Next, we calculate the probability of successfully decoding the signal from BS j after successfully decoding and canceling the signals from the nearer BSs in {1, 2, · · · j − 1}, denoted as p n,j (s n ), by removing the condition of p n,j,d j (s n , x) on d j = x. Note that we have the p.d.f. of d j as Finally, by assuming the independence between the events W log(1+SIR j ) > snS T , j ∈ {1, 2, · · · , i} [16], we have h(s n , i) = i j=1 p n,j (s n ) = 1 We complete the proof of Lemma 1.

APPENDIX B: PROOF OF LEMMA 2
Consider any file n ∈ N . When s n = 0, we have q c n (s n ) = 0 as S → 0. It remains to calculate q c n (s n ) as S → 0 for s n ∈ S \ {0}. We note that B Thus, as S → 0, we have 8 q c n (s n ) = h s n , where (a) is due to (33), (b) is due to 2 x − 1 = (ln2)x + o(x) as x → 0, (c) is due to ∼ q c 0 (s). Therefore, we complete the proof of Lemma 2.
APPENDIX C: PROOF OF LEMMA 3 Consider any file n ∈ N . When s n = 0, we have q c n (s n ) = 0 as S → ∞. It remains to calculate q c n (s n ) as S → ∞ for s n ∈ S \ {0}. We note that B ′ (a, b, z) = B(a, b) − z a a + o(z a ), as z → 0. Thus, as S → ∞, we have In addition, from (9) and (10) Substituting feasible solution s * given in (20) into (13), we have q c ∞ (s * ) = n∈N a n 1[s * On the other hand, for any feasible solution s to Problem 4, we have q c ∞ (s) = n∈N a n 1[s n = s max ] Thus, we have q c ∞ (s) q c ∞ (s * ) = n∈N a n 1[s n = s max ] n∈N a n 1[s * n = 1] For any feasible solution s = s * to Problem 4, we show q c ∞ (s) q c ∞ (s * ) < 1 for large S by considering the following three cases. (i) If s max = 1, based on (41), we have q c ∞ (s) q c ∞ (s * ) = n∈N a n 1[s n = 1] n∈N a n 1[s * n = 1] .