| 失效链接处理 |
|
Cooperation Aware Task Assignment in Spatial Crowdsourcing PDF 下载
本站整理下载：
相关截图：
主要内容：
Game theory is the study of mathematical models of conflict
and cooperation between intelligent rational decision-makers,
which is widely used in economics, political science, and
computer science [9]. In strategic games, there are a set of
players N competing or cooperating for some resources in
order to optimize their individual objective functions (utilities).
For each player i ∈ N , he/she can choose one strategy si
(i.e., conducting task tx) out from the set of his/her possible
strategies Si, and has a utility function Ui, whose value
depends on the strategy of player i as well as the strategies of
other players. The input of the utility function Ui is a given
joint strategy S ∈ S, where S is the Cartesian product of the
actions of all players (i.e., S = S1 × S2 ×···× S|N |). Let
si be the strategy of player i in the joint strategy S and s−i
be the joint strategies of all other players except for player i.
A strategic game has a pure Nash equilibrium [19] S∗ ∈ S,
if and only if for every player i ∈ N we have the following
conditions:
Ui(s∗i , s∗−i) ≥ Ui(si, s∗−i), ∀si ∈ Si
Algorithm 3: Game Theoretic Approach
Input: A set W(ϕ) of available workers and a set T(ϕ) of
tasks at timestamp ϕ
Output: Nash Equilibrium
1 Apply TPG approach to achieve an initial assignment
2 while Not Nash Equilibrium do
3 foreach wi ∈ W(ϕ) do
4 select the best-response task tj for worker wi 5 assign worker wi to task tj 6 return the assignment of each worker
In other words, in a Nash equilibrium no player can improve
his/her utility by unilaterally changing his/her strategy when
other players persist in their current strategies.
One common used framework to search a Nash equilibrium
S∗ ∈ S for a given strategic game G = N , S, {Ui}i∈N → N is the best-response framework [21], which first randomly
selects a strategy for each player, then iteratively selects the
“best” strategy for each player i based on the current strategies
of other players until a Nash equilibrium is found (i.e., no one
will change the selected strategy).
There are several issues related to the best-response framework: a) Stability: whether the best-response frame can find a
Nash equilibrium; b) Convergence: how fast it can converge;
c) Quality: how good is the found solution. We will first
propose one game theoretic approach to solve our CA-SC
problem, then answer the three issues related to the approach
one-by-one.
B. The Game Theoretic Approach
In this section, we first model a CA-SC problem instance
as a strategic game G then propose a game theoretic approach
(GT) based on the best-response framework to find a Nash
equilibrium joint strategy for the strategic game G, where every
worker is assigned to his/her “best” task such that a high total
cooperation quality score is achieved. Specifically, we model
each worker wi as a player i, whose target is to select a “best”
task with the highest cooperation score (utility) for him/her.
For each player wi, his/her strategy set Si indicates all the
possible strategies that he/she can choose (e.g., all the valid
tasks he/she can conduct). Then, a joint strategy S for the
strategic game G corresponds to an assignment A for the CASC problem instance.
We first define the utility function Ui of worker wi in the
joint strategy S as the cooperation quality score increase:
Ui(S) = Ui(si, s−i)=ΔQ(wi, tj ) = Q(Wj )−Q(Wj−{wi}) (5)
where Wj is the assigned workers of task tj (worker wi selects
task tj ). Then, we propose a basic game theoretic approach,
shown in Algorithm 3, to achieve a Nash equilibrium for a
set of workers W(ϕ) and a set of tasks T(ϕ) at timestamp
ϕ. Specifically, we first apply TPG approach to achieve
an initial assignment (lines 1). Next, we iteratively adjust
each worker’s strategy to his/her best-response strategy that
maximizes his/her utility function Ui (as defined in Equation
5) according to the other workers’ current joint strategy until a
1446
Authorized licensed use limited to: SHENZHEN UNIVERSITY. Downloaded on January 02,2021 at 09:16:37 UTC from IEEE Xplore. Restrictions apply.
Nash equilibrium is found (i.e., no worker will change his/her
strategy in the best-response framework) (lines 2 - 5). Here,
each iteration of the WHILE loop (lines 2-5) is called a round.
C. Analysis of the Game Theoretic Approach
In this section, we analyze the three important issues related
to the game theoretic approach (Algorithm 3): a) whether it can
find a Nash equilibrium (Stability); b) how fast it can converge
(Convergence); c) how good is the found result (Quality).
The Stability of the Approach. We prove that Algorithm 3
can finally result in a Nash equilibrium. To prove the stability
of Algorithm 3, we first introduce the theory of Potential
Games [17]. A strategic game G = N , S, {Ui}i∈N → R
is called an exact potential game if and only if there exists a
potential function F(S) : S → R such that:
Ui(si, s−i) − Ui(si, s−i) = F(si, s−i) − F(si, s−i), ∀si, si ∈ Si
where si and si are the strategies that worker wi can select, and s−i is the joint strategy of the other workers except for
worker wi. Intuitively, in an exact potential game, the change
in a single player’s utility due to his/her own strategy deviation
results in exactly the same amount of change in the potential
function. The most important property of potential games is
that the best-response framework always converges to a pure
Nash equilibrium for finite-strategy potential games [17].
Next, we prove the stability of the basic game theoretic approach by proving the strategic game of our CA-SC problem is
an exact potential game in the following theorem. Specifically,
we define the potential function F as the objective function
in Equation 3.
Theorem V.1. The strategic game of the CA-SC problem is
an exact potential game.
Proof. Let si and si be any other response strategy of worker wi. Here a given joint strategy s−i is for the other workers
except for worker wi. We note the task selected in strategies si and si as tasks tj and tk, respectively, then we have:
F(si, s−i) − F(si, s−i) = Q(Wj ) + Q(Wk − {wi}) + tx∈T−{tj ,tk} Q(Wx) −Q(Wk) + Q(Wj − {wi}) +
tx∈T
−{tj ,tk} Q(Wx) = Q(Wj ) + Q(Wk − {wi}) − Q(Wk) + Q(Wj − {wi}) = Q(Wj ) − Q(Wj − {wi}) − Q(Wk) − Q(Wk − {wi}) = Ui(si, s−i) − Ui(si, s−i) (6)
Thus, according to the definition of potential games [17],
the strategic game of the CA-SC problem is an exact potential
game.
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
