Objective: Investigate alternative fairness concepts for allocating indivisible items.

Activities: Read and present the paper New Fairness Concepts for Allocating Indivisible Items by Ioannis et al. IJCAI2023

🍬Bonus: Methodology

After reading some papers in fair division with indivisible items. I have come up with a naive 👓 methodology about research in this field.

  1. Definition of Fairness Notions: This initial phase entails defining various fairness notions and exploring how these concepts can be adapted or extended to the context of indivisible items.
  2. Existence of Fair Allocation: Here, the focus lies on establishing the existence of fair allocations. This step often involves rigorous theorem proving or setting forth conditions under which fair allocations are guaranteed to exist. Mathematical analysis, combinatorial arguments, and computational complexity analysis may all come into play here. (I recognize this to be a particularly challenging step from my current perspective.)
  3. Computational Feasibility: Assuming the existence of fair allocations is assured, the next question revolves around the ease of computing such allocations. The objective here is to ascertain whether these allocations can be computed efficiently, ideally within polynomial time complexity. This phase typically involves grappling with a plethora of lemmas and theorems, much akin to the challenges encountered in Step 2.
  4. Exploration of Latent Relations Among Fairness Notions: Finally, it’s crucial to delve into the underlying relationships among different fairness notions, uncovering their interconnectedness and potential implications.

Abstract

Fair notions:

  • EFX existence for more than 3 agents - open problem

  • MMS not always exist

This paper proposes two new fairness concepts:

  • epistemic EFX, abbr. EEFX
  • minimum EFX share fairness, abbr. MXS

EEFX and MXS always exist and can be computed efficiently for additive valuations.

Introduction

Contribution

3 desideratum:

  1. Intuitively close to envy-freeness and proportionality
  2. always feasible
  3. efficiently computable (polynomial time)

EEFX

Epistemic EFX. An allocation is EEFX if \forall agent, it is possible to shuffle the items in the remaining bundles so that she becomes “EFX-satisfied”.

An example given.

EEFX is particularly relevant in environments in which each agent knows the allocation instance but her knowledge of the allocation is limited to the contents of her bundle.

The the agent is as optimistic as possible to evaluate her bundle. Which means she doesn’t know the partition and allocation for items not allocated to her.

She compares it with each bundle in the allocation of the remaining items that would be best possible for her.

In contrast to EEFX: EF, EF1, EFX are knowledge-sensitive.

MXS

Minimum envy-freeness up to any good share

It’s a threshold for each agent.

The minimum EFX share of an agent is the minimum value she has among all allocations in which she is EFX-satisfied.

Similar in spirit to PROP and MMS.

Relations Among Them

Every MMS is EEFX, every EEFX is MXS, every MXS is PROP1.

MMSEEFXMXSPROP1MMS\subset EEFX\subset MXS\subset PROP1

This paper also presents a polynomial-time algorithm for EEFX (ofc MXS).

Key ideas:

  • ordered instance

  • envy-cycle elimination

  • same algorithm in Paper on MMS (read last week) to compute 23\frac{2}{3}-MMS.

  • computing the minimum EFX share is NP-hard. Thus any efficient algorithm for computing MXS allocation cannot make use of the minimum EFX share.

Definitions and Notation

[k][k] denotes {1,2,,k}\{1,2,\cdots,k\}

Fair division instance I\mathcal I:

  • nn agents [n][n]
  • mm indivisible items [m][m]
  • each agent ii has vi(g)g[m]v_i(g)\forall g\in[m].
  • additive valuations

Ordered instance: The valuations of all agents for the items have a common ordering, i.e.,

\forall i,i'\in[n]\and g,g'\in[m],v_i(g)\ge v_i(g')\Lrarr v_{i'}(g)\ge v_{i'}(g')

An allocation X=(X1,X2,,Xn)X=(X_1,X_2,\cdots,X_n) in which XiXj=ijX_i\cap X_j=\empty\forall i\neq j and i=1nXi=[m]\bigcup_{i=1}^nX_i=[m].

Γ\Gamma denotes the set of all allocations of a given instance.

