Let G = (V, E) be a graph modeling a network where each edge is owned by a selfish agent, which establishes the cost for traversing her edge (i.e., assigns a weight to her edge) by pursuing only her personal utility. In such a setting, we aim at designing approximate truthful mechanisms for several NP-hard traversal problems on G, like the graphical traveling salesman problem, the rural postman problem, and the mixed Chinese postman problem, either of which asks for using an edge of G several times, in general. Thus, in game-theoretic terms, these are one-parameter problems, but with a peculiarity: the work load of each agent is a natural number. In this paper we refine the classic notion of monotonicity of an algorithm so as to exactly capture this property, and we then provide a general mechanism design technique that guarantees this monotonicity and that allows to compute efficiently the corresponding payments. In this way, we show that the former two problems and the latter one admit a 3/2- and a 2-approximate truthful mechanism, respectively. Thus, for the first two problems we match the best known approximation ratios holding for their corresponding centralized versions, while for the third one we are only a 4/3-factor away from it.

Bilò, D., Forlizzi, L., Gualà, L., & Proietti, G. (2007). Approximate Mechanisms for the Graphical TSP and Other Graph Traversal Problems. In Internet and Network Economics, Third International Workshop, WINE 2007... Proceedings. Springer [10.1007/978-3-540-77105-0_54].

Approximate Mechanisms for the Graphical TSP and Other Graph Traversal Problems

GUALA', LUCIANO;
2007

Abstract

Let G = (V, E) be a graph modeling a network where each edge is owned by a selfish agent, which establishes the cost for traversing her edge (i.e., assigns a weight to her edge) by pursuing only her personal utility. In such a setting, we aim at designing approximate truthful mechanisms for several NP-hard traversal problems on G, like the graphical traveling salesman problem, the rural postman problem, and the mixed Chinese postman problem, either of which asks for using an edge of G several times, in general. Thus, in game-theoretic terms, these are one-parameter problems, but with a peculiarity: the work load of each agent is a natural number. In this paper we refine the classic notion of monotonicity of an algorithm so as to exactly capture this property, and we then provide a general mechanism design technique that guarantees this monotonicity and that allows to compute efficiently the corresponding payments. In this way, we show that the former two problems and the latter one admit a 3/2- and a 2-approximate truthful mechanism, respectively. Thus, for the first two problems we match the best known approximation ratios holding for their corresponding centralized versions, while for the third one we are only a 4/3-factor away from it.
Internet and Network Economics, Third International Workshop, WINE 2007
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
eng
Algorithmic mechanism design Approximate truthful mechanisms Graph traversal problems Selfish agents
https://link.springer.com/chapter/10.1007%2F978-3-540-77105-0_54
Intervento a convegno
Bilò, D., Forlizzi, L., Gualà, L., & Proietti, G. (2007). Approximate Mechanisms for the Graphical TSP and Other Graph Traversal Problems. In Internet and Network Economics, Third International Workshop, WINE 2007... Proceedings. Springer [10.1007/978-3-540-77105-0_54].
Bilò, D; Forlizzi, L; Guala', L; Proietti, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/43007
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact