{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T23:40:22Z","timestamp":1699918822960},"reference-count":15,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T00:00:00Z","timestamp":1247788800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider <jats:italic>Effort Games<\/jats:italic>, a game\u2010theoretic model of cooperation in open environments, which is a variant of the principal\u2010agent problem from economic theory. In our multiagent domain, a common project depends on various tasks; carrying out certain subsets of the tasks completes the project successfully, while carrying out other subsets does not. The probability of carrying out a task is higher when the agent in charge of it exerts effort, at a certain cost for that agent. A central authority, called the principal, attempts to incentivize agents to exert effort, but can only reward agents based on the success of the entire project.<\/jats:p><jats:p>We model this domain as a normal form game, where the payoffs for each strategy profile are defined based on the different probabilities of carrying out each task and on the boolean function that defines which task subsets complete the project, and which do not. We view this boolean function as a simple coalitional game, and call this game the underlying coalitional game. We suggest the <jats:italic>Price of Myopia<\/jats:italic> (PoM) as a measure of the influence the model of rationality has on the minimal payments the principal has to make in order to motivate the agents in such a domain to exert effort.<\/jats:p><jats:p>We consider the computational complexity of testing whether exerting effort is a dominant strategy for an agent, and of finding a reward strategy for this domain, using either a <jats:italic>dominant strategy equilibrium<\/jats:italic> or using <jats:italic>iterated elimination of dominated strategies<\/jats:italic>. We show these problems are generally #P\u2010hard, and that they are at least as computationally hard as calculating the Banzhaf power index in the underlying coalitional game. We also show that in a certain restricted domain, where the underlying coalitional game is a weighted voting game with certain properties, it is possible to solve all of the above problems in polynomial time. We give bounds on PoM in weighted voting effort games, and provide simulation results regarding PoM in another restricted class of effort games, namely effort games played over Series\u2010Parallel Graphs (\u00a9 2009 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200810018","type":"journal-article","created":{"date-parts":[[2009,7,18]],"date-time":"2009-07-18T07:49:09Z","timestamp":1247903349000},"page":"377-396","source":"Crossref","is-referenced-by-count":1,"title":["Effort Games and the Price of Myopia"],"prefix":"10.1002","volume":"55","author":[{"given":"Yoram","family":"Bachrach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Zuckerman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey S.","family":"Rosenschein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2009,7,17]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"M.Babaioff M.Feldman andN.Nisan Combinatorial agency. In: ACM EC'06(2006).","DOI":"10.1145\/1134707.1134710"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"Y.Bachrach andJ. S.Rosenschein Computing the Banzhaf power index in network flow games. In: AAMAS'07 pp. 323\u2013329 (Honolulu 2007).","DOI":"10.1145\/1329125.1329433"},{"key":"e_1_2_1_4_2","first-page":"317","article-title":"Weighted voting doesn't work: a mathematical analysis","volume":"19","author":"Banzhaf J. F.","year":"1965","journal-title":"Rutgers Law Review"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"V.Conitzer andT.Sandholm Complexity of (iterated) dominance. In: EC\u20102005 pp. 88\u201397 (2005).","DOI":"10.1145\/1064009.1064019"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.19.2.257"},{"key":"e_1_2_1_7_2","unstructured":"E.Elkind L. A.Goldberg P. W.Goldberg andM.Wooldridge A tractable and expressive class of marginal contribution nets and its applications. In: The International Conference on Autonomous Agents and Multi\u2010Agent Systems (L. Padgham D. C. Parkes J. Muller and S. Parsons eds.) pp. 1007\u20131014 (IFAAMAS 2008)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.3.553"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.2307\/3003457"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(88)90075-2"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00251-6"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"D.Monderer andM.Tennenholtz k\u2010Implementation. In EC '03: Proceedings of the 4th ACM conference on Electronic commerce pp. 19\u201328 (ACM 2003).","DOI":"10.1145\/779928.779931"},{"key":"e_1_2_1_13_2","unstructured":"M. J.Osborne andA.Rubinstein A Course in Game Theory (MIT Press 1999)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"L. S.Shapley A value for n\u2010person games. In: Contributions to the Theory of Games pp. 31\u201340 (1953).","DOI":"10.1017\/CBO9780511528446.003"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.2307\/1951053"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1257\/0002828041464434"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810018","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810018","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200810018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T23:19:02Z","timestamp":1699917542000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200810018"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,17]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1002\/malq.200810018"],"URL":"https:\/\/doi.org\/10.1002\/malq.200810018","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,17]]}}}