This paper revisits fairness-aware interactive recommendation (e.g., TikTok, KuaiShou) by introducing a novel control knob, i.e., the lifecycle of items. We make threefold contributions. First, we conduct a comprehensive empirical analysis and uncover that item lifecycles in short-video platforms follow a compressed three-phase pattern, i.e., rapid growth, transient stability, and sharp decay, which significantly deviates from the classical four-stage model (introduction, growth, maturity, decline). Second, we introduce LHRL, a lifecycle-aware hierarchical reinforcement learning framework that dynamically harmonizes fairness and accuracy by leveraging phase-specific exposure dynamics. LHRL consists of two key components: (1) PhaseFormer, a lightweight encoder combining STL decomposition and attention mechanisms for robust phase detection; (2) a two-level HRL agent, where the high-level policy imposes phase-aware fairness constraints, and the low-level policy optimizes immediate user engagement. This decoupled optimization allows for effective reconciliation between long-term equity and short-term utility. Third, experiments on multiple real-world interactive recommendation datasets demonstrate that LHRL significantly improves both fairness and user engagement. Furthermore, the integration of lifecycle-aware rewards into existing RL-based models consistently yields performance gains, highlighting the generalizability and practical value of our approach.

This paper proposes a variant of multiple-play stochastic bandits tailored to resource allocation problems arising from LLM applications, edge intelligence, etc. The model is composed of finite number of arms and plays. Each arm has a stochastic number of capacities, and each unit of capacity is associated with a reward function. Each play is associated with a priority weight. When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner. Instance independent and instance dependent regret lower bounds are proved, revealing the impact of model parameters on the hardness of learning the optimal allocation policy. When model parameters are given, we design an algorithm named MSB-PRS-OffOpt to locate the optimal play allocation policy with a polynomial computational complexity in the number of arms and plays. Utilizing MSB-PRS-OffOpt as a subroutine, an approximate upper confidence bound (UCB) based algorithm is designed, which has instance independent and instance dependent regret upper bounds matching the corresponding lower bound up to acceptable factors. To this end, we address nontrivial technical challenges arising from optimizing and learning under a special nonlinear combinatorial utility function induced by the prioritized resource sharing mechanism.

Online rating systems are an indispensable building block for many web applications, yet they are pervasively affected by data biases that distort our understanding of user preferences. A key source of this bias is the “Spiral of Silence” (SoS) phenomenon, where users who perceive their opinions to be in the minority tend to withhold them, leading to non-random missing data. While initial research has begun to explore this issue, existing SoS models for recommender systems fail to capture real-world complexities, such as rating recency, user heterogeneity (e.g., “hardcore” users immune to social pressure), and asymmetric responses to conforming versus dissenting opinions. Furthermore, these models often lack formal theoretical guarantees. To fill this gap, we introduce Bi-MCP, a modular probabilistic framework to quantify and mitigate SoS effects. Bi-MCP models a bifurcated user population (hardcore vs. conformist) and their bidirectional (asymmetric) response to the perceived opinion climate. The framework is (i) Expressive, capturing novel factors missed by prior work; (ii) Modular, allowing its components to be extended or replaced to support future research; and (iii) Theoretically grounded, with a formal proof of convergence for its Generalized Expectation-Maximization (GEM) inference algorithm. Experimental results on four large-scale public datasets demonstrate that our model significantly improves recommendation accuracy over state-of-the-art baselines, showcasing the practical benefit of explicitly modeling these nuanced SoS effects.

An advertiser typically conducts a campaign across several publishers. Different publishers often reach different sets of persons, and some people may be exposed to the campaign via multiple publishers. Due to privacy restrictions, it is prohibited to collect all audience activities from multiple publishers in a centralized manner, therefore, we desire secure protocols for mining audience activities. In this paper, we propose a secure protocol for efficiently estimating the frequency histogram, i.e. the fraction of persons (or users) appearing a given number of times across all publishers. Our protocolMPC-FHis designed based on a novel sketch methodMPSthat uniformly samples a fraction of users across multiple parties and can be efficiently implemented on SPDZ, which is a popular secure multiparty computation (MPC) scheme. Our protocol provides more strict security guarantees than the state-of-the-art. In addition, our experimental results on a variety of large datasets demonstrate that our protocol can also accelerate the computation speed of existing protocols by orders of magnitudes.

Cloud Workload Prediction (CWP) is a critical task in cloud computing, essential for resource scheduling, performance optimization, and cost management. However, existing time series prediction methods struggle with instability and inefficiency when applied directly to cloud workloads due to their high variability and frequent fluctuations. To address these challenges, we propose DEL4CW, a novel D eep E xpansion L earning framework specifically designed for CWP . DEL4CW introduces a unique self-decoupling mechanism to disentangle the complex dependencies present in highly variable cloud workloads, leading to more accurate predictions of job arrival rates. The core contribution of DEL4CW lies in its ability to decouple cloud workload signals into three key components—trend, periodicity, and residuals—by treating these as hidden variables. This enables the model to better manage both short-term fluctuations and long-term workload trends. DEL4CW employs a deep expansion learning framework structured as stacked blocks, where each block includes dedicated modules for trend, periodicity, and compensation. Specifically, the trend module utilizes multi-layer fully connected networks to capture evolving trends at multiple granularities, while the periodicity module leverages multi-head attention to identify diverse periodic patterns. The compensation module addresses unpredictable, localized fluctuations, improving the model’s robustness to noise. In addition to its predictive accuracy, DEL4CW provides interpretable insights through its hierarchical design, allowing for layer-by-layer aggregation of meaningful partial predictions. This interpretability stems from the doubly residual learning pipeline, which ensures that each prediction block contributes progressively refined predictions. Extensive experiments on real-world cloud workload traces demonstrate that DEL4CW significantly outperforms existing baselines, with error reductions reaching up to 27.74% in certain scenarios.

As recommender systems are essential to various web domains such as e-commerce and web content sharing, providing equitable item exposure regardless of popularity becomes an imperative requirement. However, traditional fairness-aware approaches typically aim to achieve a better tradeoff between recommendation accuracy and fairness, and focus on improving the exposure rate of the long-tail items on static settings, evaluating fairness on one-shot recommendation decisions using logged data. Such methods overlook the dynamic nature of user preferences in real-world interactive environments. In contrast, our work seeks a win-win solution that simultaneously enhances recommendation accuracy and fairness over the long term, rather than merely trading off one against the other. To achieve this goal, we empirically demonstrate and analyze the spatiotemporal heterogeneity of user popularity preference. Our findings reveal complementary characteristics that, when fully exploited, can guide personalized strategies for long-term fairness. Building on this insight, we propose HER4IF, a novel hierarchical reinforcement learning framework designed for interactive recommendation. HER4IF decomposes the recommendation process into two key tasks: dynamic fairness control and item recommendation. The high-level agent continuously learns adaptive fairness constraints from evolving user popularity preferences, while the low-level agent refines recommendation policies under these personalized constraints. Extensive experiments on three real-world datasets and the interactive recommendation platform KuaiSim demonstrate that HER4IF significantly outperforms state-of-the-art methods, achieving substantial improvements in both fairness and recommendation accuracy. Our code is available at: https://github.com/1163710212/HER4IF .

As cloud services become increasingly integral to modern IT infrastructure, ensuring hardware reliability is essential to sustain high-quality service. Memory failures pose a significant threat to overall system stability, making accurate failure prediction through the analysis of memory error logs (i.e., Correctable Errors) imperative. Existing memory failure prediction approaches have notable limitations: rule-based expert models suffer from limited generalizability and low recall rates, while automated feature extraction methods exhibit suboptimal performance. To address these limitations, we propose M2-MFP: a Multi-scale and Multi-Level Memory Failure Prediction framework designed to enhance the reliability and availability of cloud infrastructure. M2-MFP converts correctable errors (CEs) into multi-level binary matrix representations and introduces a Binary Spatial Feature Extractor (BSFE) to automatically extract high-order features at both DIMM-level and bit-level. Building upon the BSFE outputs, we develop a dual-path temporal modeling architecture: 1) a time-patch module that aggregates multi-level features within observation windows, and 2) a time-point module that employs interpretable rule-generation trees trained on bit-level patterns. Experiments on both benchmark datasets and real-world deployment show the superiority of M2-MFP as it outperforms existing state-of-the-art methods by significant margins. Code and data are available at this repository: https://github.com/hwcloud-RAS/M2-MFP.

Deep long-tailed recognition (DLTR) has garnered increasing attention due to the inherent imbalance in many real-world problems (e.g., multimedia processing). Recently, some multi-objective optimization (MOO)-based solutions have been proposed to address conflicts during representation learning in DLTR. However, these methods face two primary challenges: (1) their effectiveness is subject to the power of MOO, which is arguable in recent literature, and (2) MOO approaches are resource-intensive due to frequent gradient operations. In this paper, we propose a novel approach: conflict-Buffering OptimizatiOn by Symmetry Teleportation (BOOST), which avoids altering complicated gradient combinations as previous methods did. A major challenge in this approach is the absence of off-the-shelf symmetry teleportation algorithms suitable for modern deep neural networks. To address this, we cast symmetry teleportation as the optimization of low-rank adaptation (LoRA). Specifically, we first divide categories into multiple groups and detect conflicts among them. When a conflict arises, we employ LoRA to identify an alternative point on the same loss level set, reducing conflicts and facilitating balanced optimization. To achieve this, we decouple symmetry teleportation into two objectives-loss invariance and balanced gradient maximization-and design corresponding objectives for LoRA optimization. Besides, we propose a trajectory reuse strategy to continually benefit from advanced optimizers. Extensive experiments demonstrate that BOOST achieves state-of-the-art performance across multiple mainstream DLTR datasets.

