January 12, Wednesday
14:00 – 15:30
Mechanism Design for Scheduling: Theoretical and Experimental Perspectives
Computer Science seminar
Lecturer : Ahuva Mu'alem
Affiliation : California Institute of Technology
Location : 202/37
Host : Dr. Paz Carmi
Scheduling is a major challenge in the design of operating systems,
and is used to achieve quality of service guarantees. In many
real-life environments, e.g., cloud computing, the service provider
and users can have different, possibly conflicting, interests, and
behave strategically. In this talk we take an economic mechanism design
approach to scheduling, and examine scheduling from both a theoretical
perspective and an experimental perspective.
We consider the challenge of designing mechanisms, that is, algorithms coupled with pricing schemes, that are both manipulation resistant and guarantee good quality of service. Our contribution is twofold:
(1) An inapproximability result for randomized mechanisms in a
well-studied machine scheduling context.
(2) A game-theoretic model for provider-consumer dynamic interaction
and simulation results based on real data that establish existence
of a single pure Nash equilibrium in practice.
No prior knowledge is assumed. Joint work with Lior Amar, Amnon Barak, Michael Schapira, and Sergei Shudler