{"entities":{"Q6971745":{"pageid":21333525,"ns":120,"title":"Item:Q6971745","lastrevid":84045224,"modified":"2026-05-08T17:39:45Z","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"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a662b634ed87551bfdcdd5a4549263cb1fc10290","datavalue":{"value":{"entity-type":"item","numeric-id":1910557,"id":"Q1910557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$30CC3304-38F2-48FC-B983-DCABCA6E743A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53645eb5b36ac37889ac7c00b5207ed0579850a5","datavalue":{"value":{"entity-type":"item","numeric-id":6829698,"id":"Q6829698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$FF8E3ADA-E615-4DC4-8616-A0F3D40A51E8","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":"Q6971745$B35B29E6-F5F2-4941-B8EC-C8815B4003F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dedd49bf756395672770d61359060a436b7d5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3169079,"id":"Q3169079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$7EF9A1FC-B5AF-4551-9963-37146A64C2D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0b4635995c76e09be71fb3f76b65bb20a5e63df","datavalue":{"value":{"entity-type":"item","numeric-id":5891528,"id":"Q5891528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$FA643473-B3E6-4FC4-B907-AA81217CA203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b80a48c2b9ce4c68613bcedd51f2df82a979a0d","datavalue":{"value":{"entity-type":"item","numeric-id":3581517,"id":"Q3581517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$EB6D4A85-9AAC-4476-9036-9FDBA77D1747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$7D7F7143-5813-4590-A651-03D426F7DE0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09c8325103d5389cff120712c05743b4061fda10","datavalue":{"value":{"entity-type":"item","numeric-id":943868,"id":"Q943868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$70E49E95-A553-4A3F-9516-FA0429EB5A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5df05bc83b5f828f91d2699677c5b7ac22445b4","datavalue":{"value":{"entity-type":"item","numeric-id":2396159,"id":"Q2396159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$8C33C214-47B9-4A4B-BE73-DA83F677C6E3","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":"Q6971745$BD4C8B09-AC74-419B-960B-02199712F47C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cccc2942d8bcf41fd5d4822d4565bcac913cdec","datavalue":{"value":{"entity-type":"item","numeric-id":2506310,"id":"Q2506310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$9D524422-BB84-4339-AF01-9BDA3DBC6FCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b261824350a68192c75098b1568d5ab23afd7c67","datavalue":{"value":{"entity-type":"item","numeric-id":5168718,"id":"Q5168718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$226E5ABB-3B9C-441D-8FFB-29EC8C321594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beda1f46b41a49a2e9f8eaca1a93254a3b220d3e","datavalue":{"value":{"entity-type":"item","numeric-id":1116891,"id":"Q1116891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$C753523C-3A52-404A-AB69-3FBA73D9D922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"617c1b944f799532e45efce36ce8324481b7dfc3","datavalue":{"value":{"entity-type":"item","numeric-id":2784019,"id":"Q2784019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6971745$7D67F784-C026-49D0-A01A-83D44197BA60","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"}}}}}