# Utility Distribution Strategy of the Task Agents in Coalition Skill Games
## 1 Introduction  
The coalition skill game is a typical model of task allocation problem for self-interested agents, the studies on which may help provide new thoughts for solving other cooperation problems of self-interested agents. Coalitional skill games were first proposed by [PERSON] et al. [1; 2]. As a restricted form of coalition generating problem, a coalitional skill game model includes three sets: service agent set, skill set, and task agent set. Each service agent and each task agent have their respective skill set, which will ensure that a task can be accomplished by some service agents. Each task agent has a utility value. If a set of service agents cover the skills needed by one task agent, we say that the task can be completed. Given an allocation of task agents to service agents, the system revenue is defined as the sum of the utilities of those task agents that can be completed. It is unnatural, perhaps, that task agents are assumed to be self-interested. The coalition skill game can be viewed as an agency recruiting market, where the service agent represents an applicant, each applicant has different skills, and the task agent represents the company that intends to recruit employees. Each company needs some employees to provide the skills they need. Only when all the needed skills are provided can the company operate and make profit. The company distributes its utility to the needed skills, and the expected wage of an applicant is the utility share of the skill it provides. Applicants are self-interested and will choose the companies that will bring them the greatest benefits. The companies are also self-interested, with the goal of recruiting all the employees needed to make the company operate and get benefits. In this paper, the following question for coalition skill games is considered: Given the task selection strategies of self-interested service agents, how do the task agents distribute their utilities to the service agents so that it can get all the skills they needed? A simple example is given in Figure 1 to illustrate the influences of the utility distribution strategies on the individual revenues and the system total revenue. In Figure 1, the line between \(r_{i}\in\{r_{1},r_{2}\}\) and \(s_{j}\in\{s_{1},s_{2}\}\) indicates that the service agent \(r_{i}\) possesses skill \(s_{j}\). The line between \(s_{j}\in\{s_{1},s_{2}\}\) and \(t_{k}\in\{t_{1},t_{2},t_{3}\}\) indicates that the task agent \(t_{k}\) needs skill \(s_{j}\). Numbers next to task agents indicate their utilities. For task agents \(t_{1}\) and \(t_{3}\), because they only need one skill, there is no need for them to adjust their utility distribution schemes. For task agent \(t_{2}\), if its utility is distributed averagely, the shares of \(s_{1}\) and \(s_{2}\) are both 4. The resulted payoff matrix is shown in Table 1 whose Nash equilibrium is (2, 5) (underlined in Table 1). This means that no matter which tasks are selected by \(r_{1}\) and \(r_{2}\) on initialization, the end results are: \(r_{1}\) selects \(t_{1}\) and receives individual revenue 2, \(r_{2}\) selects \(t_{3}\) and receives individual revenue 5, the system total revenue is 7. However, in the ideal case, both \(r_{1}\) and \(r_{2}\) should select \(t_{2}\), and system total revenue is 8. Because of the unreasonable distribution of \(u_{2}\), the self-interested service agents are not willing to cooperate to complete \(t_{2}\). Therefore, for the task allocation problem of the self-interested agent coalition skill game, the utility distribution strategies of task agents affect the individual revenues and the system total revenue to a certain extent. Based on this point, this paper studies the utility distribution strategies of the task agents. An algorithm, the Task Allocation Algorithm, which is based on the Utility Distribution Adjustment (TAAUDA), is proposed to allocate tasks to service agents. The final simulation results verified the effectiveness of TAAUDA. The remainder of this paper is structured as follows.