Let G=(V,E) be a graph modeling a network where each edge is owned by a selfish agent, which establishes the cost for using her edge by pursuing only her personal utility. In such a setting, several classic network optimization problems, like for instance many graph traversal problems, asks for solutions in which an edge of G can be used several times. In game-theoretic terms, these problems are known as one-parameter problems, but with a peculiarity: the workload 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 technique to efficiently develop truthful mechanisms for this family of problems.

Bilò, D., Forlizzi, L., Gualà, L., & Proietti, G. (2007). An algorithm composition scheme preserving monotonicity. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing 2007, Pages 360-361 PODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing; Portland. New York : ACM [10.1145/1281100.1281173].

An algorithm composition scheme preserving monotonicity

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 using her edge by pursuing only her personal utility. In such a setting, several classic network optimization problems, like for instance many graph traversal problems, asks for solutions in which an edge of G can be used several times. In game-theoretic terms, these problems are known as one-parameter problems, but with a peculiarity: the workload 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 technique to efficiently develop truthful mechanisms for this family of problems.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007
2007
Assocition for Computing Machinery
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
eng
http://dl.acm.org/citation.cfm?doid=1281100.1281173
Intervento a convegno
Bilò, D., Forlizzi, L., Gualà, L., & Proietti, G. (2007). An algorithm composition scheme preserving monotonicity. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing 2007, Pages 360-361 PODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing; Portland. New York : ACM [10.1145/1281100.1281173].
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/42772
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact