Previous research on causal reasoning often overlooks the subtleties crucial to understanding causal reasoning. To address this gap, our study introduces the concept of causal epistemic consistency, which focuses on the self-consistency of Large Language Models (LLMs) in differentiating intermediates with nuanced differences in causal reasoning. We propose a suite of novel metrics -- intensity ranking concordance, cross-group position agreement, and intra-group clustering -- to evaluate LLMs on this front. Through extensive empirical studies on 21 high-profile LLMs, including GPT-4, Claude3, and LLaMA3-70B, we have favoring evidence that current models struggle to maintain epistemic consistency in identifying the polarity and intensity of intermediates in causal reasoning. Additionally, we explore the potential of using internal token probabilities as an auxiliary tool to maintain causal epistemic consistency. In summary, our study bridges a critical gap in AI research by investigating the self-consistency over fine-grained intermediates involved in causal reasoning.

Conditional dichotomy, the contrast between two outputs conditioned on the same context, is vital for applications such as debate, defeasible natural language inference, and causal reasoning.Existing methods that rely on semantic similarity often fail to capture the nuanced oppositional dynamics essential for these applications.Motivated by these limitations, we introduce a novel task, Conditional Dichotomy Quantification (ConDQ), which formalizes the direct measurement of conditional dichotomy and provides carefully constructed datasets covering debate, defeasible natural language inference, and causal reasoning scenarios.To address this task, we develop the Dichotomy-oriented Geometric Embedding (DoGE) framework, which leverages complex-valued embeddings and a dichotomous objective to model and quantify these oppositional relationships effectively.Extensive experiments validate the effectiveness and versatility of DoGE, demonstrating its potential in understanding and quantifying conditional dichotomy across diverse NLP applications.Our code and datasets are available at https://github.com/cui-shaobo/ conditional-dichotomy-quantification.

Understanding uncertainty in causality is vital in various domains, including core NLP tasks like event causality extraction, commonsense reasoning, and counterfactual text generation.However, existing literature lacks a comprehensive examination of this area.This survey aims to fill this gap by thoroughly reviewing the uncertainty in causality.We first introduce a novel trichotomy, categorizing causal uncertainty into aleatoric (inherent randomness in causal data), epistemic (causal model limitations), and ontological (existence of causal links) uncertainty.We then survey methods for quantifying uncertainty in causal analysis and highlight the complementary relationship between causal uncertainty and causal strength.Furthermore, we examine the challenges that large language models (LLMs) face in handling causal uncertainty, such as hallucinations and inconsistencies, and propose key traits for an optimal causal LLM.Our paper reviews current approaches and outlines future research directions, aiming to serve as a practical guide for researchers and practitioners in this emerging field.

Large Language Models (LLMs) are increasingly expected to handle complex decision-making tasks, yet their ability to perform structured resource allocation remains underexplored. Evaluating their reasoning is also difficult due to data contamination and the static nature of existing benchmarks. We present a dual-purpose framework leveraging Participatory Budgeting (PB) both as (i) a practical setting for LLM-based resource allocation and (ii) an adaptive benchmark for evaluating their reasoning capabilities. We task LLMs with selecting project subsets under feasibility (e.g., budget) constraints via three prompting strategies: greedy selection, direct optimization, and a hill-climbing–inspired refinement. We benchmark LLMs’ allocations against a utility-maximizing oracle. Interestingly, we also test whether LLMs can infer structured preferences from natural-language voter input or metadata, without explicit votes. By comparing allocations based on inferred preferences to those from ground-truth votes, we evaluate LLMs’ ability to extract preferences from open-ended input. Our results underscore the role of prompt design and show that LLMs hold promise for mechanism design with unstructured inputs.

The increasing sophistication of text-to-image generative models raises challenges in defining and enforcing copyright criteria. Existing methods like watermarking and dataset deduplication fall short due to the lack of standardized metrics and the complexity of addressing copyright issues in diffusion models. To tackle these challenges, we propose RLCP, a Reinforcement Learning-based Copyright Protection method for Text-to-Image Diffusion Models. Our approach introduces a novel copyright metric grounded in legal precedents and employs the Denoising Diffusion Policy Optimization (DDPO) framework to minimize copyright-infringing content while preserving image quality. A reward function based on our metric and KL divergence regularization ensures stable fine-tuning. Experiments on mixed datasets of copyright and non-copyright images show that RLCP effectively reduces copyright infringement risk without compromising output quality.

In Federated Learning, heterogeneity in client data distributions often means that a single global model does not have the best performance for individual clients. Consider for example training a next-word prediction model for keyboards: user-specific language patterns due to demographics (dialect, age, etc.), language proficiency, and writing style result in a highly non-IID dataset across clients. Other examples are medical images taken with different machines, or driving data from different vehicle types. To address this, we propose a simple yet effective personalized federated learning framework (pFedLIA) that utilizes a computationally efficient influence approximation, called ‘Lazy Influence’, to cluster clients in a distributed manner before model aggregation. Within each cluster, data owners collaborate to jointly train a model that captures the specific data patterns of the clients. Our method has been shown to successfully recover the global model’s performance drop due to the non-IID-ness in various synthetic and real-world settings, specifically a next-word prediction task on the Nordic languages as well as several benchmark tasks. It matches the performance of a hypothetical Oracle clustering, and significantly improves on existing baselines, e.g., an improvement of 17% on CIFAR100.

Assessing whether AI-generated images are substantially similar to copyrighted works is a crucial step in resolving copyright disputes. In this paper, we propose CopyJudge, an automated copyright infringement identification framework that leverages large vision-language models (LVLMs) to simulate practical court processes for determining substantial similarity between copyrighted images and those generated by text-to-image diffusion models. Specifically, we employ an abstraction-filtration-comparison test framework with multi-LVLM debate to assess the likelihood of infringement and provide detailed judgment rationales. Based on the judgments, we further introduce a general LVLM-based mitigation strategy that automatically optimizes infringing prompts by avoiding sensitive expressions while preserving the non-infringing content. Besides, our approach can be enhanced by exploring non-infringing noise vectors within the diffusion latent space via reinforcement learning, even without modifying the original prompts.Experimental results show that our identification method achieves comparable state-of-the-art performance, while offering superior generalization and interpretability across various forms of infringement, and that our mitigation method could more effectively mitigate memorization and IP infringement without losing non-infringing expressions.

Luca Mouchel, Debjit Paul, Shaobo Cui, Robert West, Antoine Bosselut, Boi Faltings. 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.

Peer prediction incentive mechanisms for crowdsourcing are generally limited to eliciting samples from categorical distributions. Prior work on extending peer prediction to arbitrary distributions has largely relied on assumptions on the structures of the distributions or known properties of the data providers. We introduce a novel class of incentive mechanisms that extend peer prediction mechanisms to arbitrary distributions by replacing the notion of an exact match with a concept of neighborhood matching. We present conditions on the belief updates of the data providers that guarantee incentive-compatibility for rational data providers, and admit a broad class of possible reasonable updates.

In Federated Learning, it is crucial to handle low-quality, corrupted, or malicious data. However, traditional data valuation methods are not suitable due to privacy concerns. To address this, we propose a simple yet effective approach that utilizes a new influence approximation called "lazy influence" to filter and score data while preserving privacy. To do this, each participant uses their own data to estimate the influence of another participant’s batch and sends a differentially private obfuscated score to the central coordinator. Our method has been shown to successfully filter out biased and corrupted data in various simulated and real-world settings, achieving a recall rate of over > 90% (sometimes up to 100%) while maintaining strong differential privacy guarantees with ε ≤ 1.

Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, Boi Faltings. Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

Understanding commonsense causality is a unique mark of intelligence for humans.It helps people understand the principles of the real world better and benefits the decisionmaking process related to causation.For instance, commonsense causality is crucial in judging whether a defendant's action causes the plaintiff's loss in determining legal liability.Despite its significance, a systematic exploration of this topic is notably lacking.Our comprehensive survey bridges this gap by focusing on taxonomies, benchmarks, acquisition methods, qualitative reasoning, and quantitative measurements in commonsense causality, synthesizing insights from over 200 representative articles.Our work aims to provide a systematic overview, update scholars on recent advancements, provide a pragmatic guide for beginners, and highlight promising future research directions in this vital field.A summary of the related literature is available at https://github. com/cui-shaobo/causality-papers . Form ConnectivesCause-Effect Connectives Cause-Effect as, because, cause, since, bring about, due to, lead to, owing to, resulting in Consequence accordingly, as a result, consequently, for this reason, hence, so, therefore, thus Reason in light of, given that, on account of, by reason of, for the sake of, inasmuch as, seeing that Intention so that, in order to, so as to, with the aim of, for the purpose of, with this in mind, in hopes of Conditions if...then, provided that, assuming that, as long as, unless, in the event that Source arises from, stems from, comes from, originates from Counterfactual Connectives Hypothetical had...then, if it hadn't been for, had it not been for, if only Negation were it not for, but for, if it weren't for, without, in the absence of, lacking

There has recently been growing interest in the automatic generation of cooking recipes that satisfy some form of dietary restrictions, thanks in part to the availability of online recipe data.Prior studies have used pre-trained language models, or relied on small paired recipe data (e.g., a recipe paired with a similar one that satisfies a dietary constraint).However, pre-trained language models generate inconsistent or incoherent recipes, and paired datasets are not available at scale.We address these deficiencies with RecipeCrit, a hierarchical denoising auto-encoder that edits recipes given ingredientlevel critiques.The model is trained for recipe completion to learn semantic relationships within recipes.Our work's main innovation is our unsupervised critiquing module that allows users to edit recipes by interacting with the predicted ingredients; the system iteratively rewrites recipes to satisfy users' feedback.Experiments on the Recipe1M recipe dataset show that our model can more effectively edit recipes compared to strong language-modeling baselines, creating recipes that satisfy user constraints and are more correct, serendipitous, coherent, and relevant as measured by human judges.

