We study large-scale machine learning problems in changing environments where a small part of the dataset is modified, and the effect of the data modification must be monitored in order to know how much the modification changes the optimal model. When the entire dataset is large, even if the amount of the data modification is fairly small, the computational cost for re-training the model would be prohibitively large. In this paper, we propose a novel method, called the optimal solution bounding (OSB), for monitoring such a data modification effect on the optimal model by efficiently evaluating (without actually re-training) it. The proposed method provides bounds on the unknown optimal model with the cost proportional only to the size of the data modification.

The annual International Automated Negotiating Agents Competition (ANAC) is used by the automated negotiation research community to benchmark and evaluate its work andto challenge itself. The benchmark problems and evaluation results and the protocols and strategies developed are available to the wider research community.

The Automated Negotiating Agents Competition is an international event that, since 2010, has contributed to the evaluation and development of new techniques and benchmarks for improving the state-of-the-art in automated multi-issue negotiation. A key objective of the competition has been to analyze and search the design space of negotiating agents for agents that are able to operate effectively across a variety of domains. The competition is a valuable tool for studying important aspects of negotiation including profiles and domains, opponent learning, strategies, bilateral and multilateral protocols. Two of the challenges that remain are: How to develop argumentation-based negotiation agents that next to bids, can inform and argue to obtain an acceptable agreement for both parties, and how to create agents that can negotiate in a human fashion.

There has been a great deal of interest about negotiations having interdependent issues and nonlinear utility spaces as they arise in many realistic situations. In this case, reaching a consensus among agents becomes more difficult as the search space and the complexity of the problem grow. Nevertheless, none of the proposed approaches tries to quantitatively assess the complexity of the scenarios in hand, or to exploit the topology of the utility space necessary to concretely tackle the complexity and the scaling issues. We address these points by adopting a representation that allows a modular decomposition of the issues and constraints by mapping the utility space into an issue-constraint hypergraph. Exploring the utility space reduces then to a message passing mechanism along the hyperedges by means of utility propagation. Adopting such representation paradigm will allow us to rigorously show how complexity arises in nonlinear scenarios. To this end, we use the concept of information entropy in order to measure the complexity of the hypergraph. Being able to assess complexity allows us to improve the message passing algorithm by adopting a low-complexity propagation scheme. We evaluated our model using parametrized random hyper- graphs, showing that it can optimally handle complex utility spaces while outperforming previous sampling approaches.

Decision making has proposed multiple methods to help the decision maker in his analysis, by suggesting ways of formalization of the preferences as well as the assessment of the uncertainties. Although these techniques are established and proven to be mathematically sound, experience has shown that in certain situations we tend to avoid the formal approach by acting intuitively. Especially, when the decision involves a large number of attributes and outcomes, and where we need to use pragmatic and heuristic simplifications such as considering only the most important attributes and omitting the others. In this paper, we provide a model for decision making in situations subject to a large predictive uncertainty with a small learning sample. The high predictive uncertainty is concretized by a countably infinite number of prospects, making the preferences assessment more difficult. Our main result is an extension of the Maximum Entropy utility (MEU) principle into an asymptotic maximum entropy utility principle for preferences elicitation. This will allow us to overcome the limits of the existing MEU method to the extend that we focus on utility assessment when the set of the available discrete prospects is countably infinite. Furthermore, our proposed model can be used to analyze situations of high-cognitive load as well as to understand how humans handle these problems under Ceteris Paribus assumption.

This paper summarizes the online machine learning method LCore, which enables robots to learn to communicate with users from scratch through verbal and behavioral interaction in the physical world. LCore combines speech, visual, and tactile information obtained through the interaction, and enables robots to learn beliefs regarding speech units, words, the concepts of objects, motions, grammar, and pragmatic and communicative capabilities. The overall belief system is represented by a dynamic graphical model in an integrated way. Experimental results show that through a small, practical number of learning episodes with a user, the robot was eventually able to understand even fragmental and ambiguous utterances, respond to them with confirmation questions and/or actions, generate directive utterances, and answer questions, appropriately for the given situation. This paper discusses the importance of a developmental approach to realize personally and physically situated human-robot conversations.

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a Coalition Structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might assume that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve n-th power of 2 DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w*+1), 2k/n) of the optimal CS, where w* is the tree width of a constraint graph. When k=1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.