Objective: Investigate relations between several fairness properties and their approximations.

Activities: Read and present the paper Multiple birds with one stone (2020).

Abstract

Algorithm proposed, achieves (ϕ1)(\phi-1)-EFX and 2ϕ+2\frac{2}{\phi+2}-GMMS. (ϕ=5+12\phi={\sqrt5+1\over2})

Previous work: 121\over2-EFX. 121\over2-GMMS. EF1 + 232\over3-PMMS.

GMMS PMMS EFX allocation always exist when # of goods 2×\le2\times# of agents.

Introduction

Relaxation of fairness notion: EF → EFX, EF1

Approximation of relaxed fairness notion: α\alpha-EFX…

A good approximation of any one of EF1, EFX, MMS, PMMS doesn’t necessarily imply particularly strong guarantees for any of the others. Thus it’s desirable to achieve approximation of several fairness notions simultaneously.

Main Contribution

Algorithm proposed in this paper:

  1. 0.6180.618-EFX
  2. 0.5530.553-GMMS
  3. EF1
  4. 0.6670.667-PMMS

Algorithm is based on draft algorithm, envy-cycle elimination. (parametric version)

GMMS PMMS EFX always exist and can be found efficiently when # of goods 2×\le2\times# of agents. non-trivial problem

Skipped here

Preliminaries

N={1,2,,n}N=\{1,2,\cdots,n\} set of nn agents.

MM set of mm indivisible items.

Valuation function should be monotone and additive: SM,vi(S)=gSvi(g)\forall S\subseteq M,v_i(S)=\sum_{g\in S}v_i(g) and (\forall i\in N)\and(\forall g\in M),v_i(g)\ge0.

Assume that we have already know the valuation function for each agent.

All the goods should be allocated, i.e., no free disposal.

Allocation: A=(A1,,An)\mathcal A=(A_1,\cdots,A_n) where AiAjA_i\cap A_j\neq\emptyset and iAi=M\bigcup_iA_i=M.

  • AiA_i is the bundle allocated to agent ii,

Πn(M)\Pi_n(M): set of all partitions of a set MM into nn bundles.

Fairness Concepts (Review)

Family of Envy-freeness

  • EF, EF1, EFX, α\alpha-EFX

  • EF → EFX

Family of Maximin Share (worst-case guarantee)

  • Maximin Share μi\mu_i

    • To find an allocation A\mathcal A s.t., for each agent ii it maximizes minAjAvi(Aj)\min_{A_j\in\mathcal A}v_i(A_j)

      μi(n,S)=maxAΠn(S)minAjAvi(Aj)\Lrarr\mu_i(n,S)=\max_{\mathcal A\in\Pi_n(S)}\min_{A_j\in\mathcal A}v_i(A_j)

  • α\alpha-MMS iN,vi(Ai)αμi(n,M)\forall i\in N,v_i(A_i)\ge\alpha\cdot\mu_i(n,M)

  • α\alpha-P(Pairwise)MMS: For each pair i,jN,vi(Ai)αμi(2,AiAj)i,j\in N,v_i(A_i)\ge\alpha\cdot\mu_i(2,A_i\cup A_j)

  • α\alpha-G(Groupwise)MMS: For each subset NNN'\subseteq N, iN,vi(Ai)αμi(N,jNAj)\forall i\in N',v_i(A_i)\ge\alpha\cdot\mu_i(|N'|,\cup_{j\in N'}A_j)

    Thus, GMMS\RarrMMS, MMS↛\not\rarrPMMS (GMMS is for all the subset of agents, MMS is only for all the agents)

Known EF1 Algorithms

Envy-cycle Elimination Algorithm

Partial allocation PM\mathcal P\subsetneq M.

Envy graph GP=(N,EP)G_\mathcal P=(N,E_\mathcal P) where (i,j)EP(i,j)\in E_\mathcal P iff agent ii currently envies agent jj.

In each step, an agent that no one envies receives the next available good.

Tie-breaking: lexicographically order.

❗🤔Theorem 1: Let P\mathcal P be any EF1 partial allocation and M=Mi=1nPiM'=M\diagdown\cup_{i=1}^nP_i. Then,

(a) At the end of each iteration of the for loop, the resulting partial allocation is EF1. Thus the algorithm terminates with EF1 allocation.

(b) Fix an agent ii, let AiA_i be the bundle assigned to ii at the end of some iteration of the for loop. If AiA_i' is assigned to ii at the end of a future iteration, then vi(Ai)vi(Ai)v_i(A_i')\ge v_i(A_i) MONOTONICITY!

