Envy-freeness

Fair division of goods among competing agents is a fundamental problem in Economics and Computer Science. There is a set $M$ of $m$ goods and the goal is to allocate goods among $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$ into disjoint subsets $X_1, \dots , X_n$ where $X_i$ is the set of goods given to agent $i$ . Every agent $i$ has a value associated with each good $j$ ,which represented as $w_{i,j}$ . And every agent values a set of goods $S$ as the sum of the values of the goods in $S$ , which represented as $W_i(S) = \sum_{j\in S} w_{i,j}$ .

Then we define that agent $i$ envies agent $j$ if $i$ values $X_j$ more than $X_i$ , i.e. $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$ may envy agent $j$ , however this envy would vanish as soon as any good is removed from $X_j$ . i.e. if $W_i(X_j)>W_i(X_i)$ , then $\forall g \in X_j,W_i(X_j\setminus g)\le 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$ may envy agent $j$ , however this envy would vanish as soon as a good is removed from $X_j$ . i.e. if $W_i(X_j)>W_i(X_i)$ , then $\exists g \in X_j,W_i(X_j\setminus g)\le 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$ ) and Eva (agent $2$ ). At first neither of them had any goods. Then there comes $m$ operations (allocate $m$ goods) , each operation will provide three values $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$ ), the value of this good in Eva's perspective ( i.e. $W_{2,i}=e_i$ ) , and who it was allocated to (i.e. if $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".

After each operation, output a single line with:

If the current allocation is "envy-free", then output "EF";

Otherwise if the current allocation is "envy-free up to any good", then output "EFX";

Otherwise if the current allocation is "envy-free up to one good", then output "EF1";

Otherwise output "E".

#include<bits/stdc++.h> using namespace std; typedef long long LL; LL t,c,e,b,isumj,isumi,jsumi,jsumj,imin = LONG_MAX,jmin = LONG_MAX,imax = 0,jmax = 0; void solve(){ scanf("%lld%lld%lld",&c,&e,&b); if(b == 0){ isumi += c; isumj += e; jmin = min(jmin,e); jmax = max(jmax,e); } else{ jsumi += c; jsumj += e; imin = min(imin,c); imax = max(imax,c); } if(jsumj >= isumj and isumi >= jsumi) printf("EF\n"); else if(isumi >= jsumi - imin and jsumj >= isumj - jmin) printf("EFX\n"); else if(isumi >= jsumi - imax and jsumj >= isumj - jmax) printf("EF1\n"); else printf("E\n"); } signed main(){ cin >> t; while(t--) solve(); return 0; }

#include<stdio.h> long max(long a, long b) {return a > b ? a : b;} long min(long a, long b) {return a < b ? a : b;} long ii,ij,ji,jj,a,s,z=1e6,x=1e6,m,c,e,b;int main() {scanf("%ld",&m);while(m--){scanf("%ld%ld%ld", &c, &e, &b);if(!b){ii+=c;ij+=e;s=max(s,e);x=min(x,e);}else{ji+=c;jj+=e;a=max(a,c);z=min(z,c);}if(ii>=ji&&jj>=ij)printf("EF\n");else if((ji-z<=ii)&&(ij-x<=jj))printf("EFX\n");else if((ji-a<=ii)&&(ij-s<=jj))printf("EF1\n");else printf("E\n");}return 0;}

#include<iostream> using namespace std;long ii,ij,ji,jj,a,s,z=1e6,x=1e6,m,c,e,b;int main() {cin>>m;while(m--){scanf("%d%d%d",&c,&e,&b);if(!b){ii+=c;ij+=e;s=max(s,e);x=min(x,e);}else{ji+=c;jj+=e;a=max(a,c);z=min(z,c);}if(ii>=ji&&jj>=ij)printf("EF\n");else if((ji-z<=ii)&&(ij-x<=jj))printf("EFX\n");else if((ji-a<=ii)&&(ij-s<=jj))printf("EF1\n");else printf("E\n");}return 0;}

详情