EDGE AI inference [1] entails deploying machine learning models upon devices at the network edge closer to the end users, substantially reducing response time and bandwidth consumption and safeguarding data privacy [2]. As a service, edge AI inference is adopted in a range of applications, such as virtual reality [3], healthcare [4], and autonomous vehicles [5]. For example, in virtual reality, the inference service receives the end users’ inference requests such as gestures and voices and provides inference results promptly.

Unfortunately, many edge AI services do not actually have sufficient and satisfying edge devices for deploying edge AI inference. Although today’s cloud computing vendors also provide “pay-as-you-go” edge computing services [6], they could still be costly, especially for small-scale edge AI businesses. For instance, Amazon CloudFront has the computation price 6 times higher than its EC2 [7]. Besides, such existing edge infrastructures, distributed though, often reside at pre-specified fixed locations, and may still be unable to sufficiently reach the target group of end users in particular geographic locations at a finer granularity. More importantly, current commercial edge provisioning focuses on edge servers only; yet, an edge device does not actually have to be an edge server, and it can be a smart router [8], a home NAS [9], and a personal computer, e.g., the “AI PC” [10]. Ideally, it could be better if any of such edge devices at any location could be potentially and appropriately employed and released as needed by the edge AI service.

Moving toward this direction, what is needed here is an incentive mechanism to incentivize the edge device owners to contribute their edge devices or idle resources on such edge devices to the edge AI service. Auction can serve as such an incentive mechanism, as shown in Fig. 1. The edge AI inference service can act as the auctioneer and conduct auctions to procure edge resources as bids from the edge devices that can act as the bidders. Auction has many advantages indeed, including reducing the chance of mis-pricing, matching the demand with the supply better, and capturing the market dynamics in real time [11], [12].

However, it is non-trivial to design auction-based mechanisms to continuously operate and orchestrate the edge AI inference service with desired service quality at minimum cost upon dynamically-recruited edge resources, while keeping the edge devices incentivized to contribute such resources. We identify three unique and fundamental challenges as follows, also highlighted in Fig. 2.

Cost versus Accuracy under System Dynamics: Given the often limited edge capacity, we need to carefully choose between high-accuracy models which can consume excessive edge resources and low-accuracy models which can save resources but have less satisfying service quality. What complicates this is that the inference accuracy is posterior—we only observe the accuracy (or the error rate) of a model upon users’ inference queries after we actually deploy and use this model to serve those queries. When making model deployment decisions, as the actual queries have not been served yet, we have no knowledge about the model’s performance on those queries. The difficulty further escalates because meanwhile we need to (i) dispatch users’ queries to different edge devices under time-varying network conditions at minimum communication cost, and (ii) maintain and eventually clear the query queue on each edge device given models’ diverse execution speeds on different devices.

Dependency between Adjacent Auctions: The auctions are not a one-time transaction, but are often repetitive as we continuously recruit edge resources; yet, each auction cannot just work independently. An edge device that was a winning bid in the last auction but does not win in the current auction may revoke its resources, shut down, or leave the system; if it joins again in the next auction and is selected to win, then it can incur “switching cost”, because the inference service needs to re-authorize the device, re-initialize its execution environment, and re-deploy the model(s), causing leading time and effort. To mitigate such switching cost, ideally, we should choose a winning bid in one auction by cautiously expecting whether this bid could also win in the next auction; yet, this is pretty hard if ever possible, because the next auction has not occurred yet and the inputs then could all change as it happens [1], [13].

Economic Properties of Each Auction: Even for a single auction in our scenario, it is still non-trivial to design and solve. Choosing winning bids requires to not only balance cost and accuracy but also attain the desired economic properties such as truthfulness and individual rationality [11], [14]. Truthfulness ensures that every bid maximizes its utility by bidding the price that reflects the bidder’s true valuation (i.e., no motivation to lie about the bidding price), and individual rationality ensures that every bid always has non-negative utility regardless of the auction outcome (i.e., voluntary auction participation). The well-known Vickrey-Clarke-Groves (VCG) mechanisms [15] can achieve such economic properties. However, original VCG requires to exactly solve the underlying optimization problem, but our problem, due to the complexities and integer decisions, is intractable as will be shown; fractional VCG [16] is also inapplicable, due to the existence of the extra terms of the edge AI inference overhead and accuracy in each auction.

