DAG-based blockchains face the key challenge of transaction inclusion collision due to the high concurrency and network delay. In this paper, we propose “We-TIPS”, a weak-block-based transaction inclusion protocol with signaling, designed to tackle this key challenge. In We-TIPS, during the mining process, the miner can broadcast the weak block header as a signal, which can indicate the miner’s current transaction inclusion. With the prompt broadcast of the signal, the miner can effectively avoid the transaction inclusion collision and thus greatly boost the system performance. Besides, we develop a transaction inclusion game in We-TIPS to model miners’ interaction and show that it is a potential game. We propose a decentralized transaction inclusion algorithm that can achieve the approximate Nash equilibrium. Finally, we conduct intensive experiments to demonstrate the superior performance of We-TIPS.

Two-sided matching is a foundational topic that traditionally assumes participants have perfect knowledge of their pReferences. However, in practice, many participants lack precise information about potential matches. The competing bandits model, based on the multi-armed bandit framework, addresses this uncertainty by enabling participants to learn through interactions. While most existing research has focused on one-to-one matching, real-world scenarios—such as resource allocation in wireless networks—often involve cases in which a single resource can accommodate multiple participants, making it essential to adapt the framework to better reflect practical applications. In this paper, we extend the analysis to many-to-one matching. To enhance practical relevance and reduce restrictive assumptions, we introduce four key properties: full decentralization, accommodation of arbitrary and private preferences, absence of winner observation, and regret minimization with respect to the optimal stable matching. These properties introduce challenges such as severe information scarcity and complex preference structures. To address the issue of limited information, we propose techniques such as random pulls and specialized communication protocols to facilitate information gathering by agents. We further conduct a detailed analysis of complex preference structures and identify a critical property that underpins the development of our algorithm, SUBMARINE. Our proposed algorithm achieves logarithmic regret, representing a notable advancement: it is the first to satisfy all the outlined properties while attaining the lowest known regret bound.

Recently, there has been a focus on the streaming setting in a line of works on the Multi-Armed Bandit (MAB). In this scenario, a large number of arms arrive in a streaming manner, and the algorithm scans through the stream and stores some arms in its limited processing memory. We advance this line of research by introducing the Linear Streaming Bandit setup, where the arriving arms have profile vectors observable to the algorithm. The profile of an arm has a linear correlation with the expected reward. This setup is motivated by real-world applications, such as when a company or a crowdsourcing platform hires a worker from many sequentially arriving applicants with their resumes. We address two problems in this setup: Regret Minimization and Fixed-Budget Epsilon-Best Arm Identification. For the former, we propose an algorithm whose regret is independent of the number of arms, thus it is able to handle arbitrarily long arm streams. For the latter, we present a multi-pass algorithm whose error probability is sub-linear w.r.t. the number of arms, and an algorithm identifying the exact best arm in only a single pass. We validate the effectiveness of all proposed algorithms through experiments on both synthetic and real-world datasets.

With the continuous advancement in the performance of open-source large language models (LLMs), their inference services have attracted a substantial user base by offering quality comparable to closed-source models at a significantly lower cost.However, it has also given rise to trust issues regarding model consistency between users and third-party service providers.Specifically, service providers can effortlessly degrade a model's parameter scale or precision for more margin profits, and although users may perceptibly experience differences in text quality, they often lack a reliable method for concrete monitoring.To address this problem, we propose a paradigm for model consistency monitoring on the user side.It constructs metrics based on the logits produced by LLMs to differentiate sequences generated by degraded models.Furthermore, by leveraging model offloading techniques, we demonstrate that the proposed method is implementable on consumer-grade devices.Metric evaluations conducted on three widely used LLMs series (OPT, Llama 3.1 and Qwen 2.5) along with system prototype efficiency tests on a consumer device (RTX 3080 TI) confirm both the effectiveness and feasibility of the proposed approach.

We study the multi-armed bandits with auxiliary rewards problem, in which pulling an arm yields not only a primary reward but also a set of auxiliary rewards, which represents some low-quality data. The auxiliary reward distribution can be biased and have higher variances than the primary reward distribution. We analyze the regret lower bound with general-order cumulative volume function, and deduce the conditions under which an algorithm can outperform the classical optimal regret bound without auxiliary rewards, attained by the state-of-the-art (SOTA) algorithm Asymptotically-Optimal-UCB (AO-UCB). Then we propose the BVA-MIN-UCB algorithm, which carefully incorporates the primary and auxiliary rewards by adjusting the potential biases and different variances. We show that BVA-MIN-UCB always performs no worse than AO-UCB asymptotically, and nearly matches the regret lower bound, even up to a constant factor. Finally, we conduct numerical experiments to demonstrate the effectiveness of our algorithm.

