When a set of agents (human or artificial) must agree on a series of measures, it is necessary to establish which criteria must be optimized to find the best agreement. In particular, under the egalitarian social welfare, the aim is to maximize the benefit of the agent who is most disadvantaged. In this way, the aim is to ensure that no agent is too dissatisfied with the agreement reached, so that the probability of breaking the agreement is lower. Unfortunately, it is not (computationally) straightforward to compute the best agreements under egalitarian social welfare. In addition, agents may try to lie about their true preferences to try to fool the optimization algorithm. In this paper we demonstrate the computational complexity of the problem and propose strategies to discourage agents from lying. In particular, we consider the case of political parties that have to reach an agreement on a given set of laws. Genetic algorithms are used to evaluate the usefulness of different strategies from an experimental point of view.

In this paper, two optimization problems within the scope of marketing campaign design are studied. In particular, two ad positioning problems are analyzed with the objective of minimizing the cost of all the chosen media while ensuring that a set of constraints is fulfilled. In the first problem, a given minimum number of impressions (views) in each population segment is required to be reached as a constraint. In the second problem, the constraints involve achieving, in each population segment, a given minimum probability that any individual will see the ad at least once. In this second case, media dependencies are defined for each population segment: independence, exclusion, and inclusion. Since both problems are Log-APX-hard, heuristic methods are used to solve them. More specifically, greedy and genetic algorithms, as well as particle swarm optimization, are applied to address these problems. Furthermore, the usefulness of these algorithms is evaluated through concrete case studies using real data on ad prices and views. • Formally specifying two problems in the context of media planning. • Providing heuristic solutions for them by means of Genetic Algorithms. • Evaluating our implementations to deal with two concrete case studies.

