TY - GEN
T1 - Strategy-proof data auctions with negative externalities
AU - Wang, Xiang
AU - Zheng, Zhenzhe
AU - Wu, Fan
AU - Dong, Xiaoju
AU - Tang, Shaojie
AU - Chen, Guihai
N1 - Publisher Copyright:
Copyright © 2016, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2016
Y1 - 2016
N2 - Data has appeared to be a new kind of commodity with distinctive characteristics, which make it fundamentally different from physical goods as well as traditional digital goods. Therefore, new trading mechanisms for data need to be designed. In this paper, we model the data market as an auction with negative externalities, and design practical mechanisms for data trading. Specifically, we propose a family of Data auctIons in CompetiTive mArkets, namely DICTA. DICTA contains two mechanisms, including DICTA-FUL and DICTA-PAR. DICTA-FUL is a direct revelation auction mechanism in full competition markets, achieving strategy-proofness and optimal social welfare. In the partial competition markets, we show that the allocation problem is NP-hard. Therefore, we present an approximation algorithm for winner determination. By carefully integrating this approximation allocation algorithm and a charging scheme, DICTA-PAR achieves both strategy-proofness and d-approximation, where d is the maximum degree of the underlying undirected graph of the competition graph.
AB - Data has appeared to be a new kind of commodity with distinctive characteristics, which make it fundamentally different from physical goods as well as traditional digital goods. Therefore, new trading mechanisms for data need to be designed. In this paper, we model the data market as an auction with negative externalities, and design practical mechanisms for data trading. Specifically, we propose a family of Data auctIons in CompetiTive mArkets, namely DICTA. DICTA contains two mechanisms, including DICTA-FUL and DICTA-PAR. DICTA-FUL is a direct revelation auction mechanism in full competition markets, achieving strategy-proofness and optimal social welfare. In the partial competition markets, we show that the allocation problem is NP-hard. Therefore, we present an approximation algorithm for winner determination. By carefully integrating this approximation allocation algorithm and a charging scheme, DICTA-PAR achieves both strategy-proofness and d-approximation, where d is the maximum degree of the underlying undirected graph of the competition graph.
KW - Auction
KW - Data market
KW - Externality
UR - https://www.scopus.com/pages/publications/85014223298
M3 - Conference contribution
AN - SCOPUS:85014223298
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 1269
EP - 1270
BT - AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016
Y2 - 9 May 2016 through 13 May 2016
ER -