Existing studies fall short to effectively tackle the aforementioned challenges. Many works [1], [13], [17], [18], [19] on edge AI inference systems often assume abundant resources without dynamically adding or removing resources through economic means, unable to meet the needs of our scenario. Other works [11], [12], [20], [21], [22], [23] on incentive mechanisms at the network edge typically do not consider AI inference, or ignore the unique features and challenges of edge AI inference as we highlight above, thus inapplicable to our scenario. See Section VI for detailed discussions.

In this paper, we overcome all the aforementioned challenges via a mathematical and algorithmic study with solid theoretical analysis. We make multiple contributions:

First, we model and formulate a time-cumulative social cost optimization problem, which minimizes the sum of the edge AI service’s cost, the edge devices’ cost, and the inference error rate, subject to resource capacity and inference query queue dynamics. The control decisions include winning-bid selection, model placement, query dispatch, and payments to bids in each auction at each corresponding time slot. This problem is a non-linear integer program, unsurprisingly NP-hard, but is general enough with almost zero assumption on the input dynamics and heterogeneities.

Second, to enable the edge AI service to solve this problem to provision the inference service while procuring the resources, we propose four novel polynomial-time online algorithms that can work jointly. We decouple our original problem into two sub-problems based on the bid-switching cost. We design our overall online optimization algorithm to dynamically balance the switching cost and all the rest of the cost terms by only triggering a new switch operation when the accumulated other costs exceed a pre-specified parameter times the switching cost of the last switch operation. To that end, we invoke our second algorithm, which is based on online learning, to address the posterior inference accuracy and the query queue state transitions for each auction. During this process, we also invoke our third algorithm which adopts randomization to convert all our fractional control decisions into integers without violating any constraints at each time slot. Via our fractional and integral bid-selection decisions, our fourth algorithm calculates payments in each auction using the real bidding prices and the conceived alternative bidding prices of the winning bids.

Third, we rigorously prove the multiple worst-case performance guarantees associated with our algorithms. Overall, our combined algorithmic approach achieves a constant competitive ratio, i.e., the social cost incurred by our online approach (which observes the inputs gradually) is upper-bounded by this constant times the social cost in the offline optimal situation (which observes all inputs in hindsight at once). For our online learning component that addresses all the non-switching costs, we achieve sub-linear regret and fit, i.e., as time goes, the time-averaged difference between those costs incurred by our approach and those incurred in the series of one-shot optimums vanishes, and the time-averaged violation of the long-term constraints also vanishes. Our payment allocation component meets the sufficient and necessary conditions for truthfulness and individual rationality in randomized auctions, and thus achieves these economic properties simultaneously.

Fourth, we build a testbed with real hardware, adopt real AI models, and compare our approach to a variety of other methods driven by real traces (e.g., edge device locations, workload variations) for various performance metrics. We briefly summarize our observations: (i) Our approach saves social cost in real time, reducing social cost by 55%∼70% cumulatively compared to baselines and by 30%∼49% cumulatively compared to state-of-the-arts; (ii) Our approach scales well with inputs and consistently outperforms others; (iii) Our online learning component has the lowest regret, achieving sub-linear growth in both regret and fit; (iv) Our approach achieves truthfulness and individual rationality in practice; (v) Our algorithms run fast and finish in tens of milliseconds, except the payment allocation which could consume seconds, acceptable per 15-minute-long time slot.

The rest of this paper is structured as follows. Section II models and formulates the social cost optimization problem. Section III proposes and designs our algorithms to solve this problem online. Section IV analyzes and proves the theoretical performance guarantees of our algorithms. Section V validates the practical performance of our algorithms via testbed-based experiments. Section VI summarizes the existing research. Section VII discusses some related issues in this work. Section VIII concludes.

Today’s user-owned edge hardware already supports the deployment of edge AI inference and also has the idle capacity for it. These edge devices just need to be incentivized to participate in edge AI inference, which motivates our study.

Our notations are summarized in Table I.

The edge AI inference system under our consideration is mainly composed of three entities. First, the inference service is operated and managed by a service provider, who wants to leverage the edge devices to deploy its AI models and run the inference service on such edge devices to serve the end users’ inference queries. We use the set M = {1,2,...,M} to denote the AI models of the inference service. Second, the edge devices are owned by the corresponding device owners, respectively, and have available resources that can be used by the edge AI inference service. Such edge devices are often distributed at diverse locations in close proximity to the end users, and can include edge servers, desktops, and mobile devices. We use the set N = {1,2,...,N} to denote all the edge devices. Third, the end users submit inference queries to the edge AI inference service, which will be processed on the edge devices, and receive the inference results. We consider the entire system operating over consecutive time slots, denoted by the set T = {1,2,...,T}.

