We consider a general non-stochastic online pricing bandit setting in a procurement scenario where a buyer with a budget wants to procure items from a fixed set of sellers to maximize the buyer's reward by dynamically offering purchasing prices to the sellers, where the sellers' costs and values at each time period can change arbitrarily and the sellers determine whether to accept the offered prices to sell the items. This setting models online pricing scenarios of procuring resources or services in multi-agent systems. We first consider the offline setting when sellers' costs and values are known in advance and investigate the best fixed-price policy in hindsight. We show that it has a tight approximation guarantee with respect to the offline optimal solutions. In the general online setting, we propose an online pricing policy, Granularity-based Pricing (GAP), which exploits underlying side-information from the feedback graph when the budget is given as the input. We show that GAP achieves an upper bound of O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln B) on the alpha-regret where n, v_{max}, c_{min}, and B are the number, the maximum value, the minimum cost of sellers, and the budget, respectively. We then extend it to the unknown budget case by developing a variant of GAP, namely Doubling-GAP, and show its alpha-regret is at most O(n{v_{max}}{c_{min}}sqrt{B/c_{min}}ln2 B). We also provide an alpha-regret lower bound Omega(v_{max}sqrt{Bn/c_{min}}) of any online policy that is tight up to sub-linear terms. We conduct simulation experiments to show that the proposed policy outperforms the baseline algorithms.

Mobile crowdsourcing has emerged as a popular approach for organizations to leverage the collective intelligence of a crowd of users to obtain services. Considering users’ costs for providing services, it is vital for the requester to design incentive mechanisms to encourage users’ participation in crowdsourcing under the budget constraint. This aligns with the concept of budget-feasible mechanism design. Existing budget-feasible mechanisms often assume immediate user reachability and willingness of joining the crowdsourcing, which is unrealistic. To address this issue, a promising approach is to have participating users diffuse auction information to potential users in the social network. However, this brings another challenge in that participating users can be strategic and therefore hesitant to invite more potential competitors to join the crowdsourcing platform. In this paper, we focus on developing diffusion mechanisms that incentivize strategic users to actively diffuse auction information through the social network. This helps to attract more informed users and ultimately increases the value of the procured services. Specifically, we propose optimal budget-feasible diffusion mechanisms that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentive-compatibility (i.e., users report real costs and diffuse auction information to all their neighbors) and approximation. Experiment results under real datasets further demonstrate the efficiency of proposed mechanisms.

Information freshness, measured by the Age-of-Information (AoI) metric, is a crucial aspect of conventional network systems. However, the emergence of the Artificial Intelligence of Things (AIoT) introduces unique requirements for assessing information freshness, rendering the traditional AoI definition inadequate. This is because the traditional AoI metric operates under the presumption that each data packet bears equal significance. In contrast, AIoT systems must prioritize the transmission of event summaries from smart IoT devices. To promptly capture events as they occur at the sources, we propose a novel information freshness metric called Age of Event (AoE). Subsequently, we thoroughly investigate the problem of AoE-minimizing transmission scheduling. This issue presents a formidable challenge because the event occurrence pattern can be unpredictable, and more crucially, the base station only becomes aware of these occurrences post-transmission. In response, we formulate algorithms and conduct a theoretical analysis applicable to scenarios characterized by complete, zero, or partial knowledge of event occurrences. Evaluations performed on a real traffic event dataset reveal that even in the absence of complete knowledge, our algorithms exhibit competitive performance when compared against the clairvoyant benchmark and markedly outperform AoI baselines.