Artificial Intelligence often relies on information obtained from others through crowdsourcing, federated learning, or data markets. It is crucial to ensure that this data is accurate. Over the past 20 years, a variety of incentive mechanisms have been developed that use game theory to reward the accuracy of contributed data. These techniques are applicable to many settings where AI uses contributed data. This survey categorizes the different techniques and their properties, and shows their limits and tradeoffs. It identifies open issues and points to possible directions to address these.

Utterance-level intent detection and token-level slot filling are two key tasks for spoken language understanding (SLU) in task-oriented systems. Most existing approaches assume that only a single intent exists in an utterance. However, there are often multiple intents within an utterance in real-life scenarios. In this paper, we propose a multi-intent SLU framework, called SLIM, to jointly learn multi-intent detection and slot filling based on BERT. To fully exploit the existing annotation data and capture the interactions between slots and intents, SLIM introduces an explicit slot-intent classifier to learn the many-to-one mapping between slots and intents. Empirical results on three public multi-intent datasets demonstrate (1) the superior performance of SLIM compared to the current state-of-the-art for SLU with multiple intents and (2) the benefits obtained from the slot-intent classifier.

Abstract Can artificial agents benefit from human conventions? Human societies manage to successfully self-organize and resolve the tragedy of the commons in common-pool resources, in spite of the bleak prediction of non-cooperative game theory. On top of that, real-world problems are inherently large-scale and of low observability. One key concept that facilitates human coordination in such settings is the use of conventions. Inspired by human behavior, we investigate the learning dynamics and emergence of temporal conventions, focusing on common-pool resources. Extra emphasis was given in designing arealistic evaluation setting: (a) environment dynamics are modeled on real-world fisheries, (b) we assume decentralized learning, where agents can observe only their own history, and (c) we run large-scale simulations (up to 64 agents). Uncoupled policies and low observability make cooperation hard to achieve; as the number of agents grow, the probability of taking a correct gradient direction decreases exponentially. By introducing anarbitrary common signal(e.g., date, time, or any periodic set of numbers) as a means to couple the learning process, we show that temporal conventions can emerge and agents reachsustainableharvesting strategies. The introduction of the signal consistently improves the social welfare (by $$258\%$$ 258% on average, up to $$3306\%$$ 3306% ), the range of environmental parameters where sustainability can be achieved (by $$46\%$$ 46% on average, up to $$300\%$$ 300% ), and the convergence speed in low abundance settings (by $$13\%$$ 13% on average, up to $$53\%$$ 53% ).

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on Device-to-Device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distributed ledgers (DLs) to function. DLs, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However, such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing DLs are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce and analyze Mneme, a DAG-based DL that can be maintained solely by mobile devices. Mneme utilizes two novel consensus protocols: 1) Proof of Context (PoC) and 2) Proof of Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze Mneme’s security and justify the ability of PoC and PoE to guarantee the characteristics of DLs: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.

LIA

No abstract available.

Automated predictions require explanations to be interpretable by humans. Past work used attention and rationale mechanisms to find words that predict the target variable of a document. Often though, they result in a tradeoff between noisy explanations or a drop in accuracy. Furthermore, rationale methods cannot capture the multi-faceted nature of justifications for multiple targets, because of the non-probabilistic nature of the mask. In this paper, we propose the Multi-Target Masker (MTM) to address these shortcomings. The novelty lies in the soft multi-dimensional mask that models a relevance probability distribution over the set of target variables to handle ambiguities. Additionally, two regularizers guide MTM to induce long, meaningful explanations. We evaluate MTM on two datasets and show, using standard metrics and human annotations, that the resulting masks are more accurate and coherent than those generated by the state-of-the-art methods. Moreover, MTM is the first to also achieve the highest F1 scores for all the target variables simultaneously.

As the labeling cost for different modules in task-oriented dialog (ToD) systems is expensive, a major challenge is to train different modules with the least amount of labeled data.Recently, large-scale pre-trained language models, have shown promising results for few-shot learning in ToD.In this paper, we devise a selftraining approach to utilize the abundant unlabeled dialog data to further improve state-ofthe-art pre-trained models in few-shot learning scenarios for ToD systems.Specifically, we propose a self-training approach that iteratively labels the most confident unlabeled data to train a stronger Student model.Moreover, a new text augmentation technique (GradAug) is proposed to better train the Student by replacing non-crucial tokens using a masked language model.We conduct extensive experiments and present analyses on four downstream tasks in ToD, including intent classification, dialog state tracking, dialog act prediction, and response selection.Empirical results demonstrate that the proposed self-training approach consistently improves state-of-the-art pre-trained models (BERT, ToD-BERT) when only a small number of labeled data are available.

Using personalized explanations to support recommendations has been shown to increase trust and perceived quality. However, to actually obtain better recommendations, there needs to be a means for users to modify the recommendation criteria by interacting with the explanation. We present a novel technique using aspect markers that learns to generate personalized explanations of recommendations from review texts, and we show that human users significantly prefer these explanations over those produced by state-of-the-art techniques. Our work's most important innovation is that it allows users to react to a recommendation by critiquing the textual explanation: removing (symmetrically adding) certain aspects they dislike or that are no longer relevant (symmetrically that are of interest). The system updates its user model and the resulting recommendations according to the critique. This is based on a novel unsupervised critiquing method for single- and multi-step critiquing with textual explanations. Empirical results show that our system achieves good performance in adapting to the preferences expressed in multi-step critiquing and generates consistent explanations.

We present a multi-agent learning algorithm, ALMA-Learning, for efficient and fair allocations in large-scale systems. We circumvent the traditional pitfalls of multi-agent learning (e.g., the moving target problem, the curse of dimensionality, or the need for mutually consistent actions) by relying on the ALMA heuristic as a coordination mechanism for each stage game. ALMA-Learning is decentralized, observes only own action/reward pairs, requires no inter-agent communication, and achieves near-optimal (<5% loss) and fair coordination in a variety of synthetic scenarios and a real-world meeting scheduling problem. The lightweight nature and fast learning constitute ALMA-Learning ideal for on-device deployment.

Recent studies have shown that providing personalized explanations alongside recommendations increases trust and perceived quality. Furthermore, it gives users an opportunity to refine the recommendations by critiquing parts of the explanations. On one hand, current recommender systems model the recommendation, explanation, and critiquing objectives jointly, but this creates an inherent trade-off between their respective performance. On the other hand, although recent latent linear critiquing approaches are built upon an existing recommender system, they suffer from computational inefficiency at inference due to the objective optimized at each conversation’s turn. We address these deficiencies with M&Ms-VAE, a novel variational autoencoder for recommendation and explanation that is based on multimodal modeling assumptions. We train the model under a weak supervision scheme to simulate both fully and partially observed variables. Then, we leverage the generalization ability of a trained M&Ms-VAE model to embed the user preference and the critique separately. Our work’s most important innovation is our critiquing module, which is built upon and trained in a self-supervised manner with a simple ranking objective. Experiments on four real-world datasets demonstrate that among state-of-the-art models, our system is the first to dominate or match the performance in terms of recommendation, explanation, and multi-step critiquing. Moreover, M&Ms-VAE processes the critiques up to 25.6x faster than the best baselines. Finally, we show that our model infers coherent joint and cross generation, even under weak supervision, thanks to our multimodal-based modeling and training scheme.

