A Double Auction for Querying the Web of Data

Currently, the Web of Data (WoD) suffers from a lack of incentives for data providers. In this paper, we address this issue by designing a double auction to allocate answers (from data providers) to queries in the WoD. However, our domain exhibits a number of complicating features. Most importantly, the market mechanism only has estimates about what data is available to answer a specific query. Thus, there is "uncertainty about which goods exist in the market," and this may sometimes lead to inefficient allocations. If not handled properly, these inefficient allocations can make the payment rule infeasible because the "participation" constraint and the "budget balance" constraint may be violated. To address this, we propose three new payment rules that always satisfy the participation constraint, and compare the efficiency of these rules via a computational Bayes-Nash equilibrium analysis.