At each time slot, the edge AI inference service acts as the auctioneer and conducts an auction with the edge devices that act as the bidders. Without loss of generality, we consider each edge device submitting one bid in each auction. If an edge device does not submit a bid in an auction, we equivalently treat it as submitting a “virtual bid” with the positive infinity bidding price, and thus this virtual bid will never be chosen as a winning bid.

The auction at any time slot t ∈ T has multiple steps, as depicted in Fig. 3. First, the inference service solicits bids, and each edge device submits a bid in the format of B_{n,t} = {b_{n,t},c_n,β_n}, n ∈ N, where b_{n,t} represents the bidding price, i.e., the amount of money that the edge device n wants to charge for the inference service’s usage of the resources on this edge device during the time slot t; c_n denotes the available resource capacity, e.g., total number of available processors (or processor cores) on the edge device n; and β_n is the processing speed per processor (or per processor core) on the edge device n. Here, processor types and speeds may vary across devices, but we only consider homogeneous processors (or cores) on a given device; our work in this paper can be easily extended to the heterogeneous case. Second, after receiving all the bids, the inference service determines the winning bids while also calculating the payment to each winning bid. Note that the payment to a winning bid may not be necessarily equal to the bidding price of the bid. Part of our goal in this paper is to design algorithms to decide the winning bids and the payments. Third, based on the auction outcome, the inference service sends selected AI models to the corresponding edge devices, dispatches the users’ inference queries to those edge devices, uses the models to process the queries, and returns the inference results to the users. Fourth, the inference service makes payments to the edge devices. Depending on the reached agreement between the auctioneer and the bidders, the third step may occur before or after the fourth step.

We consider multiple control decisions for the inference service at each time slot: x_{n,t} ∈ {1,0} indicates whether or not the inference service chooses the edge device (or the bid) n as a winner in the auction at the time slot t; y_{n,m,t} ∈ {1,0} indicates whether or not the inference service selects and deploys the model m on the edge device n at the time slot t; z_{n,m,t} ∈ Z+ indicates the number of inference queries that the inference service distributes to the model m on the edge device n for processing at the time slot t; and w_{n,t} ≥ 0 indicates the payment that the inference service makes to the edge device n at the time slot t.

At each time slot t, the cost incurred at the inference service consists of multiple components. First, the service makes payments to the winning bids as Σ_n x_{n,t}w_{n,t}. Second, the service dispatches models to each edge device, which incurs the communication cost, denoted as Σ_nΣ_m e_{n,m,t} y_{n,m,t}δ_{n,m,t}. Here, e_{n,m,t} can represent the transmission time or traffic volume for sending the model m to the edge device n at the time slot t. δ_{n,m,t} is a binary indicator that captures whether or not the model m actually needs to be sent to the edge device n at the time slot t. If it is needed, then δ_{n,m,t}=1; if not, δ_{n,m,t}=0. The model may not be needed if this same model has already been on the edge device due to previous auctions; the model could be needed, because the model itself may be updated by the inference service, or the edge device may have deleted the model due to not winning a previous auction. Third, the service dispatches inference queries to each model on each edge device for processing, which also incurs the communication cost, denoted as Σ_nΣ_m d_{n,t}z_{n,m,t}. Here, d_{n,t} can represent the transmission time or traffic volume for sending a single inference query to the edge device n at the time slot t. Consequently, the total cost of the inference service over time is Σ_t(Σ_n x_{n,t}w_{n,t}+Σ_nΣ_m(e_{n,m,t}y_{n,m,t}δ_{n,m,t}+d_{n,t}z_{n,m,t})).

At each time slot t, the cost incurred on each edge device n also consists of multiple components. First, the bidding cost x_{n,t}b_{n,t}, which can be determined by the edge device’s operational cost such as electricity consumption at the time slot t, amortized hardware expense per time slot, etc. Second, the payment received from the inference service, which is treated as negative cost, i.e., −x_{n,t}w_{n,t}. The third is the “switching cost”. When the inference service did not choose an edge device as a winner in the previous auction at t−1 but chooses this edge device as a winner in the current auction at t, then the inference service may need to re-connect to and re-authorize the edge device; and the edge device may also need to re-initialize the execution environment, re-prepare the resources, or even re-start the device. Such operations can take the leading time, considered as a type of cost that we call the switching cost. We use Σ_n l_n[x_{n,t}−x_{n,t−1}]+ to denote the switching cost, where [·]+ ≜ max{·,0}, and l_n is such leading or startup time of the edge device n. Consequently, the total cost of the edge devices over time is Σ_tΣ_n(x_{n,t}(b_{n,t}−w_{n,t})+l_n[x_{n,t}−x_{n,t−1}]+).