We revisit the concept of order fairness in blockchain systems. Order fairness imposes additional constraints on the actual order of the transactions, preventing adversaries from manipulating the order of transactions to gain undue advantages. While numerous notions of fairness and corresponding fair ordering protocols have been proposed, these efforts typically focus on designing a dedicated protocol tailored to each specific fairness notion. Consequently, it remains unclear whether multiple fairness notions can be realized simultaneously within a single framework. In this work, we propose “2-hop receiver fairness”, a new and unified fairness notion that simultaneously captures approximate sender fairness, block order fairness, and consequence transaction fairness. To achieve 2-hop receiver fairness, we propose TxSort, a generic framework that reduces the fair ordering problem to the asynchronous common subset (ACS), an extensively studied primitive for asynchronous consensus and multiparty computation. In this way, we can integrate the state-of-theart ACS protocols to provide a communication-efficient and round-optimal fair ordering protocol. Specifically, our protocol achieves an amortized communication complexity per transaction (CCpT) of$O\left(n^{2}\right)$, while existing state-of-the-art fair ordering protocols achieve$O\left(n^{3}\right)$CCpT. As a crucial building block of our framework, we introduce a novel and computation-efficient local algorithm called “pivot quick sort”, which might be of independent interest.

Empowered by blockchain technology, smart contracts have attracted considerable interest from Web3 users due to their distinct advantages. Nevertheless, it is challenging to address problems caused by the dramatic expansion of the Web3 ecosystem. This article introduces the smart contract-as-a-service (SCaaS) paradigm to mitigate smart contracts’ redundant deployment via their composability and reusability. Moreover, we design trust and incentive schemes to ensure project security and developer engagement in SCaaS. Specifically, we first introduce a reputation filter by leveraging the authentic on-chain data, aiming to eliminate high-risk contracts. We then design a contract-based incentive mechanism to help the foundation attract heterogeneous developers with multidimensional private information, and maximize the foundation’s utility by inducing developers to undertake projects of differing complexities based on their ability. We further differentiate between veteran and newcome developers and examine their influences on foundational strategies. Finally, extensive experimental results demonstrate that our proposed contracts can efficiently remove high-risk smart contracts, maximize the foundation’s utility, and ensure that developers select contracts honestly and participate in the SCaaS ecosystem actively.

Evolution of the 5G network introduces much higher QoS standards and energy saving objectives, which requires a more refined and smoothed online control method in many scenarios. To address this challenge, we study the online decision problem with switching costs where the agent incurs both a convex hitting cost and an additional switching cost of changing decisions, i.e., Smoothed Online Convex Optimization (SOCO). While there have been a wide variety of online algorithms designed, their theoretical performance relies on certain assumptions about loss functions, e.g., linearity and smoothness, predictability, or prior knowledge of regularity measures of environment. This paper addresses this limitation by developing a universal algorithm IOMD-SOCO that applies to general convex loss functions without predictions. We show that IOMD-SOCO achieves an order-optimal, universal dynamic regret bound. We also propose its parameter-free versions, i.e., without requiring the prior knowledge of path length of the comparator sequence, and achieve the same-order regret bound. We are the first to provide dynamic regret bounds for SOCO with general convex loss functions via parameter-free algorithms. Our numerical experiments show that IOMD-SOCO indeed achieves a substantial performance improvement. We also discuss potential applications of SOCO in communication networks.

We consider a decentralized multi-player multi-armed bandit (MP-MAB) problem where players cannot observe the actions and rewards of other players and no explicit communication or coordination between players is possible. Prior studies mostly focus on maximizing the sum of rewards of the players over time. However, the total reward maximization learning may lead to imbalanced reward among players, leading to poor Quality of Service (QoS) for some players. In contrast, our objective is to let each player n achieve a predetermined expected average reward over time, i.e., achieving a predetermined level of QoS. We develop a novel decentralized MP-MAB algorithm to accomplish this objective by leveraging the methodology of randomized matching. We prove that our decentralized algorithm can ensure that all players have an O(1) QoS regret. We also reveal an analog between our MP-MAB model and the online wireless queuing systems, which builds a connection between QoS in MP-MAB learning and stability in queuing theory.

