{"entities":{"Q6542876":{"pageid":14154019,"ns":120,"title":"Item:Q6542876","lastrevid":55962727,"modified":"2026-02-21T13:37:43Z","type":"item","id":"Q6542876","labels":{"en":{"language":"en","value":"Maximize liquid welfare in combinatorial auctions with monotone valuations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7852415"}},"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":"Q6542876$F532801D-879A-4013-B0F7-9CD312119166","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5589039e3be1178aa1043f2074c1f4bf9d0640a1","datavalue":{"value":{"text":"Maximize liquid welfare in combinatorial auctions with monotone valuations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6542876$437DA9E0-57BD-491F-B850-48059B957FA1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02508005c8ed162537ca2082ed1aced01b79f78a","datavalue":{"value":"1542.91094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6542876$B9F8F534-E3B7-4F75-BA1C-EDCE4C5F09E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"334a2cc15abe700b1a26e9b09e05aa3af4fb9edc","datavalue":{"value":{"entity-type":"item","numeric-id":260036,"id":"Q260036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$73BF76F8-C4CB-4363-90CA-5464D0A2314E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e007e31df6adcf14fc0a77c324ab29904c5ad1f3","datavalue":{"value":{"entity-type":"item","numeric-id":839670,"id":"Q839670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$1C96B7B9-70F4-4DBE-9E56-B926DD30CFBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"45e4b32dae280502bacb87463350988422ce91cd","datavalue":{"value":{"entity-type":"item","numeric-id":1987554,"id":"Q1987554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$0BAB15C5-A801-4CD0-BE87-730C7EA784A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc08f1fac83edaa211200f4e64030c099814db53","datavalue":{"value":{"entity-type":"item","numeric-id":421190,"id":"Q421190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$03471966-A0B0-4B2B-A842-DBA36796CDCF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"117d527d19a5eb6d762b048a576de23e5f533691","datavalue":{"value":{"entity-type":"item","numeric-id":2788520,"id":"Q2788520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$58B5B9A1-FC8F-4388-9464-3CD08A1F762E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dd93ea963f5d7735b8cb72a9ce8a903924b81314","datavalue":{"value":{"time":"+2024-05-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6542876$4D9D5EA2-60AB-4A9C-9794-205944991A39","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"196faacfd7ea5b303886263f08300d6ef8593489","datavalue":{"value":"In this article, the authors study a public budget model where the auctioneer knows each bidder's budget. More precisely, the authors concentrate on finding mechanisms that satisfy the following properties: \\N\\begin{itemize}\\N\\item[i)] Universal truthful -- for any fixed outcome made by the random mechanism, reporting their true private information still is a dominant strategy.\\N\\item[ii)] Budget feasible -- the bidder will not pay more than his budget.\\N\\item[iii)] Computationally-efficient -- the mechanism can run in polynomial time.\\N\\end{itemize}\\NA universal truthful, budget feasible and computationally-efficient mechanism for combinatorial auctions with monotone valuations that achieve an \\(O(\\sqrt{mn})\\)-approximation to the maximum liquid welfare in expectation is presented. Approximation ratio of the mechanism is discussed in Section 4.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6542876$96B04C65-45DA-474D-9AD7-950D247DD98E","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":"Q6542876$70CA78CE-4E10-407E-925E-5CA378897B61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e419163fd9b5f210c8c0c28cdb07c2197a2bcac","datavalue":{"value":"91B26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6542876$40DF35B3-1FBB-4C86-84AD-65B1CE95F786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7b5d210ccf30ae4c3a1a1262f928f15988911a0","datavalue":{"value":"91B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6542876$E35BDBB9-82CA-48F3-B80B-55294AB82B1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd2d244d4fdb383f9b651f3eca4545a8df0d666a","datavalue":{"value":"7852415","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6542876$5937F895-A75E-4C5C-B52D-6C9D7FADDE8B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e3f9e28ecacbb8b2eda297bdef8936d2fab711f","datavalue":{"value":"combinatorial auction","type":"string"},"datatype":"string"},"type":"statement","id":"Q6542876$C61D0259-67D1-42E7-8F47-7CFDC8AA855D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f08d6e1f50147cc98d119a70c0de620a4d55f8c5","datavalue":{"value":"truthful","type":"string"},"datatype":"string"},"type":"statement","id":"Q6542876$43ADF649-615F-401D-9248-243EBA4B65DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q6542876$A2859A51-0FDA-4116-B982-D28DBB9F6D7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db66d9c064cea77c83faf4e1f9a940cbf24eb530","datavalue":{"value":"budget feasible","type":"string"},"datatype":"string"},"type":"statement","id":"Q6542876$904C27AF-DE72-4D55-A20F-2CB8A2E5E6D0","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":"Q6542876$257EE245-A728-4423-92BB-45A200B8D67C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"87c7ef676234f724783e722d2ff8a9cf24cc3011","datavalue":{"value":{"entity-type":"item","numeric-id":6147289,"id":"Q6147289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$544158A8-F3B6-41FE-B6BB-C289E0B08A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc7d694323b8890a0a868fd0a270dae647e48cac","datavalue":{"value":{"entity-type":"item","numeric-id":3603458,"id":"Q3603458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$E28F5093-37BA-4281-B75A-3C8707388A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27004bb11c2fbc168efcd9c4d9aa29dbd8186016","datavalue":{"value":{"entity-type":"item","numeric-id":765207,"id":"Q765207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$C7465577-F74E-4167-81FC-622B0B320EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e73cfdeecc602895cb4920351e2d38ea4ebb7b6","datavalue":{"value":{"entity-type":"item","numeric-id":5891931,"id":"Q5891931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$4F4ED2AC-E79E-49AF-8AFF-F263C98CC805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75b7ea3eb3c4f5c4cee896b9a6cfa6e9213f66ce","datavalue":{"value":{"entity-type":"item","numeric-id":3581408,"id":"Q3581408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$EEE6DE7E-4D75-4FFF-8EEF-023DD3726EA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfd25da74b40da7aae24b9c0f5d5e07aac5058f4","datavalue":{"value":{"entity-type":"item","numeric-id":5167758,"id":"Q5167758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$AE385D46-8DA4-4C98-8495-FCAB5F5C69BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9564041f1809c44382fc090c4dc9fb8b9fd3d419","datavalue":{"value":{"entity-type":"item","numeric-id":5919606,"id":"Q5919606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$C2833286-CA76-4496-974E-7F2ED6915FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$C2117D1A-E366-48F6-9274-0FBAC2F083BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0de80cf24c585af9f2e9c814f9c3aa534e748e97","datavalue":{"value":{"entity-type":"item","numeric-id":3167050,"id":"Q3167050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$C6BBE4ED-C395-4234-A4D6-10414BBF1A41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9900c1f4d9b45e4aece638374295b5bba4b55399","datavalue":{"value":{"entity-type":"item","numeric-id":681843,"id":"Q681843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6542876$32B1F824-8350-45E8-9577-5D6709524BF0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"20e88e7c3d6fa3fb870a65614bedcfa92add5e09","datavalue":{"value":"10.1142/S0217595923400109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6542876$486E0826-E0BF-4EF6-8499-E50A8E6BC7F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"512d4e3ebdceedce7bc49e69afd835d4ae7e44b4","datavalue":{"value":{"entity-type":"item","numeric-id":681843,"id":"Q681843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbead3ee6d9badb7282070a24ac81fd6f5d821eb","datavalue":{"value":{"amount":"+0.8393288254737854","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":"Q6542876$5208FD11-F9EE-421E-9894-7055F8E14665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22144cede419653abce66760d5c55b12546597a5","datavalue":{"value":{"entity-type":"item","numeric-id":2692272,"id":"Q2692272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4994869ae76f1c7c8073bb9430f2ff0ebc06da55","datavalue":{"value":{"amount":"+0.8317385315895081","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":"Q6542876$AFA23874-310F-4880-B017-BB6DB7450D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f53b724af739037571b9bdaf1141da34183c52cc","datavalue":{"value":{"entity-type":"item","numeric-id":5167758,"id":"Q5167758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6759f5661e2add3874e3c69f2c39c550146c62b","datavalue":{"value":{"amount":"+0.8224482536315918","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":"Q6542876$DAAF0326-F100-4577-BA17-6E5F35C5E10D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe4ab4934c68fa333dcf6f4fc5e5376ceed5cff4","datavalue":{"value":{"entity-type":"item","numeric-id":3169079,"id":"Q3169079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8f48e521770d8ca426c7a966802e1f266ae1db3","datavalue":{"value":{"amount":"+0.8222010731697083","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":"Q6542876$F828CE21-CD8A-4FBA-A145-DDCE662CE42F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75fa1709faf887ed67d1c8c10b8657985c44c7c","datavalue":{"value":{"entity-type":"item","numeric-id":5419084,"id":"Q5419084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c5f7cbb81d97f52a9655b67c794bce01c766a74","datavalue":{"value":{"amount":"+0.8196470141410828","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":"Q6542876$EF651FF3-93A0-4F60-98AC-598AF22584BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6542876","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6542876"}}}}}