Single-minded agent explained

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.

Notes and References

1. Book: Devanur. Nikhil R.. Goldner. Kira. Saxena. Raghuvansh R.. Schvartzman. Ariel. Weinberg. S. Matthew. Proceedings of the 21st ACM Conference on Economics and Computation . Optimal Mechanism Design for Single-Minded Agents . 2020-07-13. https://doi.org/10.1145/3391403.3399454. EC '20. Virtual Event, Hungary. Association for Computing Machinery. 193–256. 10.1145/3391403.3399454. 978-1-4503-7975-5. 2002.06329. 211132939 .
2. Aziz. Haris. 2019-12-04. Strategyproof multi-item exchange under single-minded dichotomous preferences. Autonomous Agents and Multi-Agent Systems. en. 34. 1. 3. 10.1007/s10458-019-09426-w. 1573-7454. 1905.10778. 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. 1602.09088 . 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. 10.1080/15427951.2004.10129086. 1542-7951. free.
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. 10.1016/j.jcss.2004.04.012. 0022-0000. free.
6. Book: De Keijzer. Bart. Kyropoulou. Maria. Ventre. Carmine. 2020-06-29. Obviously Strategyproof Single-Minded Combinatorial Auctions. en. Saarbrücken, Germany [online]. Schloss Dagstuhl--Leibniz-Zentrum. 10.4230/LIPIcs.ICALP.2020.71. free . 978-3-95977-138-2.
7. Book: 23 January 2005. On profit-maximizing envy-free pricing Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. 2020-01-16. dl.acm.org. 1164–1173. Society for Industrial and Applied Mathematics. EN. 9780898715859.
8. Book: Cheung. M.. Swamy. C.. 2008 49th Annual IEEE Symposium on Foundations of Computer Science . Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply . 2008-10-01. https://ieeexplore.ieee.org/document/4690938. 35–44. 10.1109/FOCS.2008.15. 978-0-7695-3436-7. 1318192 .