Definition of EFX: omitted

Definition of EEFX and EEFX certificates: For a fair division instance, an allocation XX is called EEFX if for every agent ii, there exists an allocation YY s.t. Yi=XiY_i=X_i and agent ii is EFX-satisfied with YY. We refer to such an allocation YY as an EEFX certificate of agent ii for bundle XX.

In other words, an allocation XX is EEFX if there exists an EEFX certificate \forall agent w.r.t. her bundle in XX.

Trivially, EFX is EEFX: EFXEEFXEFX\subset EEFX.

Definition of MMS: omitted

Definition of EFX-satisfied w.r.t. ii:

EFXi={ZΓ:vi(Zi)maxgZj:vi(g)>0vi(Zj{g}),j[n]}EFX_i=\{Z\in\Gamma:v_i(Z_i)\ge\max_{g\in Z_j:v_i(g)\gt0}v_i(Z_j\diagdown\{g\}),\forall j\in[n]\}

Definition of MXS: For a fair division instance, minimum EFX share for ii is

MXSi=minZEFXivi(Zi).MXS_i=\min_{Z\in EFX_i}v_i(Z_i).

ZZ is an MXS allocation if vi(Zi)MXSii[n]v_i(Z_i)\ge MXS_i\forall i\in[n].

Definition of PROP1: omitted

Relations to Other Fairness Concepts

MMSTheorem 2EEFXTheorem 1MXSTheorem 3PROP1MMS\stackrel{\text{Theorem 2}}\Longrightarrow EEFX\stackrel{\text{Theorem 1}}\Longrightarrow MXS\stackrel{\text{Theorem 3}}\Longrightarrow PROP1

🎯🤔Theorem 1. EEFXMXSEEFX\Rarr MXS.

Let XX denote an EEFX allocation.

Fixing an agent ii, we will prove vi(Xi)v_i(X_i) is at least as high as her minimum EFX share.

By definition, XX is EEFX, \exist an EEFX certificate Y=(Y1,,Yn)Y=(Y_1,\cdots,Y_n) for agent ii s.t. Yi=XiY_i=X_i and YEFXiY\in EFX_i, thus

vi(Xi)=vi(Yi)minZEFXivi(Zi)=MXSi.v_i(X_i)=v_i(Y_i)\ge\min_{Z\in EFX_i}v_i(Z_i)=MXS_i.

Q. E. D.

MXS⇏EEFXMXS\not\Rarr EEFX. By giving an example.

🎯🤔Theorem 2. MMSEEFXMMS\Rarr EEFX.

For an allocation ZZ and an agent ii.

rZ,ir^{Z,i} denotes the (n1)(n-1)-entry vector with entries the values vi(Zj)v_i(Z_j) for j[n]{i}j\in[n]\diagdown\{i\}, sorted in non-decreasing order, i.e., the vector rZ,i=r1Z,i,r2Z,i,,rn1Z,ir^{Z,i}=\langle r_1^{Z,i},r_2^{Z,i},\cdots,r_{n-1}^{Z,i}\rangle satisfies rtZ,irt+1Z,ir_t^{Z,i}\le r_{t+1}^{Z,i} for t[n2]t\in[n-2].

Let XX be an MMS allocation in the fair division instance and i[n]i\in[n] any agent. Let YY be an allocation with Yi=XiY_i=X_i so that rY,ir^{Y,i} is lexicographically minimum.