Data augmentation is a kind of mainstream domain generalization method aimed at enhancing the model’s ability to learn from out-of-distribution data. Most existing data augmentation methods fail to simultaneously preserve the semantic consistency and ensure the domain diversity in the augmented samples, which hinders further improvements in the generalization capacity of the model. To cope with this issue, we propose a novel cross-domain semantic transfer (CDST)-based data augmentation method, which improves generalizability from a novel perspective of exploring the diversity of semantic directions. Specifically, to ensure semantic consistency, an adjacent domain center interpolation module is proposed to find new generalization centers far from the classification boundary. To ensure data diversity, a semantic sample reproduction module is proposed to synthesize new semantic directions by transferring the cross-domain semantic information and reproduce new samples along new semantic directions around new feature centers. Furthermore, a category-preserving regularization is introduced to further constrain the category invariance of the augmented samples. Extensive experiments are implemented to verify the superiority, effectiveness, and transferability of CDST on the Digit-DG, PACS, VLCS, and OfficeHome datasets.

The Probabilistic Maximum Coverage (PMC) problem plays a pivotal role in modeling various network applications, such as mobile crowdsensing, which involves selecting nodes within a graph that probabilistically cover other nodes. Our study focuses on PMC within the framework of online learning, termed the PMC bandit, where the network parameters are initially unknown. In this scenario, the decision-maker is tasked with learning these parameters to maximize the cumulative rewards from covered nodes. Despite prior research on the PMC bandit, we propose a novel variant, dynamic PMC-G bandit, which extends the semi-bandit feedback model to represent applications more accurately. To tackle the complexities of the time-varying combinatorial arm set rather than traditional static, we enhance the Combinatorial Upper Confidence Bound (CUCB) algorithms by developing two innovative variance-aware strategies: the Variance-Adaptive Combinatorial Upper Confidence Bound (VACUCB) for probabilistically triggered arms, and the Action-Based Combinatorial Upper Confidence Bound (ABCUCB) for self-reliant arms, i.e., independent arms with probabilistically triggered outcomes. Based on variance-aware properties, our contributions notably reduce the dependence on the number of nodes$K$selected per round, demonstrating that: (i) VACUCB effectively minimizes the regret associated with the triggered arms, enhancing the CUCB by a factor of$\tilde{O}(K)$; (ii) ABCUCB further diminishes the dependence on$K$in the leading term. Empirical results from synthetic and real-world datasets confirm that our proposed algorithms outperform current benchmarks in three network applications.

Reposting plays an essential role in boosting visibility on online social networks (OSNs). In this paper, we study the problem of designing “reposting service” in an OSN to incentivize “transactions” between requesters (users who seek to enhance visibility) and suppliers (users who are willing to repost if certain incentives are given), and maximize the welfare increase accumulated through a given time horizon. We formulate a mathematical model for reposting which captures various factors like click-through rates (CTRs), requesters’ valuations and suppliers’ costs. We formulate the problem of maximizing the welfare increase via judiciously assigning suppliers to requesters from two aspects: (a) “user-centric” and (b) “platform-centric”. The user-centric aspect deals with situations where requesters and suppliers collaborate and share valuations and costs. To address the challenge of unknown CTRs, we propose an online learning protocol and achieve a sub-linear regret. The platform-centric aspect corresponds to the scenario where users keep their valuations or costs private. To address the challenges of unknown CTRs, valuations and costs, we design an “explore-then-commit” online protocol. We prove the truthfulness of the proposed online protocol, and we also prove that this protocol has a sub-linear regret. Lastly, we conduct extensive experiments on six public datasets to evaluate the effectiveness and scalability of the proposed protocols.

We study the problem of federated contextual combinatorial cascading bandits, where agents collaborate under the coordination of a central server to provide tailored recommendations to users. Existing works consider either a synchronous framework, necessitating full agent participation and global synchronization, or assume user homogeneity with identical behaviors. We overcome these limitations by considering (1) federated agents operating in an asynchronous communication paradigm, where no mandatory synchronization is required and all agents communicate independently with the server, (2) heterogeneous user behaviors, where users can be stratified into latent user clusters, each exhibiting distinct preferences. For this setting, we propose a UCB-type algorithm with delicate communication protocols. Through theoretical analysis, we give sub-linear regret bounds on par with those achieved in the synchronous framework, while incurring only logarithmic communication costs. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.

With the growing influence of Recommender System (RS) in people’s daily lives, the issue of fairness in recommendations has become increasingly crucial. Previous fairness-aware methods focus on static or one-shot recommendation settings, where the recommendation model provides static fairness solutions via solving a fixed fairness-constrained optimization. However, these approaches face challenges in maintaining the delicate balance between recommendation accuracy and fairness in dynamic environments, as they fail to account for the evolving nature of RS, including changes in user preferences and item popularity over time.In this paper, we explore the problem of long-term fairness in interactive recommendation and accomplish the problem through dynamic fairness-constrained decisions. We focus on maintaining the exposure fairness of items across different groups. We argue that fairness does not always in conflict with recommendation performance, especially when considering the spatiotemporal heterogeneity of user preference on item popularity. To achieve this, we propose HER4IF, a dynamic fairness-aware interactive recommendation method based on a hierarchical reinforcement learning framework. Its main idea is first to aggregate the interacted item popularity with the time-forgetting model in state representation to capture user popularity preference. It then introduces a high-level agent to generate a dynamic fairness constraint based on the user’s current state, while a low-level agent generates recommendations under this constraint. Experiments on two datasets and an authentic Reinforcement Learning environment (KuaiSim) show the effectiveness and superiority of the proposed framework in terms of recommendation accuracy and fairness. It demonstrates a win-win for fairness and accuracy in a dynamic recommendation setting, when considering the dynamic nature of RS and incorporating spatiotemporal heterogeneity in user preference on item popularity.

User-centric selection problems arise from mobile edge computing systems, ride-sharing applications, etc. Novel variants of the multi-play multi-armed bandit model are proposed to balance the exploration vs. exploitation tradeoff of user-centric selection problems. Two significant limitations of these variants are: (1) all plays must be assigned; (2) full feedback on the resource is required. This paper relaxes these two assumptions by assigning a subset of plays and capturing bandit feedback on the resource. We show that under this relaxation of assumptions, previous algorithms have a linear regret, i.e., failing to learn the optimal decision. We design a Thompson sampling type algorithm called USP-TS for this relaxation and prove it has a sub-linear regret. To attain a better exploration vs. exploitation tradeoff, we design a variant of the USP-TS called USP-TS-AER, which is tailored for the structure of bandit feedback on the resource. Extensive experiments validate the superior performance of USP-TS against various baselines and that USP-TS-AER can reduce the regret of USP-TS by as much as 50%.

It is a longstanding problem that Q-learning suffers from the overestimation bias. This issue originates from the fact that Q-learning uses the expectation of maximum Q-value to approximate the maximum expected Q-value. A number of algorithms, such as Double Q-learning, were proposed to address this problem by reducing the estimation of maximum Q-value, but this may lead to an underestimation bias. Note that this underestimation bias may have a larger performance penalty than the overestimation bias. Different from previous algorithms, this article studies this issue from a fresh perspective, i.e., meta-learning view, which leads to our Meta-Debias Q-learning. The main idea is to extract the maximum expected Q-value with meta-learning over multiple tasks to remove the estimation bias of maximum Q-value and help the agent choose the optimal action more accurately. However, there are two challenges: (1) How to automatically select suitable training tasks? (2) How to positively transfer the meta-knowledge from selected tasks to remove the estimation bias of maximum Q-value? To address the two challenges mentioned above, we quantify the similarity between the training tasks and the test task. This similarity enables us to select appropriate “partial” training tasks and helps the agent extract the maximum expected Q-value to remove the estimation bias. Extensive experiment results show that our Meta-Debias Q-learning outperforms SOTA baselines drastically in three evaluation indicators, i.e., maximum Q-value, policy, and reward. More specifically, our Meta-Debias Q-learning only underestimates \(1.2*10^{-3}\) than the maximum expected Q-value in the multi-armed bandit environment and only differs \(5.04\%-5\%=0.04\%\) than the optimal policy in the two states MDP environment. In addition, we compare the uniform weight and our similarity weight. Experiment results reveal fundamental insights into why our proposed algorithm outperforms in the maximum Q-value, policy, and reward.

