{"entities":{"Q6971745":{"pageid":21333525,"ns":120,"title":"Item:Q6971745","lastrevid":76196958,"modified":"2026-04-23T05:03:36Z","type":"item","id":"Q6971745","labels":{"en":{"language":"en","value":"Approximation algorithm and mechanism design for bisubmodular welfare maximization problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8052657"}},"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":"Q6971745$B09B4300-FBA9-41AF-A85F-C9FA3B94B311","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82446c96b6c6c84c099476fbecbbc71cb39a1896","datavalue":{"value":{"text":"Approximation algorithm and mechanism design for bisubmodular welfare maximization problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6971745$7BF7DAD7-453B-48CD-8D3C-FD2575A6B07F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c7c0995942c845a9c3d0d8bd6624f0b5b9173348","datavalue":{"value":"1567.91173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971745$CC7C9E52-735E-475C-95A7-683BE5873BFC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b65368fcee6f96ca8b4f9803ea7d18a399ef59f","datavalue":{"value":"10.1016/J.TCS.2025.115302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971745$6B069E12-5713-4E0B-886F-337912CECB44","rank":"normal"}],"P16":[{"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":"Q6971745$169F0226-9B1A-4CF3-9258-A7751F7917DA","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":"Q6971745$F8592ACC-011C-465D-AA06-1DA9B04F7B05","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":"Q6971745$CD8263A7-589A-4498-8C8A-C9182BC68A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"383155c97f8ef6c7036eec4781dc5058653c1200","datavalue":{"value":{"entity-type":"item","numeric-id":201372,"id":"Q201372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$A601690A-25F0-44BC-96E7-AD3765953DA4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$907F7006-E8B5-4D32-BB15-B7F8ABC8DD52","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"752cbd85e48c29097ef77f01360fb6a232ac8d6d","datavalue":{"value":{"time":"+2025-06-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6971745$25E229F7-144C-434B-AA77-C585A44E4184","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8dc4b42810a69ef737abe6dba1249b8bf608bdd0","datavalue":{"value":"This paper focuses on studying auctions with two-dimensional demand, specifically, buyers have bisubmodular valuations, which have not been explored in previous researchers. Focusing on welfare maximization for efficiency, the authors present a simple greedy algorithm that produces an allocation achieving a 2-approximation when buyers' valuations are public. Furthermore, the authors propose a dominant-strategy incentive compatible (DSIC) mechanism that outputs an allocation achieving an \\(O(\\sqrt{m})\\)-approximation when buyers' valuations are private. The algorithm for the bisubmodular welfare maximization is presented in Section 3. The dominant-strategy incentive compatible mechanism is given in Section 4.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971745$DAE4BD9A-6220-4953-AD28-8C4A8512E5FE","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":"Q6971745$4A2C8F11-3489-4668-96EF-12C2ECC9B752","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e419163fd9b5f210c8c0c28cdb07c2197a2bcac","datavalue":{"value":"91B26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971745$D91B4919-928D-4163-857F-CE8FA7A2D307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a2c83f3ed548bfb0bd3d5bad2cfe44028fdf3d4d","datavalue":{"value":"91B03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971745$6856C48C-0E85-4806-8AAC-DF00A43E7C0D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"54631bae0c6168b81548c0c3f9fa042fa5bf298a","datavalue":{"value":"8052657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6971745$A0BF19E3-1252-4117-9BCD-5778452D8A30","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e3f9e28ecacbb8b2eda297bdef8936d2fab711f","datavalue":{"value":"combinatorial auction","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971745$4C1AFB45-D57F-46C3-B7F3-D88D224B5771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4d86a165bf5e4b0ece7c90864bf7a3ef06c46a7","datavalue":{"value":"welfare maximization","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971745$B64B8041-4F62-48DE-A059-2C4A34C3C1BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f433a279eda99c83a4c2fb8a0d97eb1b8c691bd4","datavalue":{"value":"bisubmodular","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971745$089F489D-69AE-4E18-87C2-C8BFBE9A8BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971745$C6A1905C-CD3A-453E-BC78-9147819C8DE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d519162980da134dd91ce5a5c160b3b85930a8d","datavalue":{"value":"mechanism","type":"string"},"datatype":"string"},"type":"statement","id":"Q6971745$067675C8-A8B4-4D45-B735-37C051E2D9BD","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":"Q6971745$802F9327-3550-49AC-906A-243A17631F75","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithm and mechanism design for bisubmodular welfare maximization problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithm_and_mechanism_design_for_bisubmodular_welfare_maximization_problem"}}}}}