Rongwu Xu, Brian Lin, Shujian Yang, Tianqi Zhang, Weiyan Shi, Tianwei Zhang, Zhixuan Fang, Wei Xu, Han Qiu. Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Effective action abstraction is crucial in tackling challenges associated with large action spaces in Imperfect Information Extensive-Form Games (IIEFGs). However, due to the vast state space and computational complexity in IIEFGs, existing methods often rely on fixed abstractions, resulting in sub-optimal performance. In response, we introduce RL-CFR, a novel reinforcement learning (RL) approach for dynamic action abstraction. RL-CFR builds upon our innovative Markov Decision Process (MDP) formulation, with states corresponding to public information and actions represented as feature vectors indicating specific action abstractions. The reward is defined as the expected payoff difference between the selected and default action abstractions. RL-CFR constructs a game tree with RL-guided action abstractions and utilizes counterfactual regret minimization (CFR) for strategy derivation. Impressively, it can be trained from scratch, achieving higher expected payoff without increased CFR solving time. In experiments on Heads-up No-limit Texas Hold'em, RL-CFR outperforms ReBeL's replication and Slumbot, demonstrating significant win-rate margins of $64\pm 11$ and $84\pm 17$ mbb/hand, respectively.

In this paper, we investigate a Multi-Armed Bandit (MAB) setting where an arm exits the game if the algorithm continuously neglects it. This setup is motivated by real-world scenarios, such as online advertising and crowdsourcing, where arms only gain benefits after being pulled by the algorithm. We identify the intrinsic hardness of this problem and limitations in existing approaches. We propose FC-SE algorithm with expected regret upper bounds as our solution to this problem. As an extension, we even allow new arms to enter after the game starts and design FC-Entry algorithm with performance guarantees for this setup. Finally, we conduct experiments to validate our theoretical results.

Cloud deep learning platforms provide cost-effective deep neural network (DNN) training for customers who lack computation resources. However, cloud systems are often untrustworthy and vulnerable to attackers, leading to growing concerns about model privacy. Recently, researchers have sought to protect data privacy in deep learning by leveraging CPU trusted execution environments (TEEs), which minimize the use of cryptography, but existing works failed to simultaneously utilize the computational resources of GPUs to assist in training and prevent model leakage. This paper presents Tempo, the first cloud-based deep learning system that cooperates with TEE and distributed GPUs for efficient DNN training with model confidentiality preserved. To tackle the challenge of preserving privacy while offloading linear algebraic operations from TEE to GPUs for efficient batch computation, we introduce a customized permutation-based obfuscation algorithm to blind both inputs and model parameters. An optimization mechanism that reduces encryption operations is proposed for faster weight updates during backpropagation to speed up training. We implement Tempo and evaluate it with both training and inference for two prevalent DNNs. Empirical results indicate that Tempo outperforms baselines and offers sufficient privacy protection.

The problem of scheduling packets from multiple sources over unreliable channels has attracted much attention due to its great practicability in the Internet of things systems. Most previous work focuses on the throughput/energy consumption/operational cost optimization or the setting that the channel information is known a priori. In this paper, we consider a more generic setting to this problem where packets from different sources have different values, and each heterogeneous source has a distinct Quality of Service (QoS) requirement. The information about packet value and channel reliability is unknown in advance, and the controller schedules sources over time to maximize its collected packet values while providing a QoS guarantee for each source. For the stationary case where packet values are independent and identically distributed (i.i.d.), we propose an efficient learning policy based on linear-programming (LP) methodology. Our proof shows that it meets the QoS constraint of each source and only incurs a logarithmic regret. In the special case that the channel reliability is known a priori, our algorithm can further guarantee a bounded regret. Furthermore, in the case of non-stationary packet values, we apply the sliding window technique to our LP-based algorithm and prove that it still guarantees a sublinear regret while meeting each source’s QoS requirement. Finally, we provide numerical simulations to support our theoretical results.

