Objective: Explore the concept of the Price of Fairness and Maximin Share (MMS) property.

Activities: Read and present paper Optimal Bounds on the Price of Fairness for Indivisible Goods (2020) and Approximation Algorithms for Maximin Fair Division (2020).

Paper on PoF

Price of Fairness measures the worst-case loss of social welfare due to fairness constraints.

This paper: Both EF1 and 12{1\over2}-MMS guarantees has PoF O(n)O(\sqrt n), where nn is number of agents.

  • For 12{1\over2}-MMS, this bound holds for additive valuations.
  • For EF1, this bound holds for more general class of subadditive valuations.

Introduction

EF family omitted here

MMS family

  • 343\over4-MMS always exist.

Fair is not the only objective of interest, another criterion is the social welfare.

Tradeoff between fairness and social welfare is measure by price of fairness, the supremum ratio of the maximum welfare of any allocation to the maximum welfare of any allocation satisfying the desired fairness notion. This measures the factor by which welfare may be lost to achieve the desired fairness.

Caragiannis et al. Initiated PoF: PoF of Envy-freeness is between Ω(n)\Omega(\sqrt n) and O(n)O(n).

Beretsimas et al. Closed the gap, bound the PoF to Θ(n)\Theta(\sqrt n), matching upper bound can be achieved by maximizing the Nash welfare.

For Indivisible goods and additive valuations

  • Bei et al. showed PoF of EF1 is between Ω(n)\Omega(\sqrt n) and O(n)O(n).

Contributions

Price of EF1 is O(n)O(n): subadditive valuation function

Price of PROP1: Θ(n)\Theta(n)

Price of 12{1\over2}-MMS: Θ(n)\Theta(\sqrt n). For a fixed ϵ>0\epsilon\gt0, a (12ϵ)(\frac{1}{2}-\epsilon)-MMS allocation with welfare with O(n)O(\sqrt n) factor of the optimal can be computed in polynomial time.

Preliminaries

Set [m][m] of indivisible goods

Set [n][n] of agents

Agent valuations. Each agent i[n]i\in[n] has non-negative valuation over goods.

2 valuation classes:

  • Additive vi(A+B)=vi(A)+vi(B)v_i(A+B)=v_i(A)+v_i(B)

  • Subadditive vi(A+B)vi(A)+vi(B)v_i(A+B)\le v_i(A)+v_i(B)

    (Additive \subset Subadditive)

Oracle access.

  • Value query: Input ii and S[m]S\subset[m] output vi(S)v_i(S).
  • Demand query: Input ii and price pgR0p_g\in\mathbb R_{\ge0} for each g[m]g\in[m], output a profit-maximizing set SargmaxS[m]vi(S)gSpgS^*\in\arg\max_{S\in[m]}v_i(S)-\sum_{g\in S}p_g.

Allocations. omitted here

Fairness. omitted here

Social welfare. The SW of allocation A\mathcal A, is defined as the sum of the values that the agents derive from the allocation: SW(A)=i=1nvi(Ai)SW(\mathcal A)=\sum_{i=1}^nv_i(A_i). Maximum social welfare allocation: W=(W1,W2,,Wn)\mathcal W^*=(W_1^*,W_2^*,\cdots,W_n^*).

WargmaxAΠn([m])SW(A)\mathcal W^*\in\arg\max_{\mathcal A\in\Pi_n([m])}SW(\mathcal A)

OPTOPT denote the optimal social welfare, i.e., OPT=SW(W)OPT=SW(\mathcal W^*).

Price of fairness.

PoF=SW(W)maxAFair AllocationSW(A)PoF={SW(\mathcal W^*)\over\max_{\mathcal A\in\text{Fair Allocation}}SW(\mathcal A)}

Scaling. This paper considers both scaled and unscaled valuations of agents’ valuations.

What does scaling here means

To ensure that agent valuations are on the same scale, much of the literature on fair division assumes that agent valuations are scaled, i.e. vi([m])=1i[n]v_i([m])=1\forall i\in[n]. Nothing that unscaled valuations are common in other areas of social choice.

In my words, scaled means for all agents, their valuations for all the goods are the same.

My question: Must the valuation here be additive?

Price of EF1

🎯🤔Theorem 1 The price of EF1 is O(n)O(\sqrt n) for scaled subadditive valuations and Θ(n)\Theta(n) for unscaled subadditive valuations. Both bounds are tight even when the valuations are additive.

An Absolute Welfare Guarantee

First, we show that when agents have subadditive valuations {vi}i[n]\{v_i\}_{i\in[n]} (not necessarily scaled), there always exists an EF1 allocation A\mathcal A with social welfare SW(A)12ni=1nvi([m])SW(\mathcal A)\ge{1\over2n}\sum_{i=1}^nv_i([m]).

2 implications:

i=1nvi([m])\because\sum_{i=1}^nv_i([m]) is a trivial upper bound on the optimal social welfare OPT, the result establishes am O(n)O(n) upper bound on the price of EF1.

  • For unscaled valuations, this is exactly the bound.
  • For scaled valuations, we improve this to O(n)O(\sqrt n). Since i=1nvi([m])=n\sum_{i=1}^nv_i([m])=n under scaled valuations, the result gives SW(A)1/2SW(\mathcal A)\ge1/2. Hence, if OPT=O(n)OPT=O(\sqrt n), then we have the desired O(n)O(\sqrt n) upper bound.

This paper will analyze the case when OPT=Ω(n)OPT=\Omega(\sqrt n).

This paper also give an algorithm to produce absolute welfare guarantee.

Pseudo code for Algorithm ALF-EF1-ABS:

Input: Fair-division instance I=[n],[m],{vi}i[n]\mathcal I=\lang[n],[m],\{v_i\}_{i\in[n]}\rang with value-query oracle access to the subadditive valuations viv_is.

Output: An EF1 allocation B\mathcal B with SW(B)12ni[n]vi([m])SW(\mathcal B)\ge{1\over2n}\sum_{i\in[n]}v_i([m]).

  1. Consider the weighted bipartite graph G=([n][m],[n]×[m])G=([n]\cup[m],[n]\times[m]) with weight of each edge (i,g)[n]×[m](i,g)\in[n]\times[m] set as vi(g)v_i(g). Let π\pi be a maximum-weight matching in GG that matches all nodes in [n][n].
  2. Construct the partial allocation B\mathcal B' s.t. Bi={π(i)}\mathcal B_i'=\{\pi(i)\} for each i[n]i\in[n].
  3. Use the algorithm of Lipton et al to extend the partial EF1 allocation B\mathcal B' into a complete EF1 allocation B\mathcal B s.t. vi(Bi)vi(Bi)v_i(B_i)\ge v_i(B_i') for each agent i[n]i\in[n].s
  4. return allocation B\mathcal B

🤔Lemma 1. Let I=[n],[m],{vi}i[n]\mathcal I=\lang[n],[m],\{v_i\}_{i\in[n]}\rang be a fair-division instance in which agent valuations are subadditive. Then, given value-query oracle access to the valuations, ALG-EF1-ABS algorithm efficiently computes an EF1 allocation B\mathcal B with social welfare SW(B)12ni[n]vi([m])SW(\mathcal B)\ge{1\over2n}\sum_{i\in[n]}v_i([m]).

