Aigaion: RACTI / RU1 Technical Report Series (Web Based)

[RACTI-RU1-2008-73] Caragiannis, Ioannis, Kaklamanis, Christos, Kanellopoulos, Panagiotis and Papaioannou, Evi, Scheduling to maximize participation, in: Theoretical Computer Science (TCS), volume 402, number 2-3, pages 142-155, 2008. [DOI]
Abstract: We study a problem of scheduling client requests to servers. Each client has a particular latency requirement at each server and may choose either to be assigned to some server in order to get serviced provided that her latency requirement is met, or not to participate in the assignment at all. From a global perspective, in order to optimize the performance of such a system, one would aim to maximize the number of clients that participate in the assignment. However, clients may behave selfishly in the sense that, each of them simply aims to participate in an assignment and get serviced by some server where her latency requirement is met with no regard to overall system performance. We model this selfish behavior as a strategic game, show how to compute pure Nash equilibria efficiently, and assess the impact of selfishness on system performance. We also show that the problem of optimizing performance is computationally hard to solve, even in a coordinated way, and present efficient approximation and online algorithms.
[RACTI-RU1-2006-98] Caragiannis, Ioannis, Kaklamanis, Christos, Kanellopoulos, Panagiotis and Papaioannou, Evi, Scheduling to maximize participation, in: 2nd Symposium on Trustworthy Global Computing (TGC 2006), pages 218-232, Springer, 2006.
Abstract: We study a problem of scheduling client requests to servers. Each client has a particular latency requirement at each server and may choose either to be assigned to some server in order to get serviced provided that her latency requirement is met or not to participate in the assignment at all. From a global perspective, in order to optimize the performance of such a system, one would aim to maximize the number of clients that participate in the assignment. However, clients may behave selfishly in the sense that each of them simply aims to participate in an assignment and get serviced by some server where her latency requirement is met with no regard to the overall system performance. We model this selfish behavior as a strategic game, show how to compute equilibria efficiently, and assess the impact of selfishness on system performance. We also show that the problem of optimizing performance is computationally hard to solve, even in a coordinated way, and present efficient approximation and online algorithms.