Combinatorial Double Auction Algorithm

onsider a vector of service providers 𝑹 = ⟨𝑅1,𝑅2,...,𝑅𝑛⟩ and inference tasks 𝑻 = ⟨𝑇1, 𝑇2, ..., 𝑇𝑚⟩. Additionally, each inference task should be represented as 𝑇𝑖 = ⟨𝐶𝑖,1𝑡1,𝐶𝑖,2𝑡2,...𝐶𝑖,𝑘𝑡𝑘⟩ where 𝐶𝑖,𝑗 represents the demand for each of the 𝑘 inference task types (e.g. each of the machine learning model types). Let 𝑣𝑖 represent the adjusted valuation of computing the sub-task 𝑇𝑖, which reflects factors imposed by the demand such as the slashing mechanism discussed in Section 6. Let 𝑺 be the set 𝑆𝑗 = (𝒔𝒋, 𝑤𝑗, 𝑐𝑗) where 𝒔𝒋 represents the 𝑗- th resource (e.g. CPU processing power). 𝑤𝑗 represents the maximum number of units of service that device 𝑗 can provide for each resource type 𝑠𝑗,𝑖 and 𝑐𝑗 represents the true adjusted valuation of the 𝑖-th device’s cost.

We can construct a matrix 𝐴 ∈ 𝑀{𝑚×𝑛}(𝟙) such that 𝐴𝑖,𝑗 = {1 𝑅𝑗 accepts the 𝑖 -th task

0 else

Indeed, ∑𝑚𝑘=1 𝐴𝑘,𝑗 ≤ 1, for 1 ≤ 𝑗 ≤ 𝑛 since a model can strictly accept only one model inference. Let the additional cost function be defined by 𝑒𝑖 = 𝑡𝑖 log𝛼(𝑡𝑖) + 𝛽 where 𝛼, 𝛽 ∈ Z+. Then, a utility function for users can be defined as

utility𝑢𝑖 = {𝑣𝑖 − (trade price𝑖 + 𝑒𝑖) if the 𝑖 -th task wins 0 else

Similarly, the utility function for service providers can be defined as

utility𝑝𝑗 = {trade price𝑗 − ∑𝑛𝑖=1 𝐴𝑖,𝑗 if the 𝑗 -th task wins 0 else

We must optimize the function max(∑𝑚𝑖=1 utility𝑢𝑖 − ∑𝑛𝑗=1 utility𝑝𝑗 ) such that:

𝑚 ∑ 𝐴𝑖,𝑗 ≤ 𝑤𝑗 For each user device

𝑖=1 𝐴𝑖,𝑗 ∈ [0,1],∀𝑖 ∈ [1,𝑚],𝑗 ∈ [1,𝑛]

If the provider fails to complete the task within the alloted time, the task will be inserted back into the auction with a higher demand 𝑣𝑖.