For each agent i[n]i\in[n], sort the goods as gi1,,gimg_{i_1},\cdots,g_{i_m} in a non-decreasing order of their value to agent ii i.e. vi(gi1)vi(gim)v_i(g_{i_1})\ge\cdots\ge v_i(g_{i_m}), and let Gi={gi1,,gin}G_i=\{g_{i_1},\cdots,g_{i_n}\} be the set of nn most valuable goods to agent ii.

Consider a subgraph G=([n][m],E)G'=([n]\cup[m],E') of the weighted bipartite graph GG constructed in line 1 of the algorithm, in which we only retain the edges E={(i,g):i[n],gGi}E'=\{(i,g):i\in[n],g\in G_i\} (i.e. from each agent ii to her nn most valuable goods). Because GG' is nn-left-regular, it can be decomposed into nn disjoint left-perfect matchings M1,,MnM_1,\cdots,M_n, this is an easy consequence of Halls’ theorem. Due to the pigeonhole principle, one of M1,,MnM_1,\cdots,M_n must have weight at least 1n1\over n. We have

i[n]vi(π(i))=SW(B)1ni[n],gGivi(g)\sum_{i\in[n]}v_i(\pi(i))=SW(\mathcal B')\ge{1\over n}\cdot\sum_{i\in[n],g\in G_i}v_i(g)

B\mathcal B' assigns a single good to each agent; hence, it is trivially EF1. The algorithm makes sure that B\mathcal B is the extension of B\mathcal B' s.t. vi(Bi)vi(Bi)v_i(B_i)\ge v_i(B_i'). Thus,

SW(B)1ni[n]gGivi(g)SW(\mathcal B)\ge{1\over n}\sum_{i\in[n]}\sum_{g\in G_i}v_i(g)

B\mathcal B is EF1, thus for each i,j[n]i,j\in[n], there exists SjBjS_j\subseteq B_j with Sj1|S_j|\le1 s.t. vi(Bi)vi(BjSj)vi(Bj)vi(Sj)v_i(B_i)\ge v_i(B_j\diagdown S_j)\ge v_i(B_j)-v_i(S_j) (subadditive for last inequality). Summing this inequality over j[n]j\in[n], we get

nvi(Bi)j[n]vi(Bj)j[n]vi(Sj)vi([m])j[n]vi(Sj)vi([m])gGivi(g),n\cdot v_i(B_i)\ge\sum_{j\in[n]}v_i(B_j)-\sum_{j\in[n]}v_i(S_j)\\ \ge v_i([m])-\sum_{j\in[n]}v_i(S_j)\ge v_i([m])-\sum_{g\in G_i}v_i(g),

where the penultimate inequality holds because BjB_js form a partition of [m][m] and the last inequality follows from subadditivity. SjS_js are disjoint and have cardinality at most 11, and GiG_i is the set of nn most valuable goods to ii. Summing over i[n]i\in[n], we get

ni[n]vi(Bi)=nSW(B)i[n]vi([m])i[n]gGivi(g).n\cdot\sum_{i\in[n]}v_i(B_i)=n\cdot SW(\mathcal B)\ge\sum_{i\in[n]}v_i([m])-\sum_{i\in[n]}\sum_{g\in G_i}v_i(g).

Substituting equation, we get the desired bound

nSW(B)+nSW(B)i[n]vi([m])i[n]gGivi(g)+i[n]gGivi(g)=i[n]vi([m])n\cdot SW(\mathcal B)+n\cdot SW(\mathcal B)\ge\sum_{i\in[n]}v_i([m])-\sum_{i\in[n]}\sum_{g\in G_i}v_i(g)+\sum_{i\in[n]}\sum_{g\in G_i}v_i(g)\\ =\sum_{i\in[n]}v_i([m])

which implies SW(B)12ni[n]vi([m])SW(\mathcal B)\ge{1\over 2n}\sum_{i\in[n]}v_i([m]) as needed.

The Case of High Optimal Welfare

Lemma 1 focuses on fair division with scaled subadditive valuations in which the optimal social welfare is Ω(n)\Omega(\sqrt n), which means we can sacrifice O(n)O(\sqrt n) of the welfare in OPT, obtain O(n)O(\sqrt n) approximation to the remaining welfare through an EF1 allocation, and yet achieve O(n)O(\sqrt n) approximation to OPT.

In particular, this paper presents an algorithm that efficiently finds an EF1 allocation A\mathcal A with social welfare SW(A)OPT2n12nSW(\mathcal A)\ge{OPT-2\sqrt n\over12\sqrt n}.

W\mathcal W^* corresponds to optimal social welfare OPTOPT.

However, for subadditive valuations, computing such an allocation is NP-hard under both value queries and demand queries.

Using a polynomial number of value queries, it’s Θ(m)\Theta(\sqrt m) best possible approximation to the optimal social welfare. (Too loose)

Starting with high-welfare allocation W\mathcal W returned by Feige’s Algorithm, the algorithm works as follows: It first indexes mm goods as g1,,gmg_1,\cdots,g_m s.t. the goods n each WiW_i receive consecutive indices. Alternatively, consider a line graph L=([m],E)L=([m],E) over the set of goods with edges E={(gk,gk+1):k[m1]}E=\{(g_k,g_{k+1}):k\in[m-1]\}. Then each WiW_i induces a connected subgraph of LL.

Definition of line graph: Let L=([m],E)L=([m],E) be a line graph over the goods, we say that S[m]S\subseteq[m] is a connected bundle in LL if SS induces a connected subgraph of LL. Given a partial allocation P\mathcal P, define U(P)\mathcal U(\mathcal P) as the set of connected components of LL that remain after moving the allocated goods i[n]Pi\cup_{i\in[n]}P_i. We refer to UU(P)U\in\mathcal U(\mathcal P) as an unassigned connected bundle.

Algorithm ALG-EF1-HIGH builds a partial allocation P\mathcal P by giving each agent ii her most valuable good from WiW_i. This allocation satisfies: EF1, and each PiP_i is a connected bundle in LL. (trivial) The algorithm then iteratively updates P\mathcal P to improve its social welfare while maintaining both properties.

In particular, at every iteration, the algorithm computes the set of unassigned connected bundles U(P)\mathcal U(\mathcal P). Removing nn connected bundles from P\mathcal P can create at most n+1n+1 unassigned connected bundles.

If there is an unassigned connected bundle UU that some agent envies, then the algorithm finds an inclusion-wise minimal subset of UU that is envied and allocates it to an envious agent.

  • This paper argues that inclusion-wise minimality preserves the EF1 of P\mathcal P.
  • This paper also argues that this iterative process terminates at a partial allocation P\mathcal P that satisfies the desired social welfare guarantee.

ALG-EF1-HIGH is extended from Lipton et al, which computes EF1 allocation without losing social welfare.

Pseudo code omitted here.

🤔Lemma 2. When ALG-EF1-HIGH is run on a fair division instance I=[n],[m],{vi}i[n]\mathcal I=\lang[n],[m],\{v_i\}_{i\in[n]}\rang with subadditive valuations, the following hold regarding the partial allocation Pt\mathcal P^t constructed after tt iterations of the while loop.

  1. If t1t\ge1, then for each agent i[n]i\in[n], either Pit=Pit1P_i^t=P_i^{t-1} or vi(Pit)vi(Pit1)v_i(P_i^t)\ge v_i(P_i^{t-1}).
  2. For each agent i[n]i\in[n], PiP_i is a connected bundle under the line graph LL constructed in checking whether there exists agent envying a UU(P)U\in\mathcal U(\mathcal P).
  3. PtP^t is EF1.

1. and 2. are trivial.

For 3., using induction.

🤔Lemma 3. When ALG-EF1-HIGH is run on a fair division instance I\mathcal I with subadditive valuations, the following hold:

  1. The while loop terminates after T=O(nm2)T=O(nm^2) iterations.
  2. The partial allocation PT\mathcal P^T constructed at the end of the while loop satisfies vi(PiT)vi(U)v_i(P_i^T)\ge v_i(U) for every agent i[n]i\in[n] and unassigned connected bundle UU(PT)U\in\mathcal U(\mathcal P^T).

O(m2)O(m^2) possible connected bundles in LL\Rarr an agent’s assignment can only be updated O(m2)O(m^2) times. There are nn agents in total.

The while loop would not have terminated if vi(PiT)<vi(U)v_i(P_i^T)\lt v_i(U) for any agent ii and any unassigned connected bundle UU.

🤔Lemma 4. Given a fair division instance I\mathcal I with scaled subadditive valuations, ALG-EF1-HIGH terminates in polynomial time and returns an EF1 allocation A\mathcal A satisfying

SW(A)OPT12n16.SW(\mathcal A)\ge{OPT\over12\sqrt n}-{1\over6}.

where OPTOPT is the optimal social welfare achievable in instance I\mathcal I.

Feige’s algorithm satisfies SW(W)12OPTSW(\mathcal W)\ge{1\over2}OPT. Let the while loop in ALG-EF1-HIGH terminate with partial allocation P\mathcal P; that is P=PT\mathcal P=\mathcal P^T, where TT is # of iterations. Lemma 3 ensures that the while loop terminates. It suffices to show

n+6nSW(P)SW(W).\sqrt n+6\sqrt n\cdot SW(\mathcal P)\ge SW(\mathcal W).

By lemma 2, P\mathcal P is EF1. Also, note that the algorithm of Lipton et al can extend EF1 allocation P\mathcal P into a complete EF1 allocation A\mathcal A with SW(A)SW(P)SW(\mathcal A)\ge SW(\mathcal P). Hence the inequality above along with SW(W)12OPTSW(\mathcal W)\ge{1\over2}OPT completes the proof of the lemma 4.

Due to lemma 2, each PiP_i is a connected bundle in the line graph LL. Hence, removing the goods allocated in P\mathcal P creates at most n+1n+1 connected components, i.e. U(P)<n+1|\mathcal U(\mathcal P)|\lt n+1. Let T(P)={Pj:j[n]}U(P)\mathcal T(\mathcal P)=\{P_j:j\in[n]\}\cup\mathcal U(\mathcal P) be the collection of the assigned and unassigned in LL created by P\mathcal P. Hence T(P)<2n+1|\mathcal T(\mathcal P)|\lt2n+1. For each agent i[n]i\in[n], let Qi\mathcal Q_i denote the bundles in T(P)\mathcal T(\mathcal P) that intersect with WiW_i, i.e., Qi={ST(P):SWi}\mathcal Q_i=\{S\in\mathcal T(\mathcal P):S\cap W_i\neq\empty\}. write qi=Qiq_i=|\mathcal Q_i|.

While W\mathcal W forms a partition of LL into at most nn connected components. This, along with the observation that LL is a line graph, can be used to bound the total number of intersections between the two. We can move a marker from left to right, keeping track of the bundle from W\mathcal W and the bundle from T(P)\mathcal T(\mathcal P) that contain the current good. Every time the marker encounters a new intersection, it must have entered either a new bundle from WW or a new bundle from T(P)\mathcal T(\mathcal P). Thus, we have

i[n]qi(2n+1)+n=3n+1.\sum_{i\in[n]}q_i\le(2n+1)+n=3n+1.

Next, we partition the set of agents [n][n] based on their qiq_i value. Let H={i[n]:qi>3n}H=\{i\in[n]:q_i\gt3\sqrt n\} and Hc={i[n]:qi3n}H^c=\{i\in[n]:q_i\le3\sqrt n\}. Above inequality implies Hn|H|\le\sqrt n. This along with the observation that the valuation are scaled, gives us

iHvi(Wi)Hn\sum_{i\in H}v_i(W_i)\le|H|\le\sqrt n

Next, we bound vi(Wi)v_i(W_i) for iHci\in H^c. By definition of Qi\mathcal Q_i, we have vi(Wi)=SQivi(SWi)v_i(W_i)=\sum_{S\in\mathcal Q_i}v_i(S\cap W_i). We break the sum into 2 parts, SU(P)S\in\mathcal U(\mathcal P) or SPS\in\mathcal P.

  1. If SU(P)S\in\mathcal U(\mathcal P), by lemma 3, we have vi(SWi)vi(S)vi(Pi)2vi(Pi)v_i(S\cap W_i)\le v_i(S)\le v_i(P_i)\le 2v_i(P_i).
  2. If SPS\in\mathcal P, then S=PjS=P_j for some agent j[n]j\in[n]. Let P^j=PjWi\hat P_j=P_j\cap W_i. By definition of Qi\mathcal Q_i, P^j\hat P_j\neq\empty. P\because\mathcal P is EF1 and viv_i is monotone, agent ii does not envy the bundle PjP_j up to one good in it. Thus, there exists a good g^P^j\hat g\in\hat P_j s.t. vi(Pi)vi(P^j{g^})vi(P^j)vi(g^)v_i(P_i)\ge v_i(\hat P_j\diagdown\{\hat g\})\ge v_i(\hat P_j)-v_i(\hat g), where the last transition uses subadditivity of viv_i. Further, g^P^jWi\hat g\in\hat P_j\subseteq W_i. The initialization and lemma 2 ensure that vi(g^)vi(Pi0)vi(Pi)v_i(\hat g)\le v_i(P_i^0)\le v_i(P_i). Combining with the previous step, we have vi(SWi)=vi(P^j)2vi(Pi)v_i(S\cap W_i)=v_i(\hat P_j)\le2v_i(P_i).

Thus, for iHci\in H^c, we have vi(Wi)Qi2vi(Pi)3n2vi(Pi)v_i(W_i)\le|\mathcal Q_i|\cdot2v_i(P_i)\le3\sqrt n\cdot2v_i(P_i). Thus, we get

SW(W)n+6niHcvi(Pi)n+6nSW(P)SW(\mathcal W)\le\sqrt n+6\sqrt n\sum_{i\in H^c}v_i(P_i)\le\sqrt n+6\sqrt n\cdot SW(\mathcal P)

which is desired. Q.E.D.

Proof of Theorem 1

Proof for upper bounds

For unscaled valuations, lemma 1 shows that there exists an EF1 allocation B\mathcal B with SW(B)12ni[n]vi([m])12nOPTSW(\mathcal B)\ge{1\over2n}\sum_{i\in[n]}v_i([m])\ge{1\over2n}OPT, which yields the desired O(n)O(n) bound.

For an instance I\mathcal I with scaled valuations, we consider 2 cases: OPT8nOPT\le8\sqrt n or OPT>8nOPT\gt8\sqrt n.

Case 1: OPT8nOPT\le8\sqrt n. \because valuations are scaled. Lemma 1 implies that the EF1 allocation B\mathcal B returned by ALG-EF1-ABS satisfies SW(B)12ni[n]vi([m])=12SW(\mathcal B)\ge{1\over2n}\sum_{i\in[n]}v_i([m])={1\over2}. Hence, SW(B)116nOPTSW(\mathcal B)\ge{1\over16\sqrt n}OPT,

Case 2: OPT>8nOPT\gt8\sqrt n. Then 16<OPT48n{1\over6}\lt{OPT\over48\sqrt n}. Now lemma 4 implies that the EF1 allocation A\mathcal A returned by ALG-EF1-HIGH satisfies

SW(A)OPT12n16OPT12nOPT48n=OPT16nSW(\mathcal A)\ge{OPT\over12\sqrt n}-{1\over6}\ge{OPT\over12\sqrt n}-{OPT\over48\sqrt n}={OPT\over16\sqrt n}

Proof for lower bounds

For scaled valuations, Ω(n)\Omega(\sqrt n) is proved by Bei et al.

For unscaled valuations, consider the case m=nm=n, following additive valuations: the first agent has value nn for each good, while the other agents have value 1/n1/n for each good. The optimal social welfare is allocating all goods to the first agent, yielding OPT=n2OPT=n^2. In Contrast, any EF1 allocation gives exactly one good to each agent, thus achieving welfare less than n+1n+1, this implies Ω(n)\Omega(n) bound.

\because EF1 \Rarr Prop1, thus the PoF also holds for Prop1. (PoF for Prop1 is Θ(n)\Theta(\sqrt n) for scaled additive valuations and Θ(n)\Theta(n) for unscaled additive valuations.

Price of 1/21/2-MMS

I don’t want to dive deep into the mathematical proofs🤕😓

Das ist zu schade. Ich bin sehr müde.

🎯🤔Theorem 2. The price of 121\over2-MMS is Θ(n)\Theta(\sqrt n) for scaled additive valuations and Θ(n)\Theta(n) for unscaled additive valuations.

An Absolute Welfare Guarantee

First, this paper shows that when agents have additive valuations, there always exists a 121\over2-MMS allocation A\mathcal A with social welfare SW(A)13ni=1nvi([m])SW(\mathcal A)\ge{1\over3n}\sum_{i=1}^nv_i([m]). Algorithm ALG-MMS-ABS computes such an allocation efficiently.

The result is two fold

  1. For both scaled and unscaled valuations, this establishes that the price of 121\over2-MMS is O(n)O(n). (trivial)
  2. For unscaled valuations, this is precisely the bound.
  3. For scaled valuations, we need to improve this to O(n)O(\sqrt n).

Pseudo code for ALG-MMS-ABS:

Input: A fair division instance I\mathcal I, additive valuations {vi}i[n]\{v_i\}_{i\in[n]}.

Output: A 121\over2-MMS allocation B\mathcal B with SW(B)13ni=1nvi([m])SW(\mathcal B)\ge{1\over3n}\sum_{i=1}^nv_i([m]).

  1. Initialize set of agents A=[n]A=[n], set of goods G=[m]G=[m] and bundles Bi=B_i=\empty for all i[n]i\in[n].
  2. while there exists agent iAi\in A and good gGg\in G s.t. vi(g)12Avi(G)v_i(g)\ge{1\over2|A|}v_i(G) do
    • set (i,g)argmax(i,g)A×G:vi(g)12Avi(G)vi(g)(i',g')\in\arg\max_{(i,g)\in A\times G:v_i(g)\ge{1\over2|A|}v_i(G)}v_i(g)
    • set Bi={g}B_{i'}=\{g'\} and update AA{i}A\gets A\diagdown\{i'\} along with GG{g}G\gets G\diagdown\{g'\}
  3. end while
  4. efficiently compute a Prop1 allocation (Bi)iA(B_i)_{i\in A} of the fair division instance A,G,{vi}iA\lang A,G,\{v_i\}_{i\in A}\rang
  5. return allocation B=(B1,,Bn)\mathcal B=(B_1,\cdots,B_n).

The algorithm is a refinement of the algorithm of Amandatidis et al. for computing a 121\over2-MMS allocation: in while loop, we use argmax\arg\max to break ties. They had proven the algorithm always produce 121\over2-MMS. It remains to prove that the desired welfare holds for results.

To analyze the bounds, we let tt denote the number of iterations of the while loop in ALG-MMS-ABS. We re-index the agents s.t. agent 11 through tt receive, in order, a good in this while loop. Each agent i[t]i\in[t] is assigned a good in ii-th iteration of the loop. The remaining ntn-t agents receive a bundle through the Prop1 allocation computed after while loop.

🤔Lemma 5. Consider a fair division instance I\mathcal I with the re-indexing of the agent method above, and tt denoting the number of agents assigned a good in while loop of algorithm. Let B=(B1,,Bk)\mathcal B=(B_1,\cdots,B_k) denote the allocation returned by the algorithm, then we have

k=1i11nk+1vk(Bk)+1ni+1vi([m]k=1i1Bk)1nvi([m])\sum_{k=1}^{i-1}{1\over n-k+1}\cdot v_k(B_k)+{1\over n-i+1}\cdot v_i([m]\diagdown\cup_{k=1}^{i-1}B_k)\ge{1\over n}\cdot v_i([m])

for all i[t]i\in[t], and

k=1t1nk+1vk(Bk)+1ntvi([m]k=1tBk)1nvi([m])\sum_{k=1}^t{1\over n-k+1}\cdot v_k(B_k)+{1\over n-t}\cdot v_i([m]\diagdown\cup_{k=1}^tB_k)\ge{1\over n}\cdot v_i([m])

for all i[n][t]i\in[n]\diagdown[t].

For each agent i[n]i\in[n], we establish the following inequality for every index j{0,,min{i1,t}}j\in\{0,\cdots,\min\{i-1,t\}\} via an induction on jj. Then instantiating j=min{i1,t}j=\min\{i-1,t\} yields the desired result.

🤔Lemma 6. Given any fair division instance I\mathcal I with additive valuations, ALG-MMS-ABS efficiently computes 121\over2-MMS allocation B\mathcal B with social welfare SW(B)13ni=1nvi([m])SW(\mathcal B)\ge{1\over3n}\sum_{i=1}^nv_i([m]).

Proof using lemma 5.

By summing the inequality in lemma 5, across all agents yields the desired welfare bound.

The Case of High Optimal Welfare

This paper proposes new algorithm, ALG-MMS-HIGH, to compute O(n)O(\sqrt n) welfare on 121\over2-MMS.

Computing MMSiMMS_i for each agent ii is NP-hard, there exists a polynomial-time approximation scheme (PTAS) for it. For a fixed ϵ(0,1)\epsilon\in(0,1), this PTAS can compute an estimate Zi[(1ϵ)MMSi,MMSi]Z_i\in[(1-\epsilon)MMS_i,MMS_i] for each agent ii in polynomial time. We pass these estimates as input to ALG-MMS-HIGH, which runs in polynomial time and yields a (12ϵ)({1\over2}-\epsilon)-MMS allocation with the desired welfare guarantee.

🤔Lemma 7.

Given a fair division instance I\mathcal I with scaled additive valuations, and, for a fixed ϵ[0,1)\epsilon\in[0,1). an estimate Zi[(1ϵ)MMSi,MMSi]Z_i\in[(1-\epsilon)MMS_i,MMS_i] for each agent ii, ALG-MMS-HIGH efficiently computes a (12ϵ)({1\over2}-\epsilon)-MMS allocation B\mathcal B with the property that 3nSW(B)+4nOPT3\sqrt n\cdot SW(\mathcal B)+4\sqrt n\ge OPT. (OPTOPT is the optimal social welfare in I\mathcal I)

Proof by lemma 9 and lemma 10.

The agents are partitioned into 3 sets, ΓMMS,Γsingle,Γhard\Gamma_{MMS},\Gamma_{single},\Gamma_{hard}, where agent ii is paced into a set depending on how the estimate ZiZ_i of MMSiMMS_i relates to vi(Wi)v_i(W^*_i).

\Gamma_{MMS}=\{i\in[n]:Z_i\ge{2\over3\sqrt n}v_i(W^*_i)\}\\ \Gamma_{single}=\{i\in[n]:Z_i\lt{2\over3\sqrt n}v_i(W_i^*)\and\exist g\in W_i^*,v_i(g)\ge{1\over3\sqrt n}v_i(W^*_i)\}\\ \Gamma_{hard}=\{i\in[n]:Z_i\lt{2\over3\sqrt n}v_i(W_i^*)\and\forall g\in W_i^*,v_i(g)\lt{1\over3\sqrt n}v_i(W_i^*)\}

For an agent iΓsinglei\in\Gamma_{single}, giving her a single good from argmaxgWivi(g)\arg\max_{g\in W_i^*}v_i(g) gives her value at least 13nvi(Wi)>12Zi{1\over3\sqrt n}v_i(W_i^*)\gt{1\over2}Z_i. Thus the algorithm begins by giving each such agent ii her most valuable good from WiW_i^* and adding her directly in set PP (permanent). (another set is TT temporary)

Next, for iΓMMSi\in\Gamma_{MMS}, giving her value at least 12Zi{1\over2}\cdot Z_i also guarantees that her value is at least 13nvi(Wi){1\over3\sqrt n}v_i(W_i^*); thus the algorithm solely aims to give such agents 12Zi{1\over2}\cdot Z_i value.

The situation is more tricky for agents in Γhard\Gamma_{hard}.

🤔Lemma 8. Let I\mathcal I be a fair division instance with additive valuations. Let [n]\ell\in[n] be an agent. Let {Ba}aS\{B_a\}_{a\in S} be a collection of bundles assigned to a subset of agents S[n]{}S\subseteq[n]\diagdown\{\ell\} with the property that, for all aSa\in S, we either have Ba=1|B_a|=1 or v(Ba)MMSv_\ell(B_a)\le MMS_\ell. Then the value of agent \ell for the unassigned goods satisfies

v([m]aSBa)(nS)MMSv_\ell([m]\diagdown\cup_{a\in S}B_a)\ge(n-|S|)\cdot MMS_\ell

omitted

🤔Lemma 9. The following hold at any stage during the execution of ALG-MMS-HIGH:

  1. PT=P\cap T=\empty.
  2. If iP,vi(Bi)13nvi(Wi)i\in P,v_i(B_i)\ge{1\over3\sqrt n}v_i(W_i^*) and BiB_i is never updated afterwards.
  3. If iPT,vi(Bi)12Zii\in P\cup T,v_i(B_i)\ge{1\over2}\cdot Z_i, and ii is never removed from PTP\cup T afterwards.
  4. TΓhardT\subseteq\Gamma_{hard}.

omitted

🤔Lemma 10. ALG-MMS-HIGH terminates in polynomial time, and at its termination, the following hold.

  1. PT=[n]P\cup T=[n]
  2. T4n|T|\le4\sqrt n

Each iteration of the loop, a new agent is added to PTP\cup T, and will never be removed once added.

proof for 2nd proposition omitted.

Proof of Theorem 2

For unscaled valuations: lemma 6 shows that ALG-MMS-ABS returns a 121\over2-MMS allocation B\mathcal B with social welfare SW(B)13ni=1nvi([m])SW(\mathcal B)\ge{1\over3n}\sum_{i=1}^nv_i([m]). Because OPT is trivially upper bounded as OPTi=1nvi([m])OPT\le\sum_{i=1}^nv_i([m]), we have that the price of 121\over2-MMS is at most 3n=O(n)3n=O(n). (To show this bound is tight, this paper gives an instance)

For scaled valuations: lemma 6 implies ALG-MMS-ABS returns a 121\over2-MMS allocation B\mathcal B with SW(B)13ni=1nvi([m])=13SW(\mathcal B)\ge{1\over3n}\sum_{i=1}^nv_i([m])={1\over3} for scaled valuations. Hence, if OPT5nOPT\le5\sqrt n, then the 121\over2-MMS allocation returned by ALG-MMS-ABS gives a 15n15\sqrt n approximation to the optimal social welfare.

Otherwise, suppose OPT5nOPT\ge5\sqrt n. Then by lemma 7, we know that ALG-MMS-HIGH returns an allocation with social welfare SW(B)OPT4n3nOPT4/5OPT3nOPT15nSW(\mathcal B)\ge{OPT-4\sqrt n\over 3\sqrt n}\ge{OPT-4/5OPT\over3\sqrt n}-{OPT\over15\sqrt n}. Hence, in this case, the 121\over2-MMS allocation returned by ALG-MMS-HIGH provides a 15n15\sqrt n approximation to OPTOPT.

(For lower bound, this paper also gives an instance)

Discussion

Price of EF1: O(n)O(\sqrt n) when valuations are subadditive

  • Θ(n)\Theta(\sqrt n) even if valuations are additive.

Price of 121\over2-MMS is Θ(n)\Theta(\sqrt n) when agent valuations arer additive.

Research outlook:

  1. Analyze the price of 121\over2-MMS under more general valuation classes.

    Consider other combinations of fairness and efficiency guarantees:

    • EF1 + PO (Pareto optimality), EF1 + fPO (fractional Pareto optimality)
    • Price of α\alpha-MMS for α>12\alpha\gt{1\over2}. At least 343\over4-MMS always exists.
    • Price of α\alpha-GMMS. GMMS \Rarr MMS. 121\over2-GMMS always exists.
    • Price of EFX. It remains to be solved the existence of EFX for agents more than 3.
  2. Analyze the PoF when the items are chores, (简单来说就是物品的估值可以为负)or a mixture of goods and chores.

The formal definitions fairness and corresponding prices are well-understood within fair division, but they are much less explored within other scenarios, such as social choice theory (voting or matching).

Paper on MMS

Additive and submodular valuation

A valuation function is considered submodular if adding an item to a smaller set increases its value more than adding the same item to a larger set.

232\over3-MMS always exists and can be found in polynomial time. This paper complement these results by developing a simple and efficient algorithm that achieves the same approximation guarantee.

This paper approximates MMS under submodular valuations. It shows that when the valuations of agents are non-negative, monotone and submodular, then a 0.210.21-MMS is guaranteed to exist.

0.2113(11e)0.21\approx{1\over3}(1-{1\over e})

Introduction

💡Personal comment: A very clear explanation original idea for the Maximin Share: Let agent ii partition the goods into nn bundles, then let others choose before ii choose a bundle. Then agent ii has incentive to maximize the the bundle with minimal value she partitioned.

This paper extends the previous work into both additive and submodular valuations.

Main Results and Techniques

Additive Valuations

This paper presents a polynomial time algorithm that finds a 232\over3-MMS under additive valuations. The algorithm is simple and combinatorial.

The algorithm consists of two parts. First, reducing the problem of finding a maximin fair allocation to a restricted setting where the agents value goods in the same order. This reduction preserves maximin fairness in the sense that the gg-th good in the reduced instance corresponds to the right to select a good in round gg.

With the reduction, this paper develops an efficient algorithm to find 232\over3-MMS allocation for ordered instances. To obtain the result, do some modification on envy-graph algorithm.

(An arbitrary EF1 doesn’t necessarily imply approx-MMS) But with the order, an instance of the EF1 algorithm indeed finds an allocation with desired maximin fairness guarantee.

Submodular Valuations

When valuations are non-negative, monotone and submodular, then a 0.210.21-MMS is guaranteed to exist and can be efficiently computed via a simple round-robin algorithm.

This paper analyzes this simple algorithm by employing the concept of multilinear extensions.

For each agent ii, the expected value of a random subset is at least 11e1-{1\over e} times the maximin share of ii.

Since computing the maximin share is NP-hard, the algorithm works with estimates τi\tau_i for agent ii of the maximin shares. Each estimate τi\tau_i is initialized to be greater than the corresponding maximin share. The methods ensures none of them significantly smaller than the maximin shares.

In our algorithm, we first perform a preprocessing step wherein high-valued goods are assigned as singleton bundles. In particular, if for an agent ii there exists an unallocated good of value at least 0.21τi0.21\tau_i, then we allocate the good to the agent and remove ii (and the now assigned good) from consideration. The leftover (low-valued) goods are partitioned among the remaining agents (who have not received a good yet) in a round-robin manner. In each round, the participating agents greedily select an unallocated good one after the other, i.e. in each round, every agent ii is assigned a good that leads to the maximum possible increase in ii’s valuation.

Under submodular valuations, a uniformly random allocation is (11e)(1-{1\over e}) times ii’s maximin share.

Remark: additive \subseteq submodular. We can get stronger approximation guarantee on additive valuations.

Chores (goods with negative values): 434\over3-approximate maximin fair allocation can be efficiently computed when agents have additive valuations for chores.

The envy graph algorithm is applied similarly between goods version and chores version.

omitted

Notation and Preliminaries

Agents [n][n], goods [m][m].

Valuation of an agent ii over a set S[m]S\in[m] goods: vi(S)v_i(S)

Additive valuations: vi(A+B)=vi(A)+vi(B),AB=v_i(A+B)=v_i(A)+v_i(B),A\cap B=\empty.

Non-negative valuation: vi(S)0,vi()=0v_i(S)\ge0,v_i(\empty)=0.

Monotonicity: vi(A)vi(B)ABv_i(A)\le v_i(B)\forall A\subseteq B.

Submodularity: vi(B{g})vi(B)vi(A{g})vi(A)ABv_i(B\cup\{g\})-v_i(B)\le v_i(A\cup\{g\})-v_i(A)\forall A\subseteq B

Allocate good in smaller bundles yields higher increase.

Marginal values w.r.t. H[m]H\subseteq[m]: fH(S)=f(HS)f(H)S[m]f_H(S)=f(H\cup S)-f(H)\forall S\subseteq [m]

All the nn-partition w.r.t. [m][m]: Πn([m])\Pi_n([m]).

Definition on Maximin Share, α\alpha approximation on Maximin Share: omitted here

Definition on EFX: omitted here

Additive Valuations

In this section, the paper presents an new algorithm that efficiently finds a 232\over3-MMS under additive valuations.

Contribution: the algorithm is simple and combinatorial.

🎯🤔Theorem 1. Given a set of nn agents with additive valuations {vi}i[n]\{v_i\}_{i\in[n]} for a set of mm indivisible goods, we can find a partition A\mathcal A in polynomial time that satisfies

vi(Ai)2n3n1μiv_i(A_i)\ge{2n\over3n-1}\mu_i

for all i[n]i\in[n]. Here μi\mu_i is the maximin share of agent ii.

Proof in two parts. First, we show the problem can be reduced to a restricted setting where the agents value the goods in the same order. Second, we develop a 232\over3-approximation for this restricted setting.

The Reduction of Bouveret and Lemaître

An instance is an ordered instance iff \exist a total ordering \prec over [m][m] s.t. i[n]\forall i\in[n] and g,g[m]g,g'\in[m], s.t. ggg\prec g', we have vi,gvi,gv_{i,g}\ge v_{i,g'}. i.e. vi,1vi,2vi,mv_{i,1}\ge v_{i,2}\ge\cdots v_{i,m}.

Given a fair division I=([n],[m],{vi}i[n])I=([n],[m],\{v_i\}_{i\in[n]}), the algorithm constructs an ordered instance as follows:

  1. For every agent ii, \exist a permutation σi:[m][m]\sigma_i:[m]\rarr[m] s.t. g,g[m]\forall g,g'\in[m] with g<gg\lt g', we have vi,σi(g)vi,σi(g)v_{i,\sigma_i(g)}\ge v_{i,\sigma_i(g')}. Using these permutations, we define a new valuation function viv_i' for every agent ii by setting vi,g=vi,σi(g)v_{i,g}'=v_{i,\sigma_i(g)} for all g[m]g\in[m].

    i.e. for ii, the value of gg-th good in the new instance is equal to the gg-th largest valuation of ii in the original instance.

    Denote I=([n],[m],{vi}i[n])I'=([n],[m],\{v_i'\}_{i\in[n]}) as the ordered instance of II. Note that we can find the ordered instance of II in O(nmlogm)O(nm\log m) time.

  2. Bouveret and Lemaître showed that if there is an allocation A\mathcal A' that guarantees every agent her maximin share in II', then there is an allocation A\mathcal A that guarantees every agent her maximin share in II.

    Moreover, given a maximin fair allocation A\mathcal A' for II', a maximin fair allocation A\mathcal A for II can be found in polynomial time.

Pseudo code for ALGBL

Input: II with A\mathcal A' for the ordered instance II'.

Output: A\mathcal A

  1. For all i[n]i\in[n] and gAig\in A_i' set pg=ip_g=i. // this defines a sequence of agents
  2. Initialize allocation A\mathcal A with Ai=A_i=\empty, for all i[n]i\in[n]. And initialize R[m]R\gets[m].
  3. for g=1g=1 to mm do
    • pick kargmaxgR{vpg(g)}k\in\arg\max_{g'\in R}\{v_{p_g}(g')\}
    • update ApgApg{k}A_{p_g}\gets A_{p_g}\cup\{k\} and RR{k}R\gets R\diagdown\{k\}
  4. return A\mathcal A

🎯🤔Theorem 2. Given a maximin fair division instance II and scalars {αiR}i=1n\{\alpha_i\in\mathbb R\}_{i=1}^n, let II' be the ordered instance of II. If there exists an allocation A\mathcal A' that satisfies vi(Ai)αiv_i'(A_i')\ge\alpha_i for all i[n]i\in[n], then there exists an allocation A\mathcal A s.t. vi(Ai)αiv_i(A_i)\ge\alpha_i for all i[n]i\in[n]. Furthermore, given II and A\mathcal A', ALGBL computes the allocation A\mathcal A in polynomial time.

Obviously polynomial time. We only need to show it computes required allocation.

Let kgk_g denote the good allocated in the gg-th iteration of the second for-loop in ALGBL. Now considering agent ii, suppose that gAig\in A_i' then kgAik_g\in A_i. Note that, for any ggg\neq g', since a good is removed from the set RR after it is allocated. Before the gg-th iteration of the second for loop in ALGBL, exactly g1g-1 goods had been allocated.

Therefore, kgk_g is among the top gg goods for agent ii. Hence, the condition that vi(Ai)αiv_i'(A_i')\ge\alpha_i gives us vi(Ai)αiv_i(A_i)\ge\alpha_i for all ii. Q.E.D.

Corollary: Given a maximin fair division instance II and αR\alpha\in\mathbb R write II' to denote the ordered instance of II and μi\mu_i to denote the maximin share of agent ii in II. If there exists an allocation A\mathcal A' satisfying vi(Ai)αμiv_i'(A_i')\ge\alpha\mu_i', there also exists A\mathcal A satisfying vi(Ai)αμiv_i(A_i)\ge\alpha\mu_i. And can be computed in polynomial time.

Envy Graph Algorithm

Envy-graph Elimination algorithm, omitted here.

ALGEG algorithm returns an EFX allocation. Similar to Top Trading Cycle algorithm.

Pseudo code omitted here.

Majorization

The concept is sued to establishing the desired approximation guarantee.

A multi-set XX is related to another multi-set YY iff the prefix sums of the sorted version XX are at least as large as the prefix sums of the sorted version of YY.

Definition of majorization: A multi-set X={xiR1in}X=\{x_i\in\mathbb R|1\le i\le n\} is said to majorize another multi-set Y={yiR1in}Y=\{y_i\in\mathbb R|1\le i\le n\} iff

i=1kx(i)i=1ky(i)1k<nandi=1nx(i)=i=1ny(i)\sum_{i=1}^kx_{(i)}\ge\sum_{i=1}^ky_{(i)}\forall1\le k\lt n\\ and\\ \sum_{i=1}^nx_{(i)}=\sum_{i=1}^ny_{(i)}

Here x(i)x_{(i)} and y(i)y_{(i)} is the ii-th largest element of XX and YY respectively.

🤔Proposition 1. (easy)

Let v,vRv,v'\in\mathbb R be two elements of a multi-set AA of real numbers. In addition, let u,uRu,u'\in\mathbb R satisfy u+u=v+vu+u'=v+v' and uu<vv|u-u'|\lt|v-v'|. Then AA majorizes (A{v,v}){u,u}(A\diagdown\{v,v'\})\cup\{u,u'\}.

This is trivial and obvious.

因为 u,uu,u' 中的最大值小于 v,vv,v' 中的最大值,这使得 AA 的前缀和加到 v,vv,v' 中最大值的时候一定会大于等于 (A{v,v}){u,u}(A\diagdown\{v,v'\})\cup\{u,u'\} 加到相应的位置上的前缀和。

Proof of Theorem 1

It remains to show that v1(A1)2n3n1μ1v_1(A_1)\ge{2n\over3n-1}\mu_1. (An analogous argument establishes the desired bound, vi(Ai)2n3n1μii[n]v_i(A_i)\ge{2n\over3n-1}\mu_i\forall i\in[n].

Let A\mathcal A be the return of ALGEG. Consider the set of goods that have value 12vi(A1)\ge{1\over2}v_i(A_1), specifically define τ=argmin{jv1(gj12v1(A1)}\tau=\arg\min\{j|v_1(g_j\le{1\over2}v_1(A_1)\}. Let HH denote the set of high valued goods H={g1,g2,,gτ1}H=\{g_1,g_2,\cdots,g_{\tau-1}\}. In addition, write P=(P1,P2,,Pn)\mathcal P=(P_1,P_2,\cdots,P_n) to denote the partial allocation that ALGEG computes for HH.

Let tt denote the smallest iteration count at which ALGEG assigns a good to a bundle of size 2. Hence, every bundle in the partial allocation of the first t1t-1 goods is of size at most 2.

ALGEG updates the partial allocation by adding goods to existing bundles. This implies that the cardinalities of bundles is always increasing. Thus for each final AjA_j, there \exist PjP_j in the partial allocation P\mathcal P s.t. PjAjP_j\subseteq A_j. v1(A1)v1(P1)v_1(A_1)\ge v_1(P_1).

Let Q\mathcal Q be the partial allocation considered by ALGEG at the beginning of the tt-th iteration. The definition of tt ensures that Qi2i[n]|\mathcal Q_i|\le2\forall i\in[n]. In the following, we will show that τt\tau\le t ,then we get bound Pi<2i[n]|P_i|\lt2\forall i\in[n]. This leas to the inequality τ2n\tau\le2n.

…(已经有两个物品了,在添加这个物品时,由于根据算法越到后面添加的越小,所以 v1(A1)2v1(gt)v_1(A_1)\ge2v_1(g_t)。根据定义 gτg_\tau 是最小标号的满足不等式的,所以 τt\tau\le t)

✔️Claim 1. In the partial allocation returned by ALGEG, A\mathcal A, the following inequality holds for all bundles AiA_i that satisfy Ai{gτ,,gm}A_i\cap\{g_\tau,\cdots,g_m\}\neq\empty

v1(A1)23v1(Ai)v_1(A_1)\ge{2\over3}v_1(A_i)

Proof by property of EFX: v1(A1)v1(Ai)v1(ga)v_1(A_1)\ge v_1(A_i)-v_1(g_a). v1(A1)2v1(gτ)2v1(ga)v_1(A_1)\ge2v_1(g_\tau)\ge2v_1(g_a).

✔️Claim 2. The partial allocation P\mathcal P consists of the following bundles:

{g1},{g2},,{gnh},{gnh+1,gn+h},{gnh+2,gn+h1},,{gn1,gn+2},{gn,gn+1}\{g_1\},\{g_2\},\cdots,\{g_{n-h}\},\{g_{n-h+1},g_{n+h}\},\{g_{n-h+2},g_{n+h-1}\},\cdots,\{g_{n-1},g_{n+2}\},\{g_n,g_{n+1}\}

Proof by analyzing behavior of the algorithm.

✔️Claim 3. Every partial allocation of HH majorizes P\mathcal P.

Proof by using proposition 1.

P\mathcal P minimize the sum of the largest tt bundles.

Let \ell be # of bundles in {A2,A3,,An}\{A_2,A_3,\cdots,A_n\}, that do not contain any good with index greater than τ1\tau-1. For every such bundle AiA_i, there exists a unique bundle PjP_j in P\mathcal P s.t. Ai=PjA_i=P_j. By reindexing, that Pn+1,Pn+2,,PnP_{n-\ell+1},P_{n-\ell+2},\cdots,P_n are these \ell bundles in A\mathcal A that do not satisfy the condition in claim 1.

Let M\mathcal M denote a partition of [m][m] that achieves the maximin share for player 11. Consider the partial allocation {MiH}i=1n\{M_i\cap H\}_{i=1}^n and index the set s.t. valuation is in ascending order. Claim 3 implies {MiH}i=1n\{M_i\cap H\}_{i=1}^n majorizes P\mathcal P. Hence, i=n+1nv1(MiH)i=n+1nv1(Pi)\sum_{i=n-\ell+1}^nv_1(M_i\cap H)\ge\sum_{i=n-\ell+1}^nv_1(P_i). This inequality and the fact the valuations are monotone lead to the following useful bound:

i=n+1nv1(Mi)i=n+1nv1(Pi)\sum_{i=n-\ell+1}^nv_1(M_i)\ge\sum_{i=n-\ell+1}^nv_1(P_i)

Recall that Pn+1,Pn+2,,PnP_{n-\ell+1},P_{n-\ell+2},\cdots,P_{n} are bundles in A\mathcal A, and the remaining nn-\ell bundles of A\mathcal A satisfy the inequality v1(A1)23v1(Ai)v_1(A_1)\ge{2\over3}v_1(A_i). Since v1v_1 is additive, we have i=1nv1(Mi)=i=1nv1(Ai)\sum_{i=1}^nv_1(M_i)=\sum_{i=1}^nv_1(A_i). Therefore, inequality above provides the following bound:

i=1nvi(Mi)i=1nv1(Ai)v1(A1)+(n1)32v1(A1)\sum_{i=1}^{n-\ell}v_i(M_i)\le\sum_{i=1}^{n-\ell}v_1(A_i)\\ \le v_1(A_1)+(n-\ell-1){3\over2}v_1(A_1)

Overall, this inequality implies that v1(A1)v_1(A_1) is at least 2(n)3n12(n-\ell)\over3n-1 times the average of the nn-\ell sets M+1,,MnM_{\ell+1},\cdots,M_n. Hence, v1(A1)]2n3n1minj[n]vi(Mj)=2n3n1μ1v_1(A_1)]\ge{2n\over3n-1}\min_{j\in[n]}v_i(M_j)={2n\over3n-1}\mu_1. This completes the proof.

Submodular Valuations

0.210.21-MMS is guaranteed to exist and can be found in polynomial time for submodular valuations.

Finding an Approximate Maximin Fair Allocation

We execute the subroutine RoundRobin with threshold τi\tau_i instead of the actual maximin share μi\mu_i.

RoundRobin takes as input threshold, τi\tau_is, allocates high-valued goods as singleton bundles. And then partition the remaining goods in a round-robin fashion.

This paper argues: for each agent ii, if τiμi\tau_i\le\mu_i, the bundle PiP_i allocated to ii by RoundRobin satisfies vi(Pi)13(11e)τiv_i(P_i)\ge\frac{1}{3}(1-\frac{1}{e})\tau_i.

This guarantee holds independently for each agent ii.

Algorithm ALGSUB starts by setting thresholds τi\tau_is to be more than the maximin shares. Then, it decreases the threshold for agent ii, if the partition returned by RoundRobin does not satisfy vi(Pi)13(11e)τiv_i(P_i)\ge\frac{1}{3}(1-\frac{1}{e})\tau_i i.e. τi>μi\tau_i\gt\mu_i, hence decreasing the threshold is justified.

Pseudo code for RoundRobin: input include {τi}\{\tau_i\}

Pseudo code for ALGSUB: process of decreasing τi\tau_i

How to initialize τi\tau_i???

🎯🤔Theorem 3. Given a MMS allocation with non-negative, monotone, submodular valuations, the ALGSUB finds, in polynomial time, an allocation satisfies vi(Pi)0.21μiv_i(P_i)\ge0.21\mu_i for all i[n]i\in[n]. Here μi\mu_i is the maximin share of agent ii.

Theorem 3 is about the main result for submodular valuations.

Proof by lemma 1.

🤔Lemma 1.

For a given a maximin fair division instance with mm indivisible goods and nn agents with non-negative, monotone and submodular valuations, let P\mathcal P be the allocation returned by RoundRobin with threshold τi0\tau_i\ge0. Then, for each agent ii whose input threshold satisfies τiμi\tau_i\le\mu_i, it holds that

vi(Pi)13(11e)τi0.21τiv_i(P_i)\ge\frac{1}{3}(1-\frac{1}{e})\tau_i\ge0.21\tau_i

Fix an agent ii and under assumption that τiμi\tau_i\le\mu_i.

Proof by analyzing behavior of RoundRobin.

Very sophisticated😮

Multilinear Extensions

Definition of multilinear extension: For a function f:2[m]Rf:2^{[m]}\mapsto\mathbb R, the multilinear extension F:[0,1][m]RF:[0,1]^{[m]}\mapsto\mathbb R is defined as follows:

F(x)=ERx[f(R)]=R[m]f(R)(gRxgg[m]R(1xg))F(x)=\mathbb E_{R\sim x}[f(R)]=\sum_{R\subseteq[m]}f(R)\left(\prod_{g\in R}x_g\prod_{g\in[m]\diagdown R}(1-x_g)\right)

sampling from x[0,1]mx\in[0,1]^m corresponds to selecting a random subset R[m]R\subseteq[m] in which each g[m]g\in[m] appears independently with probability xgx_g.

Fractional allocation: nn-tuple χ=(x1,x2,,xn)\chi=(x^1,x^2,\cdots,x^n) with xi[0,1]mx_i\in[0,1]^m iff i=1nxgi1\sum_{i=1}^nx_g^i\le1 for all g[m]g\in[m].

A binary fractional allocation corresponds to a partial allocation.

🤔Lemma 2. (Proportionality) Let vi:2[m]R+v_i:2^{[m]}\mapsto\mathbb R_+ denote non-negative, monotone, submodular valuations of agents i[n]i\in[n] over mm indivisible goods. Then the fractional allocation ω=(u1,u2,,un)\omega=(u^1,u^2,\cdots,u^n) in which ui=(1n,1n,,1n)[0,1]mu^i=(\frac{1}{n},\frac{1}{n},\cdots,\frac{1}{n})\in[0,1]^m for all i[n]i\in[n], satisfies Vi(ui)(11e)μiV_i(u^i)\ge(1-\frac{1}{e})\mu_i for all i[n]i\in[n]. Here Vi:[0,1]mR+V_i:[0,1]^m\mapsto\mathbb R_+ is the multilinear extension of viv_i, and μi\mu_i is the maximin share of agent ii.

hard proof, omitted

Conclusion

Algorithm proposed in this paper: approximately fair and sequenceable.

Sequenceable allocation: allocations that can be obtained by ordering the agents and then letting them select their most valued unallocated good one after the other.