{"data":{"id":"10.48550/arxiv.1902.04635","type":"dois","attributes":{"doi":"10.48550/arxiv.1902.04635","prefix":"10.48550","suffix":"arxiv.1902.04635","identifiers":[{"identifier":"1902.04635","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1902.04635"}],"creators":[{"name":"Gravin, Nick","nameType":"Personal","givenName":"Nick","familyName":"Gravin","affiliation":[],"nameIdentifiers":[]},{"name":"Jin, Yaonan","nameType":"Personal","givenName":"Yaonan","familyName":"Jin","affiliation":[],"nameIdentifiers":[]},{"name":"Lu, Pinyan","nameType":"Personal","givenName":"Pinyan","familyName":"Lu","affiliation":[],"nameIdentifiers":[]},{"name":"Zhang, Chenhao","nameType":"Personal","givenName":"Chenhao","familyName":"Zhang","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Optimal Budget-Feasible Mechanisms for Additive Valuations"}],"publisher":"arXiv","container":{},"publicationYear":2019,"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":"2019-02-12T21:08:08Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2019-02-14T01:02:17Z","dateType":"Updated","dateInformation":"v1"},{"date":"2020-07-21T00:39:22Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2020-07-22T00:06:29Z","dateType":"Updated","dateInformation":"v2"},{"date":"2019-02","dateType":"Available","dateInformation":"v1"},{"date":"2019","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":"In this paper, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio of $2$, improving the previous best known result of $3$. Our bound is tight with respect to either the optimal offline benchmark, or its fractional relaxation. We also present a simple deterministic mechanism with the tight approximation guarantee of $3$ against the fractional optimum, improving the best known result of $(2+ \\sqrt{2})$ for the weaker integral benchmark.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xOTAyLjA0NjM1PC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MTkwMi4wNDYzNTwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5HcmF2aW4sIE5pY2s8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPk5pY2s8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+R3JhdmluPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkppbiwgWWFvbmFuPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5ZYW9uYW48L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+SmluPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkx1LCBQaW55YW48L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPlBpbnlhbjwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5MdTwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5aaGFuZywgQ2hlbmhhbzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+Q2hlbmhhbzwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5aaGFuZzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+T3B0aW1hbCBCdWRnZXQtRmVhc2libGUgTWVjaGFuaXNtcyBmb3IgQWRkaXRpdmUgVmFsdWF0aW9uczwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAxOTwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkNvbXB1dGVyIFNjaWVuY2UgYW5kIEdhbWUgVGhlb3J5IChjcy5HVCk8L3N1YmplY3Q+CiAgICA8c3ViamVjdCBzdWJqZWN0U2NoZW1lPSJGaWVsZHMgb2YgU2NpZW5jZSBhbmQgVGVjaG5vbG9neSAoRk9TKSI+Rk9TOiBDb21wdXRlciBhbmQgaW5mb3JtYXRpb24gc2NpZW5jZXM8L3N1YmplY3Q+CiAgPC9zdWJqZWN0cz4KICA8ZGF0ZXM+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE5LTAyLTEyVDIxOjA4OjA4WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDE5LTAyLTE0VDAxOjAyOjE3WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMjAtMDctMjFUMDA6Mzk6MjJaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjIiPjIwMjAtMDctMjJUMDA6MDY6MjlaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IkF2YWlsYWJsZSIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxOS0wMjwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iUHJlcHJpbnQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8dmVyc2lvbj4yPC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9hcnhpdi5vcmcvbGljZW5zZXMvbm9uZXhjbHVzaXZlLWRpc3RyaWIvMS4wLyI+YXJYaXYub3JnIHBlcnBldHVhbCwgbm9uLWV4Y2x1c2l2ZSBsaWNlbnNlPC9yaWdodHM+CiAgPC9yaWdodHNMaXN0PgogIDxkZXNjcmlwdGlvbnM+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJBYnN0cmFjdCI+SW4gdGhpcyBwYXBlciwgd2Ugc2hvdyBhIHRpZ2h0IGFwcHJveGltYXRpb24gZ3VhcmFudGVlIGZvciBidWRnZXQtZmVhc2libGUgbWVjaGFuaXNtcyB3aXRoIGFuIGFkZGl0aXZlIGJ1eWVyLiBXZSBwcm9wb3NlIGEgbmV3IHNpbXBsZSByYW5kb21pemVkIG1lY2hhbmlzbSB3aXRoIGFwcHJveGltYXRpb24gcmF0aW8gb2YgJDIkLCBpbXByb3ZpbmcgdGhlIHByZXZpb3VzIGJlc3Qga25vd24gcmVzdWx0IG9mICQzJC4gT3VyIGJvdW5kIGlzIHRpZ2h0IHdpdGggcmVzcGVjdCB0byBlaXRoZXIgdGhlIG9wdGltYWwgb2ZmbGluZSBiZW5jaG1hcmssIG9yIGl0cyBmcmFjdGlvbmFsIHJlbGF4YXRpb24uIFdlIGFsc28gcHJlc2VudCBhIHNpbXBsZSBkZXRlcm1pbmlzdGljIG1lY2hhbmlzbSB3aXRoIHRoZSB0aWdodCBhcHByb3hpbWF0aW9uIGd1YXJhbnRlZSBvZiAkMyQgYWdhaW5zdCB0aGUgZnJhY3Rpb25hbCBvcHRpbXVtLCBpbXByb3ZpbmcgdGhlIGJlc3Qga25vd24gcmVzdWx0IG9mICQoMisgXHNxcnR7Mn0pJCBmb3IgdGhlIHdlYWtlciBpbnRlZ3JhbCBiZW5jaG1hcmsuPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/1902.04635","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-01T15:24:58.000Z","registered":"2022-03-01T15:24:59.000Z","published":"2019","updated":"2022-03-01T15:24:59.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1902.04635","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}