Online rating system serves as an indispensable building block for many web applications. Previous studies showed that due to assimilate-contrast effects, historical ratings could significantly distort users' ratings, leading to low accuracy of product quality estimation and recommendation. To understand assimilate-contrast effects, an “accurate” model is still missing as previous models do not capture important factors like rating recency, selection bias, etc. Furthermore, an analytical framework to characterize product estimation accuracy under assimilate-contrast effects is also missing. This paper aims to fill in this gap. We propose a probabilistic model to quantify the aforementioned important factors on assimilate-contrast effects. We apply stochastic approximation theory to show that when the rating bias satisfies mild contraction conditions, the aggregate rating converges under aggregate opinion heterogeneity. We also apply non-stationary Markov chain theory to show that when the strength of assimilate-contrast satisfies mild stable conditions, the aggregate rating converges under rating recency. We also derive an equation to characterize the converged aggregate ratings. These conditions reveal important insights on how the aforementioned factors influence the convergence and guide the online rating system operator to design appropriate rating aggregation rules and rating displaying strategies. We apply it to rating prediction tasks and product recommendation tasks. Experiment results on four public datasets show that our model can improve the rating prediction and recommendation accuracy over previous models significantly, under various metrics like RMSE, NDCG, etc. We also demonstrate the flexibility of our model by showing that it can be applied to enhance other rating behavior models.

Queueing models serve as important building blocks in many networking applications such as task scheduling in mobile edge computing nodes, traffic scheduling in networks, congestion control in Internet, etc. However, queueing theory often needs to make strong assumptions about the arrival process or service rewards at each queue. In addition, fairness in serving workload among all queues is of great importance in many applications. In this paper, we address how to optimize resource allocation among multiple queues with a fairness guarantee and without any a priori knowledge of these queues’ parameters. To characterize queues with unknown parameters and the fairness requirement, we formulate an online learning model with a varying and continuous action space, as well as a nonlinear utility objective. We design an online learning algorithm to tackle the problem. We prove that our algorithm has a regret upper bound of$O(\sqrt{T}\log T)$and our model has a regret lower bound of$\Omega (\sqrt{T})$, where$T$stands for the number of decision rounds. The asymptotic closeness of upper and lower bounds guarantees their near tightness and our algorithm's near optimality. We discuss our model's real-world applications in mobile edge computing, wireless networks, and crowdsourcing, and conduct simulations to validate our algorithm's effectiveness.

While personalization increases the utility of item recommendation, it also suffers from the issue of popularity bias. However, previous methods emphasize adopting supervised learning models to relieve popularity bias in the static recommendation, ignoring the dynamic transfer of user preference and amplification effects of the feedback loop in the recommender system (RS). In this paper, we focus on studying this issue in the interactive recommendation. We argue that diversification and novelty are both equally crucial for improving user satisfaction of IRS in the aforementioned setting. To achieve this goal, we propose a D iversity- N ovelty- a ware I nteractive R ecommendation framework (DNaIR) that augments offline reinforcement learning (RL) to increase the exposure rate of long-tail items with high quality. Its main idea is first to aggregate the item similarity, popularity, and quality into the reward model to help the planning of RL policy. It then designs a diversity-aware stochastic action generator to achieve an efficient and lightweight DNaIR algorithm. Extensive experiments are conducted on the three real-world datasets and an authentic RL environment (Virtual-Taobao). The experiments show that our model can better and full use of the long-tail items to improve recommendation satisfaction, especially those low popularity items with high-quality ones, thus achieving state-of-the-art performance.

This article considers the problem of maintaining the long-term fairness of item exposure in interactive recommender systems under the dynamic setting that user preference and item popularity evolve over time. The challenge is that the evolving dynamics of user preference and item popularity in the feedback loop amplify the long-term “unfairness” of item exposure. To address this challenge, we first formulate a constrained Markov Decision Process (MDP) to capture the evolving dynamics of user preference. The proposed constrained MDP imposes long-term fairness requirements via maximum entropy techniques. Moreover, to illuminate the “unfairness” amplifying effect caused by the evolving dynamic of item popularity in the feedback loop, we design a debiased reward function to eliminate popularity bias in the training data. To this end, the proposed framework can maintain acceptable recommendation accuracy while exposing items as randomly as possible, ensuring long-term benefits for users. To address the data sparsity issue, the proposed framework can easily integrate self-supervised learning methods to enhance state representation. Experiments on three datasets and an authentic Reinforcement Learning environment (Virtual-Taobao) demonstrate the effectiveness and superiority of the proposed framework in terms of recommendation accuracy and fairness, and show the robustness against data sparsity and noise.

This paper considers the problem of maintaining the long-term fairness of item exposure in interactive recommendation systems under the dynamic setting that user preference and item popularity evolve over time. The challenge is that the evolving dynamics of user preference and item popularity in the feedback loop amplify the long-term “unfairness” of item exposure. To address this challenge, we first formulate a constrained Markov Decision Process (MDP) to capture evolving dynamics of user preference. The proposed constrained MDP imposes long-term fairness requirements via maximum entropy techniques. Moreover, to illuminate the “unfairness” amplifying effect caused by the evolving dynamic of item popularity in the feedback loop, we design a debiased reward function to eliminate popularity bias in the training data. To this end, the proposed framework can maintain acceptable recommendation accuracy while exposing items as randomly as possible, ensuring long-term benefits for users. Experiments on three datasets demonstrate the effectiveness and superiority of our proposed framework in terms of recommendation performance and fairness.

E-commerce applications such as Amazon and Tmall often provide services in multiple countries, forming multiple markets around the world. Generally, different markets over-lap in some items and differ in users. To make effective use of data from different markets, Cross-Market Recommendation (CMR) has been proposed to improve recommendation performance in data-scarce markets(i.e. target markets) using knowledge learned from other data-rich markets(i.e. source markets). Previous works on CMR do not capture the differences between markets well and still do not provide good recommendations to users in the target market. To address this limitation, we propose the CGCCMR model to leverage data from multiple markets and to improve the recommendation performance in the target market. CGCCMR first pre-trains the embedding layer by Light Graph Convolution(LGC) and performs Mask Data Augmentation on the samples from target markets. Then, it extracts the user interest representation related to the target item by User Interest Attention Network(UIAN) and adopts Cross-Market Customized Gate Control(CM-CGC) to effectively capture the similarities and differences between markets. Finally, it adopts an auxiliary network and a market-specific tower network to make final predictions. The experimental results from real-world datasets validate the superiority of the proposed CGCCMR model.

Probabilistic maximum coverage (PMC) is an important problem that can model many network applications, including mobile crowdsensing, network content delivery, and dynamic channel allocation, where an operator chooses nodes in a graph that can probabilistically cover other nodes. In this paper, we study PMC under the online learning context: the PMC bandit. For PMC bandit where network parameters are not known a priori, the decision maker needs to learn the unknown parameters and the goal is to maximize the total rewards from the covered nodes. Though PMC bandit has been studied previously, the existing model and its corresponding algorithm can be significantly improved. First, we propose the PMC-G bandit whose feedback model generalizes existing semi-bandit feedback, allowing PMC bandit to model applications like online content delivery and online dynamic channel allocation. Next, we improve the existing combinatorial upper confidence bound (CUCB) algorithm by introducing the variance-adaptive algorithm, i.e., the VA-CUCB algorithm. We prove that VA-CUCB can achieve strictly better regret bounds, which improves CUCB by a factor of $\tilde O(K)$, where K is the number of nodes selected in each round. Finally, experiments show our superior performance compared with benchmark algorithms on synthetic and real-world datasets.

Off-policy learning, referring to the procedure of policy optimization with access only to logged feedback data, has shown importance in various important real-world applications, such as search engines and recommender systems. While the ground-truth logging policy is usually unknown, previous work simply takes its estimated value for the off-policy learning, ignoring the negative impact from both high bias and high variance resulted from such an estimator. And these impact is often magnified on samples with small and inaccurately estimated logging probabilities. The contribution of this work is to explicitly model the uncertainty in the estimated logging policy, and propose an Uncertainty-aware Inverse Propensity Score estimator (UIPS) for improved off-policy learning, with a theoretical convergence guarantee. Experiment results on the synthetic and real-world recommendation datasets demonstrate that UIPS significantly improves the quality of the discovered policy, when compared against an extensive list of state-of-the-art baselines.

Template mining is one of the foundational tasks to support log analysis, which supports the diagnosis and troubleshooting of large scale Web applications. This paper develops a human-in-the-loop template mining framework to support interactive log analysis, which is highly desirable in real-world diagnosis or troubleshooting of Web applications but yet previous template mining algorithms fail to support it. We formulate three types of light-weight user feedback and based on them we design three atomic human-in-the-loop template mining algorithms. We derive mild conditions under which the outputs of our proposed algorithms are provably correct. We also derive upper bounds on the computational complexity and query complexity of each algorithm. We demonstrate the versatility of our proposed algorithms by combining them to improve the template mining accuracy of five representative algorithms over sixteen widely used benchmark datasets.

Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users’ activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop thesocial and activity network(SAN), a two-layer hyper-graph that unifies users’ friendships and their activities, to fully utilize users’ activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil_SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil_SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil_SAN, and derive the number of rounds needed to guarantee the convergence. We use“matrix perturbation theory”to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil_SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy. Lastly, we present two extensions of Sybil_SAN to further improve its accuracy.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by theslow convergencerate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient “unbiased sampling” schemes, and we also design two variant algorithms which can reduce sampling cost and speed up the convergence. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms; and to achieve the same estimation accuracy, our approach reduces the query cost significantly. Last, we use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Random walk sampling is often used to conduct statistical estimation over graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. Our bias reduction algorithm only utilizes a small number of valid sub-samples, which can reduce more bias of the estimator but may increase the variance of the estimator significantly. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. We provide theoretical guarantees and computational complexity analysis of our proposed bias reduction algorithms. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. Extensive experiments on four public datasets confirm the effectiveness and computational efficiency of our proposed algorithmic framework under the mean square metric and beyond.

