A Survey of Multi-Agent Systems for Optimization
                   Problems
                                                          Andrea Schaerf
                                                  DIEGM, University of Udine
                                                      Via delle Scienze 206
                                                        33100 Udine, Italy
                                                     Email: schaerf@uniud.it
                                              Web: http://www.diegm.uniud.it/schaerf


   Abstract—Optimization problems, such as resource alloca-          problem. The university course timetabling (CTT) problem
tion or scheduling, often involves different entities, such as       is one of the most studied educational timetabling problems
departments or production units, which might have different          and consists in scheduling a sequence of events or lectures
constraints and objectives, but are interested in cooperating. In
this presentation, we survey various scenarios and the solutions     of university courses in a prefixed period of time (typically
proposed in the literature for this kind of situations. We start     a week), satisfying a set of various constraints on rooms and
from simple distributed constraint satisfaction problems, to move    students.
to more complex situations involving contract nets and Markov           We consider the timetabling problem for a set of university
Decision Problems. Finally, we discuss various kinds of auctions     departments (or schools, or faculties) that have to schedule the
and market mechanisms to solve this kind of problems using a
timetabling problem as running example.                              courses of their curricula in a given term. Each department pre-
                                                                     pares its weekly schedule based on its endowment of rooms,
              I. O UTLINE OF THE P RESENTATION                       and according to its own constraints, rules, and objectives. In
   Complex optimization problems are ubiquitous in the indus-        general, a department is not willing to share its information
trial context. They range from resource allocation, to machine       with the other departments; therefore we assume that all input
scheduling, to logistics just to name some. In many cases, the       data are private for each department and thus inaccessible to
overall problem involves different entities, such as departments     the others.
or production units. The various entities, which have their             On the other hand, whenever resources are usable for
crucial decisions to make in terms of assignments, might have        more departments, e.g., they are located in the same site,
different constraints and objectives. Nevertheless, they are         departments could benefit from sharing and/or exchanging
normally interested in cooperating in order to obtain a global       their resources. Indeed, the resource endowment for each term
solution acceptable for all the entities involved. In addition, it   is not always optimally suited to the needs of the departments,
is often the case that there are privacy issues involved among       but rather based on political and historical matters. Moreover,
the entities, so that the possibility to share all the information   normally there are no global objectives to be satisfied; there-
is not a viable option.                                              fore all departments exchange resources for their own selfish
   In all these cases, it might be useful to resort to an            interest, although they have a moral impulse to be helpful with
architecture in which each decision maker is equipped with           the other departments, whenever possible without loss.
an agent-based software system. Each system should be able              We this specific timetabling setting, we discuss the possible
to solve complex optimization tasks, but also to interact            general architectures for the system and we describe the tasks
and negotiate with the other systems for the achievement of          and the functionalities of each of the agents. Finally, we will
common objectives or for the identification of actions that lead     discuss the trade-off between privacy and independence in the
to mutual advantages.                                                one side and effectiveness and efficiency on the other, for this
   In this presentation, we survey various scenarios and the so-     type of distributed problems.
lutions proposed in the literature for this kind of situations. We
start from simple distributed constraint satisfaction problems,
to move to more complex situations involving Contract Nets
or Markov Decision Problems. Finally, we discuss various
kinds of auctions and market mechanisms to solve this kind
of problems.
   We also discuss how optimization packages have to be
modified in order to take care of the presence of uncertain
resources that might be obtained from the other entities.
   Special attention will be devoted to a running case, arising
from a real-world problem, namely an educational timetabling