It remians to prove that: YY is an EEFX certificate for agent ii and bundle XiX_i, which means that the allocation is also EEFX.

  • Assume otherwise. Then by definition, there exists j1[n]{i}j_1\in[n]\diagdown\{i\} so that for the item gYj1g\in Y_{j_1} for which agent ii has the minimum non-zero value among the items in Yj1Y_{j_1}, it holds

    vi(Xi)<vi(Yj1)vi(g)v_i(X_i)\lt v_i(Y_{j_1})-v_i(g)

  • Now, assume that vi(Yj)>vi(Xi)v_i(Y_j)\gt v_i(X_i) for every j[n]{i}j\in[n]\diagdown\{i\}. Then for the allocation ZZ' that is obtained from YY after removing item gg from bundle Yj1Y_{j_1} and adding it to bundle YiY_i, we obtain an allocation in which vi(Zj)>vi(Xi)MMSiv_i(Z_j')\gt v_i(X_i)\ge MMS_i for every j[n]j\in[n]. This follows by assumption for j[n]{i,j1}j\in[n]\diagdown\{i,j_1\}, since vi(g)>0v_i(g)\gt0 for j=ij=i, and by above inequality for j=j1j=j_1 since vi(Zj1)=vi(Yj1)vi(g)>vi(Xi)v_i(Z_{j_1}')=v_i(Y_{j_1})-v_i(g)\gt v_i(X_i). The existence of allocation ZZ' contradicts the fact that allocation XX is MMS.

  • So there must be j2[n]{i,j1}j_2\in[n]\diagdown\{i,j_1\} s.t. vi(Yj2)vi(Xi)v_i(Y_{j_2})\le v_i(X_i). Now consider the allocation ZZ'' obtained after removing item gg from bundle Yj1Y_{j_1} and adding it to bundle Yj2Y_{j_2}. Notice that vi(Zj)=vi(Yj)v_i(Z''_j)=v_i(Y_j) for j[n]{j1,j2}j\in[n]\diagdown\{j_1,j_2\}, vi(Zj1)=vi(Yj1)vi(g)vi(Yj1)v_i(Z''_{j_1})=v_i(Y_{j_1})-v_i(g)\le v_i(Y_{j_1}) and vi(Zj2)=vi(Yj2)+vi(g)vi(Xi)+vi(g)vi(Yj1)v_i(Z''_{j_2})=v_i(Y_{j_2})+v_i(g)\le v_i(X_i)+v_i(g)\le v_i(Y_{j_1}), using the definition of j2j_2 and inequality above, rZ,ir^{Z'',i} is lexicographically smaller than rY,ir^{Y,i} and furthermore, Zi=XiZ''_i=X_i, contradicting the assumption on YY. Q. E. D.

EEFX allocations always exist, but not for MMS.

🎯🤔Theorem 3. An MXS allocation in a fair division instance is also PROP1.

Consider a fair division instance and let XX be an MXS allocation.

The proportionality up to one good constraints are satisfied for every agent ii with MXSi=PSiMXS_i=PS_i.

Now, consider an agent ii with MXSi<PSiMXS_i\lt PS_i, we will show XX satisfies the PROP1 constraints for agent ii as well.

Assume otherwise: vi(Xi)<PSivi(g)v_i(X_i)\lt PS_i-v_i(g) for every item g[m]Xig\in[m]\diagdown X_i. Let YY be an allocation in EFXiEFX_i s.t. vi(Yi)=MXSi<PSiv_i(Y_i)=MXS_i\lt PS_i:

  • Since j[n]vi(Yj)=nPSi\sum_{j\in[n]}v_i(Y_j)=n\cdot PS_i, there k[n]{i}\exist k\in[n]\diagdown\{i\} s.t. vi(Yk)>PSiv_i(Y_k)\gt PS_i.

  • By assumption inequality, we have vi(Yk)>vi(Xi)v_i(Y_k)\gt v_i(X_i), meaning that g\exist g^* that belongs to YkY_k but not to XiX_i. By the definition of EFXiEFX_i, we have

MXSi=vi(Yi)vi(Yk)vi(g)>PSivi(g)MXS_i=v_i(Y_i)\ge v_i(Y_k)-v_i(g^*)\gt PS_i-v_i(g^*)

and using assumption inequality, we get

vi(Xi)<PSivi(g)<MXSi,v_i(X_i)\lt PS_i-v_i(g^*)\lt MXS_i,

contradicting the fact that allocation XX is MXS.

The opposite implication is not true.

Existence and Efficient Computation of EEFX

🎯🤔theorem 4. In any fair division instance, an EEFX allocation exists and can be computed in polynomial time.

Pseudo-code for Computing EEFX Allocations

Input: A fair division instance I\mathcal I

Output: An allocation XX in I\mathcal I that satisfies EEFX

  1. I\mathcal I'\gets Order(I)(\mathcal I)

    This step creates an ordered instance I\mathcal I' by modifying instance I\mathcal I. Instance I\mathcal I' has the same set of agent as I\mathcal I. The items of I\mathcal I are arbitrarily renamed as g1,,gmg_1,\cdots, g_m and the valuation viv_i' of agent i[n]i\in[n] is defined as follows:

    • for j[m]j\in[m], the valuation vi(gj)v_i'(g_j) of agent ii for the item gjg_j is the jj-th highest value in the multiset {vi(g1),,vi(gm)}\{v_i(g_1),\cdots,v_i(g_m)\}.
  2. XX'\gets EvcyCycleElimination(I)(\mathcal I')

  3. LL\gets PickingSequence(I,X)(\mathcal I',X')

    It takes as input instance I\mathcal I' and allocation XX' and computes the picking sequence L=[L1,,Lm]L=[L_1,\cdots,L_m] as follows:

    • For j[m]j\in[m], LjL_j is the agent who gets item gjg_j in allocation XX' i.e., gjXLjg_j\in X'_{L_j}
  4. XX\gets Pick(I,L)(\mathcal I,L)

    This step is executed with input the instance I\mathcal I and picking sequence LL to compute the allocation XX as follows:

    • Pick runs mm rounds, one for each item.
    • In round jj, agent LjL_j picks the highest-valued item that has not been allocated to any agent in round before.
  5. return XX

