Strongly polynomial-time truthful mechanisms in one shot

Theoretical Computer Science - Tập 410 - Trang 1607-1615 - 2009
Paolo Penna1, Guido Proietti2,3, Peter Widmayer4
1Dipartimento di Informatica ed Applicazioni “Renato M. Capocelli”, Università di Salerno, Italy
2Dipartimento di Informatica, Università di L’Aquila, Italy
3Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, CNR, Roma, Italy
4Institut für Theoretische Informatik, ETH, Zürich, Switzerland

Tài liệu tham khảo

Agarwal, 1995

A. Archer, E. Tardos, Truthful mechanisms for one-parameter agents, in: Proc. of the Annual IEEE Symposium on Foundations of Computing, FOCS, 2001, pp. 482–491

Clarke, 1971, Multipart pricing of public goods, Public Choice, 17, 10.1007/BF01726210

Feigenbaum, 2002, Distributed algorithmic mechanism design: Recent results and future directions, 1

Groves, 1973, Incentive in teams, Econometrica, 41, 617, 10.2307/1914085

Gualà, 2005, A truthful (2-2/k)-approximation mechanism for the Steiner tree problem with k terminals, vol. 3595, 90

Gualà, 2005, Efficient truthful mechanisms for the single-source shortest paths tree problem, vol. 3648, 941

Hassin, 1995, On the minimum diameter spanning tree problem, Information Processing Letters, 53, 109, 10.1016/0020-0190(94)00183-Y

J. Hershberger, S. Suri, Vickrey prices and shortest paths: What is an edge worth?, in: Proc. of the 42nd Annual IEEE Symposium on Foundations of Computing, FOCS, 2001, pp. 252–259

M.-Y. Kao, X.-Y. Li, W. Wang, Towards truthful mechanisms for binary demand games: A general framework, in: Proc. of ACM Electronic Commerce, EC, 2005

Koutsoupias, 1999, Worst-case equilibria, vol. 1563, 404

A. Mu’Alem, N. Nisan, Truthful approximation mechanisms for restricted combinatorial auctions, in: Proc. of 18th National Conference on Artificial Intelligence, AAAI, 2002, pp. 379–384

Myerson, 1981, Optimal auction design, Mathematics of Operations Research, 6, 58, 10.1287/moor.6.1.58

Nardelli, 2003, Finding the most vital node of a shortest path, Theoretical Computer Science, 296, 167, 10.1016/S0304-3975(02)00438-3

N. Nisan, A. Ronen, Algorithmic mechanism design, in: Proc. of the 31st Annual ACM Symposium on Theory of Computing, STOC, 1999, pp. 129–140

C.H. Papadimitriou, Algorithms, games, and the internet, in: Proc. of Annual ACM Symposium on Theory of Computing, STOC, 2001, pp. 749–753

S. Pettie, V. Ramachandran, Computing shortest paths with comparisons and additions, in: Proc. of the 13th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2002, pp. 267–276

Proietti, 2005, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, 195

Tansel, 1983, Location on networks: A survey. Part I: The p-center and p-median problems, Management Sciences, 29, 482, 10.1287/mnsc.29.4.482

Vickrey, 1961, Counterspeculation, auctions and competitive sealed tenders, Journal of Finance, 8, 10.1111/j.1540-6261.1961.tb02789.x

Thông tin
Thông tin xuất bản

Theoretical Computer Science

Tập 410

1607-1615

Thông tin tác giả