Recommendations with personalized explanations have been shown to increase user trust and perceived quality and help users make better decisions. Moreover, such explanations allow users to provide feedback by critiquing them. Several algorithms for recommender systems with multi-step critiquing have therefore been developed. However, providing a user-friendly interface based on personalized explanations and critiquing has not been addressed in the last decade. In this paper, we introduce four different web interfaces (available under https://lia.epfl.ch/critiquing/) helping users making decisions and finding their ideal item. We have chosen the hotel recommendation domain as a use case even though our approach is trivially adaptable for other domains. Moreover, our system is model-agnostic (for both recommender systems and critiquing models) allowing a great flexibility and further extensions. Our interfaces are above all a useful tool to help research in recommendation with critiquing. They allow to test such systems on a real use case and also to highlight some limitations of these approaches to find solutions to overcome them.

The goal of fairness in classification is to learn a classifier that does not discriminate against groups of individuals based on sensitive attributes, such as race and gender. One approach to designing fair algorithms is to use relaxations of fairness notions as regularization terms or in a constrained optimization problem. We observe that the hyperbolic tangent function can approximate the indicator function. We leverage this property to define a differentiable relaxation that approximates fairness notions provably better than existing relaxations. In addition, we propose a model-agnostic multi-objective architecture that can simultaneously optimize for multiple fairness notions and multiple sensitive attributes and supports all statistical parity-based notions of fairness. We use our relaxation with the multi-objective architecture to learn fair classifiers. Experiments on public datasets show that our method suffers a significantly lower loss of accuracy than current debiasing algorithms relative to the unconstrained model.

The next technological revolution will be interwoven to the proliferation of intelligent systems. As we bridge the gap between physical and cyber worlds, we will give rise to large-scale, multi-agent based technologies. A key challenge that cities of the future will have to face is coordination in the use of limited resources, central to which is finding an optimal allocation between agents. To truly allow for scalable solutions, we needs to shift from traditional approaches, to multi-agent solutions, ideally run on-device.

Traditional differential privacy is independent of the data distribution. However, this is not well-matched with the modern machine learning context, where models are trained on specific data. As a result, achieving meaningful privacy guarantees in ML often excessively reduces accuracy. We propose Bayesian differential privacy (BDP), which takes into account the data distribution to provide more practical privacy guarantees. We also derive a general privacy accounting method under BDP, building upon the well-known moments accountant. Our experiments demonstrate that in-distribution samples in classic machine learning datasets, such as MNIST and CIFAR-10, enjoy significantly stronger privacy guarantees than postulated by DP, while models maintain high classification accuracy.

We derive conditions under which a peer-consistency mechanism can be used to elicit truthful data from non-trusted rational agents when an aggregate statistic of the collected data affects the amount of their incentives to lie. Furthermore, we discuss the relative saving that can be achieved by the mechanism, compared to the rational outcome, if no such mechanism was implemented. Our work is motivated by distributed platforms, where decentralized data oracles collect information about real-world events, based on the aggregate information provided by often self-interested participants. We compare our theoretical observations with numerical simulations on two public real datasets.

Blockchain based systems allow various kinds of financial transactions to be executed in a decentralized manner. However, these systems often rely on a trusted third party (oracle) to get correct information about the real-world events, which trigger the financial transactions. In this paper, we identify two biggest challenges in building decentralized, trustless and transparent oracles. The first challenge is acquiring correct information about the real-world events without relying on a trusted information provider. We show how a peer-consistency incentive mechanism can be used to acquire truthful information from an untrusted and self-interested crowd, even when the crowd has outside incentives to provide wrong informations. The second is a system design and implementation challenge. For the first time, we show how to implement a trustless and transparent oracle in Ethereum. We discuss various non-trivial issues that arise in implementing peer-consistency mechanisms in Ethereum, suggest several optimizations to reduce gas cost and provide empirical analysis.

Increasing concerns with privacy have stimulated interests in Session-based Recommendation (SR) using no personal data other than what is observed in the current browser session. Existing methods are evaluated in static settings which rarely occur in real-world applications. To better address the dynamic nature of SR tasks, we study an incremental SR scenario, where new items and preferences appear continuously. We show that existing neural recommenders can be used in incremental SR scenarios with small incremental updates to alleviate computation overhead and catastrophic forgetting. More importantly, we propose a general framework called Memory Augmented Neural model (MAN). MAN augments a base neural recommender with a continuously queried and updated nonparametric memory, and the predictions from the neural and the memory components are combined through another lightweight gating network. We empirically show that MAN is well-suited for the incremental SR task, and it consistently outperforms state-oft-he-art neural and nonparametric methods. We analyze the results and demonstrate that it is particularly good at incrementally learning preferences on new and infrequent items.

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users' context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.

Today, recommender systems are an inevitable part of everyone’s daily digital routine and are present on most internet platforms. State-of-the-art deep learning-based models require a large number of data to achieve their best performance. Many datasets fulfilling this criterion have been proposed for multiple domains, such as Amazon products, restaurants, or beers. However, works and datasets in the hotel domain are limited: the largest hotel review dataset is below the million samples. Additionally, the hotel domain suffers from a higher data sparsity than traditional recommendation datasets and therefore, traditional collaborative-filtering approaches cannot be applied to such data. In this paper, we propose HotelRec, a very large-scale hotel recommendation dataset, based on TripAdvisor, containing 50 million reviews. To the best of our knowledge, HotelRec is the largest publicly available dataset in the hotel domain (50M versus 0.9M) and additionally, the largest recommendation dataset in a single domain and with textual reviews (50M versus 22M). We release HotelRec for further research: https://github.com/Diego999/HotelRec.

Today’s research progress in the field of multi-document summarization is obstructed by the small number of available datasets. Since the acquisition of reference summaries is costly, existing datasets contain only hundreds of samples at most, resulting in heavy reliance on hand-crafted features or necessitating additional, manually annotated data. The lack of large corpora therefore hinders the development of sophisticated models. Additionally, most publicly available multi-document summarization corpora are in the news domain, and no analogous dataset exists in the video game domain. In this paper, we propose GameWikiSum, a new domain-specific dataset for multi-document summarization, which is one hundred times larger than commonly used datasets, and in another domain than news. Input documents consist of long professional video game reviews as well as references of their gameplay sections in Wikipedia pages. We analyze the proposed dataset and show that both abstractive and extractive models can be trained on it. We release GameWikiSum for further research: https://github.com/Diego999/GameWikiSum.

Session-based recommendation has received growing attention recently due to the increasing privacy concern. Despite the recent success of neural session-based recommenders, they are typically developed in an offline manner using a static dataset. However, recommendation requires continual adaptation to take into account new and obsolete items and users, and requires “continual learning” in real-life applications. In this case, the recommender is updated continually and periodically with new data that arrives in each update cycle, and the updated model needs to provide recommendations for user activities before the next model update. A major challenge for continual learning with neural models is catastrophic forgetting, in which a continually trained model forgets user preference patterns it has learned before. To deal with this challenge, we propose a method called Adaptively Distilled Exemplar Replay (ADER) by periodically replaying previous training samples (i.e., exemplars) to the current model with an adaptive distillation loss. Experiments are conducted based on the state-of-the-art SASRec model using two widely used datasets to benchmark ADER with several well-known continual learning techniques. We empirically demonstrate that ADER consistently outperforms other baselines, and it even outperforms the method using all historical data at every update cycle. This result reveals that ADER is a promising solution to mitigate the catastrophic forgetting issue towards building more realistic and scalable session-based recommenders.

An important class of game-theoretic incentive mechanisms for eliciting effort from a crowd are the peer based mechanisms, in which workers are paid by matching their answers with one another. The other classic mechanism is to have the workers solve some gold standard tasks and pay them according to their accuracy on gold tasks. This mechanism ensures stronger incentive compatibility than the peer based mechanisms but assigning gold tasks to all workers becomes inefficient at large scale. We propose a novel mechanism that assigns gold tasks to only a few workers and exploits transitivity to derive accuracy of the rest of the workers from their peers’ accuracy. We show that the resulting mechanism ensures a dominant notion of incentive compatibility and fairness.

We describe the selection, implementation and online evaluation of two e-commerce recommender systems developed with our partner company, Prediggo. The first one is based on the novel method of Bayesian Variable-order Markov Modeling (BVMM). The second, SSAGD, is a novel variant of the Matrix-Factorization technique (MF), which is considered state-of-the-art in the recommender literature.We discuss the offline tests we carried out to select the best MF variant, and present the results of two A/B tests performed on live ecommerce websites after the deployment of the new algorithms. Comparing the new recommenders and Prediggo’s proprietary algorithm of Ontology Filtering, we show that the BVMM significantly outperforms the two others in terms of CTR and prediction speed, and leads to a strong increase in recommendation-mediated sales. Although MF exhibits reasonably good accuracy, the BVMM is still significantly more accurate and avoids the high memory requirements of MF. This scalability is essential for its application in online businesses.

Recent studies have shown that the labels collected from crowdworkers can be discriminatory with respect to sensitive attributes such as gender and race. This raises questions about the suitability of using crowdsourced data for further use, such as for training machine learning algorithms. In this work, we address the problem of fair and diverse data collection from a crowd under budget constraints. We propose a novel algorithm which maximizes the expected accuracy of the collected data, while ensuring that the errors satisfy desired notions of fairness. We provide guarantees on the performance of our algorithm and show that the algorithm performs well in practice through experiments on a real dataset.

We consider the problem of reinforcing federated learning with formal privacy guarantees. We propose to employ Bayesian differential privacy, a relaxation of differential privacy for similarly distributed data, to provide sharper privacy loss bounds. We adapt the Bayesian privacy accounting method to the federated setting and suggest multiple improvements for more efficient privacy budgeting at different levels. Our experiments show significant advantage over the state-of-the-art differential privacy bounds for federated learning on image classification tasks, including a medical application, bringing the privacy budget below ε = 1 at the client level, and below ε = 0.1 at the instance level. Lower amounts of noise also benefit the model accuracy and reduce the number of communication rounds.

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on the convergence speed that is polynomial in the desired number of resources and competing agents per resource; crucially, in the realistic case where the aforementioned quantities are bounded independently of the total number of agents/resources, the convergence time remains constant as the total problem size increases. We have evaluated ALMA under three test cases: (i) an anti-coordination scenario where agents with similar preferences compete over the same set of actions, (ii) a resource allocation scenario in an urban environment, under a constant-time constraint, and finally, (iii) an on-line matching scenario using real passenger-taxi data. In all of the cases, ALMA was able to reach high social welfare, while being orders of magnitude faster than the centralized, optimal algorithm. The latter allows our algorithm to scale to realistic scenarios with hundreds of thousands of agents, e.g., vehicle coordination in urban environments.

Natural language generation (NLG) is an essential component of task-oriented dialogue systems. Despite the recent success of neural approaches for NLG, they are typically developed for particular domains with rich annotated training examples. In this paper, we study NLG in a low-resource setting to generate sentences in new scenarios with handful training examples. We formulate the problem from a meta-learning perspective, and propose a generalized optimization-based approach (Meta-NLG) based on the well-recognized model-agnostic meta-learning (MAML) algorithm. Meta-NLG defines a set of meta tasks, and directly incorporates the objective of adapting to new low-resource NLG tasks into the meta-learning optimization process. Extensive experiments are conducted on a large multi-domain dataset (MultiWoz) with diverse linguistic variations. We show that Meta-NLG significantly outperforms other training procedures in various low-resource configurations. We analyze the results, and demonstrate that Meta-NLG adapts extremely fast and well to low-resource situations.

Biased decision making by machine learning systems is increasingly recognized as an important issue. Recently, techniques have been proposed to learn non-discriminatory clas- sifiers by enforcing constraints in the training phase. Such constraints are either non-convex in nature (posing computational difficulties) or don’t have a clear probabilistic interpretation. Moreover, the techniques offer little understanding of the more subjective notion of fairness. In this paper, we introduce a novel technique to achieve non-discrimination without sacrificing convexity and probabilistic interpretation. Our experimental analysis demonstrates the success of the method on popular real datasets including ProPublica’s COMPAS dataset. We also propose a new notion of fairness for machine learning and show that our technique satisfies this subjective fairness criterion.

We study a problem of optimal information gathering from multiple data providers that need to be incentivized to provide accurate information. This problem arises in many real world applications that rely on crowdsourced data sets, but where the process of obtaining data is costly. A notable example of such a scenario is crowd sensing. To this end, we formulate the problem of optimal information gathering as maximization of a submodular function under a budget constraint, where the budget represents the total expected payment to data providers. Contrary to the existing approaches, we base our payments on incentives for accuracy and truthfulness, in particular, peer prediction methods that score each of the selected data providers against its best peer, while ensuring that the minimum expected payment is above a given threshold. We first show that the problem at hand is hard to approximate within a constant factor that is not dependent on the properties of the payment function. However, for given topological and analytical properties of the instance, we construct two greedy algorithms, respectively called PPCGreedy and PPCGreedyIter, and establish theoretical bounds on their performance w.r.t. the optimal solution. Finally, we evaluate our methods using a realistic crowd sensing testbed.

We introduce a novel technique to achieve non-discrimination in machine learning without sacrificing convexity and probabilistic interpretation. We also propose a new notion of fairness for machine learning called the weighted proportional fairness and show that our technique satisfies this subjective fairness criterion.

The popularity and applicability of mobile crowdsensing applications are continuously increasing due to the widespread of mobile devices and their sensing and processing capabilities. However, we need to offer appropriate incentives to the mobile users who contribute their resources and preserve their privacy. Blockchain technologies enable semi-anonymous multi-party interactions and can be utilized in crowdsensing applications to maintain the privacy of the mobile users while ensuring first-rate crowdsensed data. In this work, we propose to use blockchain technologies and smart contracts to orchestrate the interactions between mobile crowdsensing providers and mobile users for the case of spatial crowdsensing, where mobile users need to be at specific locations to perform the tasks. Smart contracts, by operating as processes that are executed on the blockchain, are used to preserve users' privacy and make payments. Furthermore, for the assignment of the crowdsensing tasks to the mobile users, we design a truthful, cost-optimal auction that minimizes the payments from the crowdsensing providers to the mobile users. Extensive experimental results show that the proposed privacy preserving auction outperforms state-of-the-art proposals regarding cost by ten times for high numbers of mobile users and tasks.

Recommender systems typically determine the items they should recommend by learning models of user-preferences. Most often, those preferences are modeled as static and independent of context. In real life however, users consider items in sequence: TV series are watched episode by episode and accessories are chosen after the main appliance. Unfortunately, since sequences are more complex to model, they are often not taken into account. We developed an efficient sequence-modeling approach based on Bayesian Variable-order Markov Models and combined it with an existing content-based system, the Ontology Filtering. We tested this approach through live evaluations on two e-commerce sites. It dramatically increased performance, more than doubling the CTR and strongly increasing recommendation-mediated sales. These tests also confirm that the technique works efficiently and reliably in a production setting.

An important task for intelligent healthcare systems is to predict the effect of a new intervention on individuals. This is especially true for medical treatments. For example, consider patients who do not respond well to a new drug or have adversary reactions. Predicting the likelihood of positive or negative response before trying the drug on the patient can potentially save his or her life. We are therefore interested in identifying distinctive subpopulations that respond differently to a given intervention. For this purpose, we have developed a novel technique, Intervention-based Clustering, based on a Bayesian mixture model. Compared to the baseline techniques, the novelty of our approach lies in its ability to model complex decision boundaries by using soft clustering, thus predicting the effect for individuals more accurately. It can also incorporate prior knowledge, making the method useful even for smaller datasets. We demonstrate how our method works by applying it to both simulated and real data. Results of our evaluation show that our model has strong predictive power and is capable of producing high-quality clusters compared to the baseline methods.

We propose a distributed upper confidence bound approach, DUCT, for solving distributed constraint optimization problems. We compare four variants of this approach with a baseline random sampling algorithm, as well as other complete and incomplete algorithms for DCOPs. Under general assumptions, we theoretically show that the solution found by DUCT after T steps is approximately T −1 -close to the optimal. Experimentally, we show that DUCT matches the optimal solution found by the well-known DPOP and O-DPOP algorithms on moderate-size problems, while always requiring less agent communication. For larger problems, where DPOP fails, we show that DUCT produces significantly better solutions than local, incomplete algorithms. Overall, we believe that DUCT is a practical, scalable algorithm for complex DCOPs.

Dynamic resource assignment is a common problem in multi-agent systems. We consider scenarios in which dynamic agents have preferences about assignments and the resources that can be assigned using online auctions. We study the trade-off between the following online auction properties: (i) truthfulness, (ii) expressiveness, (iii) efficiency, and (iv) average case performance. We theoretically and empirically compare four different online auctions: (i) Arrival Priority Serial Dictatorship, (ii) Split Dynamic VCG, (iii) e-Action, and (iv) Online Ranked Competition Auction. The latter is a novel design based on the competitive secretary problem. We show that, in addition to truthfulness and algorithmic efficiency, the degree of competition also plays an important role in selecting the best algorithm for a given context.

Motivating workers to provide significant effort has been recognized as an important issue in crowdsourcing. It is important not only to compensate worker effort, but also to discourage low-quality workers from participating. Several proper incentive schemes have been proposed for this purpose; they are either based on gold tasks or on peer consistency in individual tasks. As the rewards cannot become negative, these schemes have difficulty in achieving zero expected reward for random answers. We describe a novel boosting scheme, ProperRBoost, that improves the efficiency of existing incentive schemes by making a better separation between incentives for high and low quality work, and effectively discourages random answers by assigning them near minimal average rewards. We show the actual performance of the boosting scheme through simulations of various worker strategies.

The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin is a peer-to-peer (P2P) cryptocurrency protocol enabling transactions between individuals without the need of a trusted authority. Its network is formed from resources contributed by individuals known as miners. Users of Bitcoin currency create transactions that are stored in a specialised data structure called a block chain. Bitcoin's security lies in a proof-of-work scheme, which requires high computational resources at the miners. These miners have to be synchronised with any update in the network, which produces high data traffic rates. Despite advances in mobile technology, no cryptocurrencies have been proposed for mobile devices. This is largely due to the lower processing capabilities of mobile devices when compared with conventional computers and the poorer Internet connectivity to that of the wired networking. In this work, we propose LocalCoin, an alternative cryptocurrency that requires minimal computational resources, produces low data traffic and works with off-the-shelf mobile devices. LocalCoin replaces the computational hardness that is at the root of Bitcoin's security with the social hardness of ensuring that all witnesses to a transaction are colluders. It is based on opportunistic networking rather than relying on infrastructure and incorporates characteristics of mobile networks such as users' locations and their coverage radius in order to employ an alternative proof-of-work scheme. Localcoin features (i) a lightweight proof-of-work scheme and (ii) a distributed block chain.

Crowdsourcing is widely proposed as a method to solve a large variety of judgment tasks, such as classifying website content, peer grading in online courses, or collecting real-world data. As the data reported by workers cannot be verified, there is a tendency to report random data without actually solving the task. This can be countered by making the reward for an answer depend on its consistency with answers given by other workers, an approach called peer consistency . However, it is obvious that the best strategy in such schemes is for all workers to report the same answer without solving the task. Dasgupta and Ghosh [2013] show that, in some cases, exerting high effort can be encouraged in the highest-paying equilibrium. In this article, we present a general mechanism that implements this idea and is applicable to most crowdsourcing settings. Furthermore, we experimentally test the novel mechanism, and validate its theoretical properties.

The modern web critically depends on aggregation of information from self-interested agents, for example opinion polls, product ratings, or crowdsourcing. We consider a setting where multiple objects (questions, products, tasks) are evaluated by a group of agents. We first construct a minimal peer prediction mechanism that elicits honest evaluations from a homogeneous population of agents with different private beliefs. Second, we show that it is impossible to strictly elicit honest evaluations from a heterogeneous group of agents with different private beliefs. Nevertheless, we provide a modified version of a divergence-based Bayesian Truth Serum that incentivizes agents to report consistently, making truthful reporting a weak equilibrium of the mechanism.

We investigate how metrics that can be measured offline can be used to predict the online performance of recommender systems, thus avoiding costly A-B testing. In addition to accuracy metrics, we combine diversity, coverage, and serendipity metrics to create a new performance model. Using the model, we quantify the trade-off between different metrics and propose to use it to tune the parameters of recommender algorithms without the need for online testing. Another application for the model is a self-adjusting algorithm blend that optimizes a recommender's parameters over time. We evaluate our findings on data and experiments from news websites.

Many Artificial Intelligence tasks need large amounts of commonsense knowledge. Because obtaining this knowledge through machine learning would require a huge amount of data, a better alternative is to elicit it from people through human computation. We consider the sentiment classification task, where knowledge about the contexts that impact word polarities is crucial, but hard to acquire from data. We describe a novel task design that allows us to crowdsource this knowledge through Amazon Mechanical Turk with high quality. We show that the commonsense knowledge acquired in this way dramatically improves the performance of established sentiment classification methods.

There is much interest in crowdsourcing information that is distributed among many individuals, such as the likelihood of future events, election outcomes, the quality of products, or the consequence of a decision. To obtain accurate outcomes, various game-theoretic incentive schemes have been proposed. However, only prediction markets have been tried in practice. In this paper, we describe an experimental platform, swissnoise, that compares prediction markets with peer prediction schemes developed in recent AI research. It shows that peer prediction schemes can achieve similar performance while being applicable to a much broader range of questions.

Air pollution has a direct impact to human health, and data-driven air quality models are useful for evaluating population exposure to air pollutants. In this paper, we propose a novel region-based Gaussian process model for estimating urban air pollution dispersion, and applied it to a large dataset of ultrafine particle (UFP) measurements collected from a network of sensors located on several trams in the city of Zurich. We show that compared to existing grid-based models, the region-based model produces better predictions across aggregates of all time scales. The new model is appropriate for many useful user applications such as exposure assessment and anomaly detection.

We consider settings where a collective intelligence is formed by aggregating information contributed from many independent agents, such as product reviews, community sensing, or opinion polls. We propose a novel mechanism that elicits both private signals and beliefs. The mechanism extends the previous versions of the Bayesian Truth Serum (the original BTS, the RBTS, and the multi-valued BTS), by allowing small populations and non-binary private signals, while not requiring additional assumptions on the belief updating process. For priors that are sufficiently smooth, such as Gaussians, the mechanism allows signals to be continuous.

In online labor platforms such as Amazon Mechanical Turk, a good strategy to obtain quality answers is to take aggregate answers submitted by multiple workers, exploiting the wisdom of crowds. However, human computation issusceptible to systematic biases which cannot be corrected by using multiple workers.We investigate a game-theoretic bonus scheme, called peer truth serum (PTS), to overcome this problem. We report on the design and outcomes of a set of experiments to validate this scheme. Results show peer truth serum can indeed correct the biases and increase the answer accuracy by up to 80%.

We report on the live evaluation of various news recommender systems conducted on the website swissinfo.ch. We demonstrate that there is a major difference between offline and online accuracy evaluations. In an offline setting, recommending most popular stories is the best strategy, while in a live environment this strategy is the poorest. For online setting, context-tree recommender systems which profile the users in real-time improve the click-through rate by up to 35%. The visit length also increases by a factor of 2.5. Our experience holds important lessons for the evaluation of recommender systems with offline data as well as for the use of the click-through rate as a performance indicator.

Traditionally in mobile apps, news articles and recommendations are presented to the users as an ordered list. This ordering often reflects the freshness of the stories. Although most users are satisfied with such presentation, some users have different expectations and want to read stories related to some specific topics. In this demo, we depart from the classic list-view layout and aim at exploring other ways to present news stories to the users. We introduce Focal, a personalized mobile news reader, which implements a fisheye-inspired interface. We briefly describe its system architecture and interface.

We analyze symmetric protocols to rationally coordinate on an asymmetric, efficient allocation in an infinitely repeated N-agent, C-resource allocation problems, where the resources are all homogeneous. Bhaskar proposed one way to achieve this in 2-agent, 1-resource games: Agents start by symmetrically randomizing their actions, and as soon as they each choose different actions, they start to follow a potentially asymmetric "convention" that prescribes their actions from then on. We extend the concept of convention to the general case of infinitely repeated resource allocation games with N agents and C resources. We show that for any convention, there exists a symmetric subgame-perfect equilibrium which implements it. We present two conventions: bourgeois, where agents stick to the first allocation; and market, where agents pay for the use of resources, and observe a global coordination signal which allows them to alternate between different allocations. We define price of anonymity of a convention as a ratio between the maximum social payoff of any (asymmetric) strategy profile and the expected social payoff of the subgame-perfect equilibrium which implements the convention. We show that while the price of anonymity of the bourgeois convention is infinite, the market convention decreases this price by reducing the conflict between the agents.

Sensing and monitoring of our natural environment are important for sustainability. As sensor systems grow to a large scale, it will become infeasible to place all sensors under centralized control. We investigate community sensing, where sensors are controlled by self-interested agents that report their measurements to a center. The center can control the agents only through incentives that motivate them to provide the most accurate and useful reports. We consider different game-theoretic mechanisms that provide such incentives and analyze their properties. As an example, we consider an application of community sensing for monitoring air pollution.

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A selection is Pareto-optimal if no other selection has better QoS values for some attributes and at least equivalent values for all others. Exact algorithms have been proposed that find all Pareto-optimal selections. They suffer however from exponential complexity. Randomized algorithms scale well but do not offer any formal guarantees on result precision. We present the first approximation scheme for QDSS. It aims at the sweet spot between exact and randomized algorithms: It combines polynomial complexity with formal result precision guarantees. A parameter allows to seamlessly trade result precision against efficiency. We formally analyze complexity and precision guarantees and experimentally compare our algorithm against exact and randomized approaches. Comparing with exact algorithms, our approximation scheme allows to reduce optimization time from hours to seconds. Its approximation error remains below 1.4 percent while randomized algorithms come close to the theoretical maximum.

Several mechanisms have been proposed for incentivizing truthful reports of a private signals owned by rational agents, among them the peer prediction method and the Bayesian truth serum. The robust Bayesian truth serum (RBTS) for small populations and binary signals is particularly interesting since it does not require a common prior to be known to the mechanism. We further analyze the problem of the common prior not known to the mechanism and give several results regarding the restrictions that need to be placed in order to have an incentive-compatible mechanism. Moreover, we construct a Bayes-Nash incentive-compatible scheme called multi-valued RBTS that generalizes RBTS to operate on both small populations and non-binary signals.

The proliferation of online news creates a need for filtering interesting articles. Compared to other products, however, recommending news has specific challenges: news preferences are subject to trends, users do not want to see multiple articles with similar content, and frequently we have insufficient information to profile the reader.

We present the Personalized News (PEN) recommender systems framework, currently in use by a newspaper website to evaluate various algorithms for news recommendations. We briefly describe its system architecture and related components. We show how a researcher can easily evaluate different algorithms thanks to a web-based interface.

Matrix factorization techniques such as the singular value decomposition (SVD) have had great success in recommender systems. We present a new perspective of SVD for constructing a latent space from the training data, which is justified by the theory of hypergraph model. We show that the vectors representing the items in the latent space can be grouped into (approximately) orthogonal clusters which correspond to the vertex clusters in the co-rating hypergraph, and the lengths of the vectors are indicators of the representativeness of the items. These properties are used for making top-$N$ recommendations in a two-phase algorithm. In this work, we provide a new explanation for the significantly better performance of the asymmetric SVD approaches and a novel algorithm for better diversity in top-N recommendations.

To achieve an optimal outcome in many situations, agents need to choose distinct actions from one another. This is the case notably in many resource allocation problems, where a single resource can only be used by one agent at a time. How shall a designer of a multi-agent system program its identical agents to behave each in a different way? From a game theoretic perspective, such situations lead to undesirable Nash equilibria. For example consider a resource allocation game in that two players compete for an exclusive access to a single resource. It has three Nash equilibria. The two pure-strategy NE are efficient, but not fair. The one mixed-strategy NE is fair, but not efficient. Aumann's notion of correlated equilibrium fixes this problem: It assumes a correlation device that suggests each agent an action to take. However, such a "smart" coordination device might not be available. We propose using a randomly chosen, "stupid" integer coordination signal. "Smart" agents learn which action they should use for each value of the coordination signal. We present a multi-agent learning algorithm that converges in polynomial number of steps to a correlated equilibrium of a channel allocation game, a variant of the resource allocation game. We show that the agents learn to play for each coordination signal value a randomly chosen pure-strategy Nash equilibrium of the game. Therefore, the outcome is an efficient correlated equilibrium. This CE becomes more fair as the number of the available coordination signal values increases.

As large-scale theft of data from corporate servers is becoming increasingly common, it becomes interesting to examine alternatives to the paradigm of centralizing sensitive data into large databases. Instead, one could use cryptography and distributed computation so that sensitive data can be supplied and processed in encrypted form, and only the final result is made known. In this paper, we examine how such a paradigm can be used to implement constraint satisfaction, a technique that can solve a broad class of AI problems such as resource allocation, planning, scheduling, and diagnosis. Most previous work on privacy in constraint satisfaction only attempted to protect specific types of information, in particular the feasibility of particular combinations of decisions. We formalize and extend these restricted notions of privacy by introducing four types of private information, including the feasibility of decisions and the final decisions made, but also the identities of the participants and the topology of the problem. We present distributed algorithms that allow computing solutions to constraint satisfaction problems while maintaining these four types of privacy. We formally prove the privacy properties of these algorithms, and show experiments that compare their respective performance on benchmark problems.

We analyze symmetric protocols to rationally coordinate on an asymmetric, efficient allocation in an infinitely repeated N-agent, C-resource allocation problems. (Bhaskar 2000) proposed one way to achieve this in 2-agent, 1-resource allocation games: Agents start by symmetrically randomizing their actions, and as soon as they each choose different actions, they start to follow a potentially asymmetric "convention" that prescribes their actions from then on. We extend the concept of convention to the general case of infinitely repeated resource allocation games with N agents and C resources. We show that for any convention, there exists a symmetric subgame perfect equilibrium which implements it. We present two conventions: bourgeois, where agents stick to the first allocation; and market, where agents pay for the use of resources, and observe a global coordination signal which allows them to alternate between different allocations. We define price of anonymity of a convention as the ratio between the maximum social payoff of any (asymmetric) strategy profile and the expected social payoff of the convention. We show that while the price of anonymity of the bourgeois convention is infinite, the market convention decreases this price by reducing the conflict between the agents.

Monitoring and managing urban air pollution is a significant challenge for the sustainability of our environment. We quickly survey the air pollution modeling problem,introduce a new dataset of mobile air quality measurements in Zurich, and discuss the challenges of making sense of these data.

The Upper Confidence Bounds (UCB) algorithm is a well-known near-optimal strategy for the stochastic multi-armed bandit problem. Its extensions to trees, such as the Upper Confidence Tree (UCT) algorithm, have resulted in good solutions to the problem of Go. This paper introduces DUCT, a distributed algorithm inspired by UCT, for solving Distributed Constraint Optimization Problems (DCOP). Bounds on the solution quality are provided, and experiments show that, compared to existing DCOP approaches, DUCT is able to solve very large problems much more efficiently, or to find significantly higher quality solutions.

Because of the abundance of news on the web, news recommendation is an important problem. We compare three approaches for personalized news recommendation: collaborative filtering at the level of news items, content-based system recommending items with similar topics, and a hybrid technique. We observe that recommending items according to the topic profile of the current browsing session seems to give poor results. Although news articles change frequently and thus data about their popularity is sparse, collaborative filtering applied to individual articles provides the best results.

In many real-life optimization problems involving multiple agents, the rewards are not necessarily known exactly in advance, but rather depend on sources of exogenous uncertainty. For instance, delivery companies might have to coordinate to choose who should serve which foreseen customer, under uncertainty in the locations of the customers. The framework of Distributed Constraint Optimization under Stochastic Uncertainty was proposed to model such problems; in this paper, we generalize this formalism by introducing the concept of evaluation functions that model various optimization criteria. We take the example of three such evaluation functions, expectation, consensus, and robustness, and we adapt and generalize two previous algorithms accordingly. Our experimental results on a class of Vehicle Routing Problems show that incomplete algorithms are not only cheaper than complete ones (in terms of simulated time, Non-Concurrent Constraint Checks, and information exchange), but they are also often able to find the optimal solution. We also show that exchanging more information about the dependencies of their respective cost functions on the sources of uncertainty can help the agents discover higher-quality solutions.

Quality-aware service composition starts from an abstract workflow. The tasks of the workflow are associated with functional types for which concrete services can be retrieved from a registry. Abstract tasks have to be mapped to concrete services before the workflow is executed. The goal is to maximize the workflow quality by choosing the right combination of services. Spending more time in discovery and composition will increase the quality of the resulting workflow. Restricted resources motivate however the question about the optimal tradeoff between composition effort and solution quality. In this paper, we aggregate the three phases discovery, composition, and execution into a common cost metric. We motivate why this cost metric may dynamically change depending on the system state and the properties of the workflow at hand. We present and analyze an iterative algorithm that automatically balances the effort spent in different phases. We are able to prove a near-optimal number of iterations. Additionally, we provide extensive experimental evaluations showing that our algorithm significantly outperforms static approaches in dynamic scenarios.

Service-oriented architectures (SOAs) provide a successful model for structuring complex distributed software systems, as they reduce the cost of ownership and ease the creation of new applications by composing existing services. However, currently, the development of service-oriented applications requires many manual tasks and prevailing infrastructure is often based on centralized components that are central points of failure and easily become bottlenecks. In this paper, we promote self-organizing SOA as a new approach to overcome these limitations. Self-organizing SOA integrates research results in the areas of autonomic and service oriented computing. We consider self-organizing features for the whole life-cycle of a service-oriented application, from the creation to the execution, optimization, and monitoring.

Online reviews have become increasingly popular as a way to judge the quality of various products and services. However, recent work demonstrates that the absence of reporting incentives leads to a biased set of reviews that may not reflect the true quality. In this paper, we investigate underlying factors that influence users when reporting feedback. In particular, we study both reporting incentives and reporting biases observed in a widely used review forum, the Tripadvisor Web site. We consider three sources of information: first, the numerical ratings left by the user for different aspects of quality; second, the textual comment accompanying a review; third, the patterns in the time sequence of reports. We first show that groups of users who discuss a certain feature at length are more likely to agree in their ratings. Second, we show that users are more motivated to give feedback when they perceive a greater risk involved in a transaction. Third, a user's rating partly reflects the difference between true quality and prior expectation of quality, as inferred from previous reviews. We finally observe that because of these biases, when averaging review scores there are strong differences between the mean and the median. We speculate that the median may be a better way to summarize the ratings.

Recommender systems based on user feedback rank items by aggregating users' ratings in order to select those that are ranked highest. Ratings are usually aggregated using a weighted arithmetic mean. However, the mean is quite sensitive to outliers and biases, and thus may not be the most informative aggregate. We compare the accuracy and robustness of three different aggregators: the mean, median and mode. The results show that the median may often be a better choice than the mean, and can significantly improve recommendation accuracy and robustness in collaborative filtering systems.

Abstract Many read‐intensive systems where fast access to data is more important than the rate at which data can change make use of multidimensional index structures, like the generalized search tree (GiST). Although in these systems the indexed data are rarely updated and read access is highly concurrent, the existing concurrency control mechanisms for multidimensional index structures are based on locking techniques, which cause significant overhead. In this article we present the multiversion‐GiST (MVGiST), an in‐memory mechanism that extends the GiST with multiversion concurrency control. The MVGiST enables lock‐free read access and ensures a consistent view of the index structure throughout a reader's series of queries, by creating lightweight, read‐only versions of the GiST that share unchanging nodes among themselves. An example of a system with high read to write ratio, where providing wait‐free queries is of utmost importance, is a large‐scale directory that indexes web services according to their input and output parameters. A performance evaluation shows that for low update rates, the MVGiST significantly improves scalability w.r.t. the number of concurrent read accesses when compared with a traditional, locking‐based concurrency control mechanism. We propose a technique to control memory consumption and confirm through our evaluation that the MVGiST efficiently manages memory. Copyright © 2009 John Wiley & Sons, Ltd.

We consider schemes for obtaining truthful reports on a common but hidden signal from large groups of rational, self-interested agents. One example are online feedback mechanisms, where users provide observations about the quality of a product or service so that other users can have an accurate idea of what quality they can expect. However, (i) providing such feedback is costly, and (ii) there are many motivations for providing incorrect feedback. Both problems can be addressed by reward schemes which (i) cover the cost of obtaining and reporting feedback, and (ii) maximize the expected reward of a rational agent who reports truthfully. We address the design of such incentive-compatible rewards for feedback generated in environments with pure adverse selection. Here, the correlation between the true knowledge of an agent and her beliefs regarding the likelihoods of reports of other agents can be exploited to make honest reporting a Nash equilibrium. In this paper we extend existing methods for designing incentive-compatible rewards by also considering collusion. We analyze different scenarios, where, for example, some or all of the agents collude. For each scenario we investigate whether a collusion-resistant, incentive-compatible reward scheme exists, and use automated mechanism design to specify an algorithm for deriving an efficient reward mechanism.

Prediction markets efficiently extract and aggregate the private information held by individuals about events and facts that can be publicly verified. However, facts such as the effects of raising or lowering interest rates can never be publicly verified, since only one option will be implemented. Online opinion polls can still be used to extract and aggregate private information about such questions. This paper addresses incentives for truthful reporting in online opinion polls. The challenge lies in designing reward schemes that do not require a-priori knowledge of the participants' beliefs. We survey existing solutions, analyze their practicality and propose a new mechanism that extracts accurate information from rational participants.

In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authoritythat we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i's payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents. On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank.

Web service directories are shared resources that have to accommodate a high number of concurrent read requests, whereas updates are relatively infrequent. To allow for the automatic composition of complex web services based on those contained in a directory, read requests may involve a series of queries which require a consistent view of the data. We have developed an efficient web service directory that is based on the Multiversion Generalised Search Tree (MVGiST), an integration of a multidimensional index structure with multiversion concurrency control. The MVGiST is able to index web services according to their input and output parameters, supports a high level of concurrent read requests, and guarantees consistency across multiple subsequent read queries. In this paper we evaluate the performance and scalability of the MVGiST and compare it with a traditional, locking-based concurrency control mechanism.

Ontologies are being successfully used to overcome semanticheterogeneity, and are becoming fundamental elements of the SemanticWeb. Recently, it has also been shown that ontologies can be used tobuild more accurate and more personalized recommendation systems byinferencing missing user's preferences. However, these systemsassume the existence of ontologies, without considering theirconstruction. With product catalogs changing continuously, newtechniques are required in order to build these ontologies in realtime, and autonomously from any expert intervention.This paper focuses on this problem and show that it is possible tolearn ontologies autonomously by using clustering algorithms. Results on the MovieLens and Jester data sets show that recommendersystem with learnt ontologies significantly outperform the classical recommendation approach.

We consider a conversational recommender system based on example-critiquing where some recommendations are suggestions aimed at stimulating preference expression to acquire an accurate preference model. User studies show that suggestions are particularly effective when they present additional opportunities to the user according to the look-ahead principle [32].

Online reputation mechanisms need honest feedback to function effectively. Self-interested agents report the truth only when explicit rewards offset the potential gains obtained from lying. Feedback payment schemes (monetary rewardsfor submitted feedback) can make truth-telling rational based on the correlation between the reports of different buyers. In this paper we investigate incentive-compatible payment mechanisms that are also resistant to collusion: groups of agents cannot collude on a lying strategy without suffering monetary losses. We analyze several scenarios, where, for example, some or all of the agents collude. For each scenario we investigate both existential and implementation problems. Throughout the paper we use automated mechanism design to compute the best possible mechanism for a given setting.

Online reviews have become increasingly popular as a way to judge the quality of various products and services. Previous work has demonstrated that contradictory reporting and underlying user biases make judging the true worth of a service difficult. In this paper, we investigate underlying factors that influence user behavior when reporting feedback. We look at two sources of information besides numerical ratings: linguistic evidence from the textual comment accompanying a review, and patterns in the time sequence of reports. We first show that groups of users who amply discuss a certain feature are more likely to agree on a common rating for that feature. Second, we show that a user's rating partly reflects the difference between true quality and prior expectation of quality as inferred from previous reviews. Both give us a less noisy way to produce rating estimates and reveal the reasons behind user bias.Our hypotheses were validated by statistical evidence from hotel reviews on the TripAdvisor website.

Service-level agreements (SLAs) establish a contract between service providersand clients concerning Quality of Service (QoS) parameters. Without properpenalties, service providers have strong incentives to deviate from theadvertised QoS, causing losses to the clients. Reliable QoS monitoring (andproper penalties computed on the basis of delivered QoS) are thereforeessential for the trustworthiness of a service-oriented environment. In thispaper, we present a novel QoS monitoring mechanism based on quality ratings from theclients. A reputation mechanism collects the ratings and computes theactual quality delivered to the clients. The mechanism provides incentives forthe clients to report honestly, and pays special attention to minimizing costand overhead1.

Reputation mechanisms offer an effective alternative to verification authorities for building trust in electronic markets with moral hazard. Future clients guide their business decisions by considering the feedback from past transactions; if truthfully exposed, cheating behavior is sanctioned and thus becomes irrational. It therefore becomes important to ensure that rational clients have the right incentives to report honestly. As an alternative to side-payment schemes that explicitly reward truthful reports, we show that honesty can emerge as a rational behavior when clients have a repeated presence in the market. To this end we describe a mechanism that supports an equilibrium where truthful feedback is obtained. Then we characterize the set of pareto-optimal equilibria of the mechanism, and derive an upper bound on the percentage of false reports that can be recorded by the mechanism. An important role in the existence of this bound is played by the fact that rational clients can establish a reputation for reporting honestly.

Traditional, centralized workflow orchestration often leads to inefficient routing of messages. To solve this problem, we present a novel scheme to execute workflows in a fully decentralized way. We introduce service invocation triggers, a lightweight infrastructure that routes messages directly from the producing service to the consuming one, enabling fully decentralized workflow orchestration.

The internet presents people with an increasingly bewildering variety of choices. Online consumers have to rely on computerized search tools to find the most preferred option in a reasonable amount of time. Recommender systems address this problem by searching for options based on a model of the user's preferences. We consider example critiquing as a methodology for mixed-initiative recommender systems. In this technique, users volunteer their preferences as critiques on examples. It is thus important to stimulate their preference expression by selecting the proper examples, called suggestions. We describe the look-ahead principle for suggestions and describe several suggestion strategies based on it. We compare them in simulations and, for the first time, report a set of user studies which prove their effectiveness in increasing users' decision accuracy by up to 75%.

Preference-based search is the problem of finding an item thatmatches best with a user's preferences. User studies show that example-based tools for preference-based search can achievesignificantly higher accuracy when they are complemented withsuggestions chosen to inform users about the available choices. We discuss how suggestions can be efficiently implemented even for large product databases.

Traditional, centralized orchestration of composite Web services often leads to inefficient routing of messages. To solve this problem, we present a novel scheme to execute composite Web services in a fully decentralized way. We introduce service invocation triggers, a lightweight infrastructure that routes messages directly from the producing service to the consuming one, enabling fully decentralized orchestration. An evaluation confirms that decentralized orchestration can significantly reduce the network traffic when compared with centralized orchestration

Online reputation mechanisms need honest feedback to function effectively. Self interested agents report the truth only when explicit rewards offset the cost of reporting and the potential gains that can be obtained from lying. Side-payment schemes (monetary rewards for submitted feedback) can make truth-telling rational based on the correlation between the reports of different buyers.In this paper we use the idea of automated mechanism design to construct the payments that minimize the budget required by an incentive-compatible reputation mechanism. Such payment schemes are defined by a linear optimization problem that can be solved efficiently in realistic settings. Furthermore, we investigate two directions for further lowering the cost of incentive-compatibility: using several reference reports to construct the side-payments, and filtering out reports that are probably false.

Recent algorithms for automated service composition issue many complex queries to service directories. As service directories are shared resources, they may become performance bottlenecks. In order to increase scalability, we introduce a compact directory digest, which is distributed to clients and includes all information needed for automated service composition. Therefore, complex directory queries during service composition can be avoided. We encode a directory digest as a zero-suppressed reduced ordered binary decision diagram (ZDD). In several steps, we refine a simple service composition algorithm in order to leverage the ZDD representation. Introducing specialized ZDD operations, we achieve a service composition algorithm that scales very well with an increasing size of the directory digest

We consider interactive tools that help users search for their most preferred item in a large collection of options. In particular, we examine example-critiquing, a technique for enabling users to incrementally construct preference models by critiquing example options that are presented to them. We present novel techniques for improving the example-critiquing technology by adding suggestions to its displayed options. Such suggestions are calculated based on an analysis of users' current preference model and their potential hidden preferences. We evaluate the performance of our model-based suggestion techniques with both synthetic and real users. Results show that such suggestions are highly attractive to users and can stimulate them to express more preferences to improve the chance of identifying their most preferred item by up to 78%.

Service directories are a key component of distributed systems where shared information must be managed efficiently. For a directory with a large numbers of entries, the result set of a query may be large, too. In this case, it is important to order the results according to heuristics and to retrieve them incrementally. Our contribution is an integrated directory system specially adapted to large-scale service discovery and composition. We introduce DirQL, a flexible query language for the matching and ranking of service descriptions. As results are incrementally retrieved, our system is able to lazily compute the result set based on: 1) the organization of the directory as a special balanced search tree that has an extra "intersection" discriminator, 2) a scheme for transforming the original query into one taking into account the tree structure of the directory, and 3) the organization of partial results in a heap structure sorted according to the transformed query. We also report on experimental results regarding the usage of the directory by a composition engine solving randomly generated problems.

