{"entities":{"Q2670904":{"pageid":2681647,"ns":120,"title":"Item:Q2670904","lastrevid":57992058,"modified":"2026-04-03T09:10:03Z","type":"item","id":"Q2670904","labels":{"en":{"language":"en","value":"Auctions with interdependence and SOS: improved approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7535982"}},"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":"Q2670904$B48CB041-E0EB-4A36-BDC2-9768FB313054","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bbe641ee117e9b494ba80c24f77e1c490bc65e0e","datavalue":{"value":{"text":"Auctions with interdependence and SOS: improved approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2670904$5F584EAB-118F-4A8B-A458-7B8F70BB162C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61e4162b085367a9c2ad15735fa078f816425cc7","datavalue":{"value":"1498.91201","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2670904$616773D4-0989-4EC6-B809-F8F76E631B0C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"218d69f676459a859fbc9d4dbdc527541dd8c66c","datavalue":{"value":"10.1007/978-3-030-85947-3_3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2670904$F721A7CC-137A-437E-AEC5-1DD108C98C4E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"557b43c50f88759d7f9549ba1627918ca275da7f","datavalue":{"value":{"entity-type":"item","numeric-id":2670903,"id":"Q2670903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$AA9DA107-7AEA-44E2-AD46-CF0A5AC65B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e84cfc6389be4c77414b1df6ad40e04d26ea853b","datavalue":{"value":{"entity-type":"item","numeric-id":506529,"id":"Q506529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$A0A90E81-3968-4140-87BE-E07986CF2F03","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cb692f3299cf1c6e4f6dd07056e2a0cdf9e7c22a","datavalue":{"value":{"time":"+2022-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2670904$AC868217-F8C2-4E98-9113-B4F6DDA7EDBB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"906a55043c1515ecf49cb3ca18709c360abf3697","datavalue":{"value":"https://arxiv.org/abs/2107.08806","type":"string"},"datatype":"url"},"type":"statement","id":"Q2670904$699C355E-07DB-4490-A40B-9809E833BAD9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1c800f2662f26e0705465da9690a4aea1dc22ce9","datavalue":{"value":"The authors announce the existence of an ex post incentive compatible, individually rational randomized mechanism which achieves a tight 2-approximation to the optimal welfare in single-item auctions if bidders' valuation functions are submodular over their binary signals. This relates to results announced by \\textit{A. Eden} et al. [``Combinatorial auctions with interdependent valuations: SOS to the rescue'', in: Proceedings of the 20th ACM Conference on Economics and Computation, EC'19. New York, NY: Association Computing Machinery. 19--20 (2019; \\url{doi:10.1145/3328526.3329759})] where a 4-approximation to the optimal welfare is announced in a more general setting, and it is also stated that no truthful mechanism can achieve a better approximation factor than 2.  The authors consider single-item auctions with \\(n\\) bidders. The private information about the item of bidder \\(i\\) is a binary signal \\(s_{i} \\in \\{0, 1\\}\\). A signal profile \\(s = (s_1, \\dots , s_n)\\) is identified with its corresponding set \\(S = \\{i | s_i = 1\\}\\).  The valuation function of bidder \\(i\\) is a non-negative function of all bidders' signals \\(v_i = v_i(s_1, \\dots , s_n) \\geq 0\\). The valuation functions \\(v_i\\) are weakly increasing in each coordinate, strongly increasing in \\(s_i\\), and submodular: for every \\(S, T \\subseteq \\{1,\\dots,n\\}\\) with \\(S \\subseteq T\\) and \\(i \\in \\{1,\\dots,n\\}\\setminus T\\) it holds that  \\[ v_i(S \\cup \\{i\\}) - v_i(S) \\geq v_i(T \\cup \\{i\\}) - v_i(T). \\] While the signal \\(s_i\\) is known only to bidder \\(i\\), the valuation functions \\(v_1,\\dots,v_n\\) are publicly known.  A randomized mechanism \\(M = (x, p)\\) for interdependent values is a pair of allocation rule \\(x= (x_1, \\dots, x_n)\\geq 0\\) and payment rule \\(p= (p_1, \\dots, p_n)\\). The mechanism solicits signal reports from the bidders, and maps a reported signal profile \\(s\\) to \\(x\\) and \\(p\\) such that \\(\\sum_{i=1}^{n}x_i(s) \\leq 1\\). \\(M\\) is ex post incentive compatible (IC) and individually rational (IR) if for every bidder \\(i\\), true signal profile \\(s\\) and reported signal \\(s'_i\\),  \\[ x_i(s_1,\\dots, s_{i-1},s_{i}',s_{i+1},\\dots,s_n)\\cdot v_{i}(s)-p(s_1,\\dots, s_{i-1},s_{i}',s_{i+1},\\dots,s_n)\\geq 0 \\] and is maximized by \\(s_{i}'=s_{i}\\); that is, expected utility is non-negative and maximized by truthfully reporting.  The mechanism \\(M\\) achieves a \\(c\\)-approximation to the optimal welfare for a given setting if for every signal profile \\(s\\),  \\[ \\sum_{i=1}^{n}x_{i}(s)\\cdot v_{i}(s) \\geq c \\cdot \\max_{i}v_{i}(s). \\] The authors announce the result that for every single-item auction with \\(n\\) bidders, binary signals, and valuations as above, there exists an ex post IC-IR mechanism that achieves a 2-approximation to the optimal welfare. The proof of this result is constructive: an algorithm is designed which gets as input the valuation functions \\(v_1, \\dots , v_n\\), and outputs an allocation rule \\(x\\). The mechanism is randomized but uses only the \\(0\\) and \\(1/2\\) allocation probabilities.  The authors extend their result to a matroid auction setting and state that if there exists a monotone feasible allocation rule that achieves a 2-approximation to the optimal welfare for single item auctions then there exists such an allocation rule for the matroid auction setting, as well.  For the entire collection see [Zbl 1487.91002].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$DF816139-029B-41D3-8D0E-DF4A10E31971","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f90841066c0eea3979703fe8132637ed0fffebc1","datavalue":{"value":{"entity-type":"item","numeric-id":375849,"id":"Q375849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$11899A6E-DF12-4077-82F4-B891A78EE5BC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e419163fd9b5f210c8c0c28cdb07c2197a2bcac","datavalue":{"value":"91B26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2670904$3ECE54F7-4E68-4C69-81DC-A1E9A17927D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a2c83f3ed548bfb0bd3d5bad2cfe44028fdf3d4d","datavalue":{"value":"91B03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2670904$5DDEC3B5-3AD7-45C9-AA5F-C3DF4FB770FF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c38fcad5e1a92ee44efbac3ad7ab2fb6aa34d4e","datavalue":{"value":"7535982","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2670904$D485A0F7-640E-4A79-A5E9-A5E33801264A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ea97f47b227be64026eb978d7dd8bf971939953","datavalue":{"value":"randomized mechanism design for interdependent values","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$E16E2FFC-9412-4D6B-A456-EDA75ACD424F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be72d4668c549fb37838ba37fe3e0a7b13ec0d79","datavalue":{"value":"binary signals","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$2340CA21-F619-4F6C-8AFC-CEA1F3AC2901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03760b744aac67c571b6e93c88a7904848e0f938","datavalue":{"value":"ex post incentive compatible and individually rational mechanism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$12911DFD-EF6C-4C01-873D-61B7435EC1CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"584dc002da04d312edc120b34b96ea905950150a","datavalue":{"value":"submodular valuation function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$1429B036-CE35-4F94-A217-F0FEB82427F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4d86a165bf5e4b0ece7c90864bf7a3ef06c46a7","datavalue":{"value":"welfare maximization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$1DD0FFAA-D026-4255-986A-E6503862253C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d27341a1813190ca34b316ee581869eb0fabc407","datavalue":{"value":"2-approximation to optimal welfare","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$DF51E2C0-550D-4968-A068-847D2B7F0984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9201d7b83644a1fd7305164f5bf02b01eb745c83","datavalue":{"value":"matroid auction setting","type":"string"},"datatype":"string"},"type":"statement","id":"Q2670904$8B299545-8DC9-4079-B0EB-07E68D768865","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":"Q2670904$1DA12497-816B-4BFF-9FAE-6D6C83760633","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a4f28df063861f063fa1f2240335bf81cb6802bd","datavalue":{"value":"W3203145828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2670904$F9A3CA93-6739-4815-844F-5EE31429C7E7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"60756852c5813c4f31c6909cbf7ab7a180ef3848","datavalue":{"value":{"entity-type":"item","numeric-id":4495443,"id":"Q4495443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$EE4524AD-838A-470F-802A-CABD076F1585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6029be0a00c571e8209349bd51e4da3f3e7a24b1","datavalue":{"value":{"entity-type":"item","numeric-id":2670908,"id":"Q2670908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$6E220335-4095-48B1-8464-92B2FC38802B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bca7aa9fc4198715ef619981ec2d50e560dd615f","datavalue":{"value":{"entity-type":"item","numeric-id":4531033,"id":"Q4531033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$51DDB03F-8E12-41AD-BF6F-EB3D73322DBE","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":"Q2670904$37C94BFA-44DA-48CE-9FB7-86B180A48287","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4798568f26fd96c7ed65552767ccdd6970c61024","datavalue":{"value":{"entity-type":"item","numeric-id":2357821,"id":"Q2357821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$7741AE99-FD8B-47CA-81CA-83D99A20FCE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3f0a422a973703fa59963b754c64525e4a4b3d6","datavalue":{"value":{"entity-type":"item","numeric-id":3948830,"id":"Q3948830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$E2342D2F-9FE1-4253-916D-C399F31C29D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce1c9b0bd7268ee1a99c377b06d6db7f2cade491","datavalue":{"value":{"entity-type":"item","numeric-id":4969210,"id":"Q4969210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$FD872E3D-7BFE-42DD-B20A-06890C9FDE3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d683fb2836ef8e0f33b304608f2624c55a5cf0b0","datavalue":{"value":{"entity-type":"item","numeric-id":5484515,"id":"Q5484515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$186B2976-A5A8-4EFF-B615-839588540AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c5ae70ab8e506724531a484f93bdbb072c2536","datavalue":{"value":{"entity-type":"item","numeric-id":4152301,"id":"Q4152301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2670904$40AC5356-272B-48E9-AADB-EF33BDD5BE62","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2db667518dfcf99d192ea2662e6a50d519c5a9b8","datavalue":{"value":{"entity-type":"item","numeric-id":5895072,"id":"Q5895072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3f36573cefbfb066790f06e0232826ebd1bbecd","datavalue":{"value":{"amount":"+0.8280880451202393","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":"Q2670904$E4672518-8F5A-43C0-A64F-9D9A99C4B575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b27465be806745f16cffc6ede8adaea4ba02daa0","datavalue":{"value":{"entity-type":"item","numeric-id":2357821,"id":"Q2357821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99bdcf3518b7c3257164db5e3226336cb3ec1c91","datavalue":{"value":{"amount":"+0.8231801390647888","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":"Q2670904$A8B55A86-E595-4CB9-90D4-95B201AF2A75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cb35a37c847ca572e66f97761c1f554f5781170","datavalue":{"value":{"entity-type":"item","numeric-id":5900245,"id":"Q5900245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eff3486dd8c638d00853eceae857c66f51be7dba","datavalue":{"value":{"amount":"+0.8166183233261108","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":"Q2670904$18D948C0-A9DC-4367-806E-A3D5140E4238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c8c7074cd9529ef048c60b933749720aad9672f","datavalue":{"value":{"entity-type":"item","numeric-id":5495028,"id":"Q5495028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"606da1131f006af7b1d8a5db0cd5eaf265dad249","datavalue":{"value":{"amount":"+0.8084121942520142","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":"Q2670904$ADAC7DA9-BEA6-4133-AA63-B47AE687EE72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bed71fbcd285191b17c1ac4d1282e3638848ddb7","datavalue":{"value":{"entity-type":"item","numeric-id":2516249,"id":"Q2516249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30758230afbf9967856a424da7d4b80713acd1c2","datavalue":{"value":{"amount":"+0.8048781752586365","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":"Q2670904$F88802DC-BCD4-42E7-BA2C-5F643E0CA014","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2670904","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2670904"}}}}}