Single-minded agent

Last updated

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:

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

  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.
  7. ↑ "On profit-maximizing envy-free pricing". Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics. 23 January 2005. pp. 1164–1173. ISBN   9780898715859 . Retrieved 2020-01-16– via dl.acm.org.
  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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.