{"entities":{"Q6635693":{"pageid":14246845,"ns":120,"title":"Item:Q6635693","lastrevid":57268587,"modified":"2026-03-27T18:17:10Z","type":"item","id":"Q6635693","labels":{"en":{"language":"en","value":"Near-optimal auctions on independence systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7941436"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$E596C25C-9231-41AD-80F9-F8504526D153","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b6a755166a47722e15073efdeb8aab7ee67a47df","datavalue":{"value":{"text":"Near-optimal auctions on independence systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6635693$2CF82F17-1A8F-4BCD-A159-198168B0C912","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bdeb0a00d3dd6a1dfbc705cd71eaba8c41e8b1f","datavalue":{"value":{"entity-type":"item","numeric-id":6635692,"id":"Q6635692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$1F8652A7-91E7-49B3-9F61-2B2D61AAB799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97176829823cbc57502f66429fca999aeb2491bb","datavalue":{"value":{"entity-type":"item","numeric-id":993507,"id":"Q993507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$11805CC3-6F49-440C-A99B-E7BB6CCDE4F3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$D5B70520-78BA-4F35-B08F-6DCA16127AC5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"60fa3f87d97ee0a9686c2e5537009cd3455d3ea2","datavalue":{"value":{"time":"+2024-11-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6635693$0C4BC7C9-CBC8-4F68-A027-08EECE421560","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a2cd060b3b4abd0d54ba5389cbf6a6be60611640","datavalue":{"value":"It is known that the classical result by \\textit{R. B. Myerson} [Math. Oper. Res. 6, 58--73 (1981; Zbl 0496.90099)] gives a characterization of an optimal auction for any given distribution of valuations of the bidders. In this paper, the authors consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. They prove a new bound for the case of independence systems that widely generalizes matroids and contains several important combinatorial optimization problems. More precisely, the bound of \\(O\\left (\\frac{H^2n^4}{\\epsilon ^3}\\right )\\) (\\(n\\) is the number of bidders, \\(\\epsilon\\) the error and \\(H\\) the maximal valuation) falls neatly between those known for the general and the matroid case. The class of independence systems contains several well-known NP-hard problems such as knapsack. In a second result the authors show that an approximation algorithm can be used without compromising the sample complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6635693$485F46FB-4BC1-433B-B153-87623E900B1A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"282e74ca777db233b8363bf429f8526f530a428c","datavalue":{"value":{"entity-type":"item","numeric-id":282183,"id":"Q282183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$46FC79F1-38E0-4575-95A7-62938208982D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e419163fd9b5f210c8c0c28cdb07c2197a2bcac","datavalue":{"value":"91B26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6635693$AF08FD24-39E3-4B68-9EBD-A9AFB0E5668F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a2c83f3ed548bfb0bd3d5bad2cfe44028fdf3d4d","datavalue":{"value":"91B03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6635693$84A1906F-6C6E-4696-AA2E-ADA77D3A3DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6635693$7C1A65C2-06EA-4805-B4A7-860F704633FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6635693$46DF44DA-6C18-4F8D-9D82-F99C410C9310","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"629a846e153032924bd4fdf4a6020a90f52b8b5d","datavalue":{"value":"7941436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6635693$678C19F6-4AD5-4BA4-A457-2113A1ABD9CB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22719d900354c189744a42d05640a22d54ea8c17","datavalue":{"value":"mechanism design","type":"string"},"datatype":"string"},"type":"statement","id":"Q6635693$5DD0424A-F4FE-4357-8B81-FAA3DDD27593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0afe30fcd4cd25e8e8273c02ad48a97b4a0e001","datavalue":{"value":"machine learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q6635693$4F1EE910-3E5E-4CE6-9796-B3E879F86C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q6635693$4E37D7A8-0320-4A34-AAB8-86DC4881CBB3","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$1601C2D0-7474-47C8-87C2-7C7CEB4E5595","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a157df0c037c05a3ad31d788b5861e53b330e6dd","datavalue":{"value":{"entity-type":"item","numeric-id":3960505,"id":"Q3960505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$043C08EB-175A-474E-A264-52BF906432F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d0fd0b86b7b89d5c0b7f41ee73b23025ed04e9c","datavalue":{"value":{"entity-type":"item","numeric-id":5361849,"id":"Q5361849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$55E4FFE7-A021-4141-BBAC-2C9952E6CE88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a698e9356d9765b54316277f88768c4c9a19847","datavalue":{"value":{"entity-type":"item","numeric-id":4978029,"id":"Q4978029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$BCCED95F-18FF-4C9F-A9E2-B521D0B7865D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0505671b7fe37660594d2c0550778801f886455","datavalue":{"value":{"entity-type":"item","numeric-id":5259558,"id":"Q5259558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$FD71C590-D717-4A01-8DE4-945617AF9CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41eddd77b177b39bc3492905476aaae1c9e6c90f","datavalue":{"value":{"entity-type":"item","numeric-id":2934660,"id":"Q2934660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$1D217B31-0168-4739-84D9-D3168B8C5564","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df6b7b90565bb8f9969ee1c6e57f73b81f04e18d","datavalue":{"value":{"entity-type":"item","numeric-id":5212807,"id":"Q5212807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$C4985204-5246-4282-8F69-8468A1252B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8090b63ceecd18d360b529e1fad472ea65e8770","datavalue":{"value":{"entity-type":"item","numeric-id":2875157,"id":"Q2875157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$E1E0EE46-EA11-4079-83E7-EF061CC4598C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64c70480d1e1800573a0a08c506cef7987427635","datavalue":{"value":{"entity-type":"item","numeric-id":5432685,"id":"Q5432685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$C47DD7EC-3104-40F0-B36C-17455F0F0239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06edd208e2f90af90985f66881fff608b3aca017","datavalue":{"value":{"entity-type":"item","numeric-id":5494386,"id":"Q5494386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$6A07644E-0A7E-46A6-B093-7CF8AEA2F2D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65b399b3d625189fc082ad91edb5068a05e988bd","datavalue":{"value":{"entity-type":"item","numeric-id":4951814,"id":"Q4951814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$707F9824-2805-48D7-AFE3-71EA2A77616C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85ca919e1e18b80b55db3648e22f4d14adcc6637","datavalue":{"value":"10.1007/S00224-024-10189-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6635693$28114F78-7BEB-4F5E-ABCE-8348349F7B53","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6c13592fae33a9ff4309fa49d4d862a5fac18df","datavalue":{"value":{"entity-type":"item","numeric-id":5419081,"id":"Q5419081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ddfd364e1f5dbf87b0d9785f431291159cb8f66e","datavalue":{"value":{"amount":"+0.8068020343780518","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6635693$2F228D0C-9BDE-4207-B7C9-03A4AD85078D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4848c275168685e0b620b0110e085062c00ab341","datavalue":{"value":{"entity-type":"item","numeric-id":5259558,"id":"Q5259558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89bbe83e7fdfafd59d864d899e1eefe003672b57","datavalue":{"value":{"amount":"+0.8058104515075684","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6635693$68C4FE44-C7C2-46B0-AAB8-BA0C35C15350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baf65045381548f338881bbd71ccc97c43c5d17b","datavalue":{"value":{"entity-type":"item","numeric-id":5384058,"id":"Q5384058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e144cfefeb9497f5e3283bfd540bec1bfc0b573f","datavalue":{"value":{"amount":"+0.7978015542030334","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6635693$1567789D-A252-49BE-8D93-32CC388BB45A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0086141a0a7c9e1f77d775345d0619e2f53c6fd","datavalue":{"value":{"entity-type":"item","numeric-id":5741749,"id":"Q5741749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed428b803577647d62b17e0c96b6424db1adb7ae","datavalue":{"value":{"amount":"+0.7941961288452148","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6635693$C1157ACD-640F-4260-8D3C-B30F107DB422","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"219f470b197bb469d331a872e53508b6f11338bc","datavalue":{"value":{"entity-type":"item","numeric-id":2516251,"id":"Q2516251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0d022d15d86f4b9228c7c168dc5e8557729e1ff","datavalue":{"value":{"amount":"+0.7908607125282288","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6635693$17A1C436-FC28-49B1-ACED-44B2A1CCA495","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6635693$FBAF44BE-07CA-4BE0-94BD-78FBAF672FFB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6635693","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6635693"}}}}}