Task Allocation on Networks with Execution Uncertainty (Extended Abstract)∗

1 Introduction

Task allocation is an important part of real-world applications such as crowdsourcing [Wu et al., 2017; Goel et al., 2014] and market supply [Dash et al., 2007]. A common goal of task allocation is to find suitable workers to achieve a good performance at a low cost. Previous studies have made great progress in finding the best allocations under cases with a fixed number of workers. For example, the task requester seeks suitable workers in third-party platforms (e.g., Amazon Mechanical Turk) or holds a contest with attractive rewards [Chawla et al., 2019]. Yet, such cases are less scalable due to the relatively fixed number of participants. Generally, we hope to involve more workers so that the task requester is capable of finding more suitable workers. Also, nowadays, people are connected with others via social networks. Therefore, a straightforward approach is to make full use of their connections such that we can involve more workers. The challenge remains such as workers are competitors for the task and they are unwilling to provide their connections.

∗The full version is initially published at PRIMA 2022.

More precisely, we consider a single-task allocation problem where the task is allocated to a single agent and the task performance of an agent is measured by the finished quality. Each agent has a cost to perform the task. Before conducting the tasks, agents are uncertain about their actual performance and only know their probability distributions over the quality levels, which is known as the execution uncertainty. Therefore, the requester also needs to take the execution uncertainty into accounts to allocate the task.

We propose the PEV-based Diffusion Mechanism to handle the above challenges one by one. Firstly, to solve the issue of agents unwilling to invite others, the proposed mechanism rewards them such that each agent will maximize her utility by inviting others. Then, the task requester is able to reach as many agents as possible. Secondly, to handle the execution uncertainty, the mechanism gives agents payoffs after they finished the task, which guarantees that agents will not misreport their abilities because their performance is verified. More importantly, previous studies focused on the uncertainty to finish a task but not they quality, introducing the probability of success (PoS) to describe the probability of an agent successfully completing the task [Porter et al., 2008; Ramchurn et al., 2009], e.g., 70% to fail and 30% to finish the task. In our setting, we define the probability of quality (PoQ), which represents the probability distribution on completion qualities, e.g., 30% to finish with a good quality, 20% to finish with a low quality, and 50% to totally fail.

1.1 RelatedWork

The social network is an effective medium to get access to more potential agents. Mechanism design in social networks has been widely utilized in auctions [Li et al., 2020; Li et al., 2022], answer querying [Tang et al., 2011], social advertising [Li and Shiu, 2012] and influence maximization [Shi et al., 2020]. An overview and prospect of all these topics on social networks is given by Zhao [2021; 2022]. In this paper, we are inspired by the idea of the Information Diffusion Mechanism [Li et al., 2020; Li et al., 2017; Li et al., 2022], which is proposed to increase the seller' revenue in auctions via social networks. We show that the mechanism can be applied for the case where each agent can perform the task in the same quality with a probability of one. However, when the task requester is sensitive to agents' completion qualities and is uncertain about agents'

performance, the Information Diffusion Mechanism cannot incentivize agents to invite each other. Though there has also been work studying task allocation problems on social networks [Jiang et al., 2012; de Weerdt et al., 2012], the network is known in advance.

In traditional task allocation problems, the performance and cost of each agent are private information. To incentivize each agent to report her type truthfully, the task scheduling mechanisms with verification were first proposed to take both agents' declarations and their actual performance into consideration [Nisan and Ronen, 2001; Conitzer and Vidali, 2014]. Later, to describe the execution uncertainty in more general settings, probability of success (PoS) is introduced to describe the probability of an agent successfully completing the tasks [Porter et al., 2008; Ramchurn et al., 2009; Zhao et al., 2016].

2 The Model