To provide fast and accurate risk evaluation on network rare threats, importance sampling (IS) is widely used in the rare threat simulation; however, it becomes costly to deal withmany rare threatssimultaneously. For example, a rare threat can be the failure to provide quality-of-service (QoS) guarantees to a critical network flow. Considering network providers often need to deal with many critical flows (i.e., rare threats) simultaneously, if using IS, network providers have to simulate each rare threat with its customized importance distribution individually. To reduce such simulation cost, we propose an efficient mixture importance distribution to simulate multiple rare threats, and then formulate a mixture importance sampling optimization problem (MISO) to select the optimal mixture. We first show that it is challenging to locate the optimal mixture for the “search direction” is computationally expensive to evaluate. We then formulate an online learning (OL) framework to estimate the “search direction” and learn the optimal mixture from simulation samples of threats. And our OL framework has a “zero learning cost” as the samples generated in the learn phase can be reused to provide accurate estimation on the rare threats. We develop two multi-armed bandit OL algorithms so as to: (1) Minimize the sum of estimation variances with a regret of$(\ln T)^2 {/} T$; and (2) Minimize the simulation cost with a regret of$\sqrt{\ln T {/} T}$, where$T$denotes the number of simulation samples. We demonstrate the versatility of our method on different network applications. When compared with the uniform mixture IS, our method reduces cost measures (i.e., sum of estimation variances and simulation cost) by as high as 61.6 percent in the Internet backbone network scenario.

Worker reliability estimation is a fundamental problem in crowdsensing applications. This paper proposes a robust feedback rating approach to estimate worker reliability explicitly. In this approach, the requester provides a feedback rating to reflect the quality of the sensor data submitted by each worker. The aggregation of each worker's historical feedback ratings serves as a reliability estimate. The challenges are:(1) Feedback ratings are subjected to noise; (2) Workers’ cognitive bias in task selection leads to sensor data quality variations.We develop a mathematical model to quantify rating noise from requesters and the degree of cognitive bias of workers in task selection. We derive sufficient conditions, under which the aggregate rating is asymptotically accurate in estimating worker reliability, via stochastic approximation techniques. These conditions identify a class of asymptotically accurate rating aggregation rules for crowdsensing applications. We further derive the minimum number of ratings needed to guarantee a given reliability estimation accuracy, via martingale theory. Via extensive experiments: (1) We reveal fundamental understandings on how various factors such as rating noise influence the minimum number of ratings needed to achieve certain accuracy; (2) We show that our feedback rating approach improves air quality index estimation accuracy by as high as 50 percent over the a typical baseline algorithm.

Upper confidence bound (UCB)-based contextual bandit algorithms require one to know the tail property of the reward distribution. Unfortunately, such tail property is usually unknown or difficult to specify in real-world applications. Using a tail property heavier than the ground truth leads to a slow learning speed of the contextual bandit algorithm, while using a lighter one may cause the algorithm to diverge. To address this fundamental problem, we develop an estimator (evaluated from historical rewards) for the contextual bandit UCB based on the multiplier bootstrap technique. Our proposed estimator mitigates the problem of specifying a heavier tail property by adaptively converging to the ground truth contextual bandit UCB (i.e., eliminating the impact of the specified heavier tail property) with theoretical guarantees on the convergence. The design and convergence analysis of the proposed estimator is technically nontrivial. The proposed estimator is generic and it can be applied to improve a variety of UCB-based contextual bandit algorithms. To demonstrate the versatility of the proposed estimator, we apply it to improve the linear reward contextual bandit UCB (LinUCB) algorithm resulting in our bootstrapping LinUCB (BootLinUCB) algorithm. We prove that the BootLinUCB has a sublinear regret. We conduct extensive experiments on both synthetic dataset and real-world dataset from Yahoo! to validate the benefits of our proposed estimator in reducing regret and the superior performance of BootLinUCB over the latest baseline.

Contextual bandit is a popular sequential decision-making framework to balance the exploration and exploitation tradeoff in many applications such as recommender systems, search engines, etc. Motivated by two important factors in real-world applications: 1) latent contexts (or features) often exist and 2) feedbacks often have humans in the loop leading to human biases, we formulate a generalized contextual bandit framework with latent contexts. Our proposed framework includes a two-layer probabilistic interpretable model for the feedbacks from human with latent features. We design a GCL-PS algorithm for the proposed framework, which utilizes posterior sampling to balance the exploration and exploitation tradeoff. We prove a sublinear regret upper bound for GCL-PS, and prove a lower bound for the proposed bandit framework revealing insights on the optimality of GCL-PS. To further improve the computational efficiency of GCL-PS, we propose a Markov Chain Monte Carlo (MCMC) algorithm to generate approximate samples, resulting in our GCL-PSMC algorithm. We not only prove a sublinear Bayesian regret upper bound for our GCL-PSMC algorithm, but also reveal insights into the tradeoff between computational efficiency and sequential decision accuracy. Finally, we apply the proposed framework to hotel recommendations and news article recommendations, and show its superior performance over a variety of baselines via experiments on two public datasets.

The Shapley value is a cornerstone in cooperative game theory and has been widely applied in networking, data science, etc. The classical Shapley value assumes that each player has an equal preference to cooperate with each other. Since the cooperation preference is an important factor of a variety of networking applications, we first generalize the classical Shapley value to allow general degree of the cooperation preference. In particular, we develop mathematical models to solicit two types of cooperation preferences, i.e., (1) group-wise preferences and (2) pair-wise preferences, and extend the classical Shapley value to capture this feature. Our second contribution is tackling the intrinsic computational challenge because even for the classical Shapley value, it is computationally expensive to evaluate. We design computationally efficient randomized algorithms with theoretical guarantees to fully cover the computational space of our generalized Shapley value. We also extend our models and algorithms to divide payoffs for multiple coalitions with dynamic preferences. We demonstrate the versatility of our framework by applying it to divide the revenue among ISPs in deploying new Internet architectures, as well as to divide the reward among workers in crowdsourcing systems.

We generalize the multiple-play multi-armed bandits (MP-MAB) problem with a shareable arms setting, in which several plays can share the same arm. Furthermore, each shareable arm has a finite reward capacity and a “per-load” reward distribution, both of which are unknown to the learner. The reward from a shareable arm is load-dependent, which is the “per-load” reward multiplying either the number of plays pulling the arm, or its reward capacity when the number of plays exceeds the capacity limit. When the “per-load” reward follows a Gaussian distribution, we prove a sample complexity lower bound of learning the capacity from load-dependent rewards and also a regret lower bound of this new MP-MAB problem. We devise a capacity estimator whose sample complexity upper bound matches the lower bound in terms of reward means and capacities. We also propose an online learning algorithm to address the problem and prove its regret upper bound. This regret upper bound’s first term is the same as regret lower bound’s, and its second and third terms also evidently correspond to lower bound’s. Extensive experiments validate our algorithm’s performance and also its gain in 5G & 4G base station selection.

Reposting plays an essential role in visibility boosting in online social networks (OSNs). In this paper, we study the problem of designing “reposting service” in an OSN to incentivize “transactions” between requesters (users who seek to enhance visibility) and suppliers (users who are willing to repost if certain incentives are given), and maximize the welfare increase accumulated through a given time horizon. We formulate a mathematical model for reposting which captures various factors like click through rates (CTRs), requesters' valuations and suppliers' costs. We formulate the problem of maximizing the welfare increase via judiciously assigning suppliers to requesters from two aspects: (a) “user-centric” and (b) “platform-centric”. The user-centric aspect deals with the situation where requesters and suppliers would collaborate and share valuations and costs. To address the challenge of unknown CTRs, we propose an online learning protocol and achieve a sub-linear regret. The platform-centric aspect corresponds to the scenario where users keep their valuations or costs private. To address the challenges of unknown CTR, valuations and costs, we design an “explore-then-commit” online protocol which can be proved to be truthful. Lastly, we conduct extensive experiments to evaluate the efficiency and effectiveness of the proposed protocols.

Multi-player multi-armed bandits (MMAB) study how decentralized players cooperatively play the same multi-armed bandit so as to maximize their total cumulative rewards. Existing MMAB models mostly assume when more than one player pulls the same arm, they either have a collision and obtain zero rewards or have no collision and gain independent rewards, both of which are usually too restrictive in practical scenarios. In this paper, we propose an MMAB with shareable resources as an extension of the collision and non-collision settings. Each shareable arm has finite shareable resources and a “per-load” reward random variable, both of which are unknown to players. The reward from a shareable arm is equal to the “per-load” reward multiplied by the minimum between the number of players pulling the arm and the arm’s maximal shareable resources. We consider two types of feedback: sharing demand information (SDI) and sharing demand awareness (SDA), each of which provides different signals of resource sharing. We design the DPE-SDI and SIC-SDA algorithms to address the shareable arm problem under these two cases of feedback respectively and prove that both algorithms have logarithmic regrets that are tight in the number of rounds. We conduct simulations to validate both algorithms’ performance and show their utilities in wireless networking and edge computing.

