Dealing with Selfishness in Optimization

Rob van Stee

Dealing with Selfishness in Optimization

In my research, I focus on optimization problems that involve selfishness in some way. This usually takes the form of selfish agents holding part of the input data and having the option of misrepresenting their data if this is to their own benefit. A prime example of this is given by scheduling problems where the machines are controlled by selfish agents, where only each agent knows how fast their machine is. The agents are only interested in maximizing their own utility, which may be quite different from the overall optimization goal. Our goal in algorithmic mechanism design is to design mechanisms that ensure that reporting their speeds truthfully is a dominant strategy for the agents. Only in this way can we hope to discover the true speeds and optimize the overall objective function successfully.

A mechanism collects bids from the agents that are hopefully true representations of their speeds, allocates jobs to the machines and pays the agents for their work. The utility of an agent is the payout that it receives from the mechanism minus the cost that it has for processing the jobs assigned to it. This cost is also known as the load on its machine, and is equal to the total size of the jobs allocated to it divided by its speed. A strategy (reported speed) of an agent is dominant if this strategy maximizes the utility of this agent regardless of the strategies chosen by the other agents. If telling the truth is a dominant strategy for every agent, we say that our mechanism is truthful.

It is known that in order to get a truthful mechanism, a necessary and sufficient condition is that the job allocation of the mechanism be monotone. Monotone means that if one agent decreases its claimed speed, the total size of the jobs assigned to it by the mechanism as a result may not increase. The set of assigned jobs does not necessarily have to remain the same, however.

Many objective functions for scheduling have been considered in the past, both in a classical setting (without agents) and in the game-theoretical setting described above. Many of these are some function of the loads of the machines, for example, the makespan (maximum load). Together with Leah Epstein and Asaf Levin, I have recently designed a unifi ed monotone approximation scheme for all known objective functions that are functions of the loads, like the makespan, the cover (where the goal is to maximize the minimum load), and the p-norm of the loads. An approximation scheme is a family of approximation algorithms that, in addition to the given machines and jobs, takes a positive value epsilon as input and produces an output for which the value of the objective function is within one plus epsilon of the optimal value for these jobs and machines. This improves and generalizes on previous approximation schemes, which depended on randomization, required many special cases and a difficult analysis, or were only quasi-polynomial-time.

In addition to algorithmic mechanism design, I am also interested in the related question of how bad selfishness is, or put another way, by how much we could improve the performance of a system using centralized coordination compared to letting every participant make their own decisions. A well-known example of a system where everybody makes their own decisions is routing: when you plan your route to work in the morning, you are generally only interested in your own travel time and do not care about the travel times of the other people on the road. We formalize such systems as networks with selfi sh agents. Every agent has a starting point and a destination, and wants to reach its destination as fast as possible. How long this takes depends on how many other agents use the same links as this agent. Much is known about selfish routing on general graphs, but the ring structure has not yet been studied in much detail (though some initial results have been obtained). This structure is very relevant, however, as the Internet in Europe in fact consists of interlocking rings (e.g. the German network is based on a ring). Together with Xujin Chen, Benjamin Doerr, Xiaodong Hu, Weidong Ma, and Carola Winzen, I have shown that on rings, at most a factor of two can be gained by having a central coordinator, if the goal is to minimize the maximum latency of any player.