Single-minded agent

In computational economics, a single-minded agent is an agent who wants only a very specific combination of items. The valuation function of such an agent assigns a positive value only to a specific set of items, and to all sets that contain it. It assigns a zero value to all other sets. A single-minded agent regards the set of items he wants as purely complementary goods.

Various computational problems related to allocation of items are easier when all the agents are known to be single-minded. For example:

Revenue-maximizing auctions.[1]
Multi-item exchange.[2]
Fair cake-cutting and fair item allocation.[3]
Combinatorial auctions.[4][5][6]
Envy-free pricing.[7][8]

Comparison to other valuation functions

As mentioned above, a single-minded agent regards the goods as purely complementary goods

In contrast, an additive agent assigns a positive value to every item, and assigns to every bundle a value that is the sum of the items in contains. An additive agent regards the set of items he wants as purely independent goods.

In contrast, a unit-demand agent wants only a single item, and assigns to every bundle a value that is the maximum value of an item contained in it. A unit-demand agent regards the items as purely substitute goods.

References

Devanur, Nikhil R.; Goldner, Kira; Saxena, Raghuvansh R.; Schvartzman, Ariel; Weinberg, S. Matthew (2020-07-13). "Optimal Mechanism Design for Single-Minded Agents". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 193–256. arXiv:2002.06329. doi:10.1145/3391403.3399454. ISBN 978-1-4503-7975-5. S2CID 211132939.
Aziz, Haris (2019-12-04). "Strategyproof multi-item exchange under single-minded dichotomous preferences". Autonomous Agents and Multi-Agent Systems. 34 (1): 3. arXiv:1905.10778. doi:10.1007/s10458-019-09426-w. ISSN 1573-7454. S2CID 166228454.
Brânzei, Simina; Lv, Yuezhou; Mehta, Ruta (2016-07-09). "To give or not to give: fair division for single minded valuations". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 123–129. arXiv:1602.09088. ISBN 978-1-57735-770-4.
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva (2004-01-01). "An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents". Internet Mathematics. 1 (2): 129–150. doi:10.1080/15427951.2004.10129086. ISSN 1542-7951.
Chen, Ning; Deng, Xiaotie; Sun, Xiaoming (2004-12-01). "On complexity of single-minded auction". Journal of Computer and System Sciences. 69 (4): 675–687. doi:10.1016/j.jcss.2004.04.012. ISSN 0022-0000.
De Keijzer, Bart; Kyropoulou, Maria; Ventre, Carmine (2020-06-29). Obviously Strategyproof Single-Minded Combinatorial Auctions. Saarbrücken, Germany [online]: Schloss Dagstuhl--Leibniz-Zentrum. doi:10.4230/LIPIcs.ICALP.2020.71. ISBN 978-3-95977-138-2.
On profit-maximizing envy-free pricing | Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. 23 January 2005. pp. 1164–1173. ISBN 9780898715859. Retrieved 2020-01-16. {{cite book}}: |website= ignored (help)
Cheung, M.; Swamy, C. (2008-10-01). "Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 35–44. doi:10.1109/FOCS.2008.15. ISBN 978-0-7695-3436-7. S2CID 1318192.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Devanur, Nikhil R.; Goldner, Kira; Saxena, Raghuvansh R.; Schvartzman, Ariel; Weinberg, S. Matthew (2020-07-13). "Optimal Mechanism Design for Single-Minded Agents". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 193–256. arXiv:2002.06329. doi:10.1145/3391403.3399454. ISBN 978-1-4503-7975-5. S2CID 211132939.

[2] Aziz, Haris (2019-12-04). "Strategyproof multi-item exchange under single-minded dichotomous preferences". Autonomous Agents and Multi-Agent Systems. 34 (1): 3. arXiv:1905.10778. doi:10.1007/s10458-019-09426-w. ISSN 1573-7454. S2CID 166228454.

[3] Brânzei, Simina; Lv, Yuezhou; Mehta, Ruta (2016-07-09). "To give or not to give: fair division for single minded valuations". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 123–129. arXiv:1602.09088. ISBN 978-1-57735-770-4.

[4] Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva (2004-01-01). "An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents". Internet Mathematics. 1 (2): 129–150. doi:10.1080/15427951.2004.10129086. ISSN 1542-7951.

[5] Chen, Ning; Deng, Xiaotie; Sun, Xiaoming (2004-12-01). "On complexity of single-minded auction". Journal of Computer and System Sciences. 69 (4): 675–687. doi:10.1016/j.jcss.2004.04.012. ISSN 0022-0000.

[6] De Keijzer, Bart; Kyropoulou, Maria; Ventre, Carmine (2020-06-29). Obviously Strategyproof Single-Minded Combinatorial Auctions. Saarbrücken, Germany [online]: Schloss Dagstuhl--Leibniz-Zentrum. doi:10.4230/LIPIcs.ICALP.2020.71. ISBN 978-3-95977-138-2.

[:0-7] On profit-maximizing envy-free pricing | Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. 23 January 2005. pp. 1164–1173. ISBN 9780898715859. Retrieved 2020-01-16. {{cite book}}: |website= ignored (help)

[8] Cheung, M.; Swamy, C. (2008-10-01). "Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 35–44. doi:10.1109/FOCS.2008.15. ISBN 978-0-7695-3436-7. S2CID 1318192.