Contextual bandit serves as an invaluable tool to balance theexploration vs. exploitationtradeoff in various applications such as online recommendation. In many applications,heterogeneous information networks(HINs) provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this article, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users’ preference over items, the target of our online learning, are closely related to users’ preference over meta-paths. However, it is unknown which meta-path a user prefers more. Thus, both preferences are needed to be learned in an online fashion with exploration vs. exploitation tradeoff balanced. We propose the HIN-assisted upper confidence bound (HUCB) algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendations by leveraging the relationship captured in this meta-path. A bandit master is then employed to learn users’ preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration vs. exploitation tradeoff. We theoretically prove that the HUCB algorithm can achieve similar performance compared with the optimal algorithm where each user is served according to his true preference over meta-paths (assuming the optimal algorithm knows the preference). Moreover, we prove that the HUCB algorithm benefits from leveraging HIN in achieving a smaller regret upper bound than the baseline algorithm without leveraging HIN. Experimental results on a synthetic dataset, as well as real datasets from LastFM and Yelp demonstrate the fast learning speed of the HUCB algorithm.

In the past few years, many companies are considering “social recommendation” for their businesses, e.g., firms are offering rewards to customers who recommend the firms’ products/services in online social networks (OSNs). However, the pros and cons of such social recommendation scheme are still unclear. Thus, it is difficult for firms to design rewarding schemes, and for OSN platforms to design regulating policies. By analyzing real data from Weixin and Yelp, we first identify key factors that affect the spreading of products/services in OSNs. These findings enable us to develop an accurate (i.e., with a high validation accuracy) mathematical model on social recommendations. Our model captures how users decide whether to recommend an item, which is a key factor but often ignored by previous social recommendation models such as the “Independent Cascade model”. We also design algorithms to infer model parameters. Using our model, we uncover conditions when social recommendation improves a firm’s profit and users’ utilities, as well as when it cannot improve the profit or hurts users’ utilities. These conditions help the design of both rewarding schemes and regulating policies. Moreover, we extend our model to a dynamic setting, so that a firm can improve its profit by dynamically optimizing its rewarding schemes.

How to generate more revenues is crucial to cloud providers. Evidences from the Amazon cloud system indicate that "dynamic pricing" would be more profitable than "static pricing." The challenges are: How to set the price in real-time so to maximize revenues? How to estimate the price dependent demand so to optimize the pricing decision? We first design a discrete-time based dynamic pricing scheme and formulate a Markov decision process to characterize the evolving dynamics of the price-dependent demand. We formulate a revenue maximization framework to determine the optimal price and theoretically characterize the "structure" of the optimal revenue and optimal price. We apply the Q -learning to infer the optimal price from historical transaction data and derive sufficient conditions on the model to guarantee its convergence to the optimal price, but it converges slowly. To speed up the convergence, we incorporate the structure of the optimal revenue that we obtained earlier, leading to the VpQ-learning ( Q -learning with value projection) algorithm. We derive sufficient conditions, under which the VpQ-learning algorithm converges to the optimal policy. Experiments on a real-world dataset show that the VpQ-learning algorithm outperforms a variety of baselines, i.e., improves the revenue by as high as 50% over the Q -learning, speedy Q -learning, and adaptive real-time dynamic programming (ARTDP), and by as high as 20% over the fixed pricing scheme.

Traditional graph systems mainly use the iteration-based model, which iteratively loads graph blocks into memory for analysis so as to reduce random I/Os. However, this iteration-based model limits the efficiency and scalability of running random walk, which is a fundamental technique to analyze large graphs. In this article, we first propose a state-aware I/O model to improve the I/O efficiency of running random walk, then we develop a block-centric indexing and buffering scheme for managing walk data, and leverage an asynchronous walk updating strategy to improve random walk efficiency. We implement an I/O-efficient graph system, GraphWalker , which is efficient to handle very large disk-resident graphs and also scalable to run tens of billions of random walks with only a single commodity machine. Experiments show that GraphWalker can achieve more than an order of magnitude speedup when compared with DrunkardMob, which is tailored for random walks based on the classical graph system GraphChi, as well as two state-of-the-art single-machine graph systems, Graphene and GraFSoft. Furthermore, when compared with the most recent distributed system KnightKing, GraphWalker still achieves comparable performance with only a single machine, thereby making it a more cost-effective alternative.

In online social networks (OSNs), users may want to enhance their social visibility, as it can make their contents, i.e., opinions, videos, pictures, etc., attract attention from more users. Motivated by this, we propose a mechanism, where the OSN operator provides a "social visibility boosting service" to incentivize "transactions" between requesters (users who seek to enhance their social visibility via adding new "neighbors") and suppliers (users who are willing to be added as a new "neighbor" of any requester when certain "rewards" is provided). We design a posted pricing scheme for the OSN provider to charge the requesters who use such boosting service, and reward the suppliers who contribute to such boosting service. The OSN operator keeps a fraction of the payment from requesters and distributes the remaining part to participating suppliers "fairly" via a scheme based on the Shapley value. The objective of the OSN provider is to select the price and supplier set to maximize the revenue under the budget constraint of requesters. We first show that the revenue maximization problem is not simpler than an NP-hard problem. We then decompose it into two subroutines, prove the hardness of each sub-routine, and eventually design computationally efficient approximation algorithms to solve the revenue maximization problem. We conduct extensive experiments to evaluate our proposed algorithms.

Graphs are commonly used in various applications such as online social networks (OSNs), E-commerce systems and social recommender systems. Random walk sampling is often used to conduct statistical estimation over such graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. A new feature of this bias reduction algorithm is that it allows the variance to increase whenever the bias can be further reduced. The increased variance may lead to a large mean square error of the estimator. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. Our algorithmic framework enables one to attain different trade-offs between the sample complexity (i.e., number of parallel random walks) and the mean square error of the statistical estimation. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. To demonstrate the versatility of the framework, we apply it to optimize the Metropolis random walk and simple random walk sampling. Extensive experiments confirm the effectiveness and efficiency of our proposed algorithmic framework.

Contextual bandit serves as an invaluable tool to balance the exploration vs. exploitation trade-off in various applications like online recommendation. In many applications, heterogeneous information network (HIN) can be derived to provide rich side information for contextual bandits, such as different types of attributes and relationships among users and items. In this paper, we propose the first HIN-assisted contextual bandit framework, which utilizes a given HIN to assist contextual bandit learning. The proposed framework uses meta-paths in HIN to extract rich relations among users and items for the contextual bandit. The main challenge is how to leverage these relations, since users' preference over items, the target of our online learning, are closely related to users' preference over meta-paths, however it is unknown which meta-path a user prefers more. We propose the HUCB algorithm to address such a challenge. For each meta-path, the HUCB algorithm employs an independent base bandit algorithm to handle online item recommendation by leveraging the relationship captured in this meta-path. The bandit master is then employed to learn users' preference over meta-paths to dynamically combine base bandit algorithms with a balance of exploration-exploitation trade-off. Experimental results on real datasets from LastFM and Yelp demonstrate the efficacy of the HUCB algorithm.

Online social network (OSN) is an ideal venue to enhance one's visibility. This paper considers how a user (called requester) in an OSN selects a small number of available users and invites them as new friends/followers so as to maximize his "social visibility". More importantly, the requester has to do this under the anonymity setting, which means he is not allowed to know the neighborhood information of these available users in the OSN. In this paper, we first develop a mathematical model to quantify the social visibility and formulate the problem of visibility maximization with anonymity guarantee, abbreviated as "VisMAX-A". Then we design an algorithmic framework named as "AdaExp", which adaptively expands the requester's visibility in multiple rounds. In each round of the expansion, AdaExp uses a query oracle with anonymity guarantee to select only one available user. By using probabilistic data structures like the k-minimum values (KMV) sketch, we design an efficient query oracle with anonymity guarantees. We also conduct experiments on real-world social networks and validate the effectiveness of our algorithms.

Utilizing offline logged data to improve sequential or online decision making is drawing more and more attention. VirUCB is one of the latest notable algorithmic framework in this research line, and it has both sound theoretical guarantee and nice empirical performance. However, regarding VirUCB, it is still unclear: (1) how imbalanced offline logged data influences the decision making accuracy; (2) how to schedule offline logged data across the decision making horizon so as to reduce offline logged data consumption. We show that with imbalanced offline logged data, VirUCB can have a learning speed slower than the baseline algorithm without offline logged data. This finding inspires us to design RobVirUCB algorithm, which is robust against such imbalanced data, i.e., still maintains a fast learning speed. RobVirUCB adaptively selects “useful” offline logged data to speed up learning and it has theoretical guarantees on regret. Finally, we design EffVirUCB algorithm, which reduces offline logged data consumption of RobVirUCB. EffVirUCB schedules the offline logged data to the decision round that the decision maker may select suboptimal arms and it has theoretical guarantees on regret. Extensive experiments on both synthetic data and real-world data validate the superior performance of RobVirUCB and EffVirUCB.

