Dynamic Banzhaf Value Computation in Data Market

With the widespread popularity of Artificial Intelligence, the Internet of Things, and various data-driven applications, the economic value of data has become a hot topic in academic research. The demand for data is growing continuously. The data market is an information system used to alleviate the problem of data acquisition and aims to promote efficient trading and sharing of data. A fundamental issue in the data market is data valuation, that is, quantifying the value of data. Banzhaf value, as a concept in cooperative game theory, can be applied to data valuation. Since the accurate calculation of the Banzhaf value is NP-hard, existing research usually uses the Monte Carlo algorithm for approximate calculation. However, in practical applications, the dataset may change continuously with the addition of new data points. This makes recalculating Banzhaf value challenging because of the high time cost. This paper studies the dynamic scenario of adding new data points to the dataset, derives the incremental calculation formula of the Banzhaf value in dynamic scenarios, and proposes an incremental algorithm based on this. The algorithm requires fewer samples to converge, thereby reducing time overhead. We further prove the lower limit of the sample requirement of the algorithm under a given error bound and confidence probability. Experimental results show the effectiveness of the algorithm.