TY - JOUR
T1 - Optimal and Quantized Mechanism Design for Fresh Data Acquisition
AU - Zhang, Meng
AU - Arafa, Ahmed
AU - Wei, Ermin
AU - Berry, Randall
N1 - Funding Information:
Manuscript received July 8, 2020; revised December 15, 2020; accepted February 13, 2021. Date of publication March 11, 2021; date of current version April 16, 2021. This work was supported in part by NSF under Grant CNS-1908807. (Corresponding author: Meng Zhang.) Meng Zhang, Ermin Wei, and Randall Berry are with the Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208 USA (e-mail: meng.zhang@northwestern.edu; ermin.wei@ northwestern.edu; rberry@northwestern.edu). Ahmed Arafa is with the Department of Electrical and Computer Engineering, University of North Carolina at Charlotte, Charlotte, NC 28223 USA (e-mail: aarafa@uncc.edu). Color versions of one or more figures in this article are available at https://doi.org/10.1109/JSAC.2021.3065090. Digital Object Identifier 10.1109/JSAC.2021.3065090
Publisher Copyright:
© 1983-2012 IEEE.
PY - 2021/5
Y1 - 2021/5
N2 - The proliferation of real-time applications has spurred much interest in data freshness, captured by the age-of-information (AoI) metric. When strategic data sources have private market information, a fundamental economic challenge is how to incentivize them to acquire fresh data and optimize the age-related performance. In this work, we consider an information update system in which a destination acquires, and pays for, fresh data updates from multiple sources. The destination incurs an age-related cost, modeled as a general increasing function of the AoI. Each source is strategic and incurs a sampling cost, which is its private information and may not be truthfully reported to the destination. The destination decides on the price of updates, when to get them, and who should generate them, based on the sources' reported sampling costs. We show that a benchmark that naively trusts the sources' reports can lead to an arbitrarily bad outcome compared to the case where sources truthfully report. To tackle this issue, we design an optimal (economic) mechanism for timely information acquisition following Myerson's seminal work. To this end, our proposed optimal mechanism minimizes the sum of the destination's age-related cost and its payment to the sources, while ensuring that the sources truthfully report their private information and will voluntarily participate in the mechanism. However, finding the optimal mechanisms may suffer from prohibitively expensive computational overheads as it involves solving a nonlinear infinite-dimensional optimization problem. We further propose a quantized version of the optimal mechanism that achieves asymptotic optimality, maintains the other economic properties, and enables one to tradeoff between optimality and computational overheads. Our analytical and numerical studies show that (i) both the optimal and quantized mechanisms can lead to an unbounded benefit under some distributions of the source costs compared against a benchmark; (ii) the optimal and quantized mechanisms are most beneficial when there are few sources with heterogeneous sampling costs.
AB - The proliferation of real-time applications has spurred much interest in data freshness, captured by the age-of-information (AoI) metric. When strategic data sources have private market information, a fundamental economic challenge is how to incentivize them to acquire fresh data and optimize the age-related performance. In this work, we consider an information update system in which a destination acquires, and pays for, fresh data updates from multiple sources. The destination incurs an age-related cost, modeled as a general increasing function of the AoI. Each source is strategic and incurs a sampling cost, which is its private information and may not be truthfully reported to the destination. The destination decides on the price of updates, when to get them, and who should generate them, based on the sources' reported sampling costs. We show that a benchmark that naively trusts the sources' reports can lead to an arbitrarily bad outcome compared to the case where sources truthfully report. To tackle this issue, we design an optimal (economic) mechanism for timely information acquisition following Myerson's seminal work. To this end, our proposed optimal mechanism minimizes the sum of the destination's age-related cost and its payment to the sources, while ensuring that the sources truthfully report their private information and will voluntarily participate in the mechanism. However, finding the optimal mechanisms may suffer from prohibitively expensive computational overheads as it involves solving a nonlinear infinite-dimensional optimization problem. We further propose a quantized version of the optimal mechanism that achieves asymptotic optimality, maintains the other economic properties, and enables one to tradeoff between optimality and computational overheads. Our analytical and numerical studies show that (i) both the optimal and quantized mechanisms can lead to an unbounded benefit under some distributions of the source costs compared against a benchmark; (ii) the optimal and quantized mechanisms are most beneficial when there are few sources with heterogeneous sampling costs.
KW - Mechanism design
KW - age-of-information
KW - data acquisition
KW - game theory
UR - http://www.scopus.com/inward/record.url?scp=85102717036&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85102717036&partnerID=8YFLogxK
U2 - 10.1109/JSAC.2021.3065090
DO - 10.1109/JSAC.2021.3065090
M3 - Article
AN - SCOPUS:85102717036
VL - 39
SP - 1226
EP - 1239
JO - IEEE Journal on Selected Areas in Communications
JF - IEEE Journal on Selected Areas in Communications
SN - 0733-8716
IS - 5
M1 - 9376775
ER -