· · · Institutional Repository

The judgment of king Solomon is an early example of mechanism design. Mechanism design attempts to achieve desired outcomes in situations with self-interested players by setting the rules of the game in a specific way. We will see that the game Solomon proposed would not have worked if the women were rational, and we will see an alternative mechanism (or game) as proposed by Moore (1992). Then we will relate this mechanism to another mechanism, namely the auction protocol used in e-Bay. Finally, we briefly introduce some mechanism design problems we study in the Algorithmics group (under prof. dr. Cees Witteveen).

Autonomous agents usually plan their actions. Sometimes agents can benefit from cooperation, and sometimes they cannot even do without resources from another. We can either coordinate the plans of agents after they have constructed their plans (plan merging), or we can plan the coordination of agents. Plan merging can only be used for agents that are able to (first) create a valid plan on their own. We distinguish two ways to plan coordination. With servicebased plan coordination agents offer resources they can produce for others. With task-based coordination agents are allowed to place requests for resources thay need. These forms of coordination can be integrated in the plans, and be realized by adapting existing planning algorithms at a few points. All methods use a model of the state of the world and of actions where a proposition is extended to describe all properties of an available entity relevant for planning. Such a proposition is called a resource, and can be exchanged among plans more conveniently than propositions as used by, e.g., STRIPS. Actions consume all resources that are given as a precondition, and produce the resources designed by the post-condition.

To test and compare different forms of cooperative planning algorithms developed in the CABS project we use a generic simulator called MARS. Examples in the transportation sector are implemented in this simulator.

In many applications of the task allocation problem such as peer-topeer and grid computing, and virtual organizations, the (social or business) relations between the participating agents play an important role, and thus they should be taken into account. Furthermore, in such applications, agents providing the resources usually act self-interested. This paper therefore studies the problem of finding truthful mechanisms for these kinds of social task allocation problems. In this paper we give on the one hand an optimal mechanism and model the problem as an integer linear program (ILP), and on the other hand a polynomialtime approximation by splitting the problem into smaller sub-problems, each of which is solved optimally. We show that both mechanisms are truthful. The optimal mechanism may take exponential time for some instances, and in theory, the quality of the approximation is not guaranteed. However, we show experimentally that for problem instances where the social network has the smallworld property, the quality of the results for the approximation is quite good, due to the fact that the division into subproblems uses the locality of tasks in the social network.

To come to a deal, a bargaining process can sometimes take a long time. An auction may be a faster, but existing auction models cannot cope with situations where money is not an issue, or where it is difficult to express the utility of all participants in a monetary domain. We propose a modified Vickrey auction based only on preferences over the possible bids. This approach also allows for situations where a bid is not just a price or some fixed set of attributes, but can be any possible offer. We prove that in this flexible, generalized setting, the Vickrey mechanism is still incentive compatible and results in a Pareto-efficient solution.

Multi-attribute auctions allow negotiations over multiple attributes besides price. For example in task allocation, service providers can define their service by means of multiple attributes, such as quality of service, deadlines, or delay penalties. Auction mechanisms assume that the players have evaluation functions over the space of attributes that assign a single value to any combination of attributes. This value (or cost) is directly comparable to price. We argue that in some situations, some of the attributes are difficult to convert to cost, e.g., in transportation it is often important which driver is going to deliver a given truckload. Such personal preferences of a customer are difficult to quantify. To allow negotiations over such non-monetary attributes we relax the requirement of universally comparable utility functions, and give an incentive-compatible auction mechanism that uses only preference orders of the parties and not globally comparable function values. The suggested mechanism assumes that the bidders and the auctioneer have individual total orders over the space of possible contracts, but no utility functions. Each bidder places its bids using its own order, and the winner is chosen by the auctioneer’s order. The actual attribute values are chosen based on the second-best bid. It is shown that this Vickrey intuition yields an incentive-compatible mechanism.

When information or control in a multiagent system is private to the agents, they may misreport this information or refuse to execute an agreed outcome, in order to change the resulting end state of such a system to their benefit. This may result in execution failures. When only information is private, mechanisms such as VCG use payments to create incentives for truthful behavior, and can then guarantee a non-negative utility for all agents. However, when control is also private, such existing mechanisms lose truthfulness and individual rationality: payments should depend on the actual outcome (not on the planned outcome) and some agents should be compensated. We give a more general version of the known negative result in the context of actions with dependencies, and we give a mechanism that can guarantee a nonnegative utility to the agents and is truthful in an ex-post Nash equilibrium.

In games where agents are asked to declare their available resources, they can also strategize over this declaration. Surprisingly, not in all such games a VCG payment can be applied to construct a truthful mechanism using an optimal algorithm, though such payments can prevent under-reporting of resources. We show this for the problem of allocating tasks in a social network (STAP). Since STAP is NP-hard, we introduce an approximation algorithm as well. However for such an approximation, a VCG payment cannot prevent under-reporting anymore. Therefore we introduce an alternative payment function that motivates agents to fully declare their resources. We also demonstrate by experiments that the approximation algorithm works well in different types of social networks.

When information or control in a multiagent system is private to the agents, they may misreport this information or refuse to execute an agreed outcome, in order to change the resulting end state of such a system to their benefit. In some domains this may result in an execution failure. We show that in such settings VCG mechanisms lose truthfulness, and that the utility of truthful agents can become negative when using VCG payments (i.e., VCG is not strongly individually rational). To deal with this problem, we introduce an extended payment structure which takes into account the actual execution of the promised outcome. We show that this extended mechanism can guarantee a nonnegative utility and is (i) incentive compatible in a Nash equilibrium, and (ii) incentive compatible in dominant strategies if and only if all agents can be verified during execution.

In most multiagent systems planning on forehand can help to seriously improve the efficiency of executing actions. The main difference between centrally creating a plan and constructing a plan for a system of agents lies in the fact that in the latter coordination plays the main part. This introduces a number of additional difficulties. This special issue discusses some of these difficulties in detail. To place these in a context, this introduction gives a brief overview of multiagent planning problems, and most multiagent planning techniques.

Many different problems are called distributed or multiagent planning problems. Existing approaches each deal with only a subset of these problems. Which properties are essential in determining a solution method for multiagent planning problems? We argue that mainly the facts that communication is limited, agents have private goals, and the frequency of the dependencies between agents have a significant impact on the solution method.

We argue that timed models are a suitable framework for the detection of behavior in real-world event systems. A timed model which detects behavior is constructible by a domain expert. The inference of these timed models from data is a hard problem. We prove the inference of a class of timed automata (event recording automata) to be harder than the inference of finite automata.

Plan library's have proven their added value to the efficiency of planning. In this paper, we present results on the use of a plan library to plan repair. We show that using a relatively simple library, we can already obtain significant improvements in efficiency compared to plan repair without a library.

In this interactive event we demonstrate a web-based software tool to teach theorem proving in propositional logic, called Bop. This tool is a proof editor in the Fitch proof system that can give hints, proofsteps, or even complete proofs to the student.

We present a novel approach to multiagent planning for selfinterested agents. The main idea behind our approach is that multiagent planning systems should be built upon (singleagent) plan repair systems. In our system agents can exchange goals and subgoals through an auction, using their own heuristics or utility functions to determine when to auction and what to bid. Some experimental results for a logistics domain demonstrate empirically that this system supports the coordination of self-interested agents.