Yoram Bachrach, Rahul Savani, and Nisarg Shah
Procuring multiple agents with different ability levels to independently solve the same task is common in labor markets, crowdsourcing environments and research and development
projects due to two reasons: some agents may fail to provide a satisfactory solution, and the redundancy increases the quality of the best solution found. However, incentivizing
large number of agents to compete for one task is difficult; agents need fair ex-ante guaranteed payoffs that consider their ability levels and failure rates to exert efforts.
We model such domains as a cooperative game called the Max-Game, where each agent has a weight representing its ability level, and the value of an agent coalition is the maximal
weight of the agents in the coalition. When agents may fail, we redefine the value of a coalition as the expected maximal weight of its surviving members. We analyze the core, the Shapley value, and the Banzhaf index as methods of payoff division. Surprisingly, the latter two, which are usually computationally hard, can be computed in polynomial
time. Finally, we initiate the study of a new form of sabotage where agents may be incentivized to influence the failure probabilities of their peers, and show that no such
incentive is present in a restricted case of Max-Games.