Algorithm

We present a polynomial time combinatorial algorithm for Equation 1, which is NP-Hard.

Following Zhai et. al. (2018) and Jiang et. al. (2021), our scheduling mechanism invokes a bid

density (𝑏𝑑) mechanism to push bids for efficient allocations. Let 𝑀𝑖 represent the compute

power of 𝑅𝑖, which will be determined by benchmarking. Let 𝚿 be a constant representing the

ability for a service provider to complete a task determined by an algorithm that considers GPU

compute power, CPU compute power, etc. and let 𝑀 , π‘π‘‘π‘‘π‘Žπ‘ π‘˜, and π‘π‘‘π‘π‘Ÿπ‘œπ‘£π‘–π‘‘π‘’π‘Ÿ be defined as: 𝑖𝑖𝑖

√ π‘˜ π‘π‘‘π‘‘π‘Žπ‘ π‘˜=βˆšβˆ‘πΆ2 +𝑣2

𝑖 𝑖,𝑗𝑖 ⎷ 𝑗=1

π‘π‘Ÿπ‘œπ‘£π‘–π‘‘π‘’π‘Ÿ √ π‘˜ 𝑗 𝑏𝑑𝑖 = βˆ‘1/𝑠2𝑖,𝑗+βˆ‘Ξ¨π‘–,𝑗

⎷ 𝑗=1 𝑗=1 Setting the bidding density for service providers in this manner heavily incentivize providers

that are able to run WebGPU inference on relatively large models such as Llama and SDXL.

The main combinatorial double auction resource allocation algorithm is presented below. As mentioned earlier, this auction mechanism is utilized to determine fair prices for users and service providers. An important qualification is that only users are able to influence the auction by increasing 𝑣𝑖 through bidding more token, which increases the bidding density. However, providers themselves are not able to set the price of their own bid. Instead, it is computed within the platform and a fair price is assigned to the provider.

Prices(𝑁tasks, 𝑁providers, 𝐡providers, 𝐡tasks):

  1. Users and service providers send their bids to the auctioneer.

  2. Compute a sorted list of bids of tasks and providers

  3. Normalize components of 𝚿 and normalize 𝒔 ∈ 𝑀(R),𝐢 and

    𝑣 to be in the range (0, 1)

  4. 𝐺 ← βŸ¨π‘π‘‘π‘‘π‘Žπ‘ π‘˜βŸ© sorted in non-increasing order 𝐻 ← βŸ¨π‘π‘‘π‘π‘Ÿπ‘œπ‘£π‘–π‘‘π‘’π‘ŸβŸ© sorted in non-increasing order

  5. 𝑖=𝑗←1

  6. Flag Price:

  7. π‘˜β†1

  8. 𝑋 ∈ π‘€π‘š,𝑛(𝟘)

  9. 𝑃 ∈ π‘€π‘š,𝑛(𝟘)

  10. if(𝐢=0)∨(𝑣𝑖<π‘žπ‘–):

  11. π‘˜ += 1

  12. 𝑋[𝑖,𝑗]=π‘žπ‘–

  13. 𝑃[𝑖,𝑗]=(Pr(providerperunit)𝑗+Pr(taskperunit)𝑖)/2

  14. if Β¬(Pr(provider per unit)𝑗 ≀ 𝑃[𝑖,𝑗] ≀ Pr(task per unit)𝑖):

  15. 𝑃 [𝑖, 𝑗] = Pr(provider per unit)𝑗

  16. π‘£π‘–β†π‘£π‘–βˆ’π‘žπ‘–

  17. π‘žπ‘–β†0

  18. If all of the requests of a single user are not satisfied

  19. 𝑗 += 1

  20. GOTO Price

  21. If all of the requests of a single user are satisfied:

  22. Task trade price𝑖 = βˆ‘π‘›π‘š=1 𝑃𝑖,π‘š βˆ— 𝒔𝒋 βˆ— π΄π‘˜,𝑗

  23. Device trade price𝑗 = βˆ‘π‘›π‘›=1 𝑃𝑛,𝑗 βˆ— 𝒔𝒋 βˆ— 𝐴𝑛,𝑗

  24. 𝑖 += 1

  25. GOTO Price

  26. If all user requests are satisfied:

  27. return Task trade price, Device trade price

PreviousPricing ModelNextSlashing Mechanism

Last updated