How much power does a political party really have, compared to another party? In principle, the answer might seem obvious, since power seems to be directly pro-portional to its number of voters (or its number of deputies). However, in reality, the power of a party depends on its ability to form government majorities. In this paper we will demonstrate the computational hardness (in particular, #P-hardness) of determining the relative power of a party in different settings, and provide practical algorithms to compute it. We will use our algorithms to face a case study where we will compare the relative power of parties in real elections. Although we will use political parties as an illustration, the problem is equally applicable to any multi-agent voting system, and this type of environment poses the greatest difficulties.

In multi-agent resource allocation systems, it is reasonable that the specific allocation of resources depends on the utility functions declared by the different agents. However, this can easily lead to strategic behaviors in which the agents involved are interested in lying, since such lies can bring them more profitable deals. In this paper we analyze the case of egalitarian social welfare, where the objective is to maximize the utility of the agent who receives the least utility. In this context, agents can obtain advantages by undervaluing their preferences. Thus, we will see how to discourage such lies even in the presence of public goods and non-additive utilities. Likewise, we will use genetic algorithms to show, through experimental results, the robustness of our proposal against lies.

Reaching agreements is part of the life of any human group, but it is especially important in the context of political relations. In parliamentary systems, when no party has an absolute majority, it is necessary to establish pacts with other parties to carry out as many laws as possible that fit with our ideology. However, finding the best possible deals is not an easy task. In fact, in this work we not only show that it is an NP-complete problem, but also that it is impossible to guarantee a good approximation ratio in polynomial time. Even so, we show that it is possible to use genetic algorithms to obtain reasonably satisfactory pacts, and we illustrate it for a specific case study of the Spanish parliament.

Benchmarks are useful to allow evaluating the usefulness of new algorithms. However, care has to be taken to avoid cheating in case the users know the benchmarks in advance. In this paper, we present a blockchain-based tool that allows the generation of dynamic benchmarks. Moreover, it provides a verifiable certification about the moment when the benchmark was created, the researcher who asked for it, how much time was spent before solving it, etc. By using it, we can safely deal with the use of dynamic benchmarks without requiring a trusted third party.

When some resources are to be distributed among a set of agents following egalitarian social welfare, the goal is to maximize the utility of the agent whose utility turns out to be minimal. In this context, agents can have an incentive to lie about their actual preferences, so that more valuable resources are assigned to them. In this paper we analyze this situation, and we present a practical study where genetic algorithms are used to assess the benefits of lying under different situations.

In order to properly teach any subject, it is important to understand the underlying cognitive models of the learning process. Unfortunately, sometimes basic concepts are not adequately taught during primary school because primary school teachers lack the knowledge and/or the basic tools about these concepts. For instance, children have to learn to handle our standard base-10 positional numeral system. Unfortunately, teachers are not usually aware of the intrinsic difficulties of this learning process, the reason being that adults have internalized this knowledge so deep in their mental process that they usually think that it is an obvious and very natural representation. Thus, teachers have problems to understand the actual difficulties that children must confront. In this paper we present an experience we have conducted in the Education Faculty of our university to help future teachers to understand such difficulties. By using our tool, future teachers are forced to face all the steps children have to follow in their learning process. Thus, they learn the problems their future students will have, and they will be better prepared to improve the Mathematics skills of their students.

Nowadays, any personal computer includes a GPU that allows to use its parallelism to speedup computations. Unfortunately, it is not a trivial task to take advantage of such parallel architectures. In this paper, we present a library of swarm intelligence metaheuristics providing automatic parallelizations. The library is freely available, it is implemented by using CUDA, and it includes parallel versions of metaheuristics for both continuous and discrete domains. We show the basic ideas of the parallelization of one of the metaheuristics, and we prove its usefulness by presenting empirical results.

In this paper we take inspiration from Rain-Fall optimization metaheuristic (RFO) to modify other metaheuristics. An interesting concept of RFO is its merit list. We argue that this concept could be successfully exported to other metaheuristics. As a concrete case study, we have implemented a modified version of Artificial Bee Colony (ABC) including merit lists. The experiments we have conducted with a concrete wellknown benchmark show that it can help improving the quality of the solutions found by ABC.

The Anthropological Theory of the Didactic (ATD) has proven its usefulness to describe human learning, and has improved the methods used to acquire new knowledge. However, although the same framework could be used in the context of machine learning, no attempts have appeared in the literature to apply ATD within computing environments. In this paper we argue that we can also take profit from ATD in machine learning. In particular, we will show how we can use it to describe a simple system where we need to learn to select an algorithm among a set of predefined options. The approach will be used to analyze both human learning and machine learning, analyzing the similarities and differences between both of them.

We study the problems of picking the media where a good or service is advertised in such a way the cost of placing these advertisements is minimized but, simultaneously, the individuals of some given population segments reach some minimum average advertisement impressions (views); or they reach some minimum probabilities of watching the advertisement at least once; or they reach both. The proposed model lets the publicist explicitly define the dependencies between media audience (i.e., whether viewers of some medium typically watch some other medium; or typically do not watch it; or typically watch it as the rest of the audience). We prove the Log-APX-hardness of these three problems. We present two heuristics to suboptimally solve each of these problems (one greedy and the other one based on genetic algorithms) and compare their performance for several problem instances.

Abstract Given a finite state machine denoting the specification of a system, finding some short interaction sequences capable of reaching some/all states or transitions of this machine is a typical goal in testing methods. If these sequences are applied to an implementation under test , then equivalent states or transitions would be reached and observed in the implementation—provided that the implementation were actually defined as the specification. We study the problem of finding such sequences in the case where configurations previously traversed can be saved and restored (at some cost). In general, this feature enables sequences to reach the required parts of the machine in less time, because some repetitions can be avoided. However, we show that finding optimal sequences in this case is an NP-hard problem. We propose an heuristic method to approximately solve this problem based on an evolutionary computation approach, in particular river formation dynamics (RFD). Given finite state machine specifications and sets of states/transitions to be reached, we apply RFD to construct testing plans reaching these configurations. Experimental results show that being able to load previously traversed states generally reduces the time needed to cover the target configurations.

NP-complete problems are particularly hard to solve. Unless P=NP, any algorithm solving an NP-complete problem takes exponential time in the worst case. The intrinsic difficulty of NP-complete problems when we try to optimally solve them with compute

Due to the use of higher-order functions and laziness, debugging lazy functional programs is not a trivial task. Fortunately, several debuggers have appeared during the last years. However, the difficulty of the debugging process is increased when considering parallel extensions of lazy functional languages. Thus, it is necessary not only to develop practical debuggers, but also to provide a clear semantic environment to understand what the debuggers should do. In this paper we present a formal framework for debugging two different parallel extensions of the lazy functional language Haskell. In order to do that, we define an operational semantics model which allows us to deal with side-effects and parallelism. By doing so, we provide a formalization of a parallel debugger we have already implemented by extending the sequential debugger Hood.

In this paper we formally present a methodology that allows us to adapt the intelligence of the agents conforming a multiagent system. We perform such adaptation of the intelligence by means of genetics. We call the resulting environments metaadaptable systems, as they allow to adapt the adaptive capabilities of elements. So, we propose systems in which the capability of the agents to adapt themselves to the environment (via mechanisms producing some kind of intelligence) is itself adapted according to the changes of their own environment. Actually, finding the optimal intelligence mechanism and the optimal key parameters that govern it is not a trivial task, as they dramatically depend on the environment that produces the events that an agent has to use to infer its own conclusions. We denote by intelligence mechanism any strategy to produce behavior that could be considered intelligent. We show a simple but illustrative example of such a metaadaptable system, which can be easily extended to deal with more real situations as the construction of software systems based on intelligent mobile agents. This system has been fully implemented, and some interesting conclusions have been extracted from it.

This paper presents a generic formal framework to specify and test autonomous e-commerce agents. First, the formalism to represent the behaviour of agents is introduced. The corresponding machinery to define how implementations can be tested follows. Two testing approaches are considered. The first of them, which can be called active, is based on stimulating the implementation under test (IUT) with a test. The peculiarity is that tests will be defined as a special case of autonomous e-commerce agent. The second approach, which can be called passive, consists of observing the behaviour of the tested agent in an environment containing other agents. As a case study the framework is applied to the e-commerce system Kasbah. Copyright © 2005 John Wiley & Sons, Ltd.

Abstract. In this paper we present a design framework containing a process algebra and the concurrent functional programming language Eden. In order to study properties of a specification written in our process algebraic notation, we provide a translation mechanism to generate Eden programs. Once we have a translation, we may use the Eden tools to study the performance of the (simulation of the) system. In order to add expressiveness to our design language we use a very powerful process algebra. First, we allow the specification of delays induced by general random variables. We also consider value passing. Finally, the communication between concurrent processes is asynchronous. The usefulness of our framework is presented by two examples featuring all the characteristics of our process algebraic model, we give the corresponding translations, and we provide some performance measures obtained by using Eden tools.

The parallel functional language Eden extends Haskell with expressions to define and instantiate process systems. These extensions allow also the easy definition of skeletons as higherorder functions. P arallel programming is possible in Eden at two levels: Recursive programming and higher-order programming. At the lower level, processes are explicitly created by using recursive definitions. In this way, skeletons can be defined. This is very un usual, as most skeleton-based languages use an imperative language to create new skeletons. At the higher level, available sk eletons are used to create applications or to define new skeletons on top of the other ones. In this paper, we present five skeletons, most of them wellkno wn, covering a wide range of parallel structures. F or each one, sev eral Eden implementations are given, together with their corresponding cost models. Finally, some examples of application programming are shown, including predicted and actual results on a Beowulf cluster.