Pricing strategy based on pvcg

In the role benefit distribution model of distributed machine learning, the benefits of the global verifier and local verifier are almost fixed like the miners in the blockchain, and will only change with the activity of the system. The aggregator is the task scheduler and coordinator, and its benefits are positively correlated with the trainer. The only more complicated issue is that during the local training process of the model, the trainer may use data from other data sources, and we need to give additional consideration to the gaming problem in the local training scenario of distributed machine learning. The trainer's operating environment will have some thresholds, while other network participants who do not fulfill the hardware requirements can participate in the training process by providing data. A game model is needed between the data providers and the real trainers to distribute their benefits fairly.

To incentivize data providers to contribute the best datasets to the training process, we need to pay sufficient rewards to data providers to cover their costs. The marginal monetary reward for contributing more data should be no less than the resulting marginal cost. In addition, our goal is to maintain a balanced budget and optimize social welfare. At least three sources of information asymmetry are intertwined in this problem: 1) The dataset owned by each data provider; 2) The cost of each data provider; 3) The valuation of trained distributed machine learning models by model users.

To overcome these information asymmetries and achieve the above objectives, we design rational incentives, i.e., a function that calculates participants' payoffs.

There exists a set of $n$ data providers, denoted by $N = {0, \ldots, n - 1}$ , and another set of $m$ model users, denoted by $M = {n, \ldots, n + m - 1}$. Each data provider $i \in N$ owns a dataset $\bar{d}_i$. It claims it owns a dataset $\hat{d}_i$. The federation accepts a dataset $d_i \oslash \hat{d}_i$ from this data provider. We call $\eta_i = \frac{d_i}{\hat{d}i}$ the acceptance ratio, where $\oslash$ denotes element-wise division. Trained on datasets $d = (d_0, \ldots, d{n-1})$ from all data providers, the usefulness of the distributed machine model is $Q(d)$. Model users may be granted limited access to the distributed machine model such that the usefulness of the distributed machine model to model user $j$ is $\kappa_j Q(d)$, where $\kappa_j$ is called the access permission. Each data provider $i \in N$has a cost type $\gamma_i \in \Gamma_i$. Its cost of contributing data $d_i$ is $c(d_i, \gamma_i)$. The collection of cost types of all data providers forms the cost type profile $\gamma = (\gamma_0, \ldots, \gamma_n)$. Data provider $i$ may report a different cost type $\hat{\gamma}_i$.

Each model user $j \in M$ has a valuation type $\theta_j \in \Theta_j$. Its valuation on the trained distributed machine model is

$$w(\kappa_j Q(d), \theta_j) = v(d, \kappa_j, \theta_j)$$

The collection of valuation types of all model users forms the valuation type profile $\theta = (\theta_n, \ldots, \theta_{n+m-1})$. Model user $j$ may report a different valuation type $\hat{\theta}j$. The payment to data provider $i \in N$ is $p_i \geq 0$. The payment to model user $j \in M$ is $p_j \leq 0$. We denote $p_s = (p_0, \ldots, p{n-1})$ and $p_d = (p_n, \ldots, p_{n+m-1})$. The federation income is $I = - \sum_{j=n}^{n+m-1} p_j$; the federation expenditure is $E = \sum_{i=0}^{n-1} p_i$; the federation profit is $P = \sum_{l=0}^{n+m-1} p_l$. Participants' preferences are represented by quasi-linear utility functions:

$$u_i(\cdot) = p_i(\cdot) - c_i(\cdot) \text{ for } i \in N; \\ u_j(\cdot) = p_j(\cdot) + v_j(\cdot) \text{ for } j \in M$$

The social effect of distributed machine learning is measured by social surplus, defined as

$$S(\cdot) = \sum_{j=n}^{n+m-1} v_j(\cdot) - \sum_{i=0}^{n-1} c_i(\cdot)$$

which includes consumer surplus $S_d = \sum_{j=n}^{n+m-1} v_j(\cdot)$ and producer surplus $S_p = - \sum_{i=0}^{n-1} c_i(\cdot)$. There are user-defined unfairness functions $\bar{w}_s(p_s, c)$ and $\bar{w}_d(p_s, v)$ that measure the unfairness among data providers and model users.

We set the data providers as the supply side and the trainers as the demand side, and use the PVCG model, which maximizes social welfare, as the supply-side auction offer model, and use the Cremer-McLean mechanism to maximize the demand-side utility.

Given that the federation Income $I(Q)$ and the model quality $Q(\hat{d}, \eta)$ are exogenous functions, the supply-side distributed machine learning incentive mechanism design is to design the optimal. Specifically on the supply side, letting the data providers provide the maximum data efficiency $\eta_i(\hat{d}, \hat{\gamma})$ and provide the optimal reward $p_i(\hat{d}, \hat{\gamma})$ for them, and on the demand side, letting the trainers produce the optimal model results so that the trainer outputs the maximum model validity $\kappa_j(\hat{\theta})$ and provides the optimal reward $p_j(\hat{\theta})$ for them.