To prove theorem 4, we need lemma 1,2 and 3.

🤔Lemma 1. The allocation XX' of instance I\mathcal I' is EFX.

The application of the envy cycle elimination algorithm on ordered fair division instances produces an EFX allocation.

🤔Lemma 2. For every agent i[n]i\in[n], there exists a bijection πi:[m][m]\pi_i:[m]\rarr[m] s.t. the following are true:

  • πi(g)Xi\pi_i(g)\in X_i and vi(πi(g))vi(g)gXiv_i(\pi_i(g))\ge v_i'(g)\forall g\in X_i'.
  • πi(g)∉Xi\pi_i(g)\not\in X_i and vi(πi(g))vi(g)gXiv_i(\pi_i(g))\le v_i'(g)\forall g\notin X_i'.

Let i[n]i\in[n] be an agent. We will refer to the item using the remaining g1,,gmg_1,\cdots,g_m used by routine Order. Let σi:[m][m]\sigma_i:[m]\rarr[m] be a permutation s.t. gσi(j)g_{\sigma_i(j)} is agent ii’s jj-th most valuable item according to valuation function viv_i.

Formally, for every j1,j2[m]j_1,j_2\in[m] s.t. j1<j2j_1\lt j_2, we have vi(gσi(j1))vi(gσi(j2))v_i(g_{\sigma_i(j_1)})\ge v_i(g_{\sigma_i(j_2)}), the tie between items gσi(j1)g_{\sigma_i(j_1)} and gσi(j2)g_{\sigma_i(j_2)} is resolved in favour of gσi(j1)g_{\sigma_i(j_1)} during the execution of routine Pick in step 4 of algorithm. By the difinition of the ordered instance I\mathcal I', it holds that vi(gσi(j))=vi(gj)v_i(g_{\sigma_i(j)})=v_i'(g_j) for every j[m]j\in[m].

We define πi\pi_i: For every item gjXig_j\in X_i', define πi(gj)\pi_i(g_j) to be item picked in round jj of the execution of Pick in step 4 of algorithm. For k=1,,mXik=1,\cdots,m-|X_i'|, consider the item gg that is kk-th in the ordering g1,,gmg_1,\cdots,g_m, ignoring the items in XiX_i'. Set πi(g)\pi_i(g) to be the kk-th item in the ordering gσi(1),,gσi(m)g_{\sigma_i(1)},\cdots, g_{\sigma_i(m)}, ignoring the items in XiX_i.