Online rating system serves as an indispensable building block for many web applications such as Amazon, TripAdvior and Yelp. It enables production quality estimation via aggregate ratings (a.k.a. wisdom of the crowd) as well as product recommendation via inferring user preference from ratings, etc. Previous studies showed that due to assimilate-contrast effects, historical ratings can significantly distort user's ratings, leading to low accuracy of product quality estimation and recommendation. To understand assimilate-contrast effects, an "accurate'' model is still missing as previous models do not capture important factors like rating recency, selection bias, etc. Furthermore, an analytical framework to characterize product estimation accuracy under assimilate-contrast effects is also missing. This paper aims to fill in this gap. We propose a mathematical model to quantify the aforementioned important factors on assimilate-contrast effects. Our model attains a good balance between model complexity and model accuracy, such that it is neat enough for us to develop an analytical framework to study assimilate-contrast effects. Based on our model, we derive sufficient conditions, under which the product estimation and collective opinion converges to the "ground-truth''. These conditions reveal important insights on how the aforementioned factors influence the convergence and guide the online rating system operator to design appropriate rating aggregation rules and rating displaying strategies. To demonstrate the versatility of our model, we apply to rating prediction tasks and product recommendation tasks. Experiment results on four public datasets show that our model can improve the rating prediction and and recommendation accuracy over previous models significantly.

A fundamental question for companies with large amount of logged data is: How to use such logged data together with incoming streaming data to make good decisions? Many companies currently make decisions via online A/B tests, but wrong decisions during testing hurt users’ experiences and cause irreversible damage. A typical alternative is offline causal inference, which analyzes logged data alone to make decisions. However, these decisions are not adaptive to the new incoming data, and so a wrong decision will continuously hurt users’ experiences. To overcome the aforementioned limitations, we propose a framework to unify offline causal inference algorithms (e.g., weighting, matching) and online learning algorithms (e.g., UCB, LinUCB). We propose novel algorithms and derive bounds on the decision accuracy via the notion of “regret”. We derive the first upper regret bound for forest-based online bandit algorithms. Experiments on two real datasets show that our algorithms outperform other algorithms that use only logged data or online feedbacks, or algorithms that do not use the data properly.

Finding the set of most influential users in online social networks (OSNs) to trigger the largest influence cascade is meaningful, e.g., companies may leverage the “word-of-mouth” effect to trigger a large cascade of purchases by offering free samples/discounts to those most influential users. This task is usually modeled as an influence maximization problem, and it has been widely studied in the past decade. However, considering that users in OSNs may participate in various online activities, e.g., joining discussion groups and commenting on same pages or products, influence diffusion through online activities becomes even more significant. In this article, we study the impact of online activities by formulating social-activity networks which contain both users and online activities, and thus induce two types of weighted edges, i.e., edges between users and edges between users and activities. To address the computation challenge, we define an influence centrality via random walks, and use the Monte Carlo framework to efficiently estimate the centrality. Furthermore, we develop a greedy-based algorithm with novel optimizations to find the most influential users for node recommendation. Experiments on real-world datasets show that our approach is very computationally efficient under different influence models, and also achieves larger influence spread by considering online activities.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google Play Store, and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “ message-based persuasion ” lead to “ biased ” product ratings in a cascading manner (we call this the persuasion cascade ). This article investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on both synthetic data and real-world data from Amazon and TripAdvisor. Experiment results show that our inference algorithm has a high accuracy. Furthermore, persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

Online rating systems are often used in numerous web or mobile applications, e.g., Amazon and TripAdvisor, to assess the ground-truth quality of products. Due to herding effects, the aggregation of historical ratings (or historical collective opinion) can significantly influence subsequent ratings, leading to misleading and erroneous assessments. We study how to manage product ratings via rating aggregation rules and shortlisted representative reviews, for the purpose of correcting the assessment error. We first develop a mathematical model to characterize important factors of herding effects in product ratings. We then identify sufficient conditions (via the stochastic approximation theory), under which the historical collective opinion converges to the ground-truth collective opinion of the whole user population. These conditions identify a class of rating aggregation rules and review selection mechanisms that can reveal the ground-truth product quality. We also quantify the speed of convergence (via the martingale theory), which reflects the efficiency of rating aggregation rules and review selection mechanisms. We prove that the herding effects slow down the speed of convergence while an accurate review selection mechanism can speed it up.

Importance sampling (IS) is widely used in rare event simulation, but it is costly to deal with many rare events simultaneously. For example, a rare event can be the failure to provide the quality-of-service guarantee for a critical network flow. Since network providers often need to deal with many critical flows (i.e., rare events) simultaneously, if using IS, providers have to simulate each rare event with its customized importance distribution individually. To reduce such cost, we propose an efficient mixture importance distribution for multiple rare events, and formulate the mixture importance sampling optimization problem (MISOP) to select the optimal mixture. We first show that the "search direction" of mixture is computationally expensive to evaluate, making it challenging to locate the optimal mixture. We then formulate a " zero learning cost " online learning framework to estimate the "search direction", and learn the optimal mixture from simulation samples of events. We develop two multi-armed bandit online learning algorithms to: (1) Minimize the sum of estimation variances with a regret of (ln T)2/T; (2) Minimize the simulation cost with a regret of √ln T/T , where T denotes the number of simulation samples. We demonstrate our method on a realistic network and show that it can reduce the cost measures (i.e., sum of estimation variances and simulation cost) by as high as 61.6% compared with the uniform mixture IS.

Contextual bandit algorithms provide principled online learning solutions to balance the exploitation-exploration trade-off in various applications such as recommender systems. However, the learning speed of the traditional contextual bandit algorithms is often slow due to the need for extensive exploration. This poses a critical issue in applications like recommender systems, since users may need to provide feedbacks on a lot of uninterested items. To accelerate the learning speed, we generalize contextual bandit to conversational contextual bandit. Conversational contextual bandit leverages not only behavioral feedbacks on arms (e.g., articles in news recommendation), but also occasional conversational feedbacks on key-terms from the user. Here, a key-term can relate to a subset of arms, for example, a category of articles in news recommendation. We then design the Conversational UCB algorithm (ConUCB) to address two challenges in conversational contextual bandit: (1) which key-terms to select to conduct conversation, (2) how to leverage conversational feedbacks to accelerate the speed of bandit learning. We theoretically prove that ConUCB can achieve a smaller regret upper bound than the traditional contextual bandit algorithm LinUCB, which implies a faster learning speed. Experiments on synthetic data, as well as real datasets from Yelp and Toutiao, demonstrate the efficacy of the ConUCB algorithm.

“Unbiasedness,” which is an important property to ensure that users’ ratings indeed reflect their true evaluations of products, is vital both in shaping consumer purchase decisions and providing reliable recommendations in online rating systems. Recent experimental studies showed that distortions from historical ratings would ruin the unbiasedness of subsequent ratings. How to “discover” historical distortions in each single rating (or at the micro-level), and perform the “debiasing operations” are our main objective. Using 42M real customer ratings, we first show that users either “assimilate” or “contrast” to historical ratings under different scenarios, which can be further explained by a well-known psychological argument: the “Assimilate-Contrast” theory. This motivates us to propose the Historical Influence Aware Latent Factor Model (HIALF), the “first” model for real rating systems to capture and mitigate historical distortions in each single rating. HIALF allows us to study the influence patterns of historical ratings from a modelling perspective, which perfectly matches the assimilation and contrast effects observed in experiments. Moreover, HIALF achieves significant improvements in predicting subsequent ratings and characterizing relationships in ratings. It also contributes to better recommendations, wiser consumer purchase decisions, and deeper understanding of historical distortions in both honest rating and misbehaving rating settings.

Feedback-based reputation systems are widely deployed in E-commerce systems. Evidence shows that earning a reputable label (for sellers of such systems) may take a substantial amount of time, and this implies a reduction of profit. We propose to enhance sellers’ reputation via price discounts. However, the challenges are as follows: (1) The demands from buyers depend on both the discount and reputation, and (2) the demands are unknown to the seller. To address these challenges, we first formulate a profit maximization problem via a semi-Markov decision process to explore the optimal tradeoffs in selecting price discounts. We prove the monotonicity of the optimal profit and optimal discount. Based on the monotonicity, we design a Q-learning with forward projection (QLFP) algorithm, which infers the optimal discount from historical transaction data. We prove that the QLFP algorithm convergences to the optimal policy. We conduct trace-driven simulations using a dataset from eBay to evaluate the QLFP algorithm. Evaluation results show that QLFP improves the profit by as high as 50% over both Q-learning and Speedy Q-learning. The QLFP algorithm also improves both the reputation and profit by as high as two times over the scheme of not providing any price discount.

Emerging new applications demand the current Internet to provide new functionalities. Although many future Internet architectures and protocols have been proposed to fulfill such needs, ISPs have been reluctant to deploy many of these architectures. We believe technical issues are not the main reasons as many of these new proposals are technically sound. In this paper, we take an economic perspective and seek to answer: Why do most new Internet architectures fail to be deployed? How can the deployability of a new architecture be enhanced? We develop a game-theoretic model to characterize the outcome of an architecture's deployment through the equilibrium of ISPs' decisions. This model enables us to: (1) analyze several key factors of the deployability of a new architecture such as the number of critical ISPs and the change of routing path; (2) explain the deploying outcomes of some previously proposed architectures/protocols such as IPv6, DiffServ, CDN, etc., and shed light on the “Internet flattening phenomenon”; (3) predict the deployability of a new architecture such as NDN, and compare its deployability with competing architectures. Our study suggests that the difficulty to deploy a new Internet architecture comes from the “coordination” of distributed ISPs. Finally, we design a mechanism to enhance the deployability of new architectures.

