Plenary Speakers
In many decision-making settings, a selfish agent seeks to optimize its benefit given some situational constraints. Mathematically, the decision-maker’s task is often formulated as an optimization problem whose solution provides a prescriptive recommendation on the best decision. However, decision-making is rarely an individual task: each selfish decision-maker often interacts with other similarly self-interested decision-makers.
We explore the opportunities offered by the interplay of Mathematical Optimization and Algorithmic Game Theory by analyzing them through the lenses of a unified framework capable of integrating elements of the two disciplines. We introduce the taxonomy of Mathematical Programming Games (MPGs), simultaneous games where each agent decision problem is an optimization problem expressing a heterogeneous and possibly complex set of constraints. On the one hand, MPGs offer a rigorous and powerful mathematical framework for extending the broad family of problems involving the solution of combinatorial optimization problems – to name a few, logistics, scheduling, tactical decision-making – to a multi-agent setting. On the other hand, MPGs offer a novel perspective capturing the dynamics of strategic decision-making involving multiple agents solving optimization problems and help embed fairness paradigms into the decision-making process.
We present a few motivating examples and applications of MPGs, and we overview the challenges and opportunities associated with this promising stream of research offers. (Joint work with M. Carvalho, G. Dragotto and S. Sankaranarayanan.)
In the last thirty years, a breakthrough was obtained with the introduction of metaheuristics, such as Simulated Annealing, Tabu Search, Genetic Algorithms and Differential Evolution. These algorithms have the possibility to find their way out of local optima. Also, the development and utilization of nature inspired approaches in advanced information systems became increasingly popular. The most popular nature inspired methods are those representing successful animal and micro-organism team behavior, i.e. birds flocks or fish schools inspired Particle Swarm Optimization, the imitation of biological immune systems led to the Artificial Immune Systems, the ants foraging behaviors gave rise to Ant Colony Optimization, the optimized performance of bees inspired Honey Bees Mating Optimization algorithm and Bumble Bees Mating Optimization algorithm, etc. We present a collection of different metaheuristic and nature inspired algorithms, we analyze and compare them based on their results when applied to some classic combinatorial optimization problems, like vehicle routing problem. Each metaheuristic and nature inspired method is presented not only in its classic form but also the most known variants of each method are presented and used in the comparisons. Thus, the methods presented are Genetic Algorithms and their variants, Differential Evolution and Particle Swarm Optimization and its variants. Genetic Algorithms (GAs) are randomized search techniques that simulate some of the processes observed in natural evolution and they offer a particularly attractive approach for many kinds of problems since they are generally quite effective in solving large-scale problems and for rapid global search of large, non-linear and poorly understood spaces. Differential Evolution (DE) is a stochastic, population-based algorithm. Although Differential Evolution is an evolutionary algorithm and, thus, it shares the basic characteristic of the evolutionary algorithms, it has a number of differences compared to them. Particle Swarm Optimization (PSO) is a population-based swarm intelligence algorithm that uses the physical movements of the individuals in the swarm. The advantages and disadvantages of these and other nature inspired methods are presented based on the results of the algorithms in classic combinatorial optimization problems.
Fairness issues have received widespread attention in combinatorial optimization. In this talk we will consider fair allocation problems related to subset sum and partitioning problems.
In the first part we consider the allocation of a bounded resource among several agents. For each agent the obtained share of the resource serves as a capacity bound for a subset sum problem with the agent’s item set. If a central decision maker maximizes the total sum of item weights, this may result in a highly un- balanced allocation of the resource to the agents and hence be perceived as unfair. On the other hand, more balanced allocations may be far from the overall optimum. Therefore, we will discuss the resulting
price of fairness, based on maximin, Kalai–Smorodinski and proportional fairness.
In the second part items cannot be selected by the agents themselves but are allocated by the central decision maker from a common ground set. However, agents can express their preferences by setting a profit value for every item. The decider wants to assign each item to an agent such that the satisfaction, i.e. sum of profits, guaranteed for each of the agents gets as high as possible. This maximin problem is known as the so-called
Santa Claus problem. We extend this problem by introducing an incompatibility relation between pairs of items described in terms of a
conflict graph. Every subset of items assigned to one agent has to form an independent set in this graph. Thus, the allocation of items to the agents corresponds to a partial coloring of the conflict graph. For this setting we present complexity and algorithmic results depending on the properties of the given conflict graph.
To allow a more flexible approach of expressing preferences we also introduce a new satisfaction measure based on a directed preference graph of each agent. We measure the
dissatisfaction of an agent by means of the number of non-assigned items for which no more preferred item is given to the agent. From a fairness perspective we want to allocate the items to the agents in a way that minimizes the maximum dissatisfaction among the agents. Again we obtain NP-hardness results as well as polynomial algorithms with respect to different underlying graph structures, such as trees, stars, paths, and matchings.