πi\pi_i is a bijection. By definition of picking sequence LL, for every item gjXig_j\in X_i', it is agent ii who picks at round jj of the execution of Pick at step 4 of algorithm, and thus πi(gj)Xi\pi_i(g_j)\in X_i. The definition of πi(gj)\pi_i(g_j) for every gj∉Xig_j\not\in X_i' ensures that πi(gj)∉Xi\pi_i(g_j)\not\in X_i,

🤔Lemma 3. Allocation XX is EEFX.

Consider agent ii and let πi\pi_i be the bijection define in lemma 2. Define allocation YY with Yj={πi(g):gXj}Y_j=\{\pi_i(g):g\in X_j'\} for j[n]j\in[n], Since πi\pi_i is a bijection, allocation YY is well-defined. Also by lemma 2, Yi=XiY_i=X_i. It remains to prove that YY is an EEFX certificate for ii with XiX_i.

Let jij\neq i and gg^* be the item of bundle XjX_j' s.t. πi(g)\pi_i(g^*) has minimum non-zero value according to viv_i. Thus proving vi(Yi)vi(Yjπi(g))v_i(Y_i)\ge v_i(Y_j\diagdown\pi_i(g^*)) is enough to complete the proof.

Since g∉Xig^*\not\in X_i' and vi(πi(g))>0v_i(\pi_i(g^*))\gt0, lemma 2 implies that π(g)>0\pi(g^*)\gt0. Then, the fact that XX' is EFX w.r.t. the valuations vv' implies

vi(Xi)vi(Xj{g})v_i'(X_i')\ge v_i'(X_j'\diagdown\{g^*\})

Now the properties of πi\pi_i from lemma 2 yield

vi(Yi)=gXivi(πi(g))gXivi(g)=vi(Xi)v_i(Y_i)=\sum_{g\in X_i'}v_i(\pi_i(g))\ge\sum_{g\in X_i'}v_i'(g)=v_i'(X_i')

and

vi(Xj{g})=gXj{g}vi(g)gXj{g}vi(πi(g))=vi(Yj{πi(g})v_i'(X_j'\diagdown\{g^*\})=\sum_{g\in X_j'\diagdown\{g^*\}}v_i'(g)\ge\sum_{g\in X_j'\diagdown\{g^*\}}v_i(\pi_i(g))\\ =v_i(Y_j\diagdown\{\pi_i(g^*\})

By applying above 3 equations, we get

vi(Yi)vi(Yj{πi(g)}).v_i(Y_i)\ge v_i(Y_j\diagdown\{\pi_i(g^*)\}).

❓Verifying whether a given allocation is EEFX is currently an open problem.

Corollary: In any fair division instance there exists a Pareto-optimal MXS allocation. Furthermore, an MXS allocation can be computed in polynomial time.

Computing the Minimum EFX Share

Algorithm computing EEFX allocations is without computing the minimum EFX share of any agent at any point of its execution.

🎯🤔Theorem 5. Computing the minimum EFX share of the agents in a fair division instance is NP-hard.

Proof by developing a polynomial time reduction from the NP-hard probelm of BalancedPartition:

  • Given a set NN, containing 2t2t positive integer values s.t.

    h=12txh=2Tt,TN\sum_{h=1}^{2t}x_h=2T\forall t,T\in\mathbb N

  • Does there exist a balanced partition of NN s.t. an equipartition (S,NS(S,N\diagdown S) of the elements in NN (i.e. S=t|S|=t) s.t.

    hSxh=hNSxh?\sum_{h\in S}x_h=\sum_{h\in N\diagdown S}x_h?

Conclusion & Outlook

EEFX & MXS

EFX0: vi(g)v_i(g) can =0=0. Similarly, EEFX0, MXS0.

MMS does not imply EEFX0.

❓Open problem: Are there EEFX allocations with better MMS guarantees possible? Cam they be computed in polynomial time? Combining EEFX with other fairness properties. Are there EEFX allocations that are also EF1?

Is Pareto-optimal EEFX allocations exist?

EEFX has a low price of fairness.

The main result holds for chores as well.

How about non-additive valuations?