Семниар МЛ Теории игр от 1 апреля 2025 года
Title: Fair Scheduling of Indivisible Chores Abstract: We will discuss the problem of fairly assigning a set of discrete tasks, or chores, among a set of agents. Each chore has a designated start and finish time, and each agent can perform at most one chore at any time. We will explore the existence and computation of "fair" (specifically, envy-free up to one chore) and "efficient" (specifically, maximal or Pareto optimal) schedules under various settings. The presentation will cover novel technical ideas, including a color-switching technique and an application of the "cycle-plus-triangles" theorem (originally conjectured by Erdős) for achieving approximate envy-freeness. We will also highlight several open problems and directions for future work.
Title: Fair Scheduling of Indivisible Chores Abstract: We will discuss the problem of fairly assigning a set of discrete tasks, or chores, among a set of agents. Each chore has a designated start and finish time, and each agent can perform at most one chore at any time. We will explore the existence and computation of "fair" (specifically, envy-free up to one chore) and "efficient" (specifically, maximal or Pareto optimal) schedules under various settings. The presentation will cover novel technical ideas, including a color-switching technique and an application of the "cycle-plus-triangles" theorem (originally conjectured by Erdős) for achieving approximate envy-freeness. We will also highlight several open problems and directions for future work.