Consider a social network represented by a graph G = (V,E), where V = {s} ∪ N is the node set and E is the edge set. The task requester s has a single task to be performed and N = {1, 2, · · · , n} is the set of all other agents in the network. Each edge {i, j} ∈ E indicates that agent i can directly communicate with agent j. For i ∈ V , let ri = {j ∈ V | {i, j} ∈ E} be the neighbour set of i. Given the task to be performed, let Q ⊂ R+ ∪ {0} be the set of all possible completion qualities. Let the discrete random variable Qi be the completion quality of agent i and qi ∈ Q denote a realization of Qi. Let fi be the probability density function of Qi, i.e., P(Qi = qi) = fi(qi), which is called agent i's probability of quality (PoQ). There is also a fixed cost ci ≥ 0 for i to perform the task. Define θi = (fi, ci, ri) as agent i's private type. Let Θi be the type space of agent i and θ = (θ1, · · · , θn) be the type profile of all agents.

Initially, only the task requester's neighbours rs know the task. Hence, the task requester needs a mechanism to attract more participants, which is done by incentivizing agents to diffuse the task information to all their neighbours. Thus, each agent's action consists of reporting her PoQ, her cost to perform the task and inviting her neighbours, i.e., reporting her type. For agent i ∈ N, let θ′i = (f ′ i , c′i , r′i ) be her report, where f ′ i is a probability distribution over Q, r′i ⊆ ri and c′i ≥ 0. Let θ′ = (θ′1 , · · · , θ′n ) be a report profile of all agents in N. Denote the graph constructed from θ′ by G(θ′ ) = (V, E(θ′ )), where E(θ′ ) = {{i, j} | i ∈ V, j ∈ r′i }. Let I(θ′ ) be the set of all participants under θ′ , and i ∈ I(θ′ ) holds if and only if there exists a path from s to i in the graph G(θ′ ). Let Θ be the space of all possible type profiles.

Generally speaking, the mechanism consists of two steps. The task requester first announces a contract including a task allocation policy and a payoff policy and then assigns the task to an agent according to their declarations. After the task requester verifies the completion quality, she will give payoffs to agents according to the announced contract. We call such a mechanism the verified contract mechanism.

Definition 1 (Verified Contract Mechanism). A verified contract mechanism is defined by M = (π, p), where π : Θ → {0, 1}N and p : Θ × Q → RN are the allocation and payoff policies respectively. Given agents N and their report profile θ′ ∈ Θ, set πi(θ′ ) = 0 and pi(θ′ , ·) = 0 for all i /∈ I(θ′ ).

Given a verified contract mechanism and a report profile θ′ , πi(θ′ ) = 1 means that the task is allocated to agent i, otherwise she will not perform the task. The actual completion quality under the allocation π is drawn from the true PoQ of the selected agent, denoted by qπ. Then pi(θ′ , qπ) is the payoff given to agent i. We assume that the utilities of the task requester and the agents are quasi-linear, i.e., us(θ′ , qπ) = qπ-∑i∈N pi(θ′ , qπ) and ui(π(θ′ ), p(θ′ , qπ)) = pi(θ′ , qπ)-πi(θ′ )ci for all i ∈ N. In the following, we define several properties concerned. The first one is the efficiency of the mechanism in terms of the expected social welfare.

Definition 2 (Efficiency). A verified contract mechanism is efficient if for all θ′ ∈ Θ,

where Π is the space of all feasible allocations, f ′π′ is the PoQ reported by the agent j such that π′j = 1.

Another property is called incentive compatibility, which requires that for each agent i, reporting her type θi truthfully is a dominant strategy.

Definition 3 (Incentive Compatibility). A verified contract mechanism is incentive compatible (IC) if for all i ∈ N and θi ∈ Θi, for all θ′-i ∈ Θ-i,

where θ′-i is the report profile of all agents without i, Θ-i is the space of all possible θ′-i .

The next property ensures that the expected utility of an agent is non-negative when she truthfully reports.

Definition 4 (Individual Rationality). A verified contract mechanism is individually rational (IR) if for all i ∈ N and θi ∈ Θi, for all θ′-i ∈ Θ-i,

The last desirable property is that the task requester should not suffer a deficit in expectation.

Definition 5 (Weakly Budget Balance). A verified contract mechanism is weakly budget balanced (WBB) if for all θ′ ∈ Θ,

where fπ(θ′ ) is the true PoQ of the selected agent under θ′ .

3 The Mechanism

3.1 Without Execution Uncertainty

We first consider the setting where the task performance does not require special skills. The task requester gets the same quality no matter which agent the task is assigned to, i.e., Q = {q} and fi(q) = 1 for all i ∈ N. However, agents may need different costs to perform the given task (e.g., time). Thus, to maximize both the task requester's utility and the social welfare, a mechanism should allocate the task to an agent who can perform the task with the least cost.

We apply the VCG mechanism, the task requester selects the agent who performs with the least cost among her neighbours, and the agent's payoff equals the decrease in others' utilities due to her participation. However, the VCG mechanismwill cause deficits for the task requester 1 .

To tackle the deficit issue in this setting, we can apply the Information Diffusion Mechanism (IDM) [Li et al., 2017]. The IDM is proposed to incentivize information diffusion to sell a single item in a social network. We just need to change the goal to select the agent with the least cost. The mechanism relies on the concept of critical agents.

Definition 6. Given a report profile θ′ , for agent i, j ∈ I(θ′ ), j is one of i's critical agent if j exists in all simple paths from the task requester s to agent i in the graph G(θ′ ). The set of i's all critical agents is denoted by cti(θ′ ) and the sequence order of agents in cti(θ′ ) is denoted by (s, j1, · · · , jm), where jm = i and k < k′ if and only if jk ∈ ctjk′ .

Information Diffusion Mechanism (IDM)

INPUT: a report profile θ′ .

1. Choose j ∈ argmaxi∈I(θ′ ){q - c′i } with random tie breaking.
2. Set πi = 0, pi = 0 for all i /∈ I(θ′ ) and all i /∈ ctj(θ′ ).
3. Compute wi = ∑k̸=i π′k (q-c′k ) for each i ∈ ctj(θ′ ),

and ˆ θ = (nil, θ′-i ).

4. Let the sequence order of agents in ctj(θ′ ) be (s, i1, · · · , im), where im = j. For k = 1 : m- 1,

and πj = 1 if ∑m-1

k=1 πik = 0. 5. Suppose it be the chosen agent, i.e., πit = 1, 1 ≤ t ≤

1. Then, the payoff of each agent ik ∈ ctj(θ′ ) will be

OUTPUT: the allocation π and the payoff p.

Intuitively, the IDM allocates the task to the first critical agent with the least cost when the next agent in the sequence did not participate. The payoff of the chosen agent equals the least cost reported by other agents without her participation. The payoff of each critical agent before the chosen agent is determined by the difference between the maximum social welfare without next critical agent's participation and that without her participation. The properties of IDM will stay the same.

1 An example is illustrated in the full version of this paper in the proceeding of PRIMA 2022.

Theorem 1 ( [Li et al., 2017]). The IDM is IR, IC and WBB. Failure in the Quality-Aware Setting. Consider another setting without execution uncertainty, where the task needs special skills to be performed, and then agents may perform the task with different qualities, i.e., fi(qi) = 1 for some qi ∈ Q and i ∈ N. In this case, the application of IDM is not IC anymore. The failure lies in no guarantee for incentive compatibility since the payoff to the selected agent is always related to her reported ability.

3.2 With Execution Uncertainty

Look back to our general model. To mitigate IDM'a failure, we propose the Post Execution Verification-based Diffusion Mechanism (PEV-based Diffusion Mechanism). The PEV-based Diffusion Mechanism chooses the agent to perform the task based on agents' reports, but pays her Given a report profile θ′ ∈ Θ, define an allocation that maximizes the expected social welfare as

PEV-based Diffusion Mechanism (PDM)

INPUT: a report profile θ′ .