Two-sided matching under uncertainty has recently drawn much attention due to its wide applications. Existing works in matching bandits mainly focus on the one-sided learning setting and design algorithms with the objective of converging to stable matching with low regret. In this paper, we consider the more general two-sided learning setting, i.e. participants on both sides have to learn their preferences over the other side through repeated interactions. Inspired by the classical result that the optimal matching for the proposing side can be obtained using the Gale-Shapley algorithm, our inquiry stems from the curiosity about whether this result still holds in a two-sided learning setting. To handle this question, we formally introduce the two-sided learning setting, addressing strategies for both the arm and player sides without restrictive assumptions such as special preference structure and observation of winning players. Our results not only provide a positive answer to our inquiry but also offer a near-optimal upper bound, achieving $O(\log T)$ regret.

Multi-user delay-constrained scheduling is a crucial challenge in various real-world applications, such as wireless communication, live streaming, and cloud computing. The scheduler must make real-time decisions to guarantee both delay and resource constraints simultaneously, without prior information on system dynamics that can be time-varying and challenging to estimate. Additionally, many practical scenarios suffer from partial observability issues due to sensing noise or hidden correlation. To address these challenges, we propose a deep reinforcement learning (DRL) algorithm called Recurrent Softmax Delayed Deep Double Deterministic Policy Gradient ($\mathtt{RSD4}$) (https://github.com/hupihe/RSD4), which is a data-driven method based on a Partially Observed Markov Decision Process (POMDP) formulation.$\mathtt{RSD4}$guarantees resource and delay constraints by Lagrangian dual and delay-sensitive queues, respectively. It also efficiently handles partial observability with a memory mechanism enabled by the recurrent neural network (RNN). Moreover, it introduces user-level decomposition and node-level merging to support large-scale multihop scenarios. Extensive experiments on simulated and real-world datasets demonstrate that$\mathtt{RSD4}$is robust to system dynamics and partially observable environments and achieves superior performance over existing methods.

We consider the task scheduling scenario where the controller activates one from K task types at each time. Each task induces a random completion time, and a reward is obtained only after the task is completed. The statistics of the completion time and the reward distributions of all task types are unknown to the controller. The controller needs to learn to schedule tasks to maximize the accumulated reward within a given time horizon T. Motivated by the practical scenarios, we require the designed policy to satisfy a system throughput constraint. In addition, we introduce the interruption mechanism to terminate ongoing tasks that last longer than certain deadlines. To address this scheduling problem, we model it as an online learning problem with deadline and throughput constraints. Then, we characterize the optimal offline policy and develop efficient online learning algorithms based on the Lyapunov method. We prove that our online learning algorithm achieves an$O(\sqrt {T})$regret and zero constraint violation. We also conduct simulations to evaluate the performance of our developed learning algorithms.

In this paper, we propose a novel and energy-efficient blockchain system, CrowdMine, which exploits useful crowdsourcing computation to achieve decentralized consensus. CrowdMine solves user-proposed computing tasks and utilizes the computation committed to the task solving process to secure decentralized on-chain storage. With our designed “Proof of Crowdsourcing Work” (PoCW) protocol, our system provides an efficient paradigm for computation and storage in a trustless and decentralized environment. We also implement the system with 40 distributed nodes to demonstrate its performance and robustness.

Single sign-on (SSO) allows users to authenticate to third-party applications through a central identity provider. Despite their wide adoption, deployed SSO systems suffer from privacy problems such as user tracking by the identity provider. While numerous solutions have been proposed by academic papers, none were adopted because they require modifying identity providers, a significant adoption barrier in practice. Solutions do get deployed, however, fail to eliminate major privacy issues.Leveraging Trusted Execution Environments (TEEs), we propose MISO, the first privacy-preserving SSO system that is completely compatible with existing identity providers (such as Google and Facebook). This means MISO can be easily integrated into existing SSO ecosystem today and benefit end users. MI SO also enables new functionality that standard SSO cannot offer: MISO allows users to leverage multiple identity providers in a single SSO workflow, potentially in a threshold fashion, to better protect user accounts. We fully implemented MISO based on Intel SGX. Our evaluation shows that MISO can handle high user concurrency with practical performance.

We consider the task scheduling scenario where the controller activates one from K task types at each time. Each task induces a random completion time, and a reward is obtained only after the task is completed. The statistics of the completion time and the reward distributions of all task types are unknown to the controller. The controller needs to learn to schedule tasks to maximize the accumulated reward within a given time horizon T . Motivated by the practical scenarios, we require the designed policy to satisfy a system throughput constraint. In addition, we introduce the interruption mechanism to terminate ongoing tasks that last longer than certain deadlines. To address this scheduling problem, we model it as an online learning problem with deadline and throughput constraints. Then, we characterize the optimal offline policy and develop efficient online learning algorithms based on the Lyapunov method. We prove that our online learning algorithm achieves an $O(\sqrt T )$ regret and zero constraint violations. We also conduct simulations to evaluate the performance of our developed learning algorithms.

DAG-based blockchain faces the key challenge of transaction inclusion collision due to the high concurrency and network delay. In this paper, we propose “We-TIPS”, the weak-block-based transaction inclusion protocol with signaling to tackle this key challenge. In We-TIPS, during the mining process, the miner can broadcast their weak block header as a signal, which can indicate the miner's current transaction inclusion. With the prompt broadcast of the signal, the miner can effectively avoid the transaction inclusion collision and thus greatly boost the system performance. Besides, we develop a transaction inclusion game in We-TIPS to model miners' interaction and further show that it is a potential game. We propose a decentralized transaction inclusion algorithm that can achieve the approximate Nash equilibrium. Finally, we conduct intensive experiments to demonstrate the superior performance of the We-TIPS.

Multi-user delay constrained scheduling is important in many real-world applications including wireless communication, live streaming, and cloud computing. Yet, it poses a critical challenge since the scheduler needs to make real-time decisions to guarantee the delay and resource constraints simultaneously without prior information of system dynamics, which can be time-varying and hard to estimate. Moreover, many practical scenarios suffer from partial observability issues, e.g., due to sensing noise or hidden correlation. To tackle these challenges, we propose a deep reinforcement learning (DRL) algorithm, named Recurrent Softmax Delayed Deep Double Deterministic Policy Gradient (RSD4)1, which is a data-driven method based on a Partially Observed Markov Decision Process (POMDP) formulation. RSD4 guarantees resource and delay constraints by Lagrangian dual and delay-sensitive queues, respectively. It also efficiently tackles partial observability with a memory mechanism enabled by the recurrent neural network (RNN) and introduces user-level decomposition and node-level merging to ensure scalability. Extensive experiments on simulated/real-world datasets demonstrate that RSD4 is robust to system dynamics and partially observable environments, and achieves superior performances over existing DRL and non-DRL-based methods.

This paper proposes and studies for the first time the problem of combinatorial multi-armed bandits with linear long-term constraints. Our model generalizes and unifies several prominent lines of work, including bandits with fairness constraints, bandits with knapsacks (BwK), etc. We propose an upper-confidence bound LP-style algorithm for this problem, called UCB-LP, and prove that it achieves a logarithmic problem-dependent regret bound and zero constraint violations in expectation. In the special case of fairness constraints, we further provide a sharper constant regret bound for UCB-LP. Our regret bounds outperform the existing literature on BwK and bandits with fairness constraints simultaneously. We also develop another low-complexity version of UCB-LP and show that it yields $\tilde{O}(\sqrt{T})$ problem-independent regret and zero constraint violations with high-probability. Finally, we conduct numerical experiments to validate our theoretical results.

In this paper, we consider the matching of multi-agent multi-armed bandit problem, i.e., while agents prefer arms with higher expected reward, arms also have preferences on agents. In such case, agents pulling the same arm may encounter collisions, which leads to a reward of zero.For this problem, we design a specific communication protocol which uses deliberate collision to transmit information among agents, and propose a layer-based algorithm that helps establish optimal stable matching between agents and arms. With this subtle communication protocol, our algorithm achieves a state-of-the-art $O(\log T)$ regret in the decentralized matching market, and outperforms existing baselines in experimental results.

Payment Channel Network (PCN) is proposed as a promising layer-two solution to tackle the scalability problem of current blockchain systems, which allows the two transacting parties to perform off-chain transactions through their established payment channel. For the transacting parties who are not directly connected, PCN allows them to route the transaction through some intermediate nodes with sufficient balance. Designing an efficient routing protocol is one of the most important and challenging problems in improving the performance of PCN. To tackle this challenge, we propose Real-Time Recursive Routing (RTRR), an efficient routing algorithm that can achieve a short routing time with strong privacy protection and high flexibility in the dynamic scenario. In addition, we investigate the bidding process in RTRR and derive the equilibrium strategy, which implies that the proposed protocol prefers to route the transaction through the nodes with a higher success rate, contributing to a better performance. Both the theoretical analyses and the empirical experiment results demonstrate the high efficiency of RTRR.

In this paper, we study the problem of online convex optimization with switching costs (SOCO) that appears in diverse scenarios including power management, video streaming, resource allocation, etc. SOCO refers to online decision problems when the agent incurs both hitting cost and an additional switching cost of changing decisions. We adopt the universal dynamic regret as the performance metric, and consider the case when loss functions are unknown when making decisions. Previous results rely on the assumptions on loss function, e.g., linearity and smoothness, or prior knowledge of regularity measures, e.g., path length of the comparator sequence. In this paper, we propose an algorithm IOMD-SOCO that applies to general convex loss function, and show that the algorithm achieves an order-optimal universal dynamic regret bound. We also propose its parameter-free versions, i.e., without requiring the prior knowledge of path length of the comparator sequence, and achieve the same-order regret bound. We are the first to provide dynamic regret bounds for SOCO with general convex loss functions via parameter-free algorithm. Our numerical experiments show that IOMD-SOCO indeed achieves a substantial performance improvement.

Directed Acyclic Graph (DAG) is a popular approach to achieve scalability of blockchain networks. Due to its high efficiency in data communication and great scalability, DAG has been widely adopted in many applications such as Internet of Things (IoT) and Decentralized Finance (DeFi). DAG-based blockchain, nevertheless, faces the key challenge of transaction inclusion collision due to the high concurrency and the network delay. Particularly, the transaction inclusion collision in DAG-based blockchain leads to the revenue and throughput dilemmas, which would greatly degrade the system performance. In this paper, we propose “TIPS”, the Transaction Inclusion Protocol with Signaling, which broadcasts a signal indicating the transactions in the block. We show that with the prompt broadcast of a signal, TIPS substantially reduces the transaction collision and thus resolves these dilemmas. Moreover, we show that TIPS can defend against both the denial-of-service and the delay-of-service attacks. We also conduct intensive experiments to demonstrate the superior performance of the proposed protocol.

In current blockchain systems, the transaction fee is often not enough to cover the storage cost, jeopardizing blockchain sustainability in the long run. Such a storage sustainability issue is partially due to miners’ heterogeneous storage costs and users’ low-intensity fee competition. Motivated by these two observations, we propose a Fee and Transaction Expiration Time (FTET) mechanism to alleviate this issue. Specifically, we model the blockchain operation as a three-stage game. In Stage I, the system designer proposes the storage sustainability mechanism. In Stage II, each user decides whether to propose transactions and the corresponding transaction fees. In Stage III, each miner decides which transactions to include in the block. Although the analysis of the heterogeneous miner interaction is technically challenging, we fully solve it in closed-form motivated by how miners select transactions in practice. The equilibrium analysis reveals that high-storage-cost miners admit transactions with fees above a time-increasing threshold. Under the optimal FTET mechanism, the blockchain system can achieve the storage sustainability without any social welfare loss, comparing with the maximum achievable social welfare without the storage sustainability constraint. Moreover, the optimal FTET mechanism achieves a higher social welfare than the fee mechanism in current practice by selectively rejecting some transactions suffering high delays. Finally, we implement a blockchain prototype to compare the performance of the optimal FTET mechanism with the mining round time adjustment (MRTA) mechanism. The optimal FTET mechanism achieves higher social welfare (94.5% on average) and better storage sustainability. We find that more pending transactions may lead to lower transaction fees.

Miners in a blockchain system are suffering from ever-increasing storage costs, which in general have not been properly compensated by the users’ transaction fees. This reduces the incentives for the miners’ participation and may jeopardize the blockchain security. To mitigate this blockchain insufficient fee issue, we propose a Fee and Waiting Tax (FWT) mechanism, which explicitly considers the two types of negative externalities in the system. Specifically, we model the interactions between the protocol designer, users, and miners as a three-stage Stackelberg game. By characterizing the equilibrium of the game, we find that miners neglecting the negative externality in transaction selection cause they are willing to accept insufficient-fee transactions. This leads to the insufficient storage fee issue in the existing protocol (i.e., deployed in Bitcoin and Ethereum). Moreover, our proposed optimal FWT mechanism can motivate users to pay sufficient transaction fees to cover the storage costs and achieve the unconstrained social optimum. Numerical results show that the optimal FWT mechanism guarantees sufficient transaction fees and achieves an average social welfare improvement of 51.43% or more over the existing protocol. Furthermore, the optimal FWT mechanism reduces the average waiting time of low-fee transactions and all transactions by 68.49% and 61.56%, respectively.

A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first k (out of the total n) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platform's optimal incentive mechanism for motivating proper workers' participation in coded machine learning, despite the incomplete information about heterogeneous workers' computation performances and costs. A key contribution of this work is to summarize workers' multi-dimensional heterogeneity as a one-dimensional metric, which guides the platform's efficient selection of workers under incomplete information with a linear computation complexity. Moreover, we prove that the optimal recovery threshold k is linearly proportional to the participator number n if we use the widely adopted MDS codes for data encoding. We also show that the platform's increased cost due to incomplete information disappears when worker number is sufficiently large, but it does not monotonically decrease in worker number.

Existing risk-aware multi-armed bandit models typically focus on risk measures of individual options such as variance. As a result, they cannot be directly applied to important real-world online decision making problems with correlated options. In this paper, we propose a novel Continuous Mean-Covariance Bandit (CMCB) model to explicitly take into account option correlation. Specifically, in CMCB, there is a learner who sequentially chooses weight vectors on given options and observes random feedback according to the decisions. The agent's objective is to achieve the best trade-off between reward and risk, measured with option covariance. To capture different reward observation scenarios in practice, we consider three feedback settings, i.e., full-information, semi-bandit and full-bandit feedback. We propose novel algorithms with optimal regrets (within logarithmic factors), and provide matching lower bounds to validate their optimalities. The experimental results also demonstrate the superiority of our algorithms. To the best of our knowledge, this is the first work that considers option correlation in risk-aware bandits and explicitly quantifies how arbitrary covariance structures impact the learning performance.The novel analytical techniques we developed for exploiting the estimated covariance to build concentration and bounding the risk of selected actions based on sampling strategy properties can likely find applications in other bandit analysis and be of independent interests.

A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first k (out of the total n) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platform's optimal incentive mechanism for motivating proper workers' participation in coded machine learning, despite the multi-dimensional incomplete information about heterogeneous workers' computation performances and costs. A key contribution of this work is to summarize workers' multi-dimensional heterogeneity as a one-dimensional metric, which guides the platform's efficient selection of workers under incomplete information with a linear computation complexity. Although the exact overall runtime is intractable, we characterize the platform's (asymptotically) optimal load assignment to heterogeneous workers in coded machine learning. When the platform has incomplete information about workers' costs, it is optimal to assign loads only based on workers' computation performances; when the platform further lacks workers' computation performance information, it is optimal to design the loads to be cost-dependent and performance-dependent.

As an emerging machine learning technique, federated learning has received significant attention recently due to its promising performance in mitigating privacy risks and costs. While most of the existing work of federated learning focused on designing learning algorithm to improve training performance, the incentive issue for encouraging users' participation is still under-explored. This paper presents an analytical study on the server's optimal incentive mechanism design, in the presence of users' multi-dimensional private information (e.g., training cost and communication delay). Specifically, we consider a multi-dimensional contract-theoretic approach, with a key contribution of summarizing users' multi-dimensional private information into a one-dimensional criterion that allows a complete order of users. We further perform the analysis in three information scenarios to reveal the impact of information asymmetry levels on server's optimal strategy and minimum cost. We show that weakly incomplete information does not increase the server's cost (comparing with the complete information scenario) when training data is IID, but it in general does when data is non-IID. Furthermore, the optimal mechanism design under strongly incomplete information is much more challenging, and it is not always optimal for the server to incentivize the group of users with the lowest training cost and delay to participate.

Sharing platforms have facilitated the redistribution of underused resources by providing convenient online marketplaces for individual sellers and buyers. However, the sellers on these platforms may not fully disclose the information of their shared commodities, due to strategic behaviors or privacy concerns. Sellers' strategic information disclosure significantly affects buyers' user experiences and platforms' reputation. This paper presents one of the first analytical studies on information disclosure and pricing strategies of competing sellers on a sharing platform. In particular, we propose a three-stage game framework to capture sellers' strategic behaviors and buyers' decisions. Although the corresponding optimization problem is non-convex, we are able to completely characterize the complex market equilibria. We demonstrate that full disclosure by all sellers or non-disclosure by all sellers will both lead to intense price competition. We prove that the former all-disclosure case is never an equilibrium even when all sellers have good commodity qualities and low privacy costs, while the latter non-disclosure case can be an equilibrium under which all sellers get zero profit. Interestingly, we also reveal that buyers' estimation biases encourage information disclosure as they mitigate the competition among sellers.

Miners in a blockchain system are suffering from the ever-increasing storage costs, which in general have not been properly compensated by the users' transaction fees. In the long run, this may lead to less participation of miners and jeopardize the blockchain security. In this paper, we study the economics of blockchain storage and identify the incentive issues related to this storage cost problem. More specifically, we model the interactions among users (who generate transactions) and miners in two stages, where the users set the transaction fees in Stage 1, and the miners select which transactions to include in Stage 2. Through characterizing the Nash equilibrium of the two-stage game, we find that the transaction fees indeed cannot cover the storage costs under the current practice in general, due to the negative externality and the unfair delay-based pricing. We also identify that a longer block interval can alleviate the concern by raising the transactions fees at the expense of larger delay.

A widely adopted approach to guarantee high-quality services on on-demand service platforms is to introduce a reputation system, where good reputation workers will receive a bonus for providing high-quality services. In this paper, we propose a general reputation framework motivated by various practical examples. Our model captures the evolution of a reputation system, jointly considering worker's strategic behaviors and imperfect customer reviews that are usually studied separately before. We characterize the stationary equilibrium of the market, in particular, the existence and uniqueness of a non-trivial equilibrium that ensures high-quality services. Furthermore, we propose an efficient subsidization mechanism that helps induce high-quality services on the platform, and show the market convergence to the high service quality equilibrium under such a mechanism.

Bike sharing provides an environment-friendly way for traveling and is booming all over the world. Yet, due to the high similarity of user travel patterns, the bike imbalance problem constantly occurs, especially for dockless bike sharing systems, causing significant impact on service quality and company revenue. Thus, it has become a critical task for bike sharing operators to resolve such imbalance efficiently. In this paper, we propose a novel deep reinforcement learning framework for incentivizing users to rebalance such systems. We model the problem as a Markov decision process and take both spatial and temporal features into consideration. We develop a novel deep reinforcement learning algorithm called Hierarchical Reinforcement Pricing (HRP), which builds upon the Deep Deterministic Policy Gradient algorithm. Different from existing methods that often ignore spatial information and rely heavily on accurate prediction, HRP captures both spatial and temporal dependencies using a divide-and-conquer structure with an embedded localized module. We conduct extensive experiments to evaluate HRP, based on a dataset from Mobike, a major Chinese dockless bike sharing company. Results show that HRP performs close to the 24-timeslot look-ahead optimization, and outperforms state-of-the-art methods in both service level and bike distribution. It also transfers well when applied to unseen areas.

Loyalty programs are important tools for sharing platforms seeking to grow supply. Online sharing platforms use loyalty programs to heavily subsidize resource providers, encouraging participation and boosting supply. As the sharing economy has evolved and competition has increased, the design of loyalty programs has begun to play a crucial role in the pursuit of maximal revenue. In this paper, we first characterize the optimal loyalty program for a platform with homogeneous users. We then show that optimal revenue in a heterogeneous market can be achieved by a class of multi-threshold loyalty program (MTLP) which admits a simple implementation-friendly structure. We also study the performance of loyalty programs in a setting with two competing sharing platforms, showing that the degree of heterogeneity is a crucial factor for both loyalty programs and pricing strategies. Our results show that sophisticated loyalty programs that reward suppliers via stepwise linear functions outperform simple sign-up bonuses, which give them a one time reward for participating.

The growth of the sharing economy is driven by the emergence of sharing platforms, e.g., Uber and Lyft, that match owners looking to share their resources with customers looking to rent them. The design of such platforms is a complex mixture of economics and engineering, and how to "optimally" design such platforms is still an open problem. In this paper, we focus on the design of prices and subsidies in sharing platforms. Our results provide insights into the tradeoff between revenue maximizing prices and social welfare maximizing prices. Specifically, we introduce a novel model of sharing platforms and characterize the profit and social welfare maximizing prices in this model. Further, we bound the efficiency loss under profit maximizing prices, showing that there is a strong alignment between profit and efficiency in practical settings. Our results highlight that the revenue of platforms may be limited in practice due to supply short- ages; thus platforms have a strong incentive to encourage sharing via subsidies. We provide an analytic characterization of when such subsidies are valuable and show how to optimize the size of the subsidy provided. Finally, we validate the insights from our analysis using data from Didi Chuxing, the largest ridesharing platform in China.