Loading...
Please wait, while we are loading the content...
Similar Documents
How to route and tax selfish unsplittable traffic (2004)
| Content Provider | CiteSeerX |
|---|---|
| Author | Auletta, Vincenzo Penna, Paolo Prisco, Roberto De Persiano, Pino |
| Description | We study the problem of assigning unsplittable traffic to a set of m links so to minimize the maximum link congestion (i.e., the makespan). We consider the case of selfish agents owning pieces of the traffic. In particular, we introduce a variant of the model by Koutsopias and Papadimitriou [1999] in which owners of the traffic cannot directly choose which link to use; instead, the assignment is performed by a scheduler. The agents can manipulate the scheduler by reporting false information regarding the size of each piece of unsplittable traffic. We provide upper and lower bounds on the approximation achievable by mechanisms that induce a Nash equilibrium when all agents report their true values. For the case of each agent owning one job, our positive results for m identical links show the effectiveness of introducing such a scheduler since, in this case, (1 + ɛ)-approximate solutions are guaranteed in polynomial time. In contrast, the result by Koutsopias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash log m log log m)-approximate equilibria yield (in the worst case) Ω( solutions, even for unitary weighted traffic. When links have different speeds we prove lower and upper bounds on the approximation achievable by a mechanism inducing a Nash equilibrium. For the case of agents owning more than one job, we give mechanisms that achieve constant approximation and prove lower bounds on the approximation ratio that can be achieved by a mechanism. |
| File Format | |
| Language | English |
| Publisher Date | 2004-01-01 |
| Publisher Institution | In Proc. of the Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