Online reputation systems serve as core building blocks in various Internet services such as E-commerce (e.g., eBay) and crowdsourcing (e.g., oDesk). The flaws and deficiencies of real-world online reputation systems have been reported extensively. Users who are frustrated about the system will eventually abandon such service. However, there is no systematic and formal studies which examine such deficiencies. This paper presents the first attempt, which develops a novel data analytical framework to uncover online reputation system deficiencies from data. We develop two novel measures to quantify the efficiency of online reputation systems: (1) ramp up time of a new service provider, (2) long term profit gains for a service provider. We present a new data analytical framework to evaluate these two measures from data. We show that inherent preferences or personal biases in expressing feedbacks (or ratings) cause the computational infeasibility in evaluating the ramp up time and the long term profit gains from data. We develop two computationally efficient randomized algorithms with theoretical performance guarantees to address this computational challenge. We apply our methodology to analyze real-life datasets (from eBay, Google Helpouts, Amazon and TripAdvisor). We extensively validate our model and we uncover the deficiencies of online reputation systems. Our experimental results uncovers insights on why Google Helpouts was eventually shut down in April 2015 and why eBay is losing some sellers heavily.

Online product rating systems have become an indispensable component for numerous web services such as Amazon, eBay, Google play store and TripAdvisor. One functionality of such systems is to uncover the product quality via product ratings (or reviews) contributed by consumers. However, a well-known psychological phenomenon called “messagebased persuasion” lead to “biased” product ratings in a cascading manner (we call this the persuasion cascade). This paper investigates: (1) How does the persuasion cascade influence the product quality estimation accuracy? (2) Given a real-world product rating dataset, how to infer the persuasion cascade and analyze it to draw practical insights? We first develop a mathematical model to capture key factors of a persuasion cascade. We formulate a high-order Markov chain to characterize the opinion dynamics of a persuasion cascade and prove the convergence of opinions. We further bound the product quality estimation error for a class of rating aggregation rules including the averaging scoring rule, via the matrix perturbation theory and the Chernoff bound. We also design a maximum likelihood algorithm to infer parameters of the persuasion cascade. We conduct experiments on the data from Amazon and TripAdvisor, and show that persuasion cascades notably exist, but the average scoring rule has a small product quality estimation error under practical scenarios.

Feedback-based reputation systems are widely deployed in E-commerce systems. Evidences showed that earning a reputable label (for sellers of such systems) may take a substantial amount of time and this implies a reduction of profit. We propose to enhance sellers’ reputation via price discounts. However, the challenges are: (1) The demands from buyers depend on both the discount and reputation; (2) The demands are unknown to the seller. To address these challenges, we first formulate a profit maximization problem via a semiMarkov decision process (SMDP) to explore the optimal trade-offs in selecting price discounts. We prove the monotonicity of the optimal profit and optimal discount. Based on the monotonicity, we design a QLFP (Q-learning with forward projection) algorithm, which infers the optimal discount from historical transaction data. We conduct experiments on a dataset from to show that our QLFP algorithm improves the profit by as high as 50% over both the classical Q-learning and speedy Q-learning algorithm. Our QLFP algorithm also improves the profit by as high as four times over the case of not providing any price discount.

Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow convergence rate (a.k.a. long burn-in period). To address this issue, we propose a common neighbor aware random walk framework called CNARW, which leverages weighted walking by differentiating the next-hop candidate nodes to speed up the convergence. Specifically, CNARW takes into consideration the common neighbors between previously visited nodes and next-hop candidate nodes in each walking step. Based on CNARW, we further develop two efficient "unbiased sampling" schemes. Experimental results on real-world network datasets show that our approach converges remarkably faster than the state-of-the-art random walk sampling algorithms. Furthermore, to achieve the same estimation accuracy, our approach reduces the query cost (a measure of sampling budget) significantly. Lastly, we also use two case studies to demonstrate the effectiveness of our sampling framework in solving large-scale graph analysis tasks.

Firms are now considering to offer rewards to customers who recommend the firms' products/services in online social networks (OSN). However, the pros and cons of such social recommendation scheme are still unclear. Thus, it is difficult for firms to design rewarding schemes. Via empirical analysis of data, we first identify key factors that affect the spreading of a firm's product in OSNs. These findings enable us to develop an accurate (i.e., with a high validation accuracy) mathematical model on social recommendations. In particular, our model captures how users decide whether to recommend an item, which is a key factor but often ignored by previous social recommendation models such as the "Independent Cascade model". We also design algorithms to infer model parameters. Using these parameters in our model, we uncover conditions when social recommendation can (or cannot) improves a firm's profit. These conditions help a firm to design rewarding schemes. Finally, we extend our model to an online setting and design reinforcement learning algorithms for a firm to dynamically optimize its rewarding schemes.

Various differentiated pricing schemes have been proposed for the Internet market. Aiming at replacing the traditional single-class pricing for better welfare, yet, researchers have shown that existing schemes can bring only marginal profit gain for the ISPs. In this article, we point out that a proper form of differentiated pricing for the Internet should not only consider congestion, but more importantly, it should provide application specific treatment to data delivery. Formally, we propose an “application-driven pricing” approach, where an ISP offers a number of service classes in terms of a guaranteed quality of service and announces a unit usage price for each class, and content providers are free to choose which class to use depending on the requirement of their applications. Unlike previous studies, we point out that the revenue gain of multi-class pricing under our scheme can be significant. This is because we capture important aspects of application heterogeneity and take the quality of service and price as control knobs. We identify key factors that impact the revenue gain and reveal fundamental understandings on when and why an application-driven multi-class pricing can significantly increase the revenue of ISPs.

Emerging new applications demand the current Internet to provide new functionalities. Although many future Internet architectures and protocols have been proposed to fulfill such needs, ISPs have been reluctant to deploy these architectures. We believe technical issues are not the main reasons as many of these new proposals are technically sound. In this paper, we take an economic perspective and seek to answer: Why most new Internet architectures failed to be deployed? What makes a new architecture easier to deploy? We develop a game-theoretic model to characterize the outcome of an architecture's deployment through the equilibrium of ISP's decisions. We also use our model to explain the deploying outcomes of IPv6, DiffServ, CDN, etc., and the "Internet flattening phenomenon". Furthermore, one can use our model to predict the deployability of new architectures such as NDN, XIA, and compare the deployability of competing architectures. Our study also suggests that the architectures which try to make a fresh start may have a low deployability, unless they have efficient incremental deployment mechanisms or one introduces a centralized coordinator to help the deployment.

Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users' activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop the social and activity network (SAN), a two-layer hyper-graph that unifies users' friendships and their activities, to fully utilize users' activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil SAN, and derive the number of rounds needed to guarantee the convergence. We use "matrix perturbation theory" to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy.

The unbiasedness of online product ratings, an important property to ensure that users’ ratings indeed reflect their true evaluations to products, is vital both in shaping consumer purchase decisions and providing reliable recommendations. Recent experimental studies showed that distortions from historical ratings would ruin the unbiasedness of subsequent ratings. How to “discover” the distortions from historical ratings in each single rating (or at the micro-level), and perform the “debiasing operations” in real rating systems are the main objectives of this work. Using 42 million real customer ratings, we first show that users either “assimilate” or “contrast” to historical ratings under different scenarios: users conform to historical ratings if historical ratings are not far from the product quality (assimilation), while users deviate from historical ratings if historical ratings are significantly different from the product quality (contrast). This phenomenon can be explained by the well-known psychological argument: the “Assimilate-Contrast” theory. However, none of the existing works on modeling historical ratings’ influence have taken this into account, and this motivates us to propose the Histori- cal Influence Aware Latent Factor Model (HIALF), the first model for real rating systems to capture and mitigate historical distortions in each single rating. HIALF also allows us to study the influence patterns of historical ratings from a modeling perspective, and it perfectly matches the assimilation and contrast effects we previously observed. Also, HIALF achieves significant improvements in predicting subsequent ratings, and accurately predicts the relationships revealed in previous empirical measurements on real ratings. Finally, we show that HIALF can contribute to better recommendations by decoupling users’ real preference from distorted ratings, and reveal the intrinsic product quality for wiser consumer purchase decisions.

Reputation systems have become an indispensable component of modern E-commerce systems, as they help buyers make informed decisions in choosing trustworthy sellers. To attract buyers and increase the transaction volume, sellers need to earn reasonably high reputation scores. This process usually takes a substantial amount of time. To accelerate this process, sellers can provide price discounts to attract users, but the underlying difficulty is that sellers have no prior knowledge on buyers’ preferences over price discounts. In this article, we develop an online algorithm to infer the optimal discount rate from data. We first formulate an optimization framework to select the optimal discount rate given buyers’ discount preferences, which is a tradeoff between the short-term profit and the ramp-up time (for reputation). We then derive the closed-form optimal discount rate, which gives us key insights in applying a stochastic bandits framework to infer the optimal discount rate from the transaction data with regret upper bounds. We show that the computational complexity of evaluating the performance metrics is infeasibly high, and therefore, we develop efficient randomized algorithms with guaranteed performance to approximate them. Finally, we conduct experiments on a dataset crawled from eBay. Experimental results show that our framework can trade 60% of the short-term profit for reducing the ramp-up time by 40%. This reduction in the ramp-up time can increase the long-term profit of a seller by at least 20%.

Mining the characteristics of information spreading in networks is crucial in communication studies, network security management, epidemic investigations, etc. Previous works are restrictive because they mainly focused on the information source detection using either a single observation, or multiple but independent observations of the underlying network while assuming a homogeneous information spreading rate. We conduct a theoretical and experimental study on information spreading, and propose a new and novel estimation framework to estimate 1) information spreading rates, 2) start time of the information source, and 3) the location of information source by utilizing multiple sequential and dependent snapshots where information can spread at heterogeneous rates. Our framework generalizes the current state-of-the-art rumor centrality [1] and the union rumor centrality [2]. Furthermore, we allow heterogeneous information spreading rates at different branches of a network. Our framework provides conditional maximum likelihood estimators for the above three metrics and is more accurate than rumor centrality and Jordan center in both synthetic networks and real-world networks. Applying our framework to the Twitter's retweet networks, we can accurately determine who made the initial tweet and at what time the tweet was sent. Furthermore, we also validate that the rates of information spreading are indeed heterogeneous among different parts of a retweet network.

Macrotasking crowdsourcing systems like Elance and Fiverr serve as efficient platforms for requesters to outsource challenging and innovative tasks that require special skills to workers. It is widely practiced in such systems that requesters reward workers based on requesters' assessment on solution quality. The challenge is that requesters' assessment may not be accurate to reflect the intrinsic quality of a solution due to human factors like personal preferences or biases. In this work, we consider answering the following questions: How to design a mechanism to incentivize workers provide high quality solutions in the presence of such human factors? How to formally study the impact of human factors on workers' financial incentive to participate? We design a mechanism to incentivize workers to provide high-quality contributions, which is robust to human factors. Our incentive mechanism consists of a “task bundling scheme” and a “rating system”, which reward workers based on requesters' rating on the solution quality. We propose a probabilistic model to capture human factors, and quantify their impact on the incentive mechanism. We formulate an optimization framework to select appropriate rating system parameters, which can be viewed as a tradeoff between “system efficiency”, i.e., the total number of tasks can be solved given a fixed reward budget, and the “rating system complexity”, which determines the human cognitive cost and time in expressing ratings. We also formulate an optimization framework to select appropriate bundling size, which can tradeoff system efficiency against service delay (i.e., the waiting time to form a task bundle). Finally, we conduct experiments on a dataset from Elance. Experimental results show that our incentive mechanism achieves at least 99.95 percent of the theoretical maximum system efficiency with a service delay of at most 2.3639 hours. Furthermore, we discover that the rating system in Elance is too complex, and it should be simplified to a binary rating system (i.e., two rating points).

Product bundling is widely adopted for information goods and online services because it can increase profit for companies. For example, cable companies often bundle Internet access and video streaming services together. However, it is challenging to obtain an optimal bundling strategy, not only because it is computationally expensive, but also that customers’ private information (e.g., valuations for products) is needed for the decision, and we need to infer it from accessible datasets. As customers’ purchasing data are getting richer due to the popularity of online shopping, doors are open for us to infer this information. This paper aims to address: (1) How to infer customers’ valuations from the purchasing data? (2) How to determine the optimal product bundle to maximize the profit? We first formulate a profit maximization framework to select the optimal bundle set. We show that finding the optimal bundle set is NPhard. We then identify key factors that impact the profitability of product bundling. These findings give us insights to develop a computationally efficient algorithm to approximate the optimal product bundle with a provable performance guarantee. To obtain the input of the bundling algorithm, we infer the distribution of customers’ valuations from their purchasing data, based on which we run our bundling algorithm and conduct experiments on an Amazon co-purchasing dataset. We extensively evaluate the accuracy of our inference and the bundling algorithm. Our results reveal conditions under which bundling is highly profitable and provide insights to guide the deployment of product bundling.

We develop an optimization framework to trade short-term profits for reputation (i.e., reducing ramp-up time). We apply the stochastic bandits framework to design an online discounting mechanism which infers the optimal discount from a seller's historical transaction data. We conduct experiments on an eBay's dataset and show that our online discounting mechanism can trade 60% of the shortterm profits for reducing the ramp-up time by 40%.

We present a novel insurance mechanism consisting of an insurance protocol and a transaction mechanism to reduce new seller ramp up time in eBay-like reputation mechanisms. We conduct experiments on an eBay's dataset and show that our insurance mechanism reduces ramp up time by 90%.

Online reputation systems serve as core building blocks in various Internet services such as E-commerce (e.g. eBay) and crowdsourcing (e.g., oDesk). The flaws of real-world online reputation systems were reported extensively. Users who are frustrated about the system will eventually abandon such service. However, no formal studies have explored such flaws. This paper presents the first attempt, which develops a novel data analytical framework to uncover online reputation system deficiencies from data. We develop a novel measure to quantify the efficiency of online reputation systems, i.e., ramp up time of a new service provider. We first show that inherent preferences or personal biases in assigning feedbacks (or ratings) cause the computational infeasibility in evaluating online reputation systems from data. We develop a computationally efficient randomized algorithm with theoretical performance guarantees to address this computational challenge. We apply our methodology to real-life datasets (from eBay and Google Helpouts), we discover that the ramp up time in eBay and Google Helpouts are around 791 and 1,327 days respectively. Around 78.7% sellers have ramped up in eBay and only 1.5% workers have ramped up in Google Helpouts. This small fraction and the long ramp up time (1,327 days) explain why Google Helpouts was eventually shut down in April 2015.

Nowadays, online crowdsourcing services are quite common such as Amazon Mechanical Turk and Google Helpouts. For such online services, it is important to attract "workers" to provide high-quality solutions to the "tasks" outsourced by "requesters". We present a unified study of incentive and reputation mechanisms for online crowdsourcing systems. We first design an mechanism to incentivize workers provide their maximum effort, which allows multiple workers to solve a task, splits the reward among workers based on requester evaluations of the solution quality. We design a reputation mechanism, which ensures that low-skilled workers do not provide low-quality solutions by tracking workers' historical contributions, and penalizing those workers having poor reputation. We show that our incentive and reputation mechanisms are robust against human biases in solution quality evaluation.

Many Web services like Amazon, Epinions, and TripAdvisor provide historical product ratings so that users can evaluate the quality of products. Product ratings are important because they affect how well a product will be adopted by the market. The challenge is that we only have partial information on these ratings: each user assigns ratings to only a small subset of products. Under this partial information setting, we explore a number of fundamental questions. What is the minimum number of ratings a product needs so that one can make a reliable evaluation of its quality? How may users’ misbehavior, such as cheating in product rating, affect the evaluation result? To answer these questions, we present a probabilistic model to capture various important factors (e.g., rating aggregation rules, rating behavior) that may influence the product quality assessment under the partial information setting. We derive the minimum number of ratings needed to produce a reliable indicator on the quality of a product. We extend our model to accommodate users’ misbehavior in product rating. We derive the maximum fraction of misbehaving users that a rating aggregation rule can tolerate and the minimum number of ratings needed to compensate. We carry out experiments using both synthetic and real-world data (from Amazon and TripAdvisor). We not only validate our model but also show that the “average rating rule” produces more reliable and robust product quality assessments than the “majority rating rule” and the “median rating rule” in aggregating product ratings. Last, we perform experiments on two movie rating datasets (from Flixster and Netflix) to demonstrate how to apply our framework to improve the applications of recommender systems.

Crowd sourcing systems like Yahoo! Answers, Amazon Mechanical Turk, and Google Helpouts, etc., have seen an increasing prevalence in the past few years. The participation of users, high quality solutions, and a fair rating system are critical to the revenue of a crowd sourcing system. In this paper, we design a class of simple but effective incentive mechanisms to attract users participating, and providing high quality solutions. Our incentive mechanism consists of a task bundling scheme and a rating system, and pay workers according to solution ratings from requesters. We also propose a probabilistic model to capture various human factors like biases in rating, and we quantify its impact on the incentive mechanism, which is shown to be highly robust. We develop a model to characterize the design space of a class of commonly used rating systems - threshold based rating systems. We quantify the impact of such rating systems and the bundling scheme on the incentive mechanism.

Given the globalized economy, how to process the heterogeneous web data so to extract customers' purchase behavior is crucial to manufacturers who want to enter or sustain in a competitive market. To maximize the sales, manufacturers not only need to decide what products to produce so to meet diverse customers' requirements, but at the same time, compete with competitors' products. In this paper, we present a general framework for the following product selection problems: (1) k-BSP problem, which is for a manufacturer to enter a competitive market, and (2) k-BBP problem, which is for a manufacturer to sustain in a competitive market. We propose several product adoption models to describe the complex purchase behavior of customers, and formally show that these problems are NP-hard in general. To tackle these problems, we propose computationally efficient greedy-based approximation algorithms. Based on the submodularity analysis, we prove that our algorithms can guarantee a (1--1/e)-approximation ratio as compared to the optimal solutions. We perform large scale data analysis to show the efficiency and accuracy of our framework. In our experiments, we observe 1,300 to 250,000 times speedup as compared to the exhaustive algorithms, and our solutions can achieve on average 96% of solution quality as compared to the optimal solutions. Finally, we apply our algorithms on web dataset to show the impact of customers' different purchase behavior on the results of product selection.