Preference-based search, defined as finding the most preferred item in a large collection, is becoming an increasingly important subject in computer science with many applications: multi-attribute product search, constraint-based plan optimization, configuration design, and recommendation systems. Decision theory formalizes what the most preferred item is and how it can be identified. In recent years, decision theory has pointed out discrepancies between the normative models of how people should reason and empirical studies of how they in fact think and decide. However, many search tools are still based on the normative model, thus ignoring some of the fundamental cognitive aspects of human decision making. Consequently these search tools do not find accurate results for users. This tutorial starts by giving an overview of recent literature in decision theory, and explaining the differences between descriptive, and normative approaches. It then describes some of the principles derived from behavior decision theory and how they can be turned into principles for developing intelligent user interfaces to help users to make better choices while searching. It develops in particular the issues of how to model user preferences with a limited interaction effort, how to support tradeoff, and how to implement practical search tools using the principles.

The fundamental issue of quality-of-service (QoS) routing has triggered a lot of research during the last few years. However, the proposed algorithms attempt to route communication demands only on a call by call basis, without taking into account future traffic. There are nonetheless cases where the traffic profile is known. In this paper, we address this related problem to QoS routing, more specifically, the off-line planning of bandwidth allocation to demands known in advance. Shortest-path routing is the traditional technique applied to this problem. However, this can lead to poor network utilization and even congestion. We show how an abstraction technique combined with systematic search algorithms and heuristics derived from artificial intelligence make it possible to solve this problem more efficiently and in much tighter networks, in terms of bandwidth usage. In addition, this abstraction technique also allows to explain during search why some allocation problems are indeed infeasible. Then, the network regions between which bandwidth must be added are then identified.

