Inductive knowledge graph completion (KGC) aims to predict missing triples with unseen entities. Recent works focus on modeling reasoning paths between the head and tail entity as direct supporting evidence. However, these methods depend heavily on the existence and quality of reasoning paths, which limits their general applicability in different scenarios. In addition, we observe that latent type constraints and neighboring facts inherent in KGs are also vital in inferring missing triples. To effectively utilize all useful information in KGs, we introduce CATS, a novel context-aware inductive KGC solution. With sufficient guidance from proper prompts and supervised fine-tuning, CATS activates the strong semantic understanding and reasoning capabilities of large language models to assess the existence of query triples, which consist of two modules. First, the type-aware reasoning module evaluates whether the candidate entity matches the latent entity type as required by the query relation. Then, the subgraph reasoning module selects relevant reasoning paths and neighboring facts, and evaluates their correlation to the query triple. Experiment results on three widely used datasets demonstrate that CATS significantly outperforms state-of-the-art methods in 16 out of 18 transductive, inductive, and few-shot settings with an average absolute MRR improvement of 7.2%.

Existing frameworks for evaluating and comparing generative models consider an offline setting, where the evaluator has access to large batches of data produced by the models. However, in practical scenarios, the goal is often to identify and select the best model using the fewest possible generated samples to minimize the costs of querying data from the sub-optimal models. In this work, we propose an online evaluation and selection framework to find the generative model that maximizes a standard assessment score among a group of available models. We view the task as a multi-armed bandit (MAB) and propose upper confidence bound (UCB) bandit algorithms to identify the model producing data with the best evaluation score that quantifies the quality and diversity of generated data. Specifically, we develop the MAB-based selection of generative models considering the Fr{é}chet Distance (FD) and Inception Score (IS) metrics, resulting in the FD-UCB and IS-UCB algorithms. We prove regret bounds for these algorithms and present numerical results on standard image datasets. Our empirical results suggest the efficacy of MAB approaches for the sample-efficient evaluation and selection of deep generative models. The project code is available at \url{https://github.com/yannxiaoyanhu/dgm-online-eval}.

Selecting a sample generation scheme from multiple prompt-based generative models, including large language models (LLMs) and prompt-guided image and video generation models, is typically addressed by choosing the model that maximizes an averaged evaluation score. However, this score-based selection overlooks the possibility that different models achieve the best generation performance for different types of text prompts. An online identification of the best generation model for various input prompts can reduce the costs associated with querying sub-optimal models. In this work, we explore the possibility of varying rankings of text-based generative models for different text prompts and propose an online learning framework to predict the best data generation model for a given input prompt. The proposed PAK-UCB algorithm addresses a contextual bandit (CB) setting with shared context variables across the arms, utilizing the generated data to update kernel-based functions that predict the score of each model available for unseen text prompts. Additionally, we leverage random Fourier features (RFF) to accelerate the online learning process of PAK-UCB. Our numerical experiments on real and simulated text-to-image and image-to-text generative models show that RFF-UCB performs successfully in identifying the best generation model across different sample types. The code is available at: github.com/yannxiaoyanhu/dgm-online-select.

Muzhi Li, Cehao Yang, Chengjin Xu, Xuhui Jiang, Yiyan Qi, Jian Guo, Ho-fung Leung, Irwin King. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Abstract Recently, fake news detection on social media (SM) has attracted a lot of attention. With the emergence of fake news at a breakneck pace, the massive spread of fake news has had a serious impact in our society. The authenticity of the news is questionable and there exists a necessity for an automated tool for the detection. However, most fake news detection methods are mainly supervised, requiring huge amounts of annotated data, which is time-consuming, expensive, and almost impossible with vast new SM volume. To deal with this problem, in this paper, we propose a novel unsupervised fake news detection framework based on structural contrastive learning by combining the propagation structure of news and contrastive learning to achieve unsupervised training. To validate the influence of parameters and our method’s performance, we design experiment sets on public Twitter and Weibo datasets, which validate our approach outperforms current baseline ones and has proper robustness.

Human activity recognition (HAR) is a prominent research direction in ubiquitous computing. Current state-of-the-art HAR models achieve great success by learning the correlations between the regions of the body parts by using the attached sensing devices for feature extraction. However, explicitly computing the correlations between whole body parts and whole sub-body parts, which is crucial for extracting discriminatory features for some activities, has not been investigated due to lack of sensing devices that capture the movements of the whole (sub-)body parts. This study proposes an effective yet lightweight VirtualHAR framework, which automatically models correlations between the whole body parts, whole sub-body parts, and regions based on the concept of virtual sensing devices. The VirtualHAR framework mainly encompasses three modules. The Backbone Feature Extraction module extracts the features from a physical sensing device, based on which the Multi-purpose Correlations Learning module constructs virtual sensing devices for body parts and sub-body parts and then exploits the explicit correlations between body parts, sub-body parts as well as in regions by using their attached physical sensing devices. Finally, the Global Aggregation module learns the global aggregation representation for each physical sensing device by collecting the learned correlated representation from each virtual sensing device and physical sensing device. Comprehensive experiments on benchmark HAR datasets and a resource-constrained device confirm that VirtualHAR outperforms SOTA models in recognition performance and computational complexity. Through thorough quantitative and qualitative analysis, we validate the proposed VirtualHAR framework’s effectiveness and efficiency.

Pre-trained Language Models have been shown to be able to emulate deductive reasoning in natural language. However, PLMs are easily affected by irrelevant information (e.g., entity) in instance-level proofs when learning deductive reasoning. To address this limitation, we propose an Abstract-level Deductive Reasoner (ADR). ADR is trained to predict the abstract reasoning proof of each sample, which guides PLMs to learn general reasoning patterns rather than instance-level knowledge. Experimental results demonstrate that ADR significantly reduces the impact of PLMs learning instance-level knowledge (over 70%).

We study risk-sensitive Reinforcement Learning (RL), where we aim to maximize the Conditional Value at Risk (CVaR) with a fixed risk tolerance $\tau$. Prior theoretical work studying risk-sensitive RL focuses on the tabular Markov Decision Processes (MDPs) setting. To extend CVaR RL to settings where state space is large, function approximation must be deployed. We study CVaR RL in low-rank MDPs with nonlinear function approximation. Low-rank MDPs assume the underlying transition kernel admits a low-rank decomposition, but unlike prior linear models, low-rank MDPs do not assume the feature or state-action representation is known. We propose a novel Upper Confidence Bound (UCB) bonus-driven algorithm to carefully balance the interplay between exploration, exploitation, and representation learning in CVaR RL. We prove that our algorithm achieves a sample complexity of $\tilde{O}\left(\frac{H^7 A^2 d^4}{\tau^2 \epsilon^2}\right)$ to yield an $\epsilon$-optimal CVaR, where $H$ is the length of each episode, $A$ is the capacity of action space, and $d$ is the dimension of representations. Computational-wise, we design a novel discretized Least-Squares Value Iteration (LSVI) algorithm for the CVaR objective as the planning oracle and show that we can find the near-optimal policy in a polynomial running time with a Maximum Likelihood Estimation oracle. To our knowledge, this is the first provably efficient CVaR RL algorithm in low-rank MDPs.

Reinforcement learning (RL) problems where the learner attempts to infer an unobserved reward from some feedback variables have been studied in several recent papers. The setting of Interaction-Grounded Learning (IGL) is an example of such feedback-based reinforcement learning tasks where the learner optimizes the return by inferring latent binary rewards from the interaction with the environment. In the IGL setting, a relevant assumption used in the RL literature is that the feedback variable $Y$ is conditionally independent of the context-action $(X,A)$ given the latent reward $R$. In this work, we propose *Variational Information-based IGL (VI-IGL)* as an information-theoretic method to enforce the conditional independence assumption in the IGL-based RL problem. The VI-IGL framework learns a reward decoder using an information-based objective based on the conditional mutual information (MI) between the context-action $(X,A)$ and the feedback variable $Y$ observed from the environment. To estimate and optimize the information-based terms for the continuous random variables in the RL problem, VI-IGL leverages the variational representation of mutual information and results in a min-max optimization problem. Theoretical analysis shows that the optimization problem can be sample-efficiently solved. Furthermore, we extend the VI-IGL framework to general $f$-Information measures in the information theory literature, leading to the generalized $f$-VI-IGL framework to address the RL problem under the IGL condition. Finally, the empirical results on several reinforcement learning settings indicate an improved performance in comparison to the previous IGL-based RL algorithm.

Muzhi Li, Minda Hu, Irwin King, Ho-fung Leung. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

The aspect term extraction (ATE) task aims to extract aspect terms describing a part or an attribute of a product from review sentences. Most existing works rely on either general or domain embedding to address this problem. Despite the promising results, the importance of general and domain embeddings is still ignored by most methods, resulting in degraded performances. Besides, word embedding is also related to downstream tasks, and how to regularize word embeddings to capture context-aware information is an unresolved problem. To solve these issues, we first propose context-aware dynamic word embedding (CDWE), which could simultaneously consider general meanings, domain-specific meanings, and the context information of words. Based on CDWE, we propose an attention-based convolution neural network, called ADWE-CNN for ATE, which could adaptively capture the previous meanings of words by utilizing an attention mechanism to assign different importance to the respective embeddings. The experimental results show that ADWE-CNN achieves a comparable performance with the state-of-the-art approaches. Various ablation studies have been conducted to explore the benefit of each component. Our code is publicly available athttp://github.com/xiejiajia2018/ADWE-CNN.

Cross-domain aspect-based sentiment analysis has recently attracted significant attention, which can effectively alleviate the problem of lacking large-scale labeled data for supervised learning based methods. Most of current methods mainly focus on extracting domain-shared syntactic features to conduct the domain adaptation. Due to the language and syntax are diverse between domains, these methods lack generalization and even lead to syntactic transfer errors. External knowledge graphs have rich domain commonsense and share the relational structures between source and target domains. The domain-shared relational structure can effectively bridge the gap across domains and solve the problem of syntactic transfer errors. Moreover, not all the introduced external knowledge is equally important for the cross-domain aspect-based sentiment analysis. Motivated by these, we propose a knowledge-enhanced and topic-guided cross domain aspect-based sentiment analysis model with the domain-shared commonsense relational structure learning module and the topic-guided knowledge attention module. Extensive experiments are conducted and the experimental results evaluate the effectiveness of our proposed model.

We study the regret for risk-sensitive reinforcement learning (RL) with the exponential utility in the episodic MDP. Recent works establish both a lower bound $\Omega((e^{|\beta|(H-1)/2}-1)\sqrt{SAT}/|\beta|)$ and the best known (upper) bound $\tilde{O}((e^{|\beta|H}-1)\sqrt{H^2SAT}/|\beta|)$, where $H$ is the length of the episode, $S$ the size of state space, $A$ the size of action space, $T$ the total number of timesteps, and $\beta$ the risk parameter. The gap between the upper and the lower bound is exponential and hence is unsatisfactory. In this paper, we show that a variant of UCB-Advantage algorithm reduces a factor of $\sqrt{H}$ from the best previously known bound in any arbitrary MDP. To further sharpen the regret bound, we introduce a brand new mechanism of regret analysis and derive a problem-dependent regret bound without prior knowledge of the MDP from the algorithm. This bound is much tighter in MDPs with special structures. Particularly, we show that a regret that matches the information-theoretic lower bound up to logarithmic factors can be attained within a rich class of MDPs, which improves an exponential factor over the best previously known bound. Further, we derive a novel information-theoretic lower bound of $\Omega(\max_{h\in[H]} c_{v,h+1}^*\sqrt{SAT}/|\beta|)$, where $\max_{h\in[H]} c_{v,h+1}^*$ is a problem-dependent statistic. This lower bound shows that the problem-dependent regret bound achieved by the algorithm is optimal in its dependence on $\max_{h\in[H]} c_{v,h+1}^*$.

The options framework yields empirical success in long-horizon planning problems of reinforcement learning (RL). Recent works show that options help improve the sample efficiency in online RL. However, these results are no longer applicable to scenarios where exploring the environment online is risky, e.g., automated driving and healthcare. In this paper, we provide the first analysis of the sample complexity for offline RL with options, where the agent learns from a dataset without further interaction with the environment. We derive a novel information-theoretic lower bound, which generalizes the one for offline learning with actions. We propose the PEssimistic Value Iteration for Learning with Options (PEVIO) algorithm and establish near-optimal suboptimality bounds for two popular data-collection procedures, where the first one collects state-option transitions and the second one collects state-action transitions. We show that compared to offline RL with actions, using options not only enjoys a faster finite-time convergence rate (to the optimal value) but also attains a better performance when either the options are carefully designed or the offline data is limited. Based on these results, we analyze the pros and cons of the data-collection procedures.

Human Activity Recognition (HAR) through wear-able sensors greatly improves the quality of human life through its multiple applications in health monitoring, assisted living, and fitness tracking. For HAR, multi-sensor channel information is vital to performance. Current work states that applying an attention neural network to prioritize discriminatory sensor channels helps the model classify activity more precisely. However, getting discriminatory information from multisensory channels is not always trivial. For example, when collecting data from elderly hospitalized patients. In this context, existing HAR methods struggle to classify activities, particularly activities with similar natures. Moreover, HAR deep models predominantly suffer from overfitting due to small datasets, which leads to poor performance. Data augmentation is a viable solution to this problem. However, currently available data augmentation methods to HAR have various drawbacks, including the pos-sibility of being domain-dependent, and resulting in distorted models for test sequences. To address the aforementioned HAR problems, we propose a novel framework that primarily focuses on two aspects. First, enhancing the latent information across each sensor channel and learning to exploit the relation among multiple latent features and the ongoing activity. Consequently, this enriches the discriminatory feature representations of each activity. Second, a new augmentation strategy is introduced to address the shortcomings of existing multi-sensor channel data augmentation to generalize our HAR model. Our model outperforms existing state-of-the-art approaches on the four most commonly used HAR datasets from diverse domains. We exten-sively demonstrate the effectiveness of the proposed framework through detailed quantitative analysis of experimental results and ablation studies.

Incorporating logic reasoning with deep neural networks (DNNs) is an important challenge in machine learning. In this article, we study the problem of converting logical expressions into natural language. In particular, given a sequential logic expression, the goal is to generate its corresponding natural sentence. Since the information in a logic expression often has a hierarchical structure, a sequence-to-sequence baseline struggles to capture the full dependencies between words, and hence it often generates incorrect sentences. To alleviate this problem, we propose a model to convert Structural Logic Expressions into Natural Language (SLEtoNL). SLEtoNL converts sequential logic expressions into structural representation and leverages structural encoders to capture the dependencies between nodes. The quantitative and qualitative analyses demonstrate that our proposed method outperforms the seq2seq model, which is based on the sequential representation, and outperforms strong pretrained language models (e.g., T5, BART, GPT3) with a large margin (28.6 in BLEU3) in out-of-distribution evaluation. The data and code will be available onhttps://github.com.

Relation Classification is one of the most important tasks in text mining. Previous methods either require large-scale manually-annotated data or rely on distant supervision approaches which suffer from the long-tail problem. To reduce the expensive manually-annotating cost and solve the long-tail problem, prototypical networks are widely used in few-shot RC tasks. Despite their remarkable performance, current prototypical networks ignore the different granularities of relations, which degrades the classification performance dramatically. Moreover, the optimization of current prototypical networks simply relies on the cross-entropy loss, which cannot consider the intra-relation compactness and the dispersion among relations in a semantic space. It is not robust enough for current prototypical network in real-world and complicated scenarios. In this paper, we propose an area prototypical network with a granularity-aware measurement, aiming to considering the different granularities of relations. Each relation is represented as an area whose width can reflect the granularity level of relation. Moreover, to improve the robustness, bimargin loss is designed to force area prototypical network to improve the intra-relation compactness and inter-relation dispersion for the feature representation in a semantic space. Extensive experiments on two public datasets are conducted and evaluate the effectiveness of our proposed model.

The theoretical underpinnings of multiagent reinforcement learning has recently attracted much attention. In this work, we focus on the generalized social learning (GSL) protocol --- an agent interaction protocol that is widely adopted in the literature, and aim to develop an accurate theoretical model for the Q-learning dynamics under this protocol. Noting that previous models fail to characterize the effects of local interactions and incomplete information that arise from GSL, we model the Q-values dynamics of each individual agent as a system of stochastic differential equations (SDE). Based on the SDE, we express the time evolution of the probability density function of Q-values in the population with a Fokker-Planck equation. We validate the correctness of our model through extensive comparisons with agent-based simulation results across different types of symmetric games. In addition, we show that as the interactions between agents are more limited and information is less complete, the population can converge to a outcome that is qualitatively different than that with global interactions and complete information.

Cross-domain sentiment analysis has recently attracted significant attention, which can effectively alleviate the problem of lacking large-scale labeled data for deep neural network based methods. However, most of the existing cross-domain sentiment classification models neglect the domain-specific features, which limits their performance especially when the domain discrepancy becomes larger. Meanwhile, the relations between the aspect and opinion terms cannot be effectively modeled and thus the sentiment transfer error problem is suffered in the existing unsupervised domain-adaptation methods. To address these two issues, we propose an aspect-opinion correlation aware and knowledge-expansion few shot cross-domain sentiment classification model. Sentiment classification can be effectively conducted with only a few support instances of the target domain. Extensive experiments are conducted and the experimental results show the effectiveness of our proposed model.

Relation Classification (RC) is an important task in information extraction. In most real-world scenarios, the frequency of relations often follows a long-tailed and open-ended distribution. However, current efforts mainly focus on the partial frequency distribution of relations, which is limited in real-world applications. Meanwhile, prototypical network achieves remarkable performance among fields of deep supervised learning, few-shot learning and open set learning. Nevertheless, in the open world environment, it still suffers from the incompatible feature embedding problem as the novel and unknown relations come in. To address these problems, we propose an Open Generalized Prototypical Network with task-adaptive feature fusion for the open generalized few-shot relation classification. Extensive experiments are conducted on public large-scale datasets and our proposed model obtains the better performances.

The task of image difference captioning aims at locating changed objects in similar image pairs and describing the difference with natural language. The key challenges of this task are to comprehend the context of image pairs sufficiently and locate the changed objects accurately in the presence of viewpoint change. Previous studies focus on pixel-level image features, neglecting rich explicit features of objects in an image pair which are beneficial to generate a fine-grained difference caption. Additionally, existing generative models suffer from accurately locate the differences in the interference of viewpoint change. To address these issues, we propose an Instance-Level Fine-Grained Difference Captioning (IFDC) model, which consists of a fine-grained feature extraction module, a multi-round feature fusion module, a similarity-based difference finding module, and a difference captioning module. To describe the changed objects comprehensively, we extract the fine-grained features, i.e., visual features, semantic features, and positional features at instance-level, as the objects’ representation. To enhance the model’s immunity to viewpoint change, we design a similarity-based difference finding module to locate the changed objects accurately. Extensive experiments show that our IFDC model achieves comparable performance with the state-of-the-art models on the datasets of CLEVR-Change and Spot-the-Diff, thus verifying the effectiveness of our proposed model. Our source code is available athttps://github.com/VISLANG-Lab/IFDC.

Most existing visual question answering (VQA) models strongly rely on language bias to answer questions, i.e., they always tend to fit question-answer pairs on the train split and perform poorly on the test spilt when the answer distributions are different. This behavior makes them hard to be applied in real scenarios. To reduce the language biases, previous studies mainly integrate modules to overcome language priors (ensemble-based methods) or generate additional training data to balance dataset biases (data-balanced methods). However, all the existing ensemble-based methods drop their accuracies on the VQA v2 dataset, while data-balanced methods may introduce new biases and cannot guarantee the quality of the generated data. In this paper, we propose a model-agnostic training scheme called Suppressing Biased Samples (SBS) to overcome language priors. SBS consists of two collaborative parts, i.e., a Data Classifier Module to divide the dataset into biased samples and unbiased samples by utilizing the similarity in the semantic space, and a Bias Penalty Module to suppress the biased samples to weaken their influence. As a new way of balancing data to address language bias, SBS overcomes the shortcomings of previous data-balanced methods. Experimental results show that our method can be merged into other bias-reduction methods and achieves a new state-of-the-art performance on the commonly used VQA-CP v2 dataset.

Question generation is a challenging task and has attracted widespread attention in recent years. Although previous studies have made great progress, there are still two main shortcomings: First, previous work did not simultaneously capture the sequence information and structure information hidden in the context, which results in poor results of the generated questions. Second, the generated questions cannot be answered by the given context. To tackle these issues, we propose an entity guided question generation model with contextual structure information and sequence information capturing. We use a Graph Convolutional Network and a Bidirectional Long Short Term Memory Network to capture the structure information and sequence information of the context, simultaneously. In addition, to improve the answerability of the generated questions, we use an entity-guided approach to obtain question type from the answer, and jointly encode the answer and question type. Both automatic and manual metrics show that our model can generate comparable questions with state-of-the-art models. Our code is available at https://github.com/VISLANG-Lab/EGSS.

As an interesting and challenging task, story ending generation aims at generating a reasonable and coherent ending for a given story context. The key challenge of the task is to comprehend the context sufficiently and capture the hidden logic information effectively, which has not been well explored by most existing generative models. To tackle this issue, we propose a context-aware Multi-level Graph Convolutional Networks over Dependency Parse (MGCN-DP) trees to capture dependency relations and context clues more effectively. We utilize dependency parse trees to facilitate capturing relations and events in the context implicitly, and Multi-level Graph Convolutional Networks to update and deliver the representation crossing levels to obtain richer contextual information. Both automatic and manual evaluations show that our MGCN-DP can achieve comparable performance with state-of-the-art models. Our source code is available at https://github.com/VISLANG-Lab/MLGCN-DP.

Modelling the dynamics of multi-agent reinforcement learning has long been an important research topic. Most of the previous works focus on agents learning under global interactions. In this paper, we investigate learning in a population of agents with local interactions, such that agents learn their policies concurrently by playing with some other agents locally, without the knowledge of the whole population. We derive the stochastic differential equations (SDEs) to describe the Q-values dynamics of each individual agent under the stochastic environment. Applying the Fokker-Planck equation, the time evolution of the probability distribution (PDF) of the population Q-values is worked out. We validate our model through comparisons with agent-based simulations on typical symmetric games with various settings, and the results verify that the model can precisely capture the behaviour of the multi-agent system.

The concept of conventions has attracted much attention in the multi-agent system research. In this article, we study the emergence of conventions from repeated n -player coordination games. Distributed agents learn their policies independently and are capable of observing their neighbours in a network topology. We distinguish two types of information representation about the observations: gist trace and verbatim trace. We conjecture that learning based on the gist trace, which overlooks the details and focuses only on the general choice of action of a neighbourhood, should achieve efficient convention emergence. To this end, a novel learning method that makes use of the gist trace is proposed. The experimental results confirm that the proposed method establishes conventions much faster than the state-of-the-art learning methods across diverse settings of multi-agent systems. In particular, the use of gist trace derived at a low level of abstraction further improves the efficiency of convention emergence.

In teacher-student framework, a more experienced agent (teacher) helps accelerate the learning of another agent (student) by suggesting actions to take in certain states. In cooperative multiagent reinforcement learning (MARL), where agents need to cooperate with one another, a student may fail to cooperate well with others even by following the teachers' suggested actions, as the polices of all agents are ever changing before convergence. When the number of times that agents communicate with one another is limited (i.e., there is budget constraint), the advising strategy that uses actions as advices may not be good enough. We propose a partaker-sharer advising framework (PSAF) for cooperative MARL agents learning with budget constraint. In PSAF, each Q-learner can decide when to ask for Q-values and share its Q-values. We perform experiments in three typical multiagent learning problems. Evaluation results show that our approach PSAF outperforms existing advising methods under both unlimited and limited budget, and we give an analysis of the impact of advising actions and sharing Q-values on agents' learning.

Visual question answering aims to answer the natural language question about a given image. Existing graph-based methods only focus on the relations between objects in an image and neglect the importance of the syntactic dependency relations between words in a question. To simultaneously capture the relations between objects in an image and the syntactic dependency relations between words in a question, we propose a novel dual channel graph convolutional network (DC-GCN) for better combining visual and textual advantages. The DC-GCN model consists of three parts: an I-GCN module to capture the relations between objects in an image, a Q-GCN module to capture the syntactic dependency relations between words in a question, and an attention alignment module to align image representations and question representations. Experimental results show that our model achieves comparable performance with the state-of-theart approaches.

The research in reinforcement learning has achieved great success in strategic game playing. These successes are thanks to the incorporation of deep reinforcement learning (DRL) and Monte Carlo Tree Search (MCTS) to the agent trained under the self-play (SP) environment. By self-play, agents are provided with an incrementally more difficult curriculum which in turn facilitates learning. However, recent research suggests that agents trained via self-play may easily lead to getting stuck in local equilibria. In this paper, we consider a population of agents each independently learns to play an alternating Markov game (AMG). We propose a new training framework-group practice- for a population of decentralized RL agents. By group practice (GP), agents are assigned into multiple learning groups during training, for every episode of games, an agent is randomly paired up and practices with another agent in the learning group. The convergence result to the optimal value function and the Nash equilibrium are proved under the GP framework. Experimental study is conducted by applying GP to Q-learning algorithm and the deep Q-learning with Monte-Carlo tree search on the game of Connect Four and the game of Hex. We verify that GP is the more efficient training scheme than SP given the same amount of training. We also show that the learning effectiveness can even be improved when applying local grouping to agents.

Visual contexts often help to recognize named entities more precisely in short texts such as tweets or snapchat. For example, one can identify "Charlie'' as a name of a dog according to the user posts. Previous works on multimodal named entity recognition ignore the corresponding relations of visual objects and entities. Visual objects are considered as fine-grained image representations. For a sentence with multiple entity types, objects of the relevant image can be utilized to capture different entity information. In this paper, we propose a neural network which combines object-level image information and character-level text information to predict entities. Vision and language are bridged by leveraging object labels as embeddings, and a dense co-attention mechanism is introduced for fine-grained interactions. Experimental results in Twitter dataset demonstrate that our method outperforms the state-of-the-art methods.

Changmeng Zheng, Yi Cai, Jingyun Xu, Ho-fung Leung, Guandong Xu. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Modelling the dynamics of multi-agent learning has long been an important research topic, but all of the previous works focus on 2-agent settings and mostly use evolutionary game theoretic approaches. In this paper, we study an n-agent setting with n tends to infinity, such that agents learn their policies concurrently over repeated symmetric bimatrix games with some other agents. Using mean field theory, we approximate the effects of other agents on a single agent by an averaged effect. A Fokker-Planck equation that describes the evolution of the probability distribution of Q-values in the agent population is derived. To the best of our knowledge, this is the first time to show the Q-learning dynamics under an n-agent setting can be described by a system of only three equations. We validate our model through comparisons with agent-based simulations on typical symmetric bimatrix games and different initial settings of Q-values.

Due to technology scaling, lifetime reliability is becoming one of the major design constraints in the performance optimization of future many-core systems. Given a lifetime reliability constraint, the existing lifetime-constrained runtime mapping schemes often lead to low throughput because of the requirement to map all applications to compact regions. In this paper, we propose a runtime application mapping scheme that exploits a borrowing strategy to improve the throughput of many-core systems given a lifetime constraint. First, we propose using different strategies for mapping communication-intensive applications and computation-intensive applications. The lifetime reliability constraint can be relaxed in the local time scale when the communication requirement is high. The throughput is improved because the communication distance of communication-intensive applications is optimized while the waiting time of computation-intensive application is reduced. Then, we propose a method to effectively classify applications depending on the communication-to-computation ratio. A dynamic threshold is determined according to the current locations of available cores. Finally, we propose an improved neighborhood allocation scheme to reduce the communication cost in the task mapping. The experimental results show that compared to the state-of-the-art lifetime-constrained mapping, the proposed mapping scheme improves the throughput of many-core systems by 26% on average for synthetic task graphs and by 20% on average for realistic task graphs while the lifetime reliability is maintained within a constraint.

Due to technology scaling, aging issue is becoming one of major concerns in the design of network-on-chip (NoC). The imbalanced workload distribution and routing algorithm cause aging hotspots, where a certain group of routers have higher aging effect than others. This can possibly lead to shorter lifetime of NoC. Most existing aging-aware routing algorithms are based on minimal routing, which suffers from less degree of adaptiveness compared to non-minimal routing. Thus, they are inefficient to mitigate the aging effect of routers. In this paper, we propose to use a non-minimal routing scheme to detour the traffic away from the aging hotspots, with the objective of mitigating the aging effect for NoCs. The problem is formulated as a bottleneck shortest path problem and solved using a dynamic programming approach. Finally, the experimental results show that compared to the state-of-the-art aging-aware routing algorithm, the non-minimal routing algorithm has up to 20% lifetime improvement for hotspot traffic patterns and realistic workload traces.

This paper studies the performance for evolution strategies with the optimal weighed recombination on spherical problems in finite dimensions. We first discuss the different forms of functions that are used to derive the optimal recombination weights and step size, and then derive an inequality that establishes the relationship between these functions. We prove that using the expectation of random variables to derive the optimal recombination weights and step size can be disappointing in terms of the expected performance of evolution strategies. We show that using the realizations of random variables is a better choice. We generalize the results to any convex functions and establish an inequality for the normalized quality gain. We prove that the normalized quality gain of the evolution strategies have a better and robust performance when they use the optimal recombination weights and the optimal step size that are derived from the realizations of random variables rather than using the expectations of random variables.

The article A whitelist and blacklist-based co-evolutionary strategy for defensing against multifarious trust attacks, written by Shujuan Ji, Haiyan Ma, Yongquan Liang, Hofung Leung and Chunjin Zhang, was originally published electronically on the publisher’s internet portal.

Due to technology scaling, lifetime reliability is becoming one of major design constraints in the design of future many-core systems. In this paper, we propose a novel runtime mapping scheme which can dynamically map the applications given a lifetime reliability constraint. A borrowing strategy is adopted to manage the lifetime in a long-term scale, and the lifetime constraint can be relaxed in short-term scale when the communication performance requirement is high. The through-put can be improved because the communication performance of communication intensive applications is optimized, and mean-while the waiting time of computation intensive application is reduced. An improved neighborhood allocation method is proposed for the runtime mapping scheme. Moreover, we propose a method to effectively classify communication intensive applications and computation intensive applications. The experimental results show that compared to the state-of-the-art lifetime-constrained mapping, the proposed scheme has more than 20% throughput improvement in average.

Due to technology scaling, lifetime reliability is becoming one of major design constraints in the design of future many-core systems. In this paper, we propose a novel runtime mapping scheme which could dynamically map the applications given a lifetime reliability constraint. A borrowing strategy is adopted to manage the lifetime in a long-term scale, and the lifetime constraint could be relaxed in short-term scale when the communication performance requirement is high. The throughput could be improved because the communication performance of communication intensive applications is optimized, and meanwhile the waiting time of computation intensive application is reduced. Furthermore, an improved neighborhood allocation method is proposed for the runtime mapping scheme. The experimental results show that compared to the state-of-the-art lifetime-constrained mapping, the proposed mapping scheme could have over 20% throughput improvement.

Android apps frequently leak private data off the device with or without intentions. Researchers have proposed a large number of methods, for example, static and dynamic analysis methods, to pick out the apps which tend to leak private data. However, they are only able to identify part of private data leakage vulnerabilities, due to the dynamic features in codes or code coverage problem. This paper presents a novel hybrid approach that can find out more private data leakages than the existing static or dynamic methods. The approach, realized in a tool, called HybriDroid, which employs both static and dynamic analysis methods to extract the models of each apps, and then refines the behavior model to a more adequate one according to the dynamic analysis result. As a consequence, HybriDroid inherits the advantages of both static and dynamic analysis methods, which not only achieves a high code coverage, but also can deal with the dynamic features in codes. The evaluation results show that HybriDroid is effective in detecting privacy leakages for both inter- and intra-app communication. Comparing with the existing methods, it can achieve considerable improvements in data leakage detection performance with a 97.8% precision and 90% recall on the selected apps from DroidBench 3.0 test suite.

Recently, the study of social conventions has attracted much attention in the literature. We notice that a type of interesting phenomena, local convention phenomena, may also exist in certain multi-agent systems. When agents are partitioned into compact communities, different local conventions emerge in different communities. In this paper, we provide a definition for local conventions, and propose two metrics measuring their strength and diversity. In our experimental study, we show that agents can achieve coordination via establishing diverse stable local conventions, which indicates a practical way to solve coordination problems other than the traditional global convention emergence. Moreover, we find that with smaller community sizes, denser connections and fewer available actions, diverse local conventions emerge in shorter time.

With electronic commerce becoming increasingly popular, the problems of trust have become one of the main challenges in the development of electronic commerce. Although various mechanisms have been adopted to guarantee trust between customers and sellers (or platforms), trust and reputation systems are still frequently attacked by deceptive, collusive, or strategic agents. Therefore, it is difficult to keep these systems robust. It has been mentioned that a combined usage of both trust and distrust propagation can lead to better results. However, little work has been known to realize this insight successfully. Besides, literatures either use a social network with trust/distrust information or use one advisor list in evaluating all sellers, which leads to the lack of pertinence and inaccuracy of evaluation. This paper proposes a defensing strategy called WBCEA , in which, each buyer agent is modeled with two attributes (i.e., the trustworthy facet and the untrustworthy facet) and two lists (i.e., the whitelist and the blacklist). Based on the social network that are constructed and maintained according to its whitelist and blacklist, the honest buyer agent can find trustable buyers and evaluate the candidate sellers according to its own experience and ratings of trustable buyers. Experiments are designed and implemented to verify the accuracy and robustness of this strategy. Results show that our strategy outperforms existing ones, especially when majority of buyers are dishonest in the electronic market.

Latent Dirichlet Allocation (LDA) and its variants have been widely used to discover latent topics in textual documents. However, some of topics generated by LDA may be noisy with irrelevant words scattering across these topics. We name this kind of words as topic-indiscriminate words, which tend to make topics more ambiguous and less interpretable by humans. In our work, we propose a new topic model named TWLDA, which assigns low weights to words with low topic discriminating power (ability). Our experimental results show that the proposed approach, which effectively reduces the number of topic-indiscriminate words in discovered topics, improves the effectiveness of LDA.

Automated negotiation is very important for organizing decentralized systems such as e-business, p2p systems, cloud computing, and so on. During the course of a negotiation, reward and penalty can be used to increase the chance of reaching agreements between negotiating agents, but have not been applied into automated negotiation systems well, especially integrating both in a single negotiation system. Thus, in this work we make an effort to reveal how the reward increases the acceptability of an offer and how the penalty decreases the deniability of an offer. More specifically, our study shows that the degree, to which a reward and a penalty influence the outcome, depends on the greedy degree for the reward and the creditable degree on the penalty. Therefore, if we know an offeree's utilities of accepting and denying an offer, the greedy degree for reward and the creditable degree on penalty, we can calculate how much reward and penalty the offerer agent needs to change the offeree's mind (i.e., from denying to accepting).

Psychological experiment studies reveal that human interaction behaviors are often not the same as what game theory predicts. One of important reasons is that they did not put relevant constraints into consideration when the players choose their best strategies. However, in real life, games are often played in certain contexts where players are constrained by their capabilities, law, culture, custom, and so on. For example, if someone wants to drive a car, he/she has to have a driving license. Therefore, when a human player of a game chooses a strategy, he/she should consider not only the material payoff or monetary reward from taking his/her best strategy and others' best responses but also how feasible to take the strategy in that context where the game is played. To solve such a game, this paper establishes a model of fuzzily constrained games and introduces a solution concept of constrained equilibrium for the games of this kind. Our model is consistent with psychological experiment results of ultimatum games. We also discuss what will happen if Prisoner's Dilemma and Stag Hunt are played under fuzzy constraints. In general, after putting constraints into account, our model can reflect well the human behaviors of fairness, altruism, self-interest, and so on, and thus can predict the outcomes of some games more accurate than conventional game theory.

Automated negotiations play an important role in various domains modeled as multiagent systems, where agents represent human users and adopt different negotiation strategies. Generally, given a multiagent system, a negotiation strategy should be robust in the sense that most agents in the system have the incentive to choose it rather than other strategies. Empirical game-theoretic (EGT) analysis is a game-theoretic analysis approach to investigate the robustness of different strategies based on a set of empirical results. In this study, we propose that model-checking techniques can be adopted to improve EGT analysis for negotiation strategies. The dynamics of strategy profiles can be modeled as a labeled transition system using the counter abstraction technique. We define single-agent best deviation to represent the strategy deviations during negotiation, which focuses on each agent's best deviation benefit and is different from best single-agent deviation used in previous work. Two interesting properties in EGT analysis, i.e., empirical pure strategy Nash equilibrium and best reply cycle, are automatically verified to investigate the robustness of different strategies. For demonstration, the top-six strategies from the automated negotiating agents competition 2010-2012 are studied in terms of their robustness performance. In addition to identifying the most robust strategies, we supply complete rankings among them in different settings. We show that model checking is applicable and efficient to perform robustness analysis of negotiation strategies.

In an artificial society where agents repeatedly interact with one another, achieving high level of social utility is generally a challenge. This is especially true when the participating agents are self-interested, and that there is no central authority to coordinate, and direct communication or negotiation are not possible. Recently, Hao and Leung studied a new game theoretic approach, where a new type of repeated game as well as a new reinforcement learning based agent learning method were proposed. In particular, their game mechanism differs from traditional repeated games in that the agents are anonymous, and the agents interact with randomly chosen opponents. Their learning mechanism allows agents to coordinate without negotiations. Despite the promising initial results, however, extended simulation reveals that the outcomes are not stable in the long run, as the high level of cooperation is eventually not sustainable. In this work, we revisit the problem and propose a new learning mechanism as follows. First, we propose an enhanced Q-learning-based framework that allows the agents to better capture both the individual and social utilities that they have learned through observations. Second, we propose a new concept of "social attitude" for determining the action of the agents throughout the game. Simulation results reveal that this approach can achieve higher social utility, including close-to-optimal results in some scenarios, and more importantly, the results seem to be sustainable.

Term weighting schemes have been widely used in information retrieval and text categorization models. In this paper, we first investigate into the limitations of several state-of-the-art term weighting schemes in the context of text categorization tasks. Considering that category-specific terms are more useful to discriminate different categories, and these terms tend to have smaller entropy with respect to these categories, we then explore the relationship between a term's discriminating power and its entropy with respect to a set of categories. To this end, we propose two entropy-based term weighting schemes (i.e., tf.dc and tf.bdc) which measure the discriminating power of a term based on its global distributional concentration in the categories of a corpus. To demonstrate the effectiveness of the proposed term weighting schemes, we compare them with seven state-of-the-art schemes on a long-text corpus and a short-text corpus respectively. Our experimental results show that the proposed schemes outperform the state-of-the-art schemes in text categorization tasks with KNN and SVM.

In Artificial Intelligence, 171(2–3):161–184, 2007. Luo and Jennings identify and analyze the complete spectrum of compromise aggregation operators that can be used to model the various attitudes that decision-making agents can have toward risk in aggregation. In this paper, we extend these operators to deal with aggregation when the ratings have different degrees of importance. Specifically, we generalize the method of weighted uninorms to handle this issue. We choose this approach because uninorm compromise operators are a kind of common ones, and their weighted counterparts, which are widely accepted, can cover other common operators, such as weighted t-norms and t-conorms, as special cases. As per the analysis of weighted uninorms, we identify common properties that the weighting operators of the various compromise operators should satisfy, and in so doing, we introduce the concept of a general weighting operator for compromise operators and reveal the different properties that a specific type of weighting operator should obey. This, in turn, defines the concepts of the various weighting operators of the various compromise operators. We then go onto discuss the construction issue of weighting operators associated with the various compromise operators.

Most previous works on coordination in cooperative multiagent systems study the problem of how two (or more) players can coordinate on Pareto-optimal Nash equilibrium(s) through fixed and repeated interactions in the context of cooperative games. However, in practical complex environments, the interactions between agents can be sparse, and each agent's interacting partners may change frequently and randomly. To this end, we investigate the multiagent coordination problems in cooperative environments under a social learning framework. We consider a large population of agents where each agent interacts with another agent randomly chosen from the population in each round. Each agent learns its policy through repeated interactions with the rest of the agents via social learning. It is not clear a priori if all agents can learn a consistent optimal coordination policy in such a situation. We distinguish two different types of learners depending on the amount of information each agent can perceive: individual action learner and joint action learner . The learning performance of both types of learners is evaluated under a number of challenging deterministic and stochastic cooperative games, and the influence of the information sharing degree on the learning performance also is investigated—a key difference from the learning framework involving repeated interactions among fixed agents.

In many multiagent systems (MAS), it is desirable that the agents can coordinate with one another on achieving socially optimal outcomes to increase the system level performance, and the traditional way of attaining this goal is to endow the agents with social rationality [in: Proc. of AAAI Fall Sy mposium on Socially Intelligent Agents, 1997, pp. 61–63] – agents act as system utility maximizers. However, this is difficult to implement when we are facing open MAS domains such as peer-to-peer network and mobile ad-hoc networks, since we do not have control on all agents’ behaviors in such systems and each agent usually behaves individually rationally as an individual utility maximizer only. In this paper, we propose injecting a number of influencer agents [in: Proc. of AAMAS’13, ACM Press, 2013, pp. 447–454, AAMAS (2012)] to manipulate the behaviors of individually rational agents and investigate whether the individually rational agents can eventually be incentivized to coordinate on achieving socially optimal outcomes. We evaluate the effects of influencer agents in two common types of games: prisoner’s dilemma games and anti-coordination games. Simulation results show that a small proportion of influencer agents can significantly increase the average percentage of socially optimal outcomes attained in the system and better performance can be achieved compared with that of previous work.

The complexity of automated negotiation in a multi-issue, incomplete-information and continuous-time environment poses severe challenges, and in recent years many strategies have been proposed in response to this challenge. For the traditional evolution, strategies are studied in games assuming that “globally” negotiates with all other participates. This evaluation, however, is not suited for negotiation settings that are primarily characterized by “local” interactions among the participating agents, that is, settings in which each of possibly many participating agents negotiates only with its local neighbors rather than all other agents. A new class of negotiation games is therefore introduced that take negotiation locality (hence spatial information about the agents) into consideration. It is shown how spatial evolutionary game theory can be used to interpret bilateral negotiation results among state-of-the-art strategies.

Bayesian games can handle the incomplete information about players' types. However, in real life, the information could be not only incomplete but also ambiguous for lack of sufficient evidence, i.e., a player cannot have a probability precisely about each type of the other players. To address this issue, we extend the Bayesian games to ambiguous Bayesian games. We also illustrate and analyse our game model.

This paper presents a novel halfspace sampling method in single parent elitist evolution strategies (ESs) for unimodal functions. In halfspace sampling, the supporting hyperplane going through a parent separates the search space into a positive halfspace and a negative halfspace. If an offspring lies in the negative halfspace, it will be reflected with respect to the parent so that it lies in the positive halfspace. We derive the convergence rates of a scale-invariant step size (1+1)-ES with halfspace sampling on spherical functions in finite and infinite dimensions. We prove that the lower bounds of convergence rates are improved by a factor of 2 when strategies sample their offspring in the optimal positive halfspace. We also implement halfspace sampling into the (1+1) CMA-ES by introducing the concept of evolution halfspaces. Evolution halfspaces accumulate the significant information of the previous successful and unsuccessful steps in order to estimate the optimal positive halfspace. The (1+1)-CMA-ES with halfspace sampling is benchmarked on the BBOB noise-free testbed and experimentally compared with the standard (1+1)-CMA-ES.

The problem of coordination in cooperative multiagent systems has been widely studied in the literature. We firstly investigate the multiagent coordination problems in cooperative environments under the networked social learning framework focusing on two representative topologies: the small-world and the scale-free network. We consider a population of agents where each agent interacts with another agent randomly chosen from its neighborhood in each round. Each agent learns its policy through repeated interactions with its neighbors via social learning. It is not clear a priori if all agents can learn a consistent optimal coordination policy and what kind of impact different topology parameters could have on the learning performance of agents. We distinguish two types of learners: individual action learner and joint action learner. The learning performances of both learners are evaluated extensively in different cooperative games.

Bayesian games can handle the incomplete information about players' types. However, in real life, the information could be not only incomplete but also ambiguous for lack of sufficient evidence, i.e., a player cannot have a precise probability about each type of the other players. To address this issue, this paper firstly extends the Bayesian games to ambiguous Bayesian games. Then, we introduce the concept of a solution to this kind of games and discuss their properties, especially about solution existence, how the ambiguity degree and players' ambiguity attitude influence the outcomes of an ambiguous Bayesian game, the case of lower boundary probability, and the missing situation. We also illustrate our game model, especially in the public security domain.

Collaborative filtering (CF) is an important and popular technology for recommender systems. However, current CF methods suffer from such problems as data sparsity, recommendation inaccuracy, and big-error in predictions. In this paper, we borrow ideas of object typicality from cognitive psychology and propose a novel typicality-based collaborative filtering recommendation method named TyCo. A distinct feature of typicality-based CF is that it finds "neighbors" of users based on user typicality degrees in user groups (instead of the corated items of users, or common users of items, as in traditional CF). To the best of our knowledge, there has been no prior work on investigating CF recommendation by combining object typicality. TyCo outperforms many CF recommendation methods on recommendation accuracy (in terms of MAE) with an improvement of at least 6.35 percent in Movielens data set, especially with sparse training data (9.89 percent improvement on MAE) and has lower time cost than other CF methods. Further, it can obtain more accurate predictions with less number of big-error predictions.

In multiagent systems, social optimality is a desirable goal to achieve in terms of maximizing the global efficiency of the system. We study the problem of coordinating on socially optimal outcomes among a population of agents, in which each agent randomly interacts with another agent from the population each round. Previous work [Hales and Edmonds 2003; Matlock and Sen 2007, 2009] mainly resorts to modifying the interaction protocol from random interaction to tag-based interactions and only focus on the case of symmetric games. Besides, in previous work the agents’ decision making processes are usually based on evolutionary learning, which usually results in high communication cost and high deviation on the coordination rate. To solve these problems, we propose an alternative social learning framework with two major contributions as follows. First, we introduce the observation mechanism to reduce the amount of communication required among agents. Second, we propose that the agents’ learning strategies should be based on reinforcement learning technique instead of evolutionary learning. Each agent explicitly keeps the record of its current state in its learning strategy, and learn its optimal policy for each state independently. In this way, the learning performance is much more stable and also it is suitable for both symmetric and asymmetric games. The performance of this social learning framework is extensively evaluated under the testbed of two-player general-sum games comparing with previous work [Hao and Leung 2011; Matlock and Sen 2007]. The influences of different factors on the learning performance of the social learning framework are investigated as well.

We propose a novel variant of the (1, λ)-CMA-ES that uses the mirrored sampling and sequential selection methods. Instead of sampling all the mirrored directions along the principal axes of the covariance matrix, we cluster the eigen-values of the covariance matrix of a CMA-ES and sample search points on a mirrored eigenspace spanned by eigenvectors that have the same repeated or clustered eigenvalues in the Hessian matrices of the objective functions. We apply this sampling method to a (1, λ)-CMA-ES and compare its performance with that of a standard (1, λsm)-CMA-ES that uses the traditional mirroring method. In most of the standard test functions, the new variant is not observed to be marginally worse than the mirrored variant, and it is up to 56% faster on the sphere function when it is compared with the standard (1, λ)-CMA-ES.

Multi-agent systems, which are composed of autonomous agents, have been successfully employed as a modeling paradigm in many scenarios. However, it is challenging to guarantee the correctness of their behaviors due to the complex nature of the autonomous agents, especially when they have stochastic characteristics. In this work, we propose to apply probabilistic model checking to analyze multi-agent systems. A modeling language called PMA is defined to specify such kind of systems, and LTL property and logic of knowledge combined with probabilistic requirements are supported to analyze system behaviors. Initial evaluation indicates the effectiveness of our current progress; meanwhile some challenges and possible solutions are discussed as our ongoing work.

In many multi-agent applications, game theory can serve as a useful tool to model these multi-agent scenarios and analyse the strategic interactions among agents. Fairness is an important goal to consider in a variety of multi-agent applications such as resource allocation or job scheduling problems, but it is not taken into consideration in traditional game theory. However, in many cases the solution concepts of pure strategy or mixed strategy Nash equilibria from traditional game theory can lead to unfair and inefficient outcomes. In this paper, we explicitly introduce the concept of fairness strategy in the context of infinitely repeated game inspired from fairness motive observed in human behaviors. We show that using fairness strategy, not only the agents can receive equal payoffs (achieving fairness) but also the sum of their payoffs is maximized (achieving efficiency) in the infinitely repeated games with conflicting interests. More importantly, we prove that this desirable pair of fairness strategies is in a new type of equilibrium - fairness strategy equilibrium, which thus provides an intuitive solution concept for the agents to make their decisions and coordinate with other agents or even humans.

During multi-agent interactions, robust strategies are needed to help the agents to coordinate their actions to achieve efficient outcomes. A large body of previous work focuses on designing strategies towards the goal of Nash equilibrium, which can be extremely inefficient in many situations such as prisoner's dilemma game. A number of improved algorithms based on Q-learning have been developed recently for agents to achieve mutual cooperation in games like prisoner's dilemma. However, almost all of them involve only two agents playing the same game repeatedly. However, this may not reflect the real scenario in practical multi-agent interaction situations. In practical multi-agent environments, each agent may interact with multiple agents at the same time and each agent may only be allowed to interact with a specific set of agents, which is determined by the system's underlying topology. In this paper, we propose a learning framework by taking into consideration the underlying interaction topology of the agents. We show that the system can maintain certain level of cooperation though the agents are individually rational. To better understand this phenomenon, we also develop a mathematical model to analyze the dynamics resulting from the learning framework. The theoretical results of the mathematical model are shown to be able to successfully predict the transition point and the expected behaviors of the system compared with the simulation results.

Recently, some systems allow users to rate and annotate resources, e.g., Movie Lens, and we consider that it provides a way to identify favor tags and annoying tags of a user by integrating user's rating and tags. In this paper, we reveal and elaborate on the limitations of current works on user profiling for personalized search in collaborative tagging systems. Then we propose a new multi-level user profiling model by integrating tags and ratings to achieve personalized search, which can reflect not only the user's favor but also a user's nuisances. To the best of our knowledge, this is the first effort to integrate the ratings and tags to model multi-level user profiles for personalized search.

In cognitive psychology, typicality refers to the degree of goodness of objects as exemplars in concepts. In this paper, we apply the idea of typicality analysis from cognitive psychology to query answering, and propose a novel method to answer typicality queries effectively based on theories in cognitive psychology. The proposed method adopts multi-prototype concept modeling and basic level category detection. By a systematic empirical evaluation using real data sets, we verify the accuracy and the effectiveness of our method on answering typicality queries.

In this paper, we formalize the object membership in fuzzy ontology with property importance and property priority, while previous models lack building blocks to handle the importance and priority of properties. A formal mechanism used to measure object memberships in concepts is proposed. Such a mechanism can measure object memberships in concepts defined by properties with importance or priority well. We show that our model is more reasonable in measuring object memberships in concepts than previous models by examples and experiments.

In multi-agent system, social rationality is a desirable goal to achieve in terms of maximizing the global efficiency of the system. Using tag to select partners in agent populations has been shown to be successful to promote social rationality among agents in prisoner's dilemma game and anti-coordination game, but the results are not quite satisfactory. We develop a tag-based learning framework for a population of agents, in which each agent employs a reinforcement learning based strategy instead of using evolutionary learning as in previous works to make their decisions. We evaluate this learning framework in different games and simulation results show that better performance in terms of coordinating on socially rational outcomes can be achieved compared with that in previous work.

This paper proposes a modification to the covariance matrix adaptation evolution strategies (CMA-ES). The goal of our modification is to reduce the number of function evaluations to adapt the covariance matrix to the optimal one when the standard CMA-ES is used to optimize convex-quadratic objective functions which have repeated or clustered eigenvalues in their Hessian matrices. By randomly evaluating the minor eigenspace, the modified CMA-ES is evaluated on a standard suite of benchmark problems and its performance is compared with that of the standard CMA-ES. The experimental results show that our proposed modification can improve the performance of the CMA-ES when dominant eigenspaces and minor eigenspaces exist in the Hessian matrices of the underlying objective functions.

Current recommendation methods are mainly classified into content-based, collaborative filtering and hybrid methods. These methods are based on similarity measurements among items or users. In this paper, we investigate recommendation systems from a new perspective based on object typicality and propose a novel typicality-based recommendation approach. Experiments show that our method outperforms compared methods on recommendation quality.

Collaborative filtering (CF) is an important and popular technology for recommendation systems. However, current collaborative filtering methods suffer from some problems such as sparsity problem, inaccurate recommendation and producing big-error predictions. In this paper, we borrow ideas of object typicality from cognitive psychology and propose a novel typicality-based collaborative filtering recommendation method named TyCo. A distinct feature of typicality-based CF is that it finds `neighbors' of users based on user typicality degrees in user groups (instead of the co-rated items of users or common users of items in traditional CF). To the best of our knowledge, there is no work on investigating collaborative filtering recommendation by combining object typicality. We conduct experiments to validate TyCo and compare it with previous methods.

The criterion of fairness has not been given much attention in the research of multi-agent learning problem. We propose an adaptive strategy for agents to achieve fairness in repeated two-agent game with conflicting interests. In our strategy, each agent is equipped with inequity-averse based fairness model, and makes its decision according to its attractiveness for each action. Besides, each agent adjusts its own attitudes in an adaptive way on the basis of previous outcome and the payoff distribution of the agents in the system, and our goal is to reach fairness in the sense of obtaining equal accumulated payoffs for each agent. Simulation results show that agents using our strategy can coordinate well with each other and achieve fairness with less payoff cost than previous work.

This paper presents an adaptive prediction-regret driven negotiation strategy for bilateral bargaining without modeling opponents, which combines the prediction idea in heuristic method and the regret principle in psychology. Experimental results show that agents that employ this strategy outperform agents that use other strategies previously proposed in the literature.

Ontology has become increasingly important in facilitating information exchange, particularly in the context of the Semantic Web. Currently, most existing ontology models can only specify concepts as crisp sets. However, concepts that are without clear boundaries or are vague in meanings are abundant. Existing ontology models are therefore unable to cope with many real cases effectively. In addition, with respect to a certain category, certain objects can be considered as more representative or typical, which are explained by cognitive psychologists using the Prototype Theory of concepts. Based on this theory, we propose a formal model for fuzzy ontologies. This model is equipped with likeliness, the extent to which an object is considered as an instance of a concept, and typicality, the representativeness of an object in a concept. This model enables ontologies to model concepts and bring the results of reasoning closer to human thinking. Our work is based on an in-depth investigation of the limitations of existing models and findings in cognitive psychology. The nature and differences between likeliness and typicality are also thoroughly discussed. In addition, we present a logic for the ontology model which is based on fuzzy propositional modal logic.

Combinatorial auctions, where bidders are allowed to put bids on bundle of items, are the subject of increasing research in recent years. Combinatorial auctions can lead to better social efficiencies than tractional auctions in the resource allocation problem when bidders have complementarities and substitutabilities among items. Although many works have been conducted on combinatorial auctions, most of them focus on the winner determination problem and the auction design. A large unexplored area of research in combinatorial auctions is the bidding strategies. In this paper, we propose a Q-learning based adaptive bidding strategy for combinatorial auctions in static markets. The bidder employing this strategy can transit among different states, gradually converge to the optimal one, and obtain a high utility in the long-term run. Experiment results show that the Q-learning based adaptive strategy performs fairly well when compared to the optimal strategy and outperforms the random strategy and our previous adaptive strategy in different market environments, even without any prior knowledge.

Previous study shows that using a random immigrant scheme in a cooperative coevolutionary algorithm (RI-CCEA) can significantly track the moving peaks in dynamic optimization. In this paper, we further investigate its behavior in the multi-modal environments where peak locations, peak coverage and peak heights of the moving peaks are changing during the course of optimization. Of the particular interest to us is the different combinations of the collaboration methods used by the original individuals and the RI individuals of the CCEA populations. Empirical comparisons show that in the moderate-changing or slow-changing environments, using the best collaborations in original individuals in the RI-CCEA outperforms other variants in our experiments, while the choice of the collaboration methods in RI individuals is insignificant. In a fast-changing environment, using the random collaborations in original individuals is crucial to achieve a better performance and the choice of the collaboration methods in RI individuals is also significant.

In this paper, we propose a new heuristics called “group extinction”. The heuristics is inspired by the existence of the extinction in the nature that groups of individuals, which have been consuming a large amount of the ecological resources, are not always the best groups in the evolutionary process. Ideally, these groups should be forced to become extinct such that the resources they use can be released to the other individuals or groups. In the context of optimization, the motivation of using the group extinction is to reduce the computational resources used by groups of candidate solutions that do not have any significant contribution to the overall performances of the optimization algorithms. The proposed heuristics is tested in the well-known framework of evolution strategy and their performances on the common unimodal and multimodal optimization problems are investigated. Experimental results show that using the group extinction heuristics can significantly reduce the average numbers of function evaluations to reach the optima, in particular when large populations are used.

This paper investigates the behavior of cooperative coevolutionary algorithms (CCEAs) under dynamic environments. The backgroud of dynamic optimization and the approaches used in evolutionary algorithms (EAs) to address dynamic environments are first briefly reviewed. Two common approaches, including hypermutations and random immigrants, are incorporated into CCEAs to solve two dynamic problems: one moving peak problem and two moving peaks problem. The performance on these two problems under different change severities and different change periods are empirically compared with those of the EA counterparts. Experimental results indicate that using cooperative coevolutionary approach can generally provide a better performance than the EA conterparts. In particular, CCEA with the use of random immigrants consistently outperforms other algorithms we study. The reasons behind these observations are analyzed by studying the best-of-generation fitness against generations and the trajectories of best-of-generation individuals when tracking the moving optima in the search space.

According to the studies of cognitive psychology, object typicality plays an important role in concept representation in human cognitive process. However, computational ontologies cannot reflect the typicality of objects in concepts. Besides, context is important in measuring object typicality. In this paper, we present a formal model of context-aware ontology with multi-prototype concept and object typicality based on studies of cognitive psychology. It can tackle the problem of formalizing object typicality in context-aware ontology, which is unsolved in previous models.

In some resource allocation problems, the capacities of resources may change gradually or abruptly. We study a class of such resource allocation problems in this paper. The system consists of competitive agents that choose among several resources with changing capacities. The objective is that agents can adapt to the dynamic environment and make good utilisation of resources. We design an adaptive strategy for agents to use so that agents are not only able to adapt to the environment with gradually changing capacities but also with abruptly changing capacities so as to make good utilisation of resources. This strategy is based on individual agent's experience and prediction. Simulations show that agents using the adaptive strategy can adapt effectively to the changing capacity levels and the system as a whole results in better utilisation of resources than previous work.

Combinatorial auctions, where bidders are allowed to put bids on bundles of items, are preferred to single-item auctions in the resource allocation problem because they allow bidders to express complementarities (substitutabilities) among items and therefore achieve better social efficiency. Although many works have been conducted on combinatorial auctions, most of them focus on the winner determination problem and the auction design. A large unexplored area of research in combinatorial auctions is the bidding strategies. In this paper, we propose a new adaptive bidding strategy in multi-round combinatorial auctions in static markets. The bidder adopting this strategy can adjust his profit margin constantly according to bidding histories to maximize his expected utility. Experiment results show that the adaptive bidding strategy performs fairly well when compared to the optimal fixed strategy in different market environments, even without any prior knowledge.

With the recent advances in Internet and mobile technologies and infrastructures, there are increasing demands for ubiquitous access to tourist information systems for service coordination and integration. However, disparate tourist information and service resources such as airlines, hotels, tour operators, etc., make it difficult for tourist to use them effectively when planning their trips and/or during their trips. Motivated by the emerging technologies of multi-agent information system (MAIS) and its ability to aid Internet and mobile users, together with semantic Web that can effectively organize information and service resources. In this paper, we propose a virtual travel agent system (VTAS), which is built upon these technologies. In this paper, we formulate a scalable, flexible, and intelligent MAIS architecture for VTAS with agent clusters based on a case study of a large service-oriented travel agency. Agent clusters may comprise several types of agents to achieve the goals of the major processes of a tourist's trip. We show how agents can make use of ontology from the semantic web help tourists better plan, understand, and specify their requirements. We further illustrate how this can be successfully implemented with Web service technologies to integrate disparate Internet tourist resources.

In coelvolution, species are coevolving in a way that the egentic changes of one species in response to another species are reciprocal. One class of coevolution is cooperative coevolution in which species collaborate to solve the probelms, The fitness of an individual in a species is assigned based on how well its collaboration with other individuals of another species can perform. As an extension of evolutionary algorithms (EAs), cooperative coelvolutionary algorithms (CCEAs) operate similar to EAs, except during fitness evaluations. In this paper, we focus on genetic variation operations of a CCEA: mutations. We present how to bias mutations is cooperative coevolution and compare the performance of a CCEA adopting biasing mutaions (CCEA-BM) and a conventional CCEA in which all individuals are encoded in binary representations. Our experimental study shows that biasing mutations can prove the performance of a CCEA on function optimization, in particular when high orders of binary representation are used.

In this study, a mutation method called "guided mutation" is proposed. In guided mutation, each individual maintains two mutation control parameters: mutation direction and mutation step size. Guidance in mutations is provided by continuous updates on these parameters during the evolutionary process. We apply guided mutations to cooperative coevolutionary algorithm (CCEA), and compare its performance of optimizing nine common problem domains with those of other CCEAs. Our results show that guided mutations can improve the performance of a CCEA in some problem domains. We discuss the implications of our results and suggest some directions for future research.

Cooperative coevolution is becoming increasingly popular in solving difficult optimization problems. Its performance to solve the problems is influenced by many algorithm decisions. In this paper, a self-adaptive mutation operator "guided mutation" is proposed. The basic idea behind guided mutation is to maintain searching directions and searching step sizes at individual level, and these two strategy parameters are adaptively updated. Guided mutation is adopted in cooperative coevolutionary algorithm and its performance on the common test problems is compared. Experimental results show that guided mutation can improve cooperative coevolution in solving some problem domains. The reasons behind the differences in the performance of the various cooperative coevolutions are also discussed.

Online buyer coalition formation problem is an application of e-commerce and distributed agent technology. Most existing works in this topic involve social utility based approaches that assume the agents' utilities to be transferable. However, we argue that there are situations where the transferable utility model is not well suited for the problem, and that coalition stability is a more important solution concept than social utility. In this paper, we study the problem from a non-transferable utility approach where the focus is on achieving stable solutions in term of the core and Pare to efficiency. A new distributed mechanism is proposed where agents are allowed to propose incremental improvements toward a stable solution. We show by experiment that our mechanism is able to reach core-stable solutions in over 99% of the cases, which suggests a big improvement over the existing approaches.

Many real life situations can be modeled as Prisoner's dilemma. There are various strategies in the literature. However, few of which match the design objectives of an intelligent agent - being reactive and pro-active. In this paper, we incorporate risk attitude and reputation into infinitely repeated games. In this way, we find that the original game matrix can be transformed to a new matrix, which has a kind of cooperative equilibrium. We use the proposed concepts to analyze the Iterated Prisoner's dilemma. Simulation also shows that agents, which consider risk attitude and reputation in the decision-making process, have improved performance and are reactive as well as pro-active.

Bandwidth allocation is one of the important research issues in peer-to-peer (P2P) networks. Many different allocation mechanisms have been proposed to tackle this problem. In this paper we propose the BBMRPTT mechanism that models the allocation process as a strategic game which has a unique social welfare maximizing (hence Pareto optimal) Nash equilibrium, at which each node reveals his true bandwidth demand. Moreover, the mechanism is strategy-proof and collusion-proof. A practical protocol is designed for competing nodes to reach the Nash equilibrium dynamically. Experimental results agree to the theoretical analysis.

Persistent conversation has emerged and become the basis of many Web communities nowadays. It is also widely used in e-commerce and extended enterprises. The registration procedures for the users of most Web communities are unreliable and can be easily compromised. In this paper, we propose an anonymous and secure conversation protocol based on a concept of alias certificate with analysis to show that our scheme satisfies such requirements

Software is becoming present in every aspect of our lives, pushing us inevitably towards a world of ambient computing systems. Multi-agent systems (MAS) are a prominent technology which facilitates modeling and development of large-scale distributed systems. In recent years, software engineering research has focused on methodologies and techniques for improving MAS design and implementation. However, making large MAS dependable is still an open issue. The Fifth Workshop on Software Engineering for Large-Scale Multi-Agent Systems (SELMAS 2006) aims to bring together academic, industrial and commercial communities interested in agent-oriented software engineering topics to discuss the different technologies being defined and used in the development of dependable MAS.

With the recent advances in mobile technologies and infrastructures, there are increasing demands for ubiquitous access to tourist information systems for service coordination and integration. However, disparate tourist information and service resources make it particularly difficult for mobile tourists to use them effectively during their trips. Neither can current tourist portals assist tourists proactively or adequately to overcome this problem. Motivated by the emerging technologies of multi-agent information systems (MAIS) that can effectively assist mobile users together with Semantic Web that can effectively organize information and service resources, we propose a ubiquitous tourist assistance system (UTAS) be built upon these technologies. In this paper, we formulate a scalable, flexible, and intelligent MAIS infrastructure for a proactive UTAS with agent clusters based on a case study of a large service-oriented travel agency. Each agent cluster comprises several types of agents to achieve the goals of the major processes of a tourist's trip. We show how agents can make use of ontology from the Semantic Web to plan better as well as help tourists better understand and specify their requirements and preferences. We discuss and evaluate our approach from different stakeholders' perspective.

In the current service-oriented economy, professional workforce and service personnel have to make not only reasonable but also personalized recommendations in response to individual customer's query. This affects not only the likelihood that the customer takes the recommendations as a short-term benefit but also the service providers' reputation in a long run. However, as different customers have different risk attitudes, they have different trade-off between the service providers' reputation and the recommendations' utilities. Therefore, the classical decision model considering only the utility and success rate is inadequate. We reconsider the problem of making recommendations from multiple perspectives, including reputation and risk attitude. We explain how this model can facilitate service providers to make effective decisions at strategic, tactical, and operations level regarding service recommendations.

New technologies have introduced new ways in business transactions where online contracting is complementing and even substituting traditional paper-based transactions. One of the major recent innovations of online contracting is the use of intelligent agents to make contracts among users and businesses around the globe. Despite recent legislations on electronic contracting, there are no legislations governing automatic agent transactions except one preliminary attempt in the USA. We identify the key problem rooted at the authorization management in agent delegation as well as the proper legal identity of agents. Therefore, we advocate solutions that consider both legal and technical aspects. Based on current legal and business practices, we develop a conceptual model for agent authorization and identity management We propose an Agent Authorization Platform (AAP) for the enforcement of agent authorization during contract establishment as well as the maintenance of the legal identity of agents. The AAP also supports alerts and acknowledgment to further enforce the user's manifestation of assent to the contract terms. We also detail a required security scheme for the AAP based on Public Key Infrastructure (PKI) technologies to demonstrate the feasibility of our approach.

Electronic online voting has become one of the most popular activities over Internet recently, since it can be performed in a way that is more convenient, faster and cheaper. Security and privacy are always regarded as crucial factors in electronic voting system design. Extensive studies have been made on the electronic voting in the last twenty years, and many schemes have been proposed, in which both the security as well as the effectiveness have been improved. However, most available secure vote schemes mainly focused on the simple "one-man-one-vote" plurality protocol. In this paper, we address the security issues in Approval voting protocol, another important social decision protocol, in which voters can vote for, or approval of, as many candidates as they wish in multi-candidate elections. By employing several cryptographic primitives, such as, homomorphic encryption, mix network, etc., we propose a voter-resolved secure Approval voting scheme over Internet which guarantees the complete privacy protection of the voters as well as the universal verifiability. The "voter-resolved" means that we do not assume the existence of any trusted or semi-trusted authorities in our scheme, instead, we employ the homomorphic ElGamal encryption and distribute the private key among the all voters to achieve complete privacy protection of voters. In such a way, all voters jointly compute the outcome of the election without revealing any further information of voters' individual preferences. An analysis of the protocol against the security requirements shows that the proposed protocol achieves complete privacy protection, public verifiability, weak robustness, in addition to others addressed by other protocols in the available literature.

Nurse rostering problem is one of the most difficult scheduling problems in artificial intelligence and operation research. In general, it consists of cardinality constraints and special pattern constraints that correspond to the given workforce demands, which form a complex problem structure. Many heuristics algorithms have been proposed to solve this particular problem. In this paper, we demonstrate the efficiency of our newly defined GCS/simplex solver, which incorporates simplex method into the GCS framework, on some difficult nurse rostering problem instances. Experimental results show that the GCS/Simplex solver is efficient in solving this kind of scheduling problems in terms of both computation time and number of fails.

There are several bidding strategies proposed in the literature for agents in continuous double auctions (CDAs). For most bidding strategies, the asks or bids determined are hard and cannot be compromised. However, for human traders, we notice that the decisions are usually soft and adaptive in different situations. Therefore, we believe that integrating softness and adaptivity into the bidding strategies can enhance the performance of agents. Experimental results confirm that when agents using different bidding strategies make adaptive and soft compromise in various situations, their performance is improved significantly in general. In order to guide agents to adopt soft asks or bids in dynamic and unknown markets, an adaptive mechanism is proposed to adjust the degree of softness of soft asks or bids according to the realtime market context. Experiments results show that agents adopting the adaptive mechanism generally outperform the corresponding agents without the adaptive mechanism.

Electronic voting has become one of the most popular activities over the Internet. Security and privacy are always regarded as crucial factors in electronic voting system design. Various secure voting schemes have been proposed in the past several years to ensure the safe operation of electronic voting and most of them have focused on the common "one man, one vote" plurality voting. In this paper, we study on the security and privacy issues in the Clarke tax voting protocol, another important social choice protocol. This protocol is important in electronic voting, especially software agent based voting, because a voter's dominant strategy is truth-telling, and consequently the overhead for counterspeculation is minimized. For the very same reason, it is essential to achieve the security and the privacy protection of voters so that voters' preferences need not be made known to the public, should this protocol be practical and popular. In this paper, we first present several cryptographic building blocks, including ElGamal cryptosystem, player-resolved distributed ElGamal decryption, proof of knowledge of 1-of-k plaintext and player-resolved mix network. Then we propose a secure Clarke tax voting protocol making use of these techniques. In the proposed protocol, we achieve privacy protection, universal verifiability as well as other security requirements, such as secrecy, eligibility, completeness, etc. One important feature of the proposed protocol is that the full privacy protection of voters is guaranteed, which means that all information in voting are kept secret even in the presence of any collusion of participants involved in the voting. The only information known publicly is the final voting result, i.e., the winning candidate and the tax for each voter.

In this paper, we propose an implementation of secure watermarking protocol using cryptographic technologies for use in real-life Internet retail market of digital contents, in which there is no trust assumption between a customer and a digital content provider. The blind RSA decryption algorithm is used in our scheme to doubly lock the information by the public key of the content provider and the secret numbers of the customer separately. The privacy of watermark pattern is maintained, while the digital rights of the contents provider are protected. This is achieved by allowing the customer to choose a secret pattern of watermark combination unknown to the content provider. Consequently, the quality of the watermarked digital contents can be guaranteed. We show that the protocol is secure against any possible attacks from the customer and the content provider. Moreover, the dispute resolution process becomes mechanical.

Extensive studies have been made on electronic voting in the last twenty years, and many schemes have been proposed, in which both security and effectiveness have been improved. However, most available secure vote schemes mainly focused on the simple "one man, one vote" plurality protocol. We address the security issues of the Borda voting protocol, another important social decision protocol, in which a voter can rank the candidates by assigning them different points. We propose a secure Borda voting scheme that guarantees full privacy protection of the voters as well as universal verifiability and weak robustness. Instead of assuming existence of trusted or semi-trusted authorities as in other secure voting schemes, we employ homomorphic ElGamal encryption in our scheme and distribute the private key among all voters to achieve full privacy protection of voters. In such a way, all voters jointly compute the outcome of the election without revealing any further information of voters' individual preferences. An analysis of the protocol against the security requirements shows that the new protocol achieves full privacy protection, public verifiability, weak robustness, in addition to others addressed by other protocols reported in the literature.

Systematic tree search augmented with constraint propagation has been regarded as the de facto standard approach to solve constraint satisfaction problems (CSPs). The property of completeness of tree search is superior to incomplete stochastic local search, although local search approach is more efficient in general. Many heuristics techniques have been developed to improve the efficiency of the tree search approach. We propose a framework for combining and coordinating a complete tree search solver and a different solver in order to produce a complete and efficient CSP solver. Three different instances of the framework have been suggested including combining complete tree search with stochastic search, mathematical programming approach respectively. The experimental results show that this highly integrated hybrid scheme greatly improve the efficiency of constraint solving process in terms of both computation time and number of backtracking.

Lam and Leung's trust/honesty model and other existing reputation models are not adaptive. With which, agents may lose a lot as they cannot learn from their experiences and cannot adapt to new environments. To solve the problem, we introduce an adaptive strategy to the trust/honesty model. The adaptive strategy enables agents to be more reactive. At the same time, the adaptive strategy also increases the degree of pro-activeness to the agents. In addition, we relate the adaptive rate to the utility that an agent has gained and has lost. This mimics the model in human interaction. Simulations show that agents adopting the trust/honesty model with adaptive strategy significantly outperform agents with other existing models and strategies.

Stochastic search methods have attracted much attention of the constraint satisfaction problem (CSP) research community. Traditionally, a stochastic solver escapes from local optima or leaves plateaus by random restart or heuristic learning. In this paper, we propose the progressive stochastic search (PSS) and its variants for solving binary CSPs, in which a variable always has to choose a new value when it is designated to be repaired. Intuitively, the search can be thought to be mainly driven by a "force" to "rush through" the local minima and plateaus. Timing results show that this approach significantly outperforms LSDL(GENET) (Choi et al, 2000) in N-Queens, Latin squares, random permutation generation problems and randomly CSPs, while it fails to win LSDL(GENET) in quasigroup completion problems and increasing permutation generation problems. This prompts an interesting new research direction in the design of stochastic search schemes.

This paper surveys and analyzes the state of the art of agent-mediated electronic commerce (e-commerce), concentrating particularly on the business-to-consumer (B2C) and business-to-business (B2B) aspects. From the consumer buying behavior perspective, agents are being used in the following activities: need identification, product brokering, buyer coalition formation, merchant brokering, and negotiation. The roles of agents in B2B e-commerce are discussed through the business-to-business transaction model that identifies agents as being employed in partnership formation, brokering, and negotiation. Having identified the roles for agents in B2C and B2B e-commerce, some of the key underpinning technologies of this vision are highlighted. Finally, we conclude by discussing the future directions and potential impediments to the wide-scale adoption of agent-mediated e-commerce.

Increasingly, many systems are being conceptualized, designed, and implemented as marketplaces in which autonomous software entities (agents) trade services. These services can be commodities in e-commerce applications or data and knowledge services in information economies. In many of these cases, there are both multiple agents that are looking to procure services and multiple agents that are looking to sell services at any one time. Such marketplaces are termed continuous double auctions (CDAs). Against this background, this paper develops new algorithms that buyer and seller agents can use to participate in CDAs. These algorithms employ heuristic fuzzy rules and fuzzy reasoning mechanisms in order to determine the best bid to make given the state of the marketplace. Moreover, we show how an agent can dynamically adjust its bidding behavior to respond effectively to changes in the supply and demand in the marketplace. We then show, by empirical evaluations, how our agents outperform four of the most prominent algorithms previously developed for CDAs (several of which have been shown to outperform human bidders in experimental studies).

With recent advances in mobile technologies and infrastructures, there are increasing demands for ubiquitous access to networked services. These services, generally known as m-services, extend supports from Web browsers on personal computers to handheld devices, such as mobile phones and PDAs. However, in general, the capabilities and bandwidth of these devices are significantly inferior to desktop computers over wired connections, which have been assumed by most Internet services. Instead of redesigning or adapting m-services in an ad-hoc manner for multiple platforms available in handheld devices, we propose a methodology for such adaptation based on three tiers: user interface views, data views, and process views. These views provide customization and help balance security and trust. User interface views provide alternative presentations of inputs and outputs. Data views summarize data over limited bandwidth and map heterogeneous data sources. In addition, we introduce a novel approach of applying process views to m-service adaptation, where mobile users may execute a more concise version or modified procedures of the original process. The process view also serves as the key mechanism for integrating user interface views and data views. In addition, we present a formal model on view consistency and integrity in our methodology. We demonstrate the feasibility of our methodology by extending a service negotiation subsystem into an m-service with multi-platform support.

In a decision process, when aggregating two values with conflict meaning, sometimes the result should be a tradeoff between the two values. Applicable to many real problems, compensation operators are aggregation operators with such a property. In order to offer more freedom in the selection of suitable compensation operators for various specific application, this paper explores new sorts of compensation operators. First, we introduce the concept of general compensation operators, which form a subclass of general aggregation operators. The two existing kinds of compensation operators, compensatory operators (a special case of uninorm operators) and averaging operators, are subclasses of our general compensation operators. Second, we identify seven new subclasses of the general compensation operators. Third, we construct a new kind of compensation operator, the gray averaging operator, which can include T-norms, T-conorm and averaging operators as its special cases.

Yager et al. (1996) first introduce compensatory operators. This paper further introduces a kind of weighted compensatory operators, and a kind of prioritised compensatory operators. The difference between these similar classes of operators are identified. In addition, the paper introduces the concepts of ordered weighted/prioritised compensatory aggregation.

This paper presents the design, implementation and evaluation of a fuzzy logic based bidding strategy, the FL-strategy, for an agent in a Continuous Double Auction (CDA). According to the outstanding bid, the outstanding ask and the reference price, the FL-strategy employs heuristic fuzzy rules and a reasoning mechanism to find the best ask/bid for an agent.

Constraint satisfaction is well known to be applicable in modeling AI problems. Despite their extensive literature, the framework is sometimes inflexible and the results are not very satisfactory when applied to real-life problems. With the incorporation of the theory of fuzzy sets, fuzzy constraint satisfaction problems (FCSP's) have been exploited. FCSP's model real-life problems better by allowing both full and partial satisfaction of individual constraints. GENET, which has been shown to be efficient and effective in solving certain traditional CSPs, has been extended to handle FCSPs. Through transforming FCSPs into 0-1 integer programming problems, Wong and Leung (1998) displayed the equivalence between the underlying working mechanism of fuzzy GENET and the discrete Lagrangian method. We focus on the performance of fuzzy GENET in attacking large-scale and real-life over-constrained problems. An efficient simulator of fuzzy GENET for single-processor machines is implemented. Benchmarking results confirm its feasibility, flexibility, and superb efficiency in tackling both CSPs and FCSPs.

In the literature, the problem of global termination detection in parallel systems is usually solved by message passing. In shared-memory systems, this problem can also be solved by using exclusively accessible variables with locking mechanisms. In this paper, we present an algorithm that solves the problem of global termination detection in shared-memory asynchronous multiprocessor systems without using locking. We assume a reasonable computation model in which concurrent reading does not require locking and concurrent writing different values without locking results in an arbitrary one of the values being actually written. For a system of n processors, the algorithm allocates a working space of 2n+1 bits. The worst case time complexity of the algorithm is n+2/spl radic/+1, which we prove is the lower bound under a reasonable model of computation.

GENET has been shown to be efficient and effective on certain hard or large constraint satisfaction problems. Although GENET has been enhanced to handle also the atmost and illegal constraints in addition to binary constraints, it is deficient in handling non binary constraints in general. We present E-GENET, an extended GENET. E-GENET features a convergence and learning procedure similar to that of GENET and a generic representation scheme for general constraints, which range from disjunctive constraints to non linear constraints to symbolic constraints. We have implemented an efficient prototype of E-GENET for single processor machines. Benchmarking results confirms the efficiency and flexibility of E-GENET. Our implementation also compares well against CHIP, PROCLANN, and GENET.

An execution model for AND-parallel execution of logic programs is presented. This model is designed on the basis of the Lin-Kumar-Leung model and a Backward Execution algorithm proposed by Conery. The new algorithm is applicable to non-static data dependency graphs