{"entities":{"Q2006772":{"pageid":2017514,"ns":120,"title":"Item:Q2006772","lastrevid":72320145,"modified":"2026-04-14T04:06:03Z","type":"item","id":"Q2006772","labels":{"en":{"language":"en","value":"Simple combinatorial auctions with budget constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7259069"}},"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":"Q2006772$FD0F4BE7-8B21-4513-819C-446072B686AE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"796c51e89295cacb38c521a62b85264464ab4e36","datavalue":{"value":{"text":"Simple combinatorial auctions with budget constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2006772$9BACE567-7EDB-43D2-96E9-469494B6BCE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba8a4c69bf1bc3f4dc1a8116d53b57fcab67f77e","datavalue":{"value":"1459.91067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2006772$FF24B5AC-E035-4470-971C-F2ECE15D6DF3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6405a6224818909e70c5df965fbab6dc95667fdb","datavalue":{"value":{"entity-type":"item","numeric-id":506518,"id":"Q506518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$7E70FDA6-C38D-4CF0-A2A6-9035C64A53BF","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":"Q2006772$4EDD8BF6-354C-49CB-9262-426D76EE99FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0163f8e6677e49732de512ceb92368b6cf6a6ee5","datavalue":{"value":{"time":"+2020-10-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":"Q2006772$3AC56D3C-9FFC-40F7-8112-DCB9A995EF67","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2ab985c458fefc126c985fb867d3aab27985a0d1","datavalue":{"value":"https://arxiv.org/abs/2007.14274","type":"string"},"datatype":"url"},"type":"statement","id":"Q2006772$DC70C8A1-8A7B-4C17-807F-8E385D1CD390","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"faa724ce12ed67d0197800acf6225791abad9d94","datavalue":{"value":"The author studies the efficiency of auctions for the allocation of a set of discrete items to a set of budget-constrained agents with combinatorial preferences over the items, expressed via valuation functions.  The following statement is precisely proved  Lemma 1. Consider a player \\(i\\) with a subadditive valuation function \\(\\nu_i\\) and budget \\(c_i\\). Let \\(S\\) be a set of items, and \\(b_{-i}\\) be the bid matrix containing the bids of the other players \\(l\\neq i\\) for all items. Then, there exists a bid vector \\(y_i = (y_i)_{j\\in [m]}\\) such that the utility of player \\(i\\) when she unilaterally deviates to \\(y_i\\) is \\[ u_i(y_i,b_{-i})\\ge \\min \\{\\nu_i(S), c_i\\}-\\sum_{j\\in S}\\max_{l\\neq i} b_{lj}, \\] if her total payment does not exceed \\(c_i\\). Otherwise, \\[ \\min\\{\\nu_i(S),c_i\\} <\\sum_{j\\in S}\\max_{l\\neq i} b_{lj}. \\] Using this lemma, the author formulates the main result  Theorem 1. The pure liquid price of anarchy of any auction in \\(S\\) with subadditive valuation functions is at most 2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2006772$27C92E41-99CC-43BF-9F53-FC7BFF3B7A23","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":"Q2006772$C45EE719-5E9E-4790-B1FD-42F81D5A6C70","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e419163fd9b5f210c8c0c28cdb07c2197a2bcac","datavalue":{"value":"91B26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2006772$6550CF6A-E28B-4D9E-AEDB-6CAB9A6FC84F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca62a21af48a38588ec817a413b511412dcb3039","datavalue":{"value":"7259069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2006772$995F63ED-4C53-4B37-AD89-1AFE99A99E5B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4df3251f67581b62e09efafd8eda8d116634f699","datavalue":{"value":"combinatorial auctions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2006772$FAEBE3D8-16A1-4E4A-9466-A0365B5EEBCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7006d7e444605bb58ab217fb639621d162ce3126","datavalue":{"value":"budget constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q2006772$5E223820-F70A-4844-A07E-3FD48C485240","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"861bae6a7f0f344d61a65c5b57f1e4c96b2e8ab5","datavalue":{"value":"liquid price of anarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2006772$563CAD66-DC66-43A8-B619-A56A5B12B67B","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":"Q2006772$C5BF2609-D45B-478D-A2C8-EA095409B4AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1861bc2035a4b8ec9e78e561b7c78ac3c73158e1","datavalue":{"value":"W3044780425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2006772$34839853-5027-47E2-8D04-367D6ED9F612","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6164dac3f08fce7e68c215f5c8fa1388866af8f","datavalue":{"value":{"entity-type":"item","numeric-id":3395046,"id":"Q3395046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$CAA84BBB-4A9B-4E74-AA55-DC4B7CC18A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2a51312f5e850f5445e0061b9c4b5012f835441","datavalue":{"value":{"entity-type":"item","numeric-id":681835,"id":"Q681835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$84CC08AD-2296-47BC-B49A-C58EA798B0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d729f0f3bf9aba704519d8768fad6cd0d6ab4204","datavalue":{"value":{"entity-type":"item","numeric-id":5365074,"id":"Q5365074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$97B0241D-2488-471F-AE81-C51F448D31AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b66a1b8cc5ffe2daaa0349433874e54400f49c3","datavalue":{"value":{"entity-type":"item","numeric-id":3524720,"id":"Q3524720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$A240DD81-DDB7-414E-B31D-4D0C5C2D0FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bb9af408a2dc04228692214bad626399b66e431","datavalue":{"value":{"entity-type":"item","numeric-id":5111298,"id":"Q5111298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$BB26139B-E5E1-41FD-A1AE-86468EFF5DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a60a74eaf7b2265d983d13d06866431c4ad4eecd","datavalue":{"value":{"entity-type":"item","numeric-id":506519,"id":"Q506519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$4E2CB011-C2CB-4E49-9CFA-22A1BE42E48B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa50fd7e79c5ffb720c933e30dd3528bf0b70e9","datavalue":{"value":{"entity-type":"item","numeric-id":5895072,"id":"Q5895072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$11E16E34-3DCE-4D93-9B91-F72DC6772B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97b1f1f56d637c09afe4ff2d4568f692ab2fead9","datavalue":{"value":{"entity-type":"item","numeric-id":506522,"id":"Q506522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$CA3437A7-4885-410D-894A-6C3A9D08B007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85443e4b929974ede151da70ca3e4d8d938080ac","datavalue":{"value":{"entity-type":"item","numeric-id":2884560,"id":"Q2884560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$67ACE65A-528C-4A3B-B9BE-448A0C47CCE6","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":"Q2006772$E812F1DC-0420-432E-90E2-D5748983DE72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7866bd6a0050202ed566c43fd1d07c4822d1fdb0","datavalue":{"value":{"entity-type":"item","numeric-id":5419083,"id":"Q5419083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$F4193A42-6399-4C84-97AD-D94AE5647106","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":"Q2006772$36696064-8528-41A8-8D43-4207E8210535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c23d3e51dc0ed9ff652e6f3cad61d1ee7c94cb21","datavalue":{"value":{"entity-type":"item","numeric-id":5495790,"id":"Q5495790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$D043526C-CC61-44EB-AB05-3B72275E17A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a471ee94d7fc18cf84925669d4e710c60e0fd7b","datavalue":{"value":{"entity-type":"item","numeric-id":5363025,"id":"Q5363025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$E817A975-C0D8-4890-A93C-27D9175D9ACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7c5d2860ccfcc3ea9f9d696db75bb4de37d436","datavalue":{"value":{"entity-type":"item","numeric-id":4070951,"id":"Q4070951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$EE895518-BFBF-4C33-9E0F-69C7736E60EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"526d87677216558427ad485e325965315f8b3fb7","datavalue":{"value":{"entity-type":"item","numeric-id":3409969,"id":"Q3409969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$AC25E337-D21D-4D47-8E1E-F8D3CACBA0DB","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":"Q2006772$78580393-25C3-446F-BC50-155C74172F82","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":"Q2006772$F4D4624F-5BB3-4995-B76C-2807ED5677B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e14ee59c2bfd9ade2f440213bee906e743124bd","datavalue":{"value":{"entity-type":"item","numeric-id":5346024,"id":"Q5346024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$9D6CE2EC-92AE-4D4B-BBC3-10FB0EA510C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"835e22b03e66c1a534105c31e79a454e4c4e354d","datavalue":{"value":{"entity-type":"item","numeric-id":5495791,"id":"Q5495791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$F16CB73C-E9E4-4A61-B88B-AD8EBA4B0E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e51ca4ac3251c36d0259ce484737c86f7752da1","datavalue":{"value":{"entity-type":"item","numeric-id":1711420,"id":"Q1711420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2006772$E21F819C-6AB2-4844-BACC-32E20F398BA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c348202c5b66c50cd78851f416c7cce62509b580","datavalue":{"value":"10.1016/J.TCS.2020.07.019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2006772$080E6B8D-F0B8-4C6A-996F-03233297C1B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f1703e55903d9b05b1b4ca8e0c878ef1ba4f857","datavalue":{"value":{"entity-type":"item","numeric-id":681835,"id":"Q681835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a97211ece8fe71b92bfad44ac35b16042587fd75","datavalue":{"value":{"amount":"+0.8630587458610535","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":"Q2006772$EC668513-2859-4AD2-87A7-BC805CE821A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfa9bb427a48cd739d6f81465874f272c9edf1fb","datavalue":{"value":{"entity-type":"item","numeric-id":5495790,"id":"Q5495790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f966116b6cbcc37b3da6792a96702b1bec7d8de","datavalue":{"value":{"amount":"+0.8547956943511963","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":"Q2006772$8AD675F2-664E-4C8A-BC30-6F34CD2565AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cea4e633cfbe6b8eec420cf107bd475d7ae93ec","datavalue":{"value":{"entity-type":"item","numeric-id":2318114,"id":"Q2318114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"629bae2ffaaa563c9d109eacbf5cc78a202b8e84","datavalue":{"value":{"amount":"+0.8523032665252686","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":"Q2006772$7A0CC5A0-7179-495C-8F3F-6EA85AA176C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d4c512f25b5b874347c350aae2d57437042d32c","datavalue":{"value":{"entity-type":"item","numeric-id":5315397,"id":"Q5315397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d4f9a2651ed92101c7a5a44b141936c8469b81d","datavalue":{"value":{"amount":"+0.8497291803359985","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":"Q2006772$35C93E19-45B1-4078-8965-0453D1D113B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bb4a4941d1502287db235552d191c7b21938df8","datavalue":{"value":{"entity-type":"item","numeric-id":2822037,"id":"Q2822037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60cde6c09eb0318b90b576c194847f61a01b9136","datavalue":{"value":{"amount":"+0.8472319841384888","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":"Q2006772$B5122384-E5C4-44DF-98B0-983ABC2C18B3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Simple combinatorial auctions with budget constraints","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Simple_combinatorial_auctions_with_budget_constraints"}}}}}