In this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs with selfish edges. 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-at each time instant-the cost at the actual time for using its edge. Additionally, edges can enter into and exit from G. Among the various possible assumptions which can be made to model how this edge-cost modifications take place, we focus on two settings: (i) the dynamic, in which modifications can happen at any time, 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 (w.r.t. to suitable equilibrium concepts) mechanisms. In particular, for the dynamic setting, we analyze the minimum spanning tree problem, and we show that if edge costs can only decrease and each agent adopts a myopic best response strategy (i.e., its utility is only measured instantaneously), then there exists an efficient dynamic truthful (in myopic best response equilibrium) mechanism for handling a sequence of k declarations of edge-cost reductions having runtime O ((h + k) log n), where h is the overall number of payment changes.

Bilò, D., Gualà, L., & Proietti, G. (2009). Dynamic mechanism design. THEORETICAL COMPUTER SCIENCE, 410(17), 4564-4572 [10.1016/j.tcs.2008.12.029].

Dynamic mechanism design

GUALA', LUCIANO;
2009

Abstract

In this paper we address the question of designing truthful mechanisms for solving optimization problems on dynamic graphs with selfish edges. 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-at each time instant-the cost at the actual time for using its edge. Additionally, edges can enter into and exit from G. Among the various possible assumptions which can be made to model how this edge-cost modifications take place, we focus on two settings: (i) the dynamic, in which modifications can happen at any time, 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 (w.r.t. to suitable equilibrium concepts) mechanisms. In particular, for the dynamic setting, we analyze the minimum spanning tree problem, and we show that if edge costs can only decrease and each agent adopts a myopic best response strategy (i.e., its utility is only measured instantaneously), then there exists an efficient dynamic truthful (in myopic best response equilibrium) mechanism for handling a sequence of k declarations of edge-cost reductions having runtime O ((h + k) log n), where h is the overall number of payment changes.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
eng
Algorithmic mechanism design Approximate mechanisms Dynamic algorithms On-line problems Truthful mechanisms
http://www.sciencedirect.com/science/article/pii/S0304397508008992?via%3Dihub
Bilò, D., Gualà, L., & Proietti, G. (2009). Dynamic mechanism design. THEORETICAL COMPUTER SCIENCE, 410(17), 4564-4572 [10.1016/j.tcs.2008.12.029].
Bilò, D; Guala', L; Proietti, G
Articolo su rivista
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/37008
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact