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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
