Selfishness and optimization for multi-agent packing and coverage problems

In the last decades of computer science development the focus gradually moved from centralized systems to a network perspective, mainly motivated by the quick and deep influence of the Internet. Numerous new problems arose, i.e. the need of efficient algorithms for IOT (internet of things) or models of behavior of large numbers of people trough social networks. In this scenario, many classical optimization problems are again under the spotlight since they are rethink under the perspective of multi-agent and distributed systems. Two classical examples are problems where the resources are decentralized, such as in web servers loading distribution, or simply game theoretical setting where some part of the problem is controlled by agents which aim at pursing their own goals. In this thesis we focus on two classical optimization problems, the coverage problem and the bin packing problem, and we analyze them from both centralized and multiagent perspectives. Both of them have plenty of real-world applications such as job scheduling, facility locations and resource allocations. Firstly, we consider multi-agent coverage where agents use their own budget to cover elements. We are interested in maximizing the total revenue defined as the sum of the revenue of each agent. For this problem we study two settings that differ in how the agents share the utilities of the elements. For each sub-setting we define a game and analyze the Nash equilibrium and its properties. We also consider the centralized problem where we maximize the total revenue, while satisfying the agents’ budget constraints. The second setting that we consider is a generalization of the budgeted coverage problem, where the profit is measured by a monotone submodular function over the elements. We give an approximation factor algorithm for the general case and discuss solutions for relevant instances of the problem. Finally, we study a colorful bin packing game in which a set of items, each one controlled by a selfish agent, is to be packed into a minimum number of unit capacity bins. A bin has a unitary cost which is shared among the items it contains, so that agents are interested in selecting a bin of minimum shared cost. Moreover, each item has a color and two items with the same color can not be adjacent in a bin. We show the existence of Nash equilibria for two standard cost sharing functions and provide a tight characterization of their efficiency. We also design an algorithm which returns Nash equilibria with best achievable performance for an interesting special setting.