response.tex

\documentclass[a4paper,11pt]{exam}
\printanswers

\usepackage{color}

\renewcommand{\solutiontitle}{\noindent\textbf{Response:}\par\noindent}

\begin{document}

\title{Response to the Reviews}
\author{Shiyu Ji}
\maketitle

\begin{questions}
\section{Reviewer 1}
\question Several key issues are not presented clearly, making the paper hard to be followed. For instance, the paper discussed the n-truthful property of the proposed mechanism, during which the authors assumed that the proposed mechanism is strategyproof. So, it is better to give a lemma or a theorem to explicitly prove that the proposed mechanism is strategyproof. Actually, only Lemma 3 in this paper is related to this issue. Nevertheless, this Lemma still has not shown the strategyproof property explicitly. This makes the readers hard to follow this paper, especially for the readers who do not know this area very well. The paper requires the reader to be familiar with the theory of auctions. It is better to spend more time giving some background on auctions. 
\begin{solution}
I have made Lemma 3 more clear. Now it clearly states that for the given $n_i$ profile, the discrete crowdsensing game achieves strategyproof equilibrium. I also gave some texts before Lemma 3: before we introduce our main results, we need Lemma 3, which gives the strategyproof equilibrium for the discrete crowdsensing game. Hope by doing this the readers can better follow the logic flow.

Our mechanism is not a typical auction, since there is no selection phase. In our mechanism every user can be a winner, if finishing the task will not cause any negative utility to the user. We have not used any auction theory in our analysis. Thus I think it is enough to give details about the typical crowdsensing model in many existing papers in Section III.A. The readers can well understand our mechanism even without any background of auction theory. On the other hand, it is a good idea to give some citations to auction-based mechanisms in the related works section. But I want to be brief since they are not quite relevant to this paper.
\end{solution}

\question The model in this paper has some limitations. The authors did not consider some important issues in the platform, which are generally concerned in other papers, such as the number of tasks to be finished and the budget constraint of the platform to finish these tasks. When these issues are taken into consideration, the problem might become more difficult. Despite this, it is better to give an explanation or discussion on this, to make the proposed mechanism practical. 
\begin{solution}
I have revised the main algorithm to consider these factors: the number of tasks to finish and the budget constraint. This is done by adding the number of sensing tasks $R$ and the budget constraint $n\cdot P_m \leq B$, where $n$ is the entire user population, $P_m$ is the maximum payment to any user and $B$ is the upper bound of the budget. I have also reflected these changes and evaluated their performance in the experimental section. Hope by doing this our mechanism can have more practical value.
\end{solution}

\question In this paper, the authors assume that the range of each user’s cost unit is known to the platform and each user has a maximum payment. The proposed mechanism totally relies on the parameters in the assumption. However, the paper did not mention how to get the parameters in a real crowdsensing system.
\begin{solution}
The range of each user cost unit can be inferred from historical records. This point has been verified by Koutsopoulos's work. I have also clarified how to choose the maximum payment $P_m$. It can be related to the budget $B$ satisfying $n\cdot P_m \leq B$. From the experiments, usually each game can only consume less than 10\% of the budget. Thus the game is budget-feasible. 
\end{solution}

\question Some important related literatures are missing.
\begin{solution}
Previously I give few citations to the existing works based on auction theory. Now I have given some of them: DiPalantino's and Liu's all-pay auctions, Feng's TRAC, etc.
\end{solution}

\section{Reviewer 2}
\question In Section VII, the simulations demonstrate that the authors’ crowdsensing incentive mechanism can achieve group strategyproof and n-truthful equilibrium simultaneously. However, if we do not consider the collusion attack problem, how are about the performance of the proposed crowdsensing incentive mechanism compared to other existing ones? The authors did not discuss it.  
\begin{solution}
Previously the experiment design is not good, since to show the security properties such as achieving group strategyproofness, one has to do it in theory rigorously, rather than simulations. Now I have decided to rebuild the experiments and compare the performance of our mechanism to other works such as Koutsopoulos's. I have considered three performance measurements: running time, budget utilization ratio and finished sensing task ratio. These three measurements can verify our mechanism is efficient, budget feasible and can finish most of the given tasks appropriately. Hence I have rewritten the experimental section. Now the performance question proposed by this reviewer can be answered, while the rigor of (group) strategyproofness has been achieved by theoretical reasoning.
\end{solution}

\question In Page 1, the authors say “But like other penetration analysis, there is no guarantee of guard against unexamined cases”. However, in Page 9, they conclude that the proposed crowdsensing incentive mechanism can resist any collusion attack. So, if there exists an unexamined collusion attack except those ones in the paper, can the  crowdsensing incentive mechanism be against it?  which is not clear in the paper.
\begin{solution}
Since we have eliminated the possibility of any collusion attack even with profit trading in theory rigorously, it is safe to say that our mechanism can resist any collusion attack in any form. 
We have added more discussions regarding this point in Section IX.
\end{solution}

\question In Page 4 Section IV, “e” should be modified to “we”.
\begin{solution}
This typo has been fixed.
\end{solution}

\question In Page 2, the caption of Table 1  should be on the top of itself.
\begin{solution}
This problem has been fixed.
\end{solution}

\section{Reviewer 3}
\question The limitation of this paper is that it only studies two specific types of crowdsensing systems, where the user's participation level is measured by sensing time and the number of sensing tasks respectively. There are also other crowdsensing systems, for example, users can also submit the set of crowdsensing tasks to perform with their cost.
\begin{solution}
Even though our paper cannot cover all the possibilities in crowdsensing games, our models are quite general and typical. They capture the most important features of crowdsensing: payment and workload (sensing time of each user). The equation $u = p - \kappa t$ should reflect most crowdsensing games. If some users cannot participate due to certain restrictions, they can simply quit. All the participating users can give a game which is convenient to research. On the other hand, many restrictions such as different sets of tasks for different users are difficult to define. Thus in this paper we decide to focus on the most general and typical crowdsensing game model in existing works. 
I have added more discussions about this point in Section III.A. The new texts are in blue.
\end{solution}

\question For the first type of crowdsensing model, where the user's participation level is measured by sensing time, only a strategyproof, but not group strategyproof, incentive mechanism is described.
\begin{solution}
Our main result, Theorem 1, has given the condition which strategyproof game can also be group strategyproof. That is, the PDG must be acyclic. This is a quite general result, which can spawn many different constructions.
\end{solution}

\question Typos: 
In Section I, ``For another group of typical crowdsensing game'', ``When the possibility that colluding nodes can trade profit among them''
In Section II.B, ``a equilibrium''
In Section III, ``We also present an example to present''
In Section IV, ``e leverage...''
\begin{solution}
All the typos have been fixed. That is, 
In Section I, ``For another group of typical crowdsensing games'', ``When it is possible that colluding nodes can trade profit among them''
In Section II.B, ``an equilibrium''
In Section III, ``We also present an example to illustrate''
In Section IV, ``we leverage...''
\end{solution}

\section{Reviewer 4}
\question My major concern is that the paper is more of a kind of reverse engineering. The main architecture is similar to those in references [14][17][20]. The analysis tools are almost directly applied to the crowdsensing platform, without addressing the unique features of crowdsensing platform, which is different from other scenarios. My detailed comments are as follows:
\begin{solution}
We have only researched one typical game model. If one considers the very practical crowdsensing systems in the real world, our contribution cannot answer every problem. However, we have offered a graph based analysis method, which I think should be interesting and may give inspiration to other problems in crowdsensing game.
\end{solution}

\question First, the authors should justify the motivation for users to collude. Normally, crowdsensing users may not be aware of the identity of other users. Collusion is very hard to be conducted when the cost of coordinating colluders’ actions is high. The author did mention that one person may own multiple devices and collude among those devices. But a user may own 2-3 devices, while the entire user population may be on the scale of thousand. 
\begin{solution}
Better utilities for the nodes motivate the users to collude. This has been discussed in the introduction. However, in the previous versions, we did not discuss the collusion size. In the real-world applications, the collusion size is much smaller compared to the total user population. It is good to add more discussions on the collusion size and its relations with our results. Firstly, it is usually difficult to guarantee the upper bound of collusion size, since the adversarial always try to hide such information. Secondly, if such an upper bound can be guaranteed, then any strategyproof mechanism can be group strategyproof by satisfying a much weaker condition, i.e., the size of smallest cycles in the PDG is larger than the upper bound of collusion size. 
We have added more discussions in Sections I and IV. Corollary 1 has been added to reflect the relations between the upper bound of collusion size and our results. The new text has been highlighted in blue.
\end{solution}

\question I want to know whether the platform utility will be affected by adopting the proposed collusion-resistant mechanism. Equation (2) gives the platform utility, but afterwards there is no theoretical or numerical analysis on the platform utility. The objective of the platform operator may be more focused on utility maximization rather than eliminating all the collusions.
\begin{solution}
Note that the platform utility is never mentioned in this version. Therefore, I decide to remove all the platform utility. Now we assume the platform are always willing to conduct the crowdsensing game, since the budget is given and we can guarantee that our mechanism is budget feasible. Then the incentive for the platform can be related to the budget minus all the payments.
\end{solution}

\question Equation (3) and (4) needs clearer explanation. Notations $s*_S$ and $s*_{\overline{S}}$ should be defined. It should be clearly stated that $s*_S$ is the strategy profile of the users in set $S$, and $\overline{S}$ is the complementary set of $S$. 
\begin{solution}
I have given discussions about the notations. The explanations are also added in the symbol table. All the new entries are highlighted in blue.
\end{solution}

\question It is strange that the required sensing time, computed by the crowdsensing platform, only depends on the reported cost of users, just for the sake of collusion-resistance. The required sensing time is associated with the sensing task itself. I wonder if the collusion-resistant incentive mechanism can only manipulate the payment $p_i$ rather than the required sensing time $t_i$. 
\begin{solution}
If one assumes the platform does not return $t_i$ to each user, the resulted model is significantly different from ours. The difficulty to achieve any collusion resistance is that the platform has no idea about the exact cost unit of each user. To be fair, the platform can only give payment proportionally to each user's contribution. Then for the users with low cost unit, she can do the tasks as many as she can, and there is no maximum utility for her. Clearly for this case there is no equilibrium. On the other hand, our model has received extensive research in exsiting works. 
The general game model in this paper was proposed by Koutsopoulos in INFOCOM. Yang et al have given another similar model in MOBICOM, but the platform knows the cost unit of each user exactly. Hence I think it is still worth researching on this model. However, expanding the current results by changing the assumptions is good and requires further future work.
\end{solution}

\question The evaluation setting is very confusing. I don’t understanding why “a colluded user i’s cost unit is 1.0, and the perturbation size is 2.0. Then this user i has probability of 25\% to claim $s_i$ = 0,01, and 75\% to claim a strategy larger than 0.01” , where did the figures 25\% and 75\% come from? Can it be 10\% and 90\%? Also, if some users collude, they will choose the optimal reported cost rather than randomly choosing a cost to report, which may hurt their utility.  So I don’t think the results in Fig. 5---10 are valid. Also, the utility comparison of the platform operator under non-collusion-resistant and collusion-resistant mechanisms is wanted. 
\begin{solution}
I think in previous versions, the experiment design is not good, since if one wants to show security properties such as group strategyproofness, the only way is to do it in theory rigorously. Since we have given the conditions of group strategyproofness and profit trading resistance, it should be safe to say our mechanism achieves the desired goals and there is no need to ``verify'' by using experimental results. 

For experiments, I think it should be much better if we focus on the performance of our mechanism, e.g., running time, utilization of the budget, finishing ratio of the available sensing tasks, etc. Thus in this version, I have rewritten the experimental part. I have redone all the experiments, and given all the results of performance. Hope by doing this our experimental part can make more sense. 
\end{solution}

\question Typos, line 50, page 4, left column, “e leverage”. Line 10, page 5, left column, PDG is not defined.
\begin{solution}
The typo has been fixed. 
The definition of PDF has been push forwarded into Section IV for a better presentation.
\end{solution}
\end{questions}
\end{document}