If we use Υ_{n,m,t} to represent the accuracy of the model m on the edge n at the time slot t, then we can define the error rate correspondingly as a_{n,m,t}=1−Υ_{n,m,t}. That is, the lower the error rate is, the better the service quality the inference service provides. The error rate depends on the specific model chosen and the specific inference queries that are resolved by this model [29]. A model may also have different versions with different error rates, which can be essentially treated as different models. The total error rate of the inference of all models on all edge devices over time is Σ_tΣ_nΣ_m a_{n,m,t}y_{n,m,t}. Note that a_{n,m,t} is posterior, i.e., it is only observed by the inference service after deploying the model m on the edge n and using this model to resolve inference queries there at the time slot t, no matter what value it is. As the inference queries from the end users could vary as time goes, the error rate of a given model could thus also vary.

First, on each edge n, the AI models deployed there must respect the resource capacity of the edge:

Second, each edge device n maintains a queue formed by the inference queries and the queue dynamics needs to be correctly reflected:

Third, all the inference queries submitted to the inference service at the time slot t, i.e., τ_t, need to be fully dispatched to all the AI models on all the edge devices:

We minimize the social cost over time, i.e., the sum of the total cost of the inference service, the total cost of the edge devices, and the total error rate of the inference over time, subject to Constraints (1)–(3). Yet, solving this optimization problem as is in an online manner is particularly challenging, if ever possible. First, some inputs cannot be observed in time and can only be revealed after making the decisions, e.g., the error rate a_{n,m,t}, and/or the transmission time e_{n,m,t} and d_{n,t}. Making control decisions obliviously without observing the inputs is intrinsically difficult. Second, the state-transition constraint based on the non-linear operator [·]+ couples every pair of adjacent time slots. It is non-trivial to enforce such queue dynamics on the fly while eventually clearing the queue.

We thus reformulate our problem as follows, and treat this reformulated problem as our original problem P. In this reformulation, we selectively relax the “instantaneous” Constraints (2)–(3) to the “long-term” Constraints C2∼C4. That is, rather than enforcing the instantaneous constraint at every time slot, now we only enforce such constraints cumulatively in the long run.

In the above, the optimization objective is to minimize the social cost. Aligned with existing typical social cost optimization, the payments are cancelled in the social cost; yet, we still need to calculate the payments as part of our auction outcome in each time slot. Such cancellation is a common practice in lots of existing auction-related research. Yet, this does not imply that w_{n,t} is independent of other decision variables.

Solving the relaxed problem P as above in an online manner is still challenging. First, the switching cost that couples adjacent time slots still exists in the objective, so no matter what the bid-selection decision is made currently, it will impact the switching cost between the current time slot and the next time slot where the bid-selection decision for the next time slot is yet unknown currently. Second, the long-term constraints, supposed to be easier than instantaneous constraints though, also need to be carefully handled and enforced on the fly and due to uncertain future conditions and posterior observed inputs. Third, the integer decision variables make our problem an integer program, which is typically NP-hard [30], even in the offline setting. Fourth, we need to determine the payment for each winning bid in each auction, which often depends on the bidding prices and the auction outcome, in order to satisfy the desired economic properties such as truthfulness and individual rationality as elaborated later.

Algorithm 1 is our main online control algorithm, which invokes Algorithms 2 and 3 for bid selection, model deployment, and query dispatch and invokes Algorithm 4 for payment allocation. This is shown in Fig. 4. These four algorithms are elaborated in Sections III-A–III-D, respectively.

Our proposed algorithms compose a combination that utilizes and unifies different ideas in a common framework of handling NP-hardness in polynomial time in repetitive online auctions with switching cost and long-term constraints, while being able to provide provable overall performance guarantees.

We decouple Problem P into two sub-problems, i.e., Problem P1 and Problem P2, based on the switching cost.

Having these, Problem P1 and Problem P2 are as follows. Note that, compared to P1, the decision variables are only y and z in P2; and x-bar, produced by our algorithms, is given as input in P2.

Algorithm 1 uses the pre-specified parameter eta > 0 to balance the switching cost and the non-switching cost. If cumulative non-switching cost since the last switch exceeds 1/eta times that switch's cost, it uses newly computed decisions.

The way eta is used forces that between adjacent switch operations the previous switching cost is no greater than eta times the non-switching cost accumulated; intuitively, this guarantees the total cost is no greater than 1+eta times the non-switching cost. This “wait and delay” idea is passive or reactive, rather than proactive, and enables the algorithm to overcome the dependency between bid selections in adjacent auctions.

Both P1 and P2 have a per-time-slot objective, instantaneous constraints, and long-term constraints. The long-term constraints can be moved into a Lagrangian with multipliers, then primal and dual variables are updated online.

Algorithm 2: Set omega_t=[omega_{t-1}+mu g_{t-1}(X_{t-1})]^+. Then solve argmin over X in X: grad f_{t-1}(X_{t-1})(X-X_{t-1}) + omega_t g_{t-1}(X) + ||X-X_{t-1}||^2/(2 alpha), subject to h_{t-1}(X)<=0. Observe f_t,g_t,h_t for use at t+1.

The regularization term makes this a modified gradient-descent step. The per-time-slot problem is a standard convex optimization problem and can be solved with a standard convex solver. The long-term constraint is absorbed into the objective, leaving only instantaneous constraints; no input beyond the current time slot is used.

Algorithm 3 rounds fractional decisions into integers. For z and x, fractional parts are used as probabilities so that their expectations equal the fractional solutions. For y, a double randomization preserves the instantaneous computing-capacity constraint, the expectation, and eventually the long-term violation bounds.

The dependent rounding for y does not violate the instantaneous capacity constraint and preserves E[y-bar]=y-tilde. The simple randomized rounding for z and x also preserves expectations. Randomization permits bounded long-term constraint violations but no instantaneous violations.

For a winning bid n, w_{n,t}=b_{n,t} tilde{x}_{n,t}(b_{n,t},b_{-n,t})+ integral from b_{n,t} to bar omega_t of tilde{x}_{n,t}(b,b_{-n,t}) db. A losing bid receives zero.

The payment rule follows necessary and sufficient conditions for truthfulness and individual rationality in randomized auctions. It is possible because the expected allocation equals the fractional allocation.

The paper analyzes (i) regret and fit, (ii) competitive ratio, and (iii) truthfulness and individual rationality. Regret and fit refer to P2; competitive ratio and economic properties refer to the holistic problem P.

The authors evaluate the proposed approach with testbed measurements and existing data, comparing it with baseline and state-of-the-art approaches.

The real-world testbed includes GeForce RTX 2080Ti, RTX 3090, Tesla V100, Huawei Atlas 200DK, and Nvidia Jetson NX. Models are YOLOv4, DeepLabv3, BERT, VGG16, and Inceptionv3.

The default London workload uses passenger counts from 268 underground stations at 15-minute intervals over four days in November 2016, giving about 300 slots. Other workloads are IRSMSetting, MTA, and Shanghai Telecom.

OAA reduces average social cost by about 50% overall, 65% compared with heuristics, and 40% compared with IRSM and TARFO. Its practical competitive ratio is 1.6–3.9, mostly 1.6–3.

Regret and fit are sub-linear. As the step size changes from T^-1/2.5 to T^-1/3, fit decreases 15%–25% and regret grows 10%–15%.

Across London, IRSMSetting, MTA, and Telecom, OAA reduces cost by 63%, 38%, 27%, and 10%. Its selected models' average error is 8%–24% lower than competitors.

OAA and its OLA/RRA components run in tens of milliseconds. OPA averages around 10 seconds and can execute before the 15-minute slot ends.

Prior work studies adaptive DNN inference, online batch selection, multi-exit networks and offloading, online learning for dynamic edge environments, DAG-based DNN partitioning, and sensing-computation-communication co-optimization.

Prior incentive work covers truthful resource allocation, dynamic offloading under energy constraints, auction-based ML job pricing and scheduling, federated learning incentives, provider profit versus mobile QoE, and two-stage D2D relay auctions.

Table III contrasts prior work across problem space, solution properties, evaluation, and year. The paper argues existing inference work often assumes abundant resources or ignores their cost, while incentive work rarely targets edge AI's specific inference accuracy and service challenges.

Each time slot has one auction. The model assumes a participating bidder stays connected and committed during that auction. A bidder that leaves before the outcome could be excluded from later auctions for credibility reasons.

The model permits arbitrary participation and repeated bidding across auctions without penalties. Winning after a period of absence or losing may incur switching cost, which is already included in the social-cost model.

The authors do not use DRL because the problem has an explicit mathematical model, DRL may lack rigorous guarantees, and it often requires substantial training and cold-start overhead. Their online algorithms make decisions directly without training.

This work enables edge AI inference services to recruit diverse edge resources dynamically through repeated auctions, jointly controlling winning bids, model deployment, query dispatch, and payment, with theoretical analysis and experiments. Future work will study edge AI training with resource trading.