In this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs. More precisely, we are given a graph G of n nodes, and we assume that each edge of G is owned by a selfish agent. The strategy of an agent consists in revealing to the system the cost for using its edge, but this cost is not constant and can change over time. Additionally, edges can enter into and exit from G. Among the various possible assumptions which can be made to model how these edge-cost modifications take place, we focus on two settings: (i) the dynamic, in which modifications are unpredictable and time-independent, and for a given optimization problem on G, the mechanism has to maintain efficiently the output specification and the payment scheme for the agents; (ii) the time-sequenced, in which modifications happens at fixed time steps, and the mechanism has to minimize an objective function which takes into consideration both the quality and the set-up cost of a new solution. In both settings, we investigate the existence of exact and approximate truthful mechanisms. In particular, for the dynamic setting, we analyze the minimum spanning tree problem, and we show that if edge costs can only decrease, then there exists an efficient dynamic truthful mechanism for handling a sequence of k edge-cost reductions having runtime, where h is the overall number of payment changes.

Bilò, D., Gualà, L., & Proietti, G. (2006). Dynamic Mechanism Design. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Volume 4286 LNCS, 2006, Pages 3-15 2nd International Workshop on Internet and Network Economics, WINE 2006 (pp.3-13). Springer [10.1007/11944874_2].

Dynamic Mechanism Design

GUALA', LUCIANO;
2006

Abstract

In this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs. More precisely, we are given a graph G of n nodes, and we assume that each edge of G is owned by a selfish agent. The strategy of an agent consists in revealing to the system the cost for using its edge, but this cost is not constant and can change over time. Additionally, edges can enter into and exit from G. Among the various possible assumptions which can be made to model how these edge-cost modifications take place, we focus on two settings: (i) the dynamic, in which modifications are unpredictable and time-independent, and for a given optimization problem on G, the mechanism has to maintain efficiently the output specification and the payment scheme for the agents; (ii) the time-sequenced, in which modifications happens at fixed time steps, and the mechanism has to minimize an objective function which takes into consideration both the quality and the set-up cost of a new solution. In both settings, we investigate the existence of exact and approximate truthful mechanisms. In particular, for the dynamic setting, we analyze the minimum spanning tree problem, and we show that if edge costs can only decrease, then there exists an efficient dynamic truthful mechanism for handling a sequence of k edge-cost reductions having runtime, where h is the overall number of payment changes.
Internet and Network Economics, Second International Workshop, WINE 2006
Patras, Greece
2006
2nd
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
eng
Algorithmic mechanism design Approximate mechanisms Dynamic algorithms On-line problems
https://link.springer.com/chapter/10.1007%2F11944874_2
Intervento a convegno
Bilò, D., Gualà, L., & Proietti, G. (2006). Dynamic Mechanism Design. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Volume 4286 LNCS, 2006, Pages 3-15 2nd International Workshop on Internet and Network Economics, WINE 2006 (pp.3-13). Springer [10.1007/11944874_2].
Bilò, D; 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/41536
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact