TY - GEN
T1 - Truthful mobile crowd sensing with interdependent valuations
AU - Zhang, Meng
AU - Swenson, Brian
AU - Huang, Jianwei
AU - Vincent Poor, H.
N1 - Publisher Copyright:
© 2020 ACM.
PY - 2020/10/11
Y1 - 2020/10/11
N2 - Mobile crowd sensing (MCS) has been used to enable a wide range of resource-discovery applications by exploiting the "wisdom"of many mobile users. However, in many applications, a user's valuation depends on other users' sensory data, which introduces the problem of interdependent valuations. This feature can encourage sensory data misreport, hence makes economic mechanisms challenging. While some work has been done to address this problem, the issues of private utility information and communication overheads remain unsolved. In this study, we formulate the first interdependent-valuation model for the resource-discovery MCS systems, aiming to elicit truthful sensory reports and utility information and to maximize expected social welfare. We design a Truthful Sense-And-Bid (T-SAB) Mechanism based on surrogate functions, which can reveal marginal utility information by only requiring each user to submit one-dimensional signaling per resource. We show that the surrogate function and a reward function can limit users' willingness to misreport, when users have small informational sizes, a reasonable condition in large-scale MCS systems. Consequently, our T-SAB Mechanism yields a Perfect Bayesian Equilibrium (PBE) with the efficient allocation outcome, approximate truthfulness, individual rationality, and approximate budget balance. To illustrate the effectiveness of the T-SAB Mechanism, we perform a case study of a cognitive radio network. We demonstrate that the social welfare gain of the T-SAB Mechanism can achieve up to 20% social welfare gain comparing with a benchmark.
AB - Mobile crowd sensing (MCS) has been used to enable a wide range of resource-discovery applications by exploiting the "wisdom"of many mobile users. However, in many applications, a user's valuation depends on other users' sensory data, which introduces the problem of interdependent valuations. This feature can encourage sensory data misreport, hence makes economic mechanisms challenging. While some work has been done to address this problem, the issues of private utility information and communication overheads remain unsolved. In this study, we formulate the first interdependent-valuation model for the resource-discovery MCS systems, aiming to elicit truthful sensory reports and utility information and to maximize expected social welfare. We design a Truthful Sense-And-Bid (T-SAB) Mechanism based on surrogate functions, which can reveal marginal utility information by only requiring each user to submit one-dimensional signaling per resource. We show that the surrogate function and a reward function can limit users' willingness to misreport, when users have small informational sizes, a reasonable condition in large-scale MCS systems. Consequently, our T-SAB Mechanism yields a Perfect Bayesian Equilibrium (PBE) with the efficient allocation outcome, approximate truthfulness, individual rationality, and approximate budget balance. To illustrate the effectiveness of the T-SAB Mechanism, we perform a case study of a cognitive radio network. We demonstrate that the social welfare gain of the T-SAB Mechanism can achieve up to 20% social welfare gain comparing with a benchmark.
KW - game theory
KW - interdependent valuations
KW - mechanism design
KW - mobile crowd sensing
UR - http://www.scopus.com/inward/record.url?scp=85093957206&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85093957206&partnerID=8YFLogxK
U2 - 10.1145/3397166.3409147
DO - 10.1145/3397166.3409147
M3 - Conference contribution
AN - SCOPUS:85093957206
T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
SP - 91
EP - 100
BT - MobiHoc 2020 - Proceedings of the 2020 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
PB - Association for Computing Machinery
T2 - 21st ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2020
Y2 - 11 October 2020 through 14 October 2020
ER -