This work proposes a novel generic scheme enabling the combination of multiple inclusion representations to propagate numerical constraints. The scheme allows bringing into the constraint propagation framework the strength of inclusion techniques coming from different areas. The scheme is based on the DAG representation of the constraint system. This enables devising fine-grained combination strategies involving any factorable constraint system. The paper presents several possible combination strategies for creating practical instances of the generic scheme. The experiments reported on a particular instance using interval constraint propagation, interval arithmetic, affine arithmetic and linear programming illustrate the flexibility and efficiency of the approach.

Service matchmaking and composition has recently drawn increasing attention in the research community. Most existing algorithms construct chains of services based on exact matches of input/output types. However, this does not work when the available services only cover a part of the range of the input type. We present an algorithm that also allows partial matches and composes them using switches that decide on the required service at runtime based on the actual data type. We report experiments on randomly generated composition problems that show that using partial matches can decrease the failure rate of the integration algorithm using only complete matches by up to 7 times with no increase in the number of directory accesses required. This shows that composition with partial matches is an essential and useful element of Web service composition.

In many practical scenarios, users are faced with the problem of choosing the most preferred outcome from a large set of possibilities. As people are unable to sift through them manually, decisions support systems are often used to automatically find the optimal solution. A crucial requirement for such a system is to have an accurate model of the user's preferences. Studies have shown that people are usually unable to accurately state their preferences up front, but are greatly helped by seeing examples of actual solutions. Thus, several researchers have proposed preference elicitation strategies based on example critiquing. The essential design question in example critiquing is what examples to show users in order to best help them locate their most preferred solution. In this paper, we analyze this question based on two requirements. The first is that it must stimulate the user to express further preferences by showing the range of alternatives available. The second is that the examples that are shown must contain the solution that the user would consider optimal if the currently expressed preference model was complete so that he select it as a final solution. Copyright 2004 ACM.

