TY - GEN

T1 - Frugal mechanism design via spectral techniques

AU - Chen, Ning

AU - Elkind, Edith

AU - Gravin, Nick

AU - Petrov, Fedor

PY - 2010/12/1

Y1 - 2010/12/1

N2 - We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [2] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the √ - mechanism for buying a path in a graph [18] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, our mechanism is within a factor of k + 1 from optimal; moreover, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [10]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [18] and answers several open questions proposed in [18].

AB - We study the design of truthful mechanisms for set systems, i.e., scenarios where a customer needs to hire a team of agents to perform a complex task. In this setting, frugality [2] provides a measure to evaluate the "cost of truthfulness", that is, the overpayment of a truthful mechanism relative to the "fair" payment. We propose a uniform scheme for designing frugal truthful mechanisms for general set systems. Our scheme is based on scaling the agents' bids using the eigenvector of a matrix that encodes the interdependencies between the agents. We demonstrate that the r-out-of-k-system mechanism and the √ - mechanism for buying a path in a graph [18] can be viewed as instantiations of our scheme. We then apply our scheme to two other classes of set systems, namely, vertex cover systems and k-path systems, in which a customer needs to purchase k edge-disjoint source-sink paths. For both settings, we bound the frugality of our mechanism in terms of the largest eigenvalue of the respective interdependency matrix. We show that our mechanism is optimal for a large subclass of vertex cover systems satisfying a simple local sparsity condition. For k-path systems, our mechanism is within a factor of k + 1 from optimal; moreover, we show that it is, in fact, optimal, when one uses a modified definition of frugality proposed in [10]. Our lower bound argument combines spectral techniques and Young's inequality, and is applicable to all set systems. As both r-out-of-k systems and single path systems can be viewed as special cases of k-path systems, our result improves the lower bounds of [18] and answers several open questions proposed in [18].

UR - http://www.scopus.com/inward/record.url?scp=78751493200&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2010.77

DO - 10.1109/FOCS.2010.77

M3 - Conference contribution

AN - SCOPUS:78751493200

SN - 9780769542447

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 755

EP - 764

BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

Y2 - 23 October 2010 through 26 October 2010

ER -