Metaverse has been viewed as the next generation of human-computer interaction, which requires collecting information from both the physical and virtual world. One potential way is to employ virtual service providers (VSPs) to finish collection tasks by designing posted-pricing mechanisms via the crowdsensing platform. As VSPs’ costs and values are usually unknown, learning the optimal posted-pricing policy under uncertainty is undoubtedly critical to utilize the budget efficiently. However, existing posted-pricing learning algorithms assume that agents provide services without blocking and agents’ attributes follow an independent identical distribution, both of which are unrealistic in Metaverse, e.g., VSPs should continuously sense the physical world to make provided services realistic, which makes the long working VSP unavailable/blocked for a certain period of time. In this paper, we address the budgeted pricing problem under uncertainty by considering blocking constraints and unknown non-identical VSPs’ attributes. The problem is modeled as a Budgeted-pricing Blocking Bandit (B2-bandit) problem, which remains unaddressed even for the oracle case with known VSPs’ information. We thus first propose a pricing policy for the oracle case with an instance-dependent approximation ratio to the global optimum. For the general B2-bandit problem with unknown information, we propose an online learning algorithm satisfying blocking constraints and incurring an accumulated regret up to$O(MK\log B)$as compared to the oracle approximation algorithm, where$M,K,B$are the number of VSPs, candidate prices and the budget, respectively. Experiments on real datasets validate that the proposed algorithm improves more than 172% accumulated value compared to baseline pricing algorithms.

In many IoT applications, information needs to be gathered from multiple heterogeneous sources to the base station for real-time processing and follow-up actions. Undoubtedly, information freshness, measured by age of information (AoI), is critical in taking responsive actions. Recent studies have taken AoI into the consideration of transmission scheduling over wireless channels. However, existing studies on guaranteeing AoI either assume error-free wireless channels or priorly known link reliability, which is unrealistic. In this paper, we tackle the AoI-guaranteed transmission scheduling problem over an unreliable channel with the aim of throughput maximization, which is modelled as an AoI-Guaranteed Multi-Armed Bandit (AG-MAB) problem. Since the problem has not been studied in the literature even for the oracle case with given link reliability, we first propose an optimal stationary randomized sampling (SRS) policy for the oracle case. For the AG-MAB problem with unknown link reliability, we propose learning algorithms that meet the AoI requirements with probability 1 and incur sublinear regret compared to Oracle SRS, which can also detect the unsatisfiability of the AoI constraint and switch to the fallback policy promptly with guaranteed accuracy. Numerical results show that our algorithm outperforms the AoI-constraint-aware baselines on throughput with per-source AoI requirement guaranteed.

Unmanned Aerial Vehicle (UAV) swarm offers extended coverage and is a vital solution for many applications. A key issue in UAV swarm control is to cover all targets while maintaining connectivity among UAVs, referred to as a multi-target coverage problem. With existing dynamic routing protocols, the flying ad hoc network suffers outdated and incorrect route information due to frequent topology changes. This might lead to failures of time-critical tasks. One mitigation solution is to keep the physical topology unchanged, thus maintaining a fixed communication topology and enabling static routing. However, keeping physical topology unchanged may sacrifice the coverage. In this article, we propose to maintain a fixed communication topology among UAVs, which allows certain changes in physical topology, so that to maximize the coverage. We develop a distributed motion planning algorithm for the online multi-target coverage problem with the constraint of keeping communication topology intact. As the communication topology needs to be timely updated when UAVs leave or arrive at the swarm, we further design a topology-management protocol. Experimental results from the ns-3 simulator show that under our algorithms, UAV swarms of different sizes achieve significantly improved delay and loss ratio, efficient coverage, and rapid topology update.

In a crowdsensing platform, users are invited to provide data services, and multiple requesters compete for desired services. Due to users' costs of providing services, it is critical to design incentive mechanisms to incentivize users with (monetary) rewards. Meanwhile, requesters may have individual budgets and compete for services with different procurement abilities. Such a setting falls into the budget-feasible mechanism design. However, most of the existing budget-feasible mechanisms focus on one-sided markets with a single requester rather than the two-sided markets with multiple requesters having different procurement abilities. Moreover, requesters and users can be selfish and strategic with their private information, which requires preventing information manipulation on both requesters' and users' sides. In this paper, we investigate budget-feasible mechanisms in two-sided crowdsensing markets where multiple strategic requesters come with private budgets to obtain services from the strategic users. We also consider the fairness on the requesters' side,i.e., a requester with more budget should obtain more service. We propose budget-feasible mechanisms for two models by distinguishing the types of services,i.e., the homogeneous or heterogeneous services. All proposed mechanisms satisfy fairness, budget feasibility, truthfulness on both users' and requesters' sides, and the constant approximation ratio. Numerical experiment results further demonstrate the efficiency of our proposed mechanisms.

Ride-hailing systems (RHSs) provide passengers with convenient and flexible mobility services, have played an important role in modern urban transportation. With the limited vehicles, RHSs wish to optimize the dispatch of vehicles to requests with the objective of serving as many requests as possible. To address such a city-scale vehicle dispatch problem with thousands of vehicles and requests in each epoch, existing algorithms always take a tradeoff between effectiveness (i.e., real-time) and efficiency (i.e., service rate), such as ignoring future demands to guarantee real-time or solving a complex combinatorial optimization to improve service rate. To guarantee the service rate in a real-time fashion, this paper proposes two novel network flow-based vehicle dispatch algorithms. A network flow-based algorithm (NFBA) is provided to deal with offline scenarios. By constructing the vehicle-shareability network, a min-cost flow is built to find the optimal dispatch of vehicles to requests. To improve the request service rate in real-time, an efficient multi-sample multi-network flow-based algorithm (MNFBA) is proposed for the online scenarios. Each min-cost flow is utilized for a sample of future requests, and online vehicle dispatch policy is averaged over these flows. Extensive simulations based on real-world trip datasets in New York City are conducted. The experimental results show that compared to the benchmarks, our proposed algorithm can generate the dispatch of vehicles to requests within seconds, but can greatly increase the daily request service rate.

This paper studies the budget-feasible mechanism design over graphs, where a buyer wishes to procure items from sellers, and all participants (the buyer and sellers) can only directly interact with their neighbors during the auction campaign. The problem for the buyer is to use the limited budget to incentivize sellers to propagate auction information to their neighbors, thereby more sellers will be informed of the auction and more item value will be procured. An impossibility result shows that the large-market assumption is necessary. We propose efficient budget-feasible diffusion mechanisms for large markets that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentive-compatibility to report private costs and diffuse auction information. Moreover, the proposed mechanisms achieve logarithmic approximation that the total procured value is within a logarithmic factor of the optimal solution. Compared to most related budget-feasible mechanisms, which do not take the individual interactions among sellers into account, our mechanisms can incentivize sellers to further propagate auction information to other potential sellers. Meanwhile, existing related diffusion mechanisms only focus on seller-centric auctions and fail to satisfy the budget-feasibility of the buyer.

In this paper, we consider the problem of designing budget-feasible mechanisms for selecting agents with private costs from various groups to ensure proportional representation, where the minimum proportion of the selected agents from each group is maximized. Depending on agents' membership in the groups, we consider two main models: single group setting where each agent belongs to only one group, and multiple group setting where each agent may belong to multiple groups. We propose novel budget-feasible proportion-representative mechanisms for these models, which can select representative agents from different groups. The proposed mechanisms guarantee theoretical properties of individual rationality, budget-feasibility, truthfulness, and approximation performance on proportional representation.

This paper considers the mechanism design problem in two-sided markets where multiple strategic buyers come with budgets to procure as much value of items as possible from the strategic sellers. Each seller holds an item with public value and is allowed to bid its private cost. Buyers could claim their budgets, not necessarily the true ones. The goal is to seek budget-feasible mechanisms that ensure sellers are rewarded enough payment and buyers' budgets are not exceeded. Our main contribution is a random mechanism that guarantees various desired theoretical guarantees like the budget feasibility, the truthfulness on the sellers' side and the buyers' side simultaneously, and constant approximation to the optimal total procured value of buyers.