1. Choose j ∈ argmaxi∈N{Ef ′ i [Qi] - c′i } with random tie breaking. Set πi = 0, pi = 0 for all i /∈ ctj(θ′ ).
2. For each agent i ∈ ctj(θ′ ), compute wi =

1. Let the sequence order of agents in ctj(θ′ ) be (s, i1, i2, . . . , im), where im = j. For k = 1 : m- 1,

and πj = 1 if ∑m-1 k=1 πik = 0.

1. Suppose πit = 1 and it performs the quality qπ.
2. The payoff of each agent ik ∈ ctj(θ′ ) is defined as

OUTPUT: the allocation π and the payoff p.

Intuitively, the PDM allocates the task to the agent with the highest expected welfare when the next critical agent in the sequence did not participate. The payoff of the chosen agent is determined by her actual execution quality. Each critical agent before the chosen agent gets a payoff based on the increase of the expected social welfare due to her participation when the next one did not participate.

Example 1. Consider the network in Figure 1, and all agents' types are listed in the Table 1. Thus, PDM chooses agent 9 to perform the task. Suppose that the actual execution quality of agent 9 is qπ = 8. Then, the payoffs given to agents 2, 6 and 9 are p2 = w6-w2 = 0, p6 = w9-w6 = 0.5 and p9 = qπ - w9 = 3.5. Finally, the utility of s is us = 4.

Theorem 2. The PDM is IR, IC, and WBB 2 .

3.3 AGeneral Class

Li et al. [2022] gave a methodology to extend IDM to a generalized class of diffusion auction called Critical Diffusion Mechanisms (CDM). The key idea is choosing a different set of competitors when allocating the item. By doing this, it may give more chances to win to critical agents, and may also improve the utility of the seller.

Inspired by their idea, we can also extend PDM generally. For the allocation policy of PDM, agents who are critical parents of the best worker have priorities of winning the task. Particularly, an agent wins the task if she is the first agent among these parents whose has the best performance (i.e., the expected quality minus the cost) when her critical children are not considered. The key idea here is that a set of competitors are removed from the network when determining whether an agent can perform the task. Intuitively, the way of removing agents can be various as long as it will not affect incentive compatibility. Also, the allocation efficiency and the payoffs to the critical agents of the selected agent may vary with the removing methods. Therefore, we can have the following class of mechanisms called PEV-based Critical Diffusion Mechanism (PCDM), which is parameterized by a set selection function αi for all i ∈ ctj(θ′ ), where j is the best worker under θ′ .

2 A complete proof can be found in the full version of this paper in the proceeding of PRIMA 2022.

PEV-based Critical Diffusion Mechanism (PCDM)

INPUT: a report profile θ′ .

1. Choose j ∈ argmaxi∈N{Ef ′ i [Qi] - c′i } with random tie breaking. Set πi = 0, pi = 0 for all i /∈ ctj(θ′ ). 2. For each agent i ∈ ctj(θ′ ), compute

1. Let the sequence order of agents in ctj(θ′ ) be (s, i1, i2, . . . , im), where im = j. For k = 1 : m- 1,

and πj = 1 if ∑m-1 k=1 πik = 0.

1. Suppose πit = 1 and it performs the quality qπ.
2. The payoff of each agent ik ∈ ctj(θ′ ) is defined as

OUTPUT: the allocation π and the payoff p.

Theorem 3. The PCDM is IR, IC and WBB if for all i ∈ ctj(θ′ ), it is satisfied that αi

• contains the next agent in ctj(θ′ ) after i;
• is independent from the reports of i's critical children;
• and is monotonically increasing with r′i .

Notice that PCDMs cannot always guarantee efficiency since the task may not be allocated to the best worker. Actually, no mechanism simultaneously satisfies IR, IC, WBB and efficiency.

Proposition 1. There is no verified contract mechanism satisfying IR, IC, WBB and efficiency in the social networks.

Acknowledgements

This work is supported by Science and Technology Commission of Shanghai Municipality (No. 22ZR1442200).