(Proof by additive and monotone valuation function.)

Pseudo code for Envy-cycle Elimination(N,P,M)(N,\mathcal P,M') MM' denotes set of unallocated goods.

  1. Construct the envy graph GPG_\mathcal P.

  2. for every gMg\in M', in lexicographic order do

    • While there is no node of in-degree 0 in GPG_\mathcal P do

      • Find a cycle j1j2jrj1j_1\rarr j_2\rarr\cdots\rarr j_r\rarr j_1 in GPG_\mathcal P
      • B=Pj1B=P_{j1}
      • for k=1k=1 to r1r-1 do
        • Pjk=Pjk+1P_{jk}=P_{jk+1}
      • Pjr=BP_{jr}=B.

      // find a envy-cycle and eliminate it iteratively.

    • Let iNi\in N be a node of in-degree =0=0

    • Pi=Pi{g}P_i=P_i\cup\{g\}

    • Update GPG_\mathcal P

  3. return P\mathcal P

Round Robin Algorithm

Round-robin(N,P,M,,τ)(N,\mathcal P,M',\ell,\tau) also outputs EF1 allocation: \ell denotes an order of NN, τ\tau denotes number of steps

  1. k=1k=1

  2. while MM'\neq\emptyset and τ>0\tau\gt0 do

    • g=argmaxhMv[k](h)g=\arg\max_{h\in M'}v_{\ell[k]}(h)

      In the while loop, each round player [k]\ell[k] get currently the maximal value of good.

    • P[k]=P[k]{g}P_{\ell[k]}=P_{\ell[k]}\cup\{g\}

    • M=M{g}M'=M'\diagdown\{g\}

    • k=(k+1)modnk=(k+1)\mod n

    • τ=τ1\tau=\tau-1

  3. return (P,M)(\mathcal P,M')

Draft and Eliminate Algorithm

Draft and Eliminate(N,M)(N,M) also outputs EF1 allocation: Combination of ECE & RR

  1. (,n)=(\ell,n')= Preprocessing(N,M)(N,M)
  2. Let A=(A1,,An)\mathcal A=(A_1,\cdots,A_n) with Ai=A_i=\empty for each iNi\in N
  3. (A,M)=(\mathcal A,M')= Round-robin(N,A,M,,n)(N,\mathcal A,M,\ell,n)
  4. Reverse \ell: R=([n],[n1],,[1])\ell^R=(\ell[n],\ell[n-1],\cdots,\ell[1])
  5. (A,M)=(\mathcal A,M')= Round-robin(N,A,M,R,nn)(N,\mathcal A,M',\ell^R,n-n')
  6. A=\mathcal A= Envy-cycle Elimination(N,A,M)(N,\mathcal A,M')
  7. return A\mathcal A

❗🤔Theorem 2

Let \ell be any ordering of NN and P=(,,)\mathcal P_\empty=(\empty,\cdots,\empty), Round-robin algorithm produces an EF1 allocation in polynomial time.

✋Time complexity analysis:

  • Number of loop iterative is min(m,τ)O(m)\le\min(m,\tau)\le O(m)

  • argmax\arg\max is O(M)=O(m)O(|M'|)=O(m),

  • The rest part in the loop should be O(1)O(1).

    Thus total complexity should be O(m2)O(m^2)

A Simple Universally Fair Algorithm

Draft and Eliminate Algorithm. It suffices to run only two rounds of the round-robin algorithm, once w.r.t. \ell and once w.r.t. reverse of \ell. (WHY?) Finally it runs the envy-cycle elimination algorithm on the remaining instance.

Preprocessing

Preprocessing(N,M)(N,M) step is facilitate the presentation and the analysis of the algorithm:

  1. L=;A=N;k=1L=\empty;A=N;k=1

    //LL contains the agents that get to pick first in 1st round-robin at the expense of not choosing a second good in 2nd round-robin.

  2. while AA\neq\empty do

    • Let ii be the lexicographically first agent of AA

    • hi=argmaxgMvi(g)h_i=\arg\max_{g\in M}v_i(g)

    • ti=mM+1t_i=m-|M|+1

    • Let R=(N(AL)){i}R=(N\diagdown(A\cup L))\cup\{i\}

    • j=argmaxtRvi(ht)j=\arg\max_{t\in R}v_i(h_t)

    • if ϕvi(hi)<vi(hj)\phi\cdot v_i(h_i)\lt v_i(h_j) then here: ϕ=5+121.618\phi=\frac{\sqrt5+1}{2}\approx1.618

      //If an agent envies someone that chose before her by a factor grater than ϕ\phi, then she is moved to a position of high priority in the ordering that is created.

      //The agents moved to the first positions during this process are guaranteed a good of high value in first round-robin. To counterbalance their advantage, they are not allowed to pick a second good later in second round-robin.

      • hi=hjh_i=h_j
      • L=L{i}L=L\cup\{i\}
      • [k]=i\ell[k]=i
      • k=k+1k=k+1
      • A=(A{i}){j}A=(A\diagdown\{i\})\cup\{j\}
    • else

      • A=A{i}A=A\diagdown\{i\}
      • M=M{hi}M=M\diagdown\{h_i\}
  3. for every iNLi\in N\diagdown L in order of increasing time stamp tit_i do

    • [k]=i\ell[k]=i
    • k=k+1k=k+1
  4. return (,[L])(\ell,[L])

❓ After preprocessing, have we AL=NA\cup L=N?

This preprocessing part reorders NN so that the first few agents are quite happy with their pick in the first round of the round-robin subroutine. For the remaining agents, we make sure that they get a second good before we move to the envy-cycle elimination algorithm. To do so in a balanced way, these agents pick goods in reverse order.

The resulting partial allocation, where everyone receives one or two goods, turns out to have all the fairness properties we want to achieve at the end e.g. it’s (ϕ1)(\phi-1)-EFX w.r.t. currently allocated goods. Starting from there and then applying the envy-cycle elimination algorithm on the remaining instance maintains these properties.

Fairness Guarantees of Draft-and-Eliminate

About Preprocessing Step

❗🤔Lemma 1: At the end of the execution of preprocessing with input (N,M)(N,M), each agent ii is associated with a single good hih_i, so that

a) vi(hi)>ϕvi(g)v_i(h_i)\gt\phi\cdot v_i(g), for any iLi\in L and gMk=1n{hk}g\in M\diagdown\cup_{k=1}^n\{h_k\}.

Fix some iLi\in L and consider the last iteration of the while loop where ii was the lexicographically first agent of AA. During which ii was added to LL.

The initial good associated with ii: hioldh_i^{old} during this iteration.

The final good associated with ii: hih_i.

\because ii was added to LL eventually. \therefore condition “ϕvi(hi)<vi(hj)\phi\cdot v_i(h_i)\lt v_i(h_j)” was true, i.e.,

ii’s favorite good among the ones associated to an agent not in LL, say hjh_j, was more than ϕ\phi times more valuable than hioldh_i^{old}, we have vi(hj)>ϕvi(hiold)ϕvi(g)v_i(h_j)\gt\phi\cdot v_i(h_i^{old})\ge\phi\cdot v_i(g) for any good gg that was not associated to an agent at the time.

Number of unassociated goods during the execution only decreases, thus the last inequality also holds for any good gg that was not associated to any agent till the end.

By hi=hjh_i=h_j, we conclude that vi(hi)>ϕvi(g)v_i(h_i)\gt\phi\cdot v_i(g) gMk=1n{hk}\forall g\in M\diagdown\cup_{k=1}^n\{h_k\}.

b) ϕvi(hi)vi(hj)\phi\cdot v_i(h_i)\ge v_i(h_j) for any i,jNLi,j\in N\diagdown L.

Fix some i,jNLi,j\in N\diagdown L. Note that both i,ji,j may be considered multiple times during preprocessing, i.e., they may be removed and added back to AA in several times.

Consider 2 cases:

  1. Last time ii was considered before last time jj was considered (ti<tjt_i\lt t_j at the end)

the desire inequality is obvious as agent ii is associated with her favorite good among the available goods, hih_i, before agent jj, i.e., vi(hi)vi(hj)v_i(h_i)\ge v_i(h_j).

  1. Last time ii was considered after last time jj was considered (ti>tjt_i\gt t_j at the end)

suppose that ϕvi(hi)<vi(hj)\phi\cdot v_i(h_i)\lt v_i(h_j). Then during the last iteration that ii was considered, the if statement is true and ii would be irrevocably added to LL, which contradicts the choice of ii.

Q. E. D.

❗🤔Lemma 2: The partial allocation produced in first round-robin is ({h1},{h2},,{hn})\mathcal (\{h_1\},\{h_2\},\cdots,\{h_n\}), where hih_is are in Lemma 1.

The preprocessing step can be combined with 1st round-robin!

Observation: \ell is used in first round-robin subroutine is not the same with the order that goods get assigned to agents during the preprocessing step, even when one takes into account that moving agents into LL is similar to changing their order.

First, using induction, we show that agents in LL get assigned to them the same goods they would if there were to choose first according to \ell.

For agents in NLN\diagdown L. First observe that, on termination, agents in NLN\diagdown L all have distinct time stamp assigned in second round-robin.

By time stamp of agent ii, name the final value of tit_i. Now fix some iNLi\in N\diagdown L.

  • In preprocessing, agent ii gets assigned her favorite good available if we exclude the goods assigned to some agents in LL, and to all the agents in NLN\diagdown L with time stamp less than tit_i.

  • In round-robin, agent ii receives her favorite good available if we exclude the goods allocated to all the agents in LL, and to all the agents in NLN\diagdown L with time stamp less than tit_i. However, in this scenario the extra agents from LL that pick before ii choose goods that ii does not find attractive enough. Indeed those goods are available in the first scenario, yet ii does not prefer them to hih_i.

    Therefore, in this scenario ii also picks hih_i and Ai={hi}A_i=\{h_i\} after first round-robin.

🤔Proposition: Draft-and-elimination returns an EF1 allocation.

By Theorem 2, it suffices to show that the partial allocation produced after second round-robin is EF1. Fix two distinct agents i,jNi,j\in N. If jLj\in L, then Aj={hj}A_j=\{h_j\}. Clearly, vi(Ai)vi(Aj{hj})=0v_i(A_i)\ge v_i(A_j\diagdown\{h_j\})=0. On the other hand, if jNLj\in N\diagdown L, then Aj={hj,hj}A_j=\{h_j,h_j'\}. Since agent ii picked hih_i when hjh_j' was still available, vi(hi)vi(hj)v_i(h_i)\ge v_i(h_j'). So we have vi(Ai)vi(hi)vi(Aj{hj})v_i(A_i)\ge v_i(h_i)\ge v_i(A_j\diagdown\{h_j\}).

Envy-freeness up to Any Good

❗🤔Theorem 3: The allocation A\mathcal A returned by Draft-and-elimination is a (ϕ1)(\phi-1)-EFX allocation. ⚠️

Consider the allocation A\mathcal A returned by algorithm, and fix two distinct agents i,jNi,j\in N. If Aj=1|A_j|=1, then clearly, vi(Ai)maxgAjvi(Aj{g})=0v_i(A_i)\ge\max_{g\in A_j}v_i(A_j\diagdown\{g\})=0.

So assume that Aj2|A_j|\ge2 and let hh be the last good added to AjA_j. At time this happened, AjA_j may belonged to an agent jj' other than jj. Finally, let Aiold,AjoldA_i^{old},A_{j‘}^{old} be bundles of ii and jj' respectively, right before hh was allocated. (i.e. hAjoldh\in A_{j'}^{old} at first)

Note that AioldA_i^{old} may not necessarily be a subset of AiA_i due to the possible swaps imposed by envy-cycle elimination. But part (b) of theorem 1 implies vi(Ai)vi(Aiold)v_i(A_i)\ge v_i(A_i^{old}).

We consider 4 cases, depending on whether iLi\in L and on the type of step during which hh was added to AjoldA_{j'}^{old}.

  1. iLi\in L and hh added in second round-robin.

We have Aiold={hi}A_i^{old}=\{h_i\}, as well as jNLj'\in N\diagdown L and Aj={hj,hj}A_j=\{h_{j'},h'_{j'}\}. This immediately implies that vi(Aiold)max{vi(hj),vi(hj)}v_i(A_i^{old})\ge\max\{v_i(h_{j'}),v_i(h'_{j'})\}. Thus vi(Ai)maxgAjvi(Aj{g})v_i(A_i)\ge\max_{g\in A_j}v_i(A_j\diagdown\{g\}).

  1. iLi\in L and hh added in envy-cycle elimination.

By the way that envy-cycle-elimination chooses who to give the next good to, we know that right before hh was added, no one envied jj'. In particular, vi(Aiold)vi(Ajold)v_i(A_i^{old})\ge v_i(A_{j'}^{old}). We further have vi(Aiold)vi(hi)>ϕvi(h)v_i(A_i^{old})\ge v_i(h_i)\gt\phi\cdot v_i(h), where the last inequality directly follows from part (a) of lemma 1. Putting everything together,

vi(Aj)=vi(Ajold)+vi(h)(1+ϕ1)vi(Aiold)ϕvi(Ai)vi(Ai)(ϕ1)vi(Aj)v_i(A_j)=v_i(A_{j'}^{old})+v_i(h)\le(1+\phi-1)v_i(A_i^{old})\le\phi\cdot v_i(A_i)\\ \Lrarr v_i(A_i)\ge(\phi-1)\cdot v_i(A_j)

  1. i∉Li\not\in L and hh added in second round-robin.

We have i,jNLi,j'\in N\diagdown L and Aj={hj,hj}A_j=\{h_{j'},h'_{j'}\}. If [i]<[j]\ell[i]\lt\ell[j'], then we proceed in a way similar to case 1:

vi(Ai)vi(Aiold)vi(hi)max{vi(hj),vi(hj)}.v_i(A_i)\ge v_i(A_i^{old})\ge v_i(h_i)\ge\max\{v_i(h_{j'}),v_i(h'_{j'})\}.

So, assume that [i]>[j]\ell[i]\gt\ell[j']. This means vi(hi)vi(hj)v_i(h_i')\ge v_i(h_{j'}'). We have

vi(Ai)vi(Aiold)vi(hi)+vi(hi)1ϕvi(hj)+vi(hj)1ϕ(Vi(hj)+vi(hj))=(ϕ1)vi(Aj)v_i(A_i)\ge v_i(A_i^{old})\ge v_i(h_i)+v_i(h_i')\ge{1\over\phi}v_i(h_{j'})+v_i(h'_{j'})\\ \ge{1\over\phi}(V_i(h_{j'})+v_i(h'_{j'}))=(\phi-1)v_i(A_j)

where the third inequality directly follows from part (b) from lemma 1.

  1. i∉Li\not\in L and hh added in envy-cycle elimination.

Arguing like in case 2, we have vi(Aiold)vi(Ajold)v_i(A_i^{old})\ge v_i(A_{j'}^{old}). Moreover, by the way round-robin works, we know that vi(hi)vi(hi)vi(h)v_i(h_i)\ge v_i(h'_i)\ge v_i(h). In particular, vi(h)12vi({hi,hi})12vi(Aiold)v_i(h)\le{1\over2}v_i(\{h_i,h_i'\})\le{1\over2}v_i(A_i^{old}). Putting things together, we have

vi(Aj)=vi(Ajold)+vi(h)(1+12)vi(Aiold)ϕvi(Ai)vi(Ai)(ϕ1)vi(Aj)v_i(A_j)=v_i(A_{j'}^{old})+v_i(h)\le(1+\frac{1}{2})v_i(A_i^{old})\le\phi\cdot v_i(A_i)\\ \Lrarr v_i(A_i)\ge(\phi-1)v_i(A_j)

The analysis is tight.

Groupwise Maximin Share Fairness

Every exact EFX allocation is also a 474\over7-GMMS allocation. (Amanatidis et al.)

❗🤔Lemma 3: Suppose TΠn(M)\mathcal T\in\Pi_n(M) is an nn-maximin share defining partition for agent ii. Then, for any set of goods SS, such that there exists some jj with STjS\subseteq T_j, it holds that μi(n1,MS)μi(n,M)\mu_i(n-1,M\diagdown S)\ge\mu_i(n,M).

❗🤔Theorem 4: The allocation A=(A1,,An)\mathcal A=(A_1,\cdots,A_n) returned by Draft and Eliminate Algorithm is a 2ϕ+22\over\phi+2-GMMS allocation.

To difficult for me! 😭

Omitted

❗🤔 Theorem 5: Suppose we modified Draft and Eliminate Algorithm by changing ϕ\phi in preprocessing to 323\over2. Then the resulting allocation is a 4/74/7-GMMS allocation. It is also a 3/53/5-EFX, 2/32/3-PMMS, and EF1 allocation.

To difficult for me! 😭

Omitted

Analysis are probably not tight, because both theorems is heavily based on EF and EFX guarantees we get in the various different cases.

❓Suspect: modified draft and eliminate algorithm produces 2/32/3-GMMS.

Pairwise Maximin Share Fairness

❗🤔Theorem 6: The allocation A=(A1,,An)\mathcal A=(A_1,\cdots,A_n) returned by Draft and Eliminate Algorithm is a 2/32/3-PMMS allocation.

Proof based on proof of theorem 3.

2/32/3 factor is tight. But if we manipulate envy-graph as following, the approximation ratio goes up to 2ϕ+10.764{2\over\phi+1}\approx0.764: Detail omitted

❗🤔Theorem 7: Supposed we modified Draft and Eliminate Algorithm by using the ϕ12\phi-{1\over2}-adjusted envy graph in Envy-graph Elimination. Then the resulting allocation is a 4ϕ22ϕ+34\phi-2\over2\phi+3-PMMS and a 22ϕ12\over2\phi-1-EF1 allocation. Moreover, the theorem 3 and theorem 4 are not affected.

Proof omitted.

GMMS, PMMS, and EFX with a few Goods

For the exact versions of fairness notions,

Draft Pack and Eliminate Pseudo Code

  1. Let =(1,2,,n)\ell=(1,2,\cdots,n) and A=(,,)\mathcal A=(\empty,\cdots,\empty)
  2. (A,M)=(\mathcal A,M')= Round-Robin(N,A,M,,n1)(N,\mathcal A,M,\ell,n-1)
  3. Create 2 virtual goods p,qp,q, s.t. iN:vi(q)=mingM\forall i\in N:v_i(q)=\min_{g\in M'} and vi(p)=vi(M)vi(q)v_i(p)=v_i(M')-v_i(q)
  4. Allocate pp to agent nn
  5. A=\mathcal A= Envy-Cycle Elimination(N,A,{q})(N,\mathcal A,\{q\})
  6. Give to the final owner of pp her two favorite goods from MM' and to the final owner of qq the remaining good
  7. return A\mathcal A.

❗🤔Theorem 8: For instances with mn+2m\le n+2, a GMMS allocation always exists and can be efficiently computed.

When mnm\le n, we arbitrarily allocate one good to each agent, till there are no goods left, to produce A=(A1,,An)\mathcal A=(A_1,\cdots,A_n). Fix a subset SS of agents, and let iNi\in N. Then combined bundle of all agents in SS either contains strictly less than S|S| goods or exactly S|S| goods.

  • In the first case, we trivially have μi(S,jSAj)=0\mu_i(|S|,\cup_{j\in S}A_j)=0.

  • In the second case, we have μi(S,jSAj)=mingjSAjvi(g)\mu_i(|S|,\cup_{j\in S}A_j)=\min_{g\in\cup_{j\in S}A_j}v_i(g).

In both cases, we have vi(Ai)μi(S,jSAj)v_i(A_i)\ge\mu_i(|S|,\cup_{j\in S}A_j), and A\mathcal A is a GMMS allocation.

For m>nm\gt n, there are some simple observations.

❗🤔Lemma 4: Let QNQ\subseteq N and TMT\subseteq M s.t. T=2Q1|T|=2|Q|-1. Then, for any iQi\in Q, we have maxgTvi(g)μi(Q,T)\max_{g\in T}v_i(g)\ge\mu_i(|Q|,T).

By the pigeonhole principle, in any possible partition of TT in Q|Q| parts, at least one bundle will have at most 11 goods. So, in any Q|Q|-maximin share partition of TT for an agent iQi\in Q, her worst bundle’s worth is upper bounded by maxgTvi(g)\max_{g\in T}v_i(g).

❗🤔Lemma 5: Let iNi\in N and T={g1,g2,g3,g4}MT=\{g_1,g_2,g_3,g_4\}\subseteq M s.t. vi(g1)vi(g2)vi(g3)vi(g4)v_i(g_1)\ge v_i(g_2)\ge v_i(g_3)\ge v_i(g_4). Then

  1. vi({g1,g4})μi(2,T)v_i(\{g_1,g_4\})\ge\mu_i(2,T)
  2. max{vi(g1),vi({g2,g3})}μi(2,T)\max\{v_i(g_1),v_i(\{g_2,g_3\})\}\ge\mu_i(2,T)

Long proof…

Corollary: When mn+2m\le n+2, we can efficiently find PMMS and EFX allocations.

Proof omitted…

What should I get from this paper?

EF1\LarrEFX\LarrPMMS, GMMS

EF1: Always exist.

EFX: 0.6180.618

PMMS: 2/32/3

GMMS: Not always exist.

We are trying to relax the properties as less as possible so that a single allocation satisfies all relaxation, and if possible, with allocation computed is polynomial time.