Service matchmaking and composition has recently drawn increasing attention in the research community. Most existing algorithms construct chains of services based on exact matches of input/output types. However, this does not work when the available services only cover a part of the range of the input type. We present an algorithm that also allows partial matches and composes them using switches that decide on the required service at runtime based on the actual data type. We report experiments on randomly generated composition problems that show that using partial matches can decrease the failure rate of the integration algorithm using only complete matches by up to 7 times with no increase in the number of directory accesses required. This shows that composition with partial matches is an essential and useful element of web service composition.

Many situations present a social choice problem where different self-interested agents have to agree on joint, co-ordinated decisions. For example, power companies have to agree on how to use the power grid, and airlines have to agree on how to schedule takeoffs and landings. Mechanisms for social choice are called incentive-compatible when cooperative behavior is optimal for all parties. The most well-known examples of incentive-compatible mechanisms are auctions. However, the party that receives the auction revenue has an incentive to manipulate the outcome to increase the revenue. For example, a power gird operator has an interest to reduce capacity and drive up prices. Conversely, if it provides sufficient capacity to every user it derives no revenue to cover its costs. We present a novel mechanism for social choice that is incentive-compatible without generating a payment surplus. We give several examples of applications where it solves the social choice problem without unwanted incentives, and provides significantly better overall utility than any other known mechanism.