Crémer-McLean Mechanism

The detailed process of the Crémer-McLean mechanism for the demand side involves the following steps:

Step 1: Consumer Valuation and Preferences

Each consumer $i$ privately holds a valuation $\theta_i$ for the product or service being offered.

Step 2: Decision Rule

Consumers submit their valuations through a decision rule $\kappa(\hat{\theta})$, where $\hat{\theta}$ represents the reported valuations.

Step 3: Payment Rule Design

An interim incentive compatible and interim individually rational payment rule $p(\hat{\theta})$ is designed to extract the full consumer surplus.

Crémer-McLean Theorem Formulation

The Crémer-McLean Theorem states that for any decision rule $\kappa(\hat{\theta})$ satisfying the Crémer-McLean condition and identifiability condition, there exists a payment rule $p(\hat{\theta})$ that extracts full consumer surplus:

$$\sum_{j=n}^{n+m-1} p_j(\hat{\theta}) = \sum_{j=n}^{n+m-1} w(\kappa_j(\hat{\theta})Q, \theta_j)$$

Optimization Process

The payment rule $p(\hat{\theta})$ can be found by minimizing a loss function to ensure interim incentive compatibility, individual rationality, and full consumer surplus extraction.

Procurement-VCG (PVCG) Mechanism

As a counterpart of the Crémer-McLean mechanism, we create the PVCG on the supply side. The PVCG mechanism is designed to incentivize distributed machine learning participants to truthfully report their type parameters and offer their best datasets to the federation. This mechanism provides theoretical guarantees for incentive compatibility, allocative efficiency, individual rationality, and weak budget balancedness. The PVCG mechanism, along with the Crémer-McLean mechanism, aims to address the challenges of information asymmetry and free-riding in distributed machine learning by providing appropriate incentives to participants.

When designing the supply-side mechanism, we assume the federation income $I(Q)$ to be an exogenous function that depends on the quality of the distributed machine model $Q$. This assumption allows us to focus on optimizing the supply-side distributed machine learning incentive mechanism without directly considering the intricacies of how the federation income is determined. By assuming $I(Q)$ as an exogenous parameter, we can streamline the design process and concentrate on factors such as dataset contributions, cost types, and acceptance ratios to achieve the desired objectives in distributed machine learning. The supply-side use of the PVCG mechanism gives us the revenue of the distributed machine learning training process as:

$$I(Q) = - \sum_{j=n}^{n+m-1} p_j(\theta) = \sum_{j=n}^{n+m-1} w(\kappa_j(\theta)Q, \theta_j)$$

Procurement Auction Process of PVCG and Payment Calculation for Data Providers

Step 1: Data Providers Claim Datasets to Offer and Bid on Cost Types

As the first step, each data provider submits a sealed bid for their claimed datasets and cost types. The claimed dataset ( \hat{d}_i ) is the dataset that data provider ( i ) claims to offer for distributed machine learning. It may differ from the actual dataset ( \bar{d}_i ) owned by the data provider. Similarly, the reported cost type ( \hat{\gamma}_i ) may differ from the true cost type ( \gamma_i ).

Step 2: The Coordinator Chooses the Optimal Acceptance Ratios

The coordinator determines the optimal acceptance ratios $\eta_i$ for each data provider by maximizing the social surplus:

$$\eta^* = \arg\max_{\eta \in [0,1]^{dim(d_i) \times n}} \left\{ I(\hat{d} \cdot \eta) - \sum_{i=0}^{n-1} c_i(\hat{d}_i \cdot \eta_i, \hat{\gamma}_i) \right\}$$

Step 3: Data Providers Contribute Accepted Datasets to Distributed Lachine Learning

Data providers contribute their accepted datasets $\hat{d} \cdot \eta^*$ to distributed machine learning. If a data provider cannot contribute $\hat{d}_i \cdot \eta^*_i \leq \hat{d}_i$, a high punishment is imposed. The income to the federation is $I(\hat{d} \cdot \eta^*)$.

Step 4: The Coordinator Makes Transfer Payments to Data Providers According to the PVCG Sharing Rule

The PVCG payment $p_i(\cdot)$ consists of the VCG payment $\tau_i$ and the optimal adjustment payment $h^*_i$:

$$p_i(\cdot) = \tau_i(\cdot) + h^*_i(\cdot)$$

The VCG payment $\tau_i$ to data provider $i$ is calculated as:

$$\tau_i = S^(\hat{d}, \hat{\gamma}) - S^{-i}(\hat{d}{-i}, \hat{\gamma}_{-i}) + c(\hat{d}_i \cdot \eta^*_i)$$

where $S^*$ represents the maximum producer surplus and $S^*{-i}$ is the surplus without data provider $i$. $\hat{d}{-i}$ and $\hat{\gamma}_{-i}$ denote the claimed datasets and reported cost types excluding data provider $i$.