×

zbMATH — the first resource for mathematics

Mechanisms with monitoring for truthful RAM allocation. (English) Zbl 1403.68024
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 398-412 (2015).
Summary: Novel algorithmic ideas for big data have not been accompanied by advances in the way central memory is allocated to concurrently running programs. Commonly, RAM is poorly managed since the programs’ trade offs between speed of execution and RAM consumption are ignored. This trade off is, however, well known to the programmers. We adopt mechanism design tools to truthfully elicit this (multidimensional) information with the aim of designing more clever RAM allocation algorithms. We introduce a novel paradigm wherein programs are bound to overbidding declarations of their running times. We show the limitations of this paradigm in the absence of transfers and prove how to leverage waiting times, as a currency, to obtain optimal money burning mechanisms for the makespan.
For the entire collection see [Zbl 1326.68026].

MSC:
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
91B26 Auctions, bargaining, bidding and selling, and other market models
Software:
STXXL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Auletta, V., De Prisco, R., Penna, P., Persiano, G.: How to route and tax selfish unsplittable traffic. In: SPAA, pp. 196–205 (2004) · doi:10.1145/1007912.1007942
[2] Ben-Porath, E., Dekel, E., Lipman, B.L.: Optimal allocation with costly verification. Am. Econ. Rev. 104(12), 3779–3813 (2014) · doi:10.1257/aer.104.12.3779
[3] Blumrosen, L., Nisan, N.: On the computational power of demand queries. SIAM J. Comput. 39(4), 1372–1391 (2009) · Zbl 1193.91027 · doi:10.1137/050641181
[4] Christodoulou, G., Gourvès, L., Pascual, F.: Scheduling selfish tasks: about the performance of truthful algorithms. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 187–197. Springer, Heidelberg (2007) · Zbl 1206.90041 · doi:10.1007/978-3-540-73545-8_20
[5] Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 345–357. Springer, Heidelberg (2004) · Zbl 1098.91079 · doi:10.1007/978-3-540-27836-8_31
[6] Dementiev, R., Kettner, L., Sanders, P.: STXXL: standard template library for XXL data sets. Softw. Pract. Exper. 38(6), 589–637 (2008) · Zbl 05278578 · doi:10.1002/spe.844
[7] Fiat, A., Karp, R., Luby, M., McGeoch, L., Sleator, D., Young, N.: Competitive paging algorithms. J. Algorithms 12(4), 685–699 (1991) · Zbl 0753.68018 · doi:10.1016/0196-6774(91)90041-V
[8] Fotakis, D., Krysta, P., Ventre, C.: Combinatorial auctions without money. In: AAMAS, pp. 1029–1036 (2014) · Zbl 1411.91254
[9] Fotakis, D., Krysta, P., Ventre, C.: The power of verification for greedy mechanism design. In: AAMAS, pp. 307–315 (2015) · Zbl 1452.91071
[10] Hartline, J.D., Roughgarden,T.: Optimal mechanism design and money burning. In: STOC, pp. 75–84 (2008) · Zbl 1231.91117 · doi:10.1145/1374376.1374390
[11] Krysta, P., Ventre, C.: Combinatorial auctions with verification are tractable. Theoret. Comput. Sci. 571, 21–35 (2015) · Zbl 1307.91090 · doi:10.1016/j.tcs.2015.01.001
[12] Meyer, U., Sanders, P., Sibeyn, J.F. (eds.): Algorithms for Memory Hierarchies. LNCS, vol. 2625. Springer, Heidelberg (2003) · Zbl 1018.68761
[13] Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35, 166–196 (2001) · Zbl 0996.68251 · doi:10.1006/game.1999.0790
[14] Penna, P., Ventre, C.: Optimal collusion-resistant mechanisms with verification. Games Econ. Behav. 86, 491–509 (2014) · Zbl 1296.91130 · doi:10.1016/j.geb.2012.09.002
[15] Rochet, J.-C.: A condition for rationalizability in a quasi-linear context. J. Math. Econ. 16, 191–200 (1987) · Zbl 0628.90003 · doi:10.1016/0304-4068(87)90007-3
[16] Ventre, C.: Truthful optimization using mechanisms with verification. Theoret. Comput. Sci. 518, 64–79 (2014) · Zbl 1358.91063 · doi:10.1016/j.tcs.2013.07.034
[17] Vitter, J.S.: Algorithms and data structures for external memory. Found. Trends Theoret. Comput. Sci. 2(4), 305–474 (2006) · Zbl 1244.68007 · doi:10.1561/0400000014
[18] Vohra, R.V.: Mechanism Design: A Linear Programming Approach. Cambridge University Press, New York (2011) · Zbl 1233.91004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.