Reputation mechanisms offer an efficient way of building the necessary level of trust in electronic markets. Feedback about an agent's past behavior can be aggregated into a measure of reputation, and used by other agents for taking trust decisions. Unfortunately, true feedback cannot be automatically assumed. In the absence of Trusted Third Parties, the mechanism has to make it rational for agents to truthfully share reputation information. In this paper we describe two mechanisms that can be used in decentralized environments for eliciting true feedback. The mechanisms are accompanied by examples inspired by real scenarios.

To find products in online environments, people increasingly rely on computerized search tools. The performance of such tools depends crucially on an accurate model of their users' preferences. Obtaining such models requires an adequate interaction model and system guidance.

We consider automated decision aids that help users select the best solution from a large set of options. For such tools to successfully accomplish their task, eliciting and representing users' decision preferences is a crucial task. It is usually too complex to get a complete and accurate model of their preferences, especially regarding the trade‐offs between different criteria.We consider decision aid tools where users specify their preferences qualitatively: they are only able to state the criteria they consider, but not the precise numerical utility functions. For each criterion, the tool provides a standardized numerical function that is fixed and identical for all users and used to compare solutions. To compensate for the imprecision of this qualitative model, we let the user choose among a displayed set of possibilities rather than a single optimal solution. We consider the probability of finding the most preferred solution as a function of the number of displayed possibilities and the number of preferences. We present a probabilistic analysis, empirical validation on randomly generated configuration problems and a commercial application. We provide mathematical principles for the design of the selection mechanism, guaranteeing that users are able to find the target solution.

