Helsinki Algorithms Seminar: Aristides Gionis, Aalto University "The effects of teamwork in time-inconsistent planning"

Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design.
Department of Computer Science, image: Matti Ahlgren

The effects of teamwork in time-inconsistent planning

Aristides Gionis
Aalto University

The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder.

In this work we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost.

We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of teamwork. We show that while a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard.

This is joint work with Aris Anagnostopoulos and Nikos Parotsidis.

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.

  • Julkaistu:
  • Päivitetty:
URL kopioitu