{"data":{"id":"10.48550/arxiv.0907.5219","type":"dois","attributes":{"doi":"10.48550/arxiv.0907.5219","prefix":"10.48550","suffix":"arxiv.0907.5219","identifiers":[{"identifier":"0907.5219","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"0907.5219"}],"creators":[{"name":"Dobzinski, Shahar","nameType":"Personal","givenName":"Shahar","familyName":"Dobzinski","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"A Note on the Power of Truthful Approximation Mechanisms"}],"publisher":"arXiv","container":{},"publicationYear":2009,"subjects":[{"lang":"en","subject":"Computer Science and Game Theory (cs.GT)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2009-07-30T09:18:31Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2009-12-01T12:26:15Z","dateType":"Updated","dateInformation":"v1"},{"date":"2009-08-24T15:41:55Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2009-12-01T12:26:15Z","dateType":"Updated","dateInformation":"v2"},{"date":"2009-07","dateType":"Available","dateInformation":"v1"},{"date":"2009","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We study the power of polynomial-time truthful mechanisms comparing to polynomial time (non-truthful) algorithms. We show that there is a setting in which deterministic polynomial-time truthful mechanisms cannot guarantee a bounded approximation ratio, but a non-truthful FPTAS exists. We also show that in the same setting there is a universally truthful mechanism that provides an approximation ratio of 2. This shows that the cost of truthfulness is unbounded. The proofs are almost standard in the field and follow from known results.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4wOTA3LjUyMTk8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4wOTA3LjUyMTk8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+RG9iemluc2tpLCBTaGFoYXI8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlNoYWhhcjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Eb2J6aW5za2k8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgPC9jcmVhdG9ycz4KICA8dGl0bGVzPgogICAgPHRpdGxlPkEgTm90ZSBvbiB0aGUgUG93ZXIgb2YgVHJ1dGhmdWwgQXBwcm94aW1hdGlvbiBNZWNoYW5pc21zPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDA5PC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+Q29tcHV0ZXIgU2NpZW5jZSBhbmQgR2FtZSBUaGVvcnkgKGNzLkdUKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IENvbXB1dGVyIGFuZCBpbmZvcm1hdGlvbiBzY2llbmNlczwvc3ViamVjdD4KICA8L3N1YmplY3RzPgogIDxkYXRlcz4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDktMDctMzBUMDk6MTg6MzFaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMDktMTItMDFUMTI6MjY6MTVaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAwOS0wOC0yNFQxNTo0MTo1NVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MiI+MjAwOS0xMi0wMVQxMjoyNjoxNVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDA5LTA3PC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJQcmVwcmludCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDx2ZXJzaW9uPjI8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2FyeGl2Lm9yZy9saWNlbnNlcy9ub25leGNsdXNpdmUtZGlzdHJpYi8xLjAvIj5hclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2U8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5XZSBzdHVkeSB0aGUgcG93ZXIgb2YgcG9seW5vbWlhbC10aW1lIHRydXRoZnVsIG1lY2hhbmlzbXMgY29tcGFyaW5nIHRvIHBvbHlub21pYWwgdGltZSAobm9uLXRydXRoZnVsKSBhbGdvcml0aG1zLiBXZSBzaG93IHRoYXQgdGhlcmUgaXMgYSBzZXR0aW5nIGluIHdoaWNoIGRldGVybWluaXN0aWMgcG9seW5vbWlhbC10aW1lIHRydXRoZnVsIG1lY2hhbmlzbXMgY2Fubm90IGd1YXJhbnRlZSBhIGJvdW5kZWQgYXBwcm94aW1hdGlvbiByYXRpbywgYnV0IGEgbm9uLXRydXRoZnVsIEZQVEFTIGV4aXN0cy4gV2UgYWxzbyBzaG93IHRoYXQgaW4gdGhlIHNhbWUgc2V0dGluZyB0aGVyZSBpcyBhIHVuaXZlcnNhbGx5IHRydXRoZnVsIG1lY2hhbmlzbSB0aGF0IHByb3ZpZGVzIGFuIGFwcHJveGltYXRpb24gcmF0aW8gb2YgMi4gVGhpcyBzaG93cyB0aGF0IHRoZSBjb3N0IG9mIHRydXRoZnVsbmVzcyBpcyB1bmJvdW5kZWQuIFRoZSBwcm9vZnMgYXJlIGFsbW9zdCBzdGFuZGFyZCBpbiB0aGUgZmllbGQgYW5kIGZvbGxvdyBmcm9tIGtub3duIHJlc3VsdHMuPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/0907.5219","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-15T18:48:09.000Z","registered":"2022-03-15T18:48:10.000Z","published":"2009","updated":"2022-03-15T18:48:10.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.0907.5219","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}