No abstract available.

It has been widely recognised that matchmaking is an important component for environments populated with heterogeneous services. Several researchers have developed powerful techniques for the matchmaking problem in general. There are also specific representations of service capabilities such as DAML-S, which provide a more specific framework for matchmaking. Most approaches to matchmaking have assumed a sequential search for a service with matching capabilities. This may become intractable when the number of available services gets large. We consider how matchmaking can be developed into service directories that can be searched and maintained efficiently. Our main contribution is to show how matchmaking with DAML-S specifications can be integrated with efficient methods for searching and maintaining balanced directory trees. We also report on experimental results using an implementation based on generalised search trees.

Personalization in e-commerce has so far been server-centric, requiring users to create a separate individual profile on each server that they like to access. As product information is increasingly coming from multiple and heterogeneous sources, the number of profiles becomes unmanageably large. We present SmartClient, a technology based on constraint programming where a thin but intelligent client provides personalized information access for its user. As the process can run on the user's side, it allows much stronger filtering and visualization support with a wider range of personalization options than existing tools. It also eliminates the need to personalize many sites individually with different parameters, and supports product configuration and integration of different information sources in the same framework. We illustrate the technology using an application in travel e-commerce, which is currently under commercial deployment.

In electronic commerce, a satisfying buyer experience is a key competitive element. We show new techniques for better adapting interaction with an electronic catalog system to actual buying behavior. Our model replaces the sequential separation of needs identification and product brokering with a conversation in which both processes occur simultaneously. This conversation supports the buyer in formulating his or her needs, and in deciding which criteria to apply in selecting a product to buy. We have experimented with this approach in the area of travel planning and developed a system called SmartClient Travel which supports this process. It includes tools for need identification, visualization of alternatives, and choosing the most suitable one. We describe the system and its implementation, and report on user studies showing its advantages for electronic catalogs.

Communication networks are expected to offer a wide range of services to an increasingly large number of users, with a diverse range of quality of service. This calls for efficient control and management of these networks. We address the problem of quality-of-service routing, more specifically the planning of bandwidth allocation to communication demands. Shortest-path routing is the traditional technique applied to this problem. However, this can lead to poor network utilization and even congestion. We show how an abstraction technique combined with systematic search algorithms and heuristics derived from artificial intelligence make it possible to solve this problem more efficiently and in much tighter networks, in terms of bandwidth usage.

Communication networks are expected to offer a wide range of services to an increasingly large number of users, with a diverse range of quality of service. This calls for efficient control and management of these networks. In this paper, we address the problem of quality-of-service routing, more specifically the planning of bandwidth allocation to communication demands. Shortest path routing is the traditional technique applied to this problem. However, this can lead to poor network utilization and even congestion. We show how an abstraction technique combined with systematic search algorithms and heuristics derived from artificial intelligence make it possible to solve this problem more efficiently and in much tighter networks, in terms of bandwidth usage.

WWW servers have to serve many clients simultaneously and thus cannot provide intelligent services. We present an approach where intelligent problem solving is distributed so that compute-expensive tasks are carried out on the client side. To this end, we have implemented a library of constraint satisfaction techniques, called the JAVA constraint library, which allows composing applets that solve CSPs. We present the library and show several examples of applications.

The paper presents SpaceSolver, a constraint satisfaction toolbox, providing access to constraint satisfaction techniques on continuous variables through an intuitive, Web based user interface. Moreover, we describe possible applications of such a platform to collaborative design and conclude that Internet based use of constraint satisfaction techniques has the potential of increasing productivity in several fields in engineering.

Abstraction is a useful technique for reducing complexity in problem solving. In this paper, the authors present two abstraction techniques and one partitioning heuristic to solve resource allocation problems. The partitioning heuristic decomposes the resource allocation problem into easy and difficult components competing for pools of resources. A hierarchy of resource pools allows conflict resolution to occur at the most appropriate level of abstraction. The temporal abstraction techniques simplify the decoupled components. They also aid the user in assessing the tightness of the problem and the types of missing resources. There are two main advantages to using the abstractions the authors propose: they rapidly provide a first solution which can be refined given more computation time, and they provide an explanation in terms of missing resources if the resource allocation problem is unsolvable.

In their paper, ”Prolegomena to Any Future Qualitative Physics, ” Elisha Sacks and Jon Doyle raise interesting points regarding the applicability of qualitative reasoning to solving practical engineering problems. They criticize in particular a line of research which they identify by the letters SPQR: the qualitative simulation of processes described by a set of differential equations. While many of their criticisms are interesting, the underlying assumption that all physical systems can be adequately represented by systems of equations is invalid. Engineering has no doubt benefited strongly from using mathematical concepts such as differential equations and dynamical systems theory. However, an engineer who wants to apply these concepts first has to construct a model where their use is tractable. Consider as an example the design and analysis of mechanisms such as clockworks. An important mechanism is the ratchet shown in Figure 1, a device which allows rotation of the wheel in one direction only.

Existing methods for robot planning fall far behind human capabilities: they require approximations of shapes, and they cannot generate plans which involve moving obstacles to clear a path for the moving object. The authors explore the hypothesis that means-ends analysis based on a world model involving mental imagery allows more human-like solutions. The method is based on a way or representing planning constraints which makes it possible to generate incrementally the symbolic representations for means-ends planning using only imagery operations.>

Random-access systems (RAS) for collision-type channels have been studied extensively under the assumption of an infinite population which generates a Poisson arrival process. If the population is finite and if the (practically desirable) free-access channel-access protocol is used, then it is shown that the specification of a channel-exit protocol is crucial for the stability and the fairness of the RAS. Free-exit and blocked-exit protocols are analyzed and it is concluded that the p-persistent blocked-exit protocol provides the mechanisms to assure stability and fairness for a wide range of arrival process models.