n agents in a fair way. When can an allocation be considered "fair" ?One of the most well-studied notions of fairness is Envy-freeness.An allocation is "envy-free" if no agent envies another, however, it's not always exists.Then we define "envy-free up to any good" : In an EFX allocation, agent. j , however this envy would vanish as soon as anygood is removed from. ) . However, an EFX allocation may not exist too.j , however this envy would vanish as soon as agood is removed from. 2). At first neither of them had any goods. Then there comes. m goods) , each operation will provide three values. ), the value of this good in Eva's perspective( i.e.=0 , then it was allocated to Colin, otherwise it was allocated to Eva). They want you to tell them, after each operation, what is the highest situation for the current allocation?We define the priority as: "envy-free"is the highest, "envy-free up to any good"is the second, "envy-free up to one good"is the third, and if none of the three conditions are satisfied, the worst is "envy".
Fair division of goods among competing agents is a fundamental problem in Economics and Computer Science. There is a set M M of m m goods and the goal is to allocate goods among n n agents in a fair way. When can an allocation be considered "fair" ? One of the most well-studied notions of fairness is Envy-freeness. An allocation is a partition of M M into disjoint subsets X_1, dots , X_n X 1 ,…,X n where X_i X i is the set of goods given to agent i i . Every agent i i has a value associated with each good j j ,which represented as w_{i,j} w i,j . And every agent values a set of goods S S as the sum of the values of the goods in S S, which represented as W_i(S) = sum_{jin S} w_{i,j} W i (S)=∑ j∈S w i,j . Then we define that agent i i envies agent j j if i i values X_j X j more than X_i X i , i.e. W_i(X_j)>W_i(X_i) W i (X j )>W i (X i ). An allocation is "envy-free"(represented as EF) if no agent envies another, however, it's not always exists. Then we define "envy-free up to any good" (represented as EFX) : In an EFX allocation, agent i i may envy agent j j , however this envy would vanish as soon as any good is removed from X_j X j . i.e. if W_i(X_j)>W_i(X_i) W i (X j )>W i (X i ) , then forall g in X_j,W_i(X_jsetminus g)le W_i(X_i) ∀g∈X j ,W i (X j ∖g)≤W i (X i ) . However, an EFX allocation may not exist too. Then we define "envy-free up to one good" (represented as EF1) : In an EF1 allocation, agent i i may envy agent j j , however this envy would vanish as soon as a good is removed from X_j X j . i.e. if W_i(X_j)>W_i(X_i) W i (X j )>W i (X i ) , then exists g in X_j,W_i(X_jsetminus g)le W_i(X_i) ∃g∈X j ,W i (X j ∖g)≤W i (X i ) . Note that in EFX and EF1, no good is really removed. Today Colin and Eva wants to study this problem. To simplify the problem, we considered there only exists two agents: Colin (agent 1 1) and Eva (agent 2 2). At first neither of them had any goods. Then there comes m m operations (allocate m m goods) , each operation will provide three values c_i,e_i, b_i=0/1 c i ,e i ,b i =0/1 to represent one good , which means the value of this good in Colin's perspective ( i.e. W_{1,i}=c_i W 1,i =c i ), the value of this good in Eva's perspective ( i.e. W_{2,i}=e_i W 2,i =e i ) , and who it was allocated to (i.e. if b_i=0 b i =0 , then it was allocated to Colin, otherwise it was allocated to Eva) They want you to tell them, after each operation, what is the highest situation for the current allocation? We define the priority as: "envy-free" is the highest, "envy-free up to any good" is the second, "envy-free up to one good" is the third, and if none of the three conditions are satisfied, the worst is "envy".
标签： HBC253181Whereisthebilliardballgoing? 模拟 思维Envy-freeness题解
