Iannis 给了三篇论文,三个方向。分别通读一下这三篇论文,看看什么主题比较感兴趣吧。

Possible Project Topics of Algorithmic Game Theory

Algorithmic Game Theory

Mechanism Design ✅

  • Auction Theory
  • Market Design

The first paper is about Mechanism Design for Machine Learning/Statistical Tasks.

简单来讲就是说,将提供训练集的个体视为智能体 Agent,在训练人工智能模型的时候,这些智能体有动机操纵提供的训练集数据来使得人工智能模型最终的输出有利于该智能体。而研究者的任务是研究如何设计一个机制来鼓励智能体提供真实的数据(no incentive to misreport)

  • Mean Estimation (2016 ICML)
  • Classification
  • Regression (Current)

Games and Price of Anarchy

  • Price of Anarchy
  • Price of Stability

Equilibrium Computation

Didn’t cover in the course.

Computational Social Choice

Voting​ ✅

Didn’t cover in the course.

The second paper is about Computational Social Choice for Federated learning

Matching

  • Stable Matching (Gale–Shapley algorithm)
  • Kidney-exchange

Fair Division ✅

Didn’t cover in the course.

The third paper is about Fair Division. (Ιωάννης 在该方向上做了相当多的工作,2009-2023 current)

Mechanism Design for Machine Learning

Strategyproof Linear Regression in High Dimensions by Chen et al, ACM Economics and Computation 2018

Strategyproof

说人话:就是占优策略激励相容 (Dominant Strategy Incentive Compatible abbr. DSIC),向机制诚实报告就是最优策略 dominant strategy

Abstract

Strategyproof mechanisms on Linear regression

Agents: single-peaked preferences

Ham Sandwich Theorem

This paper proposed: Generalized Resistant Hyperplane mechanisms.

Introduction

Motivation: Designing a Machine Learning algorithm that is robust to noise in training data

Adversarial noise: sabotaging the algorithm.

这一点有印象,本科期间了解过,在图像上有策略的增加一些肉眼很难分辨的对抗噪点就能欺骗视觉模型使得图像分类的结果出错。

Training data: provided by agents

Aligning the agents’ incentives correctly → possible to obtain uncontaminated data

Scenario

Linear Regression i.e., fitting a hyperplane through given data.

Agents’ incentive: to minimize their vertical distance from the output hyperplane.

Design: Strategyproof regression mechanisms without payments.

Proposed Model

Fitting a hyperplane through data points (xi,yi)(\mathbb x_i,y_i) for xiRd;yiR;i=1,,n\mathbb x_i\in\mathbb R^d;y_i\in\mathbb R;i=1,\cdots,n.

yiy_i is held only by agent ii.

xi\mathbb x_i is independent variables, public information.

Mechanism: elicits the private information of the agents, returns a hyperplane represented by vector β=(β1,β0)Rd+1\beta=(\beta_1,\beta_0)\in\mathbb R^{d+1}.

Residual for agent ii: ri=yiβ1Txiβ0r_i=y_i-\beta_1^T\mathbb x_i-\beta_0

Agents wish to minimize ri|r_i|

Dekel et al: empirical risk minimization with L1L_1 loss (L1L_1-ERM) coupled with specific tie-breaking rule is group strategyproof.

No coalition of agents can be weakly better off by misreporting.

This paper: replacing the L1L_1 loss by a weighted L1L_1 loss and adding convex regularization to the risk function preserves group strategyproof.

Perote et al: 2-dimensional case, propose a wide family of strategyproof mechanisms, clockwise repeated median (CRM).

But this paper prove that it’s wrong, giving 3 stricter conditions. CRM mechanism coincide with resistant line mechanisms

Main Result

Generalizing CRM family to higher dimensions.

Introduce the family of generalized resistant hyperplane (GRH).

In d+1d+1 dimensions, GRH parametrized by d+1d+1 subset of agents.

Impartiality: group strategyproof.

比 DSIC 更严苛:如果智能体相互之间串通,谎报都不能使得收益增加。

Another desideratum except strategyproof: Good statistical efficiency.

Important: this paper establish a lower bound of 22 on the approximation ratio of any strategyproof mechanism, which means that any mechanism that is even close to ordinary least squares regression must be manipulable.

Research: 3 categories:

  1. Manipulable information

    Most papers assume: independent variables (feature vectors) - public; Dependent variables (labels) - private.

    • Strategyproof classifiers / agents interest in a shared set of input points.

    • Constructing classifiers robust to agents strategically misreporting feature vector.

      One-shot Stackelberg game

  2. Goal of the agents ✅ (Exact one this paper discusses)

    • Motivated by privacy concerns: Tradeoff between accuracy and privacy

    • Agent want model make accurate assessment on their own sample, even if this reduce overall accuracy.

  3. Use of payments and incentive guarantees

    • Monetary payment?

    • How strongly to guarantee truthful reporting

      stronger strategyproofness VS. Bayes-Nash incentive compatibility.

Model

(Omit Notation here)

Strategyproofness: Every single agent has no incentive to misreport its true value.

Group Strategyproofness: Stronger than strategyproofness. No coalition of agents can simultaneously misreport in a way that: no agent in the coalition is strictly worse off and some agent in the coalition is strictly better off (with no regards to other agents’ report value)

This paper does not consider weaker group strategyproofness, as mechanism proposed is able to satisfy stronger one.

Families of Strategyproof Mechanisms

Empirical Risk Minimization with the L1L_1 Loss

When dimension d=0d=0 i.e., xi=xj(i,jN)\mathbb x_i=\mathbb x_j(\forall i,j\in N). Choosing the median of the reported values achieves group strategyproofness.

Median minimize L1L_1 loss: argminyRi=1nyyi\arg\min_{y\in\mathbb R}\sum_{i=1}^n|y-y_i|.

This can be generalized into higher dimension while maintaining group strategy proof (Dekel et al)

This paper proposes Generalized L1L_1-ERM, which is also group strategyproof.

Weighted L1L_1 loss, the loss of each agent ii is multiplied by a weight wixw_i^{\mathbb x}.

adding a convex regularizer h:FRh:\mathcal F\rarr R

Advantage of Generalized L1L_1-ERM:

  1. Eliminating tie-breaking step if risk function guaranteed to have a unique minimizer (To achieve this by adding strictly convex regularizer).
  2. It covers all generalized medians while L1L_1-ERM reduces to a specific mechanism.

quantile regression mechanisms

R^q(f,D)=yif(xi)qyif(xi)+yi<f(xi)(1q)yif(xi)\hat R_q(f,\mathcal D)=\sum_{y_i\ge f(\mathbb x_i)}q\cdot|y_i-f(\mathbb x_i)|+\sum_{y_i\lt f(\mathbb x_i)}(1-q)\cdot|y_i-f(\mathbb x_i)|

Not remain strategyproof in higher dimension.

Generalized Resistant Hyperplane Mechanisms

Extending family of resistant line mechanisms.

Clockwise Repeated Median Mechanisms

Perote et al.

Only defined for the special case of simple linear regression.

Need to assume that set of points is admissible

Admissible set is a collection of data points D=(xi,yi)iN\mathcal D=(x_i,y_i)_{i\in N} that xixji,jNx_i\neq x_j\forall i,j\in N

Step:

  1. Divide agent into two subsets S,SS,S'.
  2. Compute the median clockwise angle (CWA)
  3. For each point in SS, choose iSi^*\in S whose median CWA is the median of median CWAs from all points in SS.
  4. If median CWA from ii^* is towards point jSj^*\in S', the mechanism returns the straight line passing through points ii^* and jj^*.

CWA

From (xi,yi)(x_i,y_i) to (xj,yj)(x_j,y_j), CWA is

CWA((xi,yi),(xj,yj))=π+sign(xjxi)π2+sign(yjyixjxi)arctan(yjyixjxi)sign(x)={1,x<00,x=01,x>0\text{CWA}((x_i,y_i),(x_j,y_j))=\pi+\text{sign}(x_j-x_i)\cdot\frac{\pi}{2}+\text{sign}(\frac{y_j-y_i}{x_j-x_i})|\arctan(\frac{y_j-y_i}{x_j-x_i})|\\ \text{sign}(x)=\begin{cases} -1,x\lt0\\ 0,x=0\\ 1,x\gt0 \end{cases}

Directing angle

DA(S,S)=mediSmedjS:jiCWA((xi,yi),(xj,yj))\text{DA}(S,S')=\text{med}_{i\in S}\text{med}_{j\in S':j\neq i}\text{CWA}((x_i,y_i),(x_j,y_j))

Mechanism returns the line β=(β1,β0)\beta=(\beta_1,\beta_0) s.t.

β1=tan[DA(S,S)ππ2sign(DA(S,S)π)]β0=mediS(yiβxi)\beta_1=\tan[\text{DA}(S,S')-\pi-\frac{\pi}{2}\cdot\text{sign}(\text{DA}(S,S')-\pi)]\\ \beta_0=\text{med}_{i\in S}(y_i-\beta\cdot x_i)

But this paper provides two counterexamples showing that (S,S)(S,S')-CRM mechanisms (under Perote’s loose restrict) violate strategyproofness.

This paper looks for a subset of the CRM mechanisms to establish group strategyproofness. (impose more restrictive conditions)

Separable Sets of Point in a Plane

In this paper definition is two sets can be separated by a vertical line.

(S,S)(S,S')-CRM is group strategyproof if one of the following conditions holds

  1. S=SS=S'.
  2. SS and SS' are separable.
  3. SS=S\cap S'=\empty and min(S,S)=1\min(|S|,|S'|)=1. (dictatorship)

Generalized Resistant Line Mechanisms on a Plane

This paper introduces a novel family of group strategyproof mechanisms.

Start from: Resistant Line mechanisms

3 separable subset L,M,RL,M,R. A line β\beta given by

mediLyiβ1xiβ0=mediRyiβ1xiβ0=0\text{med}_{i\in L}y_i-\beta_1x_i-\beta_0=\text{med}_{i\in R}y_i-\beta_1x_i-\beta_0=0

Making median of residuals in LL and RR zero.

Yielding (L,R)(L,R)-CRM mechanism

β1=mediLmedjRyjyixjxiβ0=mediLyiβ1xi=medjRyjβ1xj\beta_1=\text{med}_{i\in L}\text{med}_{j\in R}\frac{y_j-y_i}{x_j-x_i}\\ \beta_0=\text{med}_{i\in L}y_i-\beta_1x_i=\text{med}_{j\in R}y_j-\beta_1x_j

Brown-Mood mechanism: LL and RR are two half, MM is empty.

Tukey mechanism: L,M,RL,M,R each contains 131\over3 points.

This paper: instead of making the median residuals from SS and SS' zero, making the k-th smallest residual in SS and kk'-th smallest residual in SS' zero, for fixed k[S]k\in[|S|] and k[S]k'\in[|S'|].

Generalized Resistant Line Mechanisms (GRL)

miniSkyiβ1xiβ0=minjSkyjβ1xjβ0=0\min_{i\in S}^ky_i-\beta_1x_i-\beta_0=\min_{j\in S'}^{k'} y_j-\beta_1x_j-\beta_0=0

Theorem: (S,S,k,k)(S,S',k,k')-generalized resistant line mechanism is group strategyproof.

Noted: GRL is a generalized resistant mechanism version of (S,S)(S,S')-CRM mechanism.

Generalized Resistant Hyperplane Mechanisms in High Dimensions

In d+1d+1 dimension, take d+1d+1 separable subsets of data points. Return regression hyperplane with makes prescribed percentiles of residuals in each set zero.

How to generalize to higher dimension? Using Ham Sandwich Theorem.

A dd-dimension hyperplane HH can “bisect” a d+1d+1 hyperspace.

Well separable aka affinely independent sets

Given t[k+1]t\in[k+1], finite sets S1,,StS_1,\cdots,S_t of points in Rk\mathbb R^k are called well separable if for all disjoint I,J[t]I,J\subseteq[t], there exists a hyperplane HH s.t. SiH+HS_i\sub H^+\diagdown H for each iIi\in I and SjHHS_j\sub H^-\diagdown H for each jJj\in J, i.e. HH separates iISi\cup_{i\in I}S_i from jJSj\cup_{j\in J}S_j by putting them in different open half-spaces.

⚠️ Due to my shortage of (discrete) mathematics knowledge, hereinafter only put key words.

Weak General Position

Publicly Separable Sets of Agents

Generalized Resistant Hyperplane (GRH) Mechanism

Hyperplane Comparison Lemma

😭 Too many lemmas, propositions and theorem.

Main contribution of this paper:

Every generalized resistant hyperplane mechanism is group strategyproof.

Strategyproofness Versus Group Strategyproofness

For d=0d=0 all strategyproof mechanisms are group strategyproof.

Is it still true that all strategyproof mechanisms for linear regression are also group strategyproof? No!

Impartial Mechanism

A mechanism MM is called impartial if the outcome for each agent is independent of the agent’s report.

Propositions and theorems…

Characterizing Strategyproof Mechanisms

Locally Constant Function

ϵ>0,x[xϵ,x+ϵ],f(x)=f(x)\exist\epsilon\gt0,\forall x'\in[x-\epsilon,x+\epsilon],f(x')=f(x)

In one-dimensional setting, a mechanism elicits agents report π(y)\pi(y) (yy is private true valuation) is strategyproof iff:

  1. There exist constant α1,α2RR{,+}\alpha^1,\alpha^2\in\overline{\mathbb{R}}\triangleq\mathbb R\cup\{-\infty,+\infty\}
  2. π\pi is continuous, for every yRy\in\mathbb R, either π(y)=y\pi(y)=y or π\pi is locally constant at yy.

For higher dimension, the conditions are similar. (median and locally constant)

Efficiency of Strategyproof Mechanisms

OLS (ordinary least square) aka RSS (residual sum of squares)

Gauss-Markov Theorem: justification for OLS

OLS is not strategyproof.

Efficiency

Given x\mathbb xm the mechanism MxM^{\mathbb x} for linear regression is cc-efficient if for every D=(xi,yi)iN\mathcal D=(\mathbb x_i,y_i)_{i\in N}, we have RSS(D,Mx(y))cinfβRSS(D,β)\text{RSS}(\mathcal D,M^{\mathbb x}(\mathbb y))\le c\cdot\inf_\beta\text{RSS}(\mathcal D,\beta).

No strategyproof mechanism that is close to OLS can be strategyproof. (Proof omitted)

Discussion

Open question leaves:

How to find a constructive characterization of all strategyproof or group strategyproof mechanisms for linear regression.

L1L_1-ERM is nn-efficient, does there exist a more efficient strategyproof mechanism?

Analysis efficiency in a stochastic setting: What if data points are drawn from a underlying distribution?

Further research on “phantom”?

Different game setting?

Computational Social Choice for Federated Learning

Fairness in Federated Learning via Core-Stability by Bhaskar et al. NeurIPS 2022

Federated learning

简单来说,联邦学习就是在多个拥有本地数据样本的分布式边缘设备或服务器上训练人工智能模型,仅上传模型参数这种不敏感的数据到中心服务器中。会假定所有分布式的数据都是同分布的。训练过程是去中心化的。好处是保护数据隐私、数据安全等。

MIT Press 的 NeurIPS 人工智能顶会

Abstract

We care about fairness. It is unfair for agents with high quality data to sacrifice their performance due to other agents with low quality data.

Currently: egalitarian and weighted equity-based fairness measures suffer from the above pitfall.

This paper: model the task of learning a shared predictor in the federated setting as a fair public decision making problem.

core-stable fairness:

Given NN agents, there is no subset of agents SS that can benefit significantly by forming a coalition among themselves based on their utilities.

Core-stable predictors are robust to low quality local data

Proportionality

each agent gets at least 1n\frac{1}{n} fraction of the best utility that she can get from any predictor.

Pareto-optimality

There exists no model that can increase the utility of an agent without decreasing the utility of another.

This paper: propose an efficient federated learning protocol CoreFed to optimize a core stable predictor.

Kakutani’s fixed point theorem

Introduction

Background

Federated Learning (abbr. FL)

  • utilize valuable data scatter in different organizations.

  • Challenge: Heterogenity in local data distributions. To ensure a fair performance of classifier across all local data distributions.

Questions this paper asked: Jointly optimizing a certralized model with fairness guarantees regarding the heterogeneity of local agents. Defining such fairness s.t. no agents intend to form an coalition with a subset of agents. Finding a federated learning protocol to ensure such fairness.

Federated learning can be cast into public decision making

All agents derive respective utilities from a common global decision.

New goal: make this global decision fairly.

Fundamental fairness meaures: core-stability.

An outcome is considered “core-stable” if, once a coalition is formed and an outcome is achieved, no subgroup of that coalition has an incentive to break away and form a new coalition to achieve a more favorable outcome for themselves.

A globally trained model is core stable if there are no blocking coalitions.

2 commonly used fairness notions

  1. Egalitarian fairness

    Aims to maximize the utility of the least happy agent

  2. Proportional fairness aka weighted equity based fairness

    Ratios of the losses of any pair of the agents to be proportional to the size of their respective datasets.

This paper points out that both notions are vulnerable.

Unfair to the other agents as both may reduce loss incurred by the noisy-agent, thereby biasing the learning.

Contribution of This Paper

Defining the core-stable fairness in FL.

  • Modeling agents’ utility functions to caputre their learning loss error.

  • NN local agents, protocol PP, aggregated model ff. ff achieves core-stability if there are no coalition SS of agents that could benefit significantly by training a model with only their data.

    i.e., no agent has the incentive to deviate from curret group and thereby obtain proportionally better aggregate utility from the final trained model.

    就是说,在这一大群智能体中,没有任何一个真子集的智能体有动机去只用自己的数据训练模型。用所有人的数据训练比用这个真子集的数据训练效果更好。

    Such model ff ensures:

    • Proportionality: each agent gets 1n\frac{1}{n} times their best possible utility.
    • Pareto-optimality
  • Core-stability is popular but rare-to-exist. Learning errorrs are innately non-linear and highly complex.

Contribution of this paper:

  1. Extending core-stability from AGT to fairness in FL.

    fixed point formulation

  2. CoreFed: An Effective federated learning protocol which optimizes the final model by maximizing the protocol of agents’ utilities.

    Whenever underlying utility functions are concave.

  3. Proving that CoreFed works in linear regression and logistic regression (utility functions are convex).

    For non-convex utility function (Smooth DNN), approximately core-stable.

  4. Extending core-stability into weighted core-stability. Showing that weighted core-stable model is weighted proportional and Pareto-optimal.

    CoreFed → weighted CoreFed

  5. Experiments on 3 datasets, CoreFed achieves the core-stable fairness, while maintaining similar utility with the standard FedAvg protocol.

Fairness in Social Choice

Proportionality

Every agent receives their propotional share of the best outcome. 1n×\frac{1}{n}\times best utility themselves.

Envy-freeness

Divide a set of items among agents fairly.

No agent prefers the bundle of the other agent to her own. In public decision making this is impossible. Replaced by core-stability.

Equitability: every agent should be equally happy.

Relaxations of equitability: envy-freeness, proportionality.

Fairness in Federated Learning

  • Establishing fairness at the agent selection phase.

  • Fairness while training the global model s.t. no discrimination against protected groups.

    e.g. Egalitarian fairness

  • Considering fairness by evaluating contribution of the agents towards training the joint model.

    e.g. weighted equity fairness

  • Significance to the agents based on Shapley values.

Core-Stability in Federated Learning

Problem Setup

Model: A function mapping from XRd\mathcal X\in\mathbb R^d to YR\mathcal Y\in\mathbb R.

Regression or binary classification.

Such mapping:

F={fθθPRd}fθ:RdR\mathcal F=\{f_\theta|\theta\in P\subseteq\mathbb R^d\}\\ f_\theta:\mathbb R^d\rarr\mathbb R

s.t. for data sample (x,y)(x,y) drawn from the distribution P\mathcal P, fθ(x)yf_\theta(x)\approx y.

θ\theta is called predictor for the model.

Utility Functions of Agents

Quality of θ\theta is measured by the expected loss over the data distribution P\mathcal P, i.e., E(x,y)Pl(fθ(x),y)\mathbb E_{(x,y)\sim\mathcal P}l(f_\theta(x),y).

l(,)l(\cdot,\cdot) is a predefined loss function. Training process minimize expected loss, attaining θ=argminθPE(x,y)Pl(fθ(x),y)\theta^*=\arg\min_{\theta\in P}\mathbb E_{(x,y)\sim\mathcal P}l(f_\theta(x),y).

Utility function of a group for a predictor θ\theta:

u(θ)=ME(x,y)Pl(fθ(x),y)u(\theta)=M-\mathbb E_{(x,y)\sim\mathcal P}l(f_\theta(x),y)

where MM is a constant more than 1+ϵ1+\epsilon times the loss incurred from the worst predictor for agent ii, i.e.,

M(1+ϵ)supθP,(x,y)X×Yl(fθ(x),y)0<ϵ<<105M\ge(1+\epsilon)\sup_{\theta\in P,(x,y)\in\mathcal X\times\mathcal Y}l(f_\theta(x),y)\\ 0<\epsilon\lt\lt10^{-5}

Observation: u(θ)[Mϵ,M(1+ϵ)]u(\theta)\in[M\epsilon,M(1+\epsilon)].

Federated Leaerning and Fairness

nn groups. Each group ii has their loss function li()l_i(\cdot) and correspondingly a utility function ui()u_i(\cdot) for each θP\theta\in P.

Definition of core-stability:

A prediction θP\theta\in P is called core-stability if there exists no other θP\theta'\in P, and no subset SS of agents, s.t. Snui(θ)ui(θ)iS\frac{|S|}{n}u_i(\theta')\ge u_i(\theta)\forall i\in S, with at least one strict inequality.

No subset coalition can give agent better utility.

This ensures that all agent benefit at least 1n\frac{1}{n} of its best possible utility. (Proportionality)

Definition of proportionality:

A predictor θP\theta\in P is called proportional iff θP\forall\theta'\in P, we have ui(θ)ui(θ)nu_i(\theta)\ge\frac{u_i(\theta')}{n} (i[n])(\forall i\in[n]).

No predictor that can increase theutility of some agent without decreasing the utility of another. (Pareto-optimality)

Definition of Pareto-optimality

A prediction θP\theta\in P is Pareto-optimal iff there exists no other θP\theta'\in P s.t. ui(θ)ui(θ)u_i(\theta')\ge u_i(\theta) for all i[n]i\in[n] with at least one strict inequality.

Advantages of Core-Stability

Robust to low local data qualities of some agents.

Scale-invarance: Scaling the utility of any single agent does not alter the core-stable allocation.

Existence of Core-Stability in Federated Learning

Conditions:

  1. The utility function is continuous.

  2. The set of maximizers of any conical combination of utility functions is convex.

    Conical combination: a linear combination where the coefficients are non-negative.

2 conditions together with Kakutani’s Fixed Point Theorem (角谷不动点定理), we can prove the existence of core-stabiltiy in FL.

Computation of a Core-Stable Predictor When Utility Functions are Concave

Any predictor that maximizes the product of utilities of the agents, i.e., argmaxθPi[n]ui(θ)\arg\max_{\theta\in P}\prod_{i\in[n]}u_i(\theta) is core-stable.

Convex program:

maximize L(θ)=i[n]log(ui(θ))subject to θP\text{maximize }\mathcal L(\theta)=\sum_{i\in[n]}\log(u_i(\theta))\\ \text{subject to }\theta\in P

Theorem: if ui()u_i(\cdot) is concave for all i[n]i\in[n], then any predictor θ\theta^* that maximizes the convex program is core-stable. (Proof omitted)

Tightness of Guarantees: core-stability is tight.

CoreFed

For non-convex losses such as DNNs, applying gradient descent to maximize the objective.

nn finite samples {xi,yi}i[n]\{x_i,y_i\}_{i\in[n]} drawn from data distribution P\mathcal P. Empirical distribution P^n\hat{\mathcal P}_n.

Gradient descent:

θL(θ)=i[n]θui(θ)ui(θ)=i[n]θE(x,y)P^n(i)l(fθ(x),y)MiE(x,y)P^n(i)l(fθ(x),y)\nabla_\theta\mathcal L(\theta)=\sum_{i\in[n]}\frac{\nabla_\theta u_i(\theta)}{u_i(\theta)}=\sum_{i\in[n]}\frac{-\nabla_\theta\mathbb E_{(x,y)\sim\hat{\mathcal P}_n^{(i)}}l(f_\theta(x),y)}{M_i-\mathbb E_{(x,y)\sim\hat{\mathcal P}_n^{(i)}}l(f_\theta(x),y)}

CoreFed: the model updates are weighted then aggregated at each iteration. (formular omitted here)

Core-Stability in Linear Regression and Classification with Logistic Regression

This paper take linear regression and classification with logistic regression as example.

Since concavety of utility function in these scenarios are satisfied.

CoreFed can determin core-stable predictor in a federated learning setting training linear regression and logistic regression (classification).

Approximate Core-Stability in Deep Nerual Networks

Relaxed local core-stability we can attain for approximately first-order converged predictor.

😭 very complex theorem for pseudo core stable predictor. (mere a mention here)

Weighted Core-Stability

For each agent ii, if we assign weight wiw_i, indicating the desired bias of the final trained model towards agent ii. With subtle modifications, we can show the existence of a weighted core-stable predictor.

Weight Core-Stability

Given a weight vector w=(w1,,wn)w=(w_1,\cdots,w_n), a predictor θP\theta\in P, is weighted core-stable iff there exists no other predictor θP\theta'\in P and a subset of agent S[n]S\subseteq[n] s.t.

jSwjj[n]wjui(θ)ui(θ) for all iS\frac{\sum_{j\in S}w_j}{\sum_{j\in[n]}w_j}\cdot u_i(\theta')\ge u_i(\theta)\text{ for all }i\in S

with at least one strict inequality.

Experiment

This paper evaluates CoreFed VS. FedAvg on Adult, MNIST, CIFAR-10 on linear model and deep neural network.

Experiment Results

CoreFed achieves the core-stable fairness through comparison with FedAvg on different datasets and settings.

Conclusion

Introducing a new notion of fairness in federated learning,

More resilient to noisy data from certain clients.

Fair Division

Fair Division of Indivisible Goods: Recent Progress and Open Questions by Georgios et al, journal of Artificial Intelligence 2023

这是一篇文献综述 literature review。爱思唯尔 AIJ,CCF A,顶刊属于是。

这篇综述看完了,太爽了。感觉自己还是对公平分配感兴趣。Dive into 进去可能会有一些收获。

After reading , I drew a mindmap about this paper.

Abstract

Fair division: Allocating resources to individuals in a fair manner.

Focus on indivisible case. Fairness notion:

  • Envy-freeness
  • Proportional

Relaxation of these notion:

  • Maximin share fairness (MMS)
  • Envy-freeness up to any good (EFX)

This paper: General review of recent progress for

  • Different ways to relax fairness notions
  • Common algorithm design techniques
  • Interesting question for further research

Introduction

Fair division: Fairly partitioning or allocating a set of resources to people with diverse and heterogeneous preferences over these resources.

Most classic work: Fair division of infinitely divisible resources.

Fairness means:

  1. Proportionality

  2. Envy-freeness

    Envy-free allocation of divisible resources can always be found in a finite number of steps.

For indivisible resources, aka discrete fair division. More challenging.

  • No reasonable fair solution can be guaranteed in some cases: a single valuable item.
  • Sometimes we need relaxations of envy-freeness and proportionality.

Relaxations

  1. envy-freeness up to one good (EF1)
  2. envy-freeness up to any good (EFX)
  3. maximin share fairness (MMS)

Road map of this paper:

  1. Introduction to the problem of discrete fair division
  2. Results on EF1
  3. Results on EFX
  4. Results on MMS
  5. Other notable fairness notions for the main setting
  6. Efficiency and truthfulness
  7. Other setting e.g. limited information, general valuations, randomness …

The Setting

Set NN of nn agents

Set MM of mm goods (can’t be divided or shared)

Agent iNi\in N is equipped with a valuation function vi:2MR0v_i:2^M\rightarrow\mathbb R_{\ge0}, which assigns a non-negative real number to each possible subset of items and is normalized and monotone, i.e., vi()=0v_i(\emptyset)=0 and vi(S)vi(T)STMv_i(S)\le v_i(T)\forall S\subseteq T\subseteq M.

Focus on valuation function of each agent is assumed to be additive. vi(S)=gSvi(g)SMv_i(S)=\sum_{g\in S}v_i(g)\forall S\subseteq M.

A fair allocation instance is denoted by I=(N,M,v)I=(N,M,v) where v=(v1,,vn)v=(v_1,\cdots,v_n) is the vector of valuation functions and can be represented by a table with a row per agent and a column per good, s.t. cell (i,g)(i,g) contains the value vi(g)v_i(g).

An allocation is a tuple of subsets of MM, A=(A1,,An)A=(A_1,\cdots,A_n) s.t. each agent iNi\in N receives the bundle AiM,AiAj=A_i\subseteq M,A_i\cap A_j=\emptyset for every pair of agents i,jNi,j\in N and iNAi=M\cup_{i\in N}A_i=M. If iNAiM\cup_{i\in N}A_i\subsetneq M, the allocation is called partial.

Solution Concepts

Objective: To compute a fair allocation i.e., an allocation that satisfies a desired fairness criterion.

Two fairness notions: envy-freeness and proportionality.

Envy-freeness:

An allocation AA is envy-free (EF) if vi(Ai)vi(Aj)v_i(A_i)\ge v_i(A_j) for every pair of agents i,jNi,j\in N.

所有人认为自己分到的东西比别人分到的东西价值都高的情况,称为无嫉妒的。

Proportionality:

An allocation AA is proportional (PROP) if vi(Ai)vi(M)nv_i(A_i)\ge\frac{v_i(M)}{n} for every agent iNi\in N.

所有人分到的东西都至少能达到他认为物品总价值的 1n1\over n 的分配,成为成比例的。

Obviously, EFPROP,PROP↛EFEF\rightarrow PROP,PROP\not\rightarrow EF.

ER and PROP allocations do not always exist.

Even deciding whether an instance admits an EF or PROP allocation is NP-complete.

Important Relaxations

EF1

Envy-freeness up to one good. (Lipton et al. 2004; Budish. 2011)

对于 ii 来说,如果另一个 jj 得到的物品集中去掉一个特定的物品,ii 就不再嫉妒 jj 了。

  • It is acceptable for an agent ii to envy another agent jj, as long as there exists a good in jj’s bundle the hypothetical removal of which would eliminate ii’s envy towards jj,
  • Definition: An allocation AA is EF1 if for every pair of agents i,jNi,j\in N, it holds that vi(Ai)vi(Aj{g})v_i(A_i)\ge v_i(A_j\diagdown\{g\}) for some gAjg\in A_j.
  • A week notion of EF1: there are times when a very highly-valued good is hypothetically removed from another agent’s bundle.

EFX

To refine this week notion of EF1, we create stricter relaxation, envy-freeness up to any good aka EFX (Gourvès et al. 2014; Caragiannis et al, 2016)

An allocation is said to be EFX if the envy of the agent ii towards agent jj can be eliminated by the hypothetical removal of any good in jj’s bundle.

对于 ii 来说,如果另一个 jj 得到的物品集中去掉任意一个的物品,ii 就不再嫉妒 jj 了。

  • Definition: An allocation AA is EFX if for every pair of agents i,jNi,j\in N, it holds that vi(Ai)vi(Aj{g})v_i(A_i)\ge v_i(A_j\diagdown\{g\}) for any gAjg\in A_j.

The existence of EFX allocation is challenging open problem.

MMS

maximin share fairness (Budish. 2011)

  • Generalization of the rationale of the well-known cut-and-choose protocol.

  • Goal: Give each agent ii goods of value at least as much as her maximin share μin(M)\mu_i^n(M), which is the maximum value this agent could guarantee for herself by partitioning the set of goods MM into nn disjoint bundles and keeping the worst of them.

  • It is a relaxation of proportionality.

  • Definition: Let An(M)\mathcal A_n(M) be the collection of possible allocations of the goods in MM to nn agents. An allocation AA is said to be MMS if for each agent iNi\in N,

    vi(Ai)μin(M)=maxBAn(M)minSBvi(S)v_i(A_i)\ge\mu_i^n(M)=\max_{B\in\mathcal A_n(M)}\min_{S\in B}v_i(S)

Computing MMS allocation or even computing the maximin share of an agent is an NP-hard problem.

MMS allocations do not always exists when there are more than 2 agents. (Kurokawa et al. 2018, 2016)

It’s possible to compute approximate MMS allocations.

Envy-Freeness up to One Good (EF1)

Computing EF1 Allocations

Round-Robin Algorithm

Simplest polynomial time for EF1 allocation computing algorithm is Round-Robin.

  • Allocates the goods to the agents in multiple rounds.
  • In each round, according to some arbitrarily fixed given ordering, each agent chooses her most valuable good among the available ones.

Theorem 1: Round-Robin computes an EF1 allocation.

Envy-Cycle Elimination Algorithm

Lipton et al. 2004

  • Do not use a prefixed sequence for agents to select goods. Instead, it repeatedly chooses an agent that is in a disadvantage compared to other agents and gives an unallocated good.

  • The algorithm maintains a envy graph, where the nodes correspond to agents and there is an edge from agent ii to agent jj if ii is envious of jj’s bundle.

  • At each step of algorithm, an unassigned good is allocated to some agent who is not envied by any other agent i.e., an agent corresponds to a node with in-degree 0 in the envy graph. If no such agent exists, the envy graph must contain a directed cycle, which can be eliminated by redistributing the current bundles among the agents that participate in the cycle.

  • The cycle can be resolved by exchanging the bundles of items along the cycle.

  • Repeating the procedure, eventually leads to a modified ency graph with at least one agent who is not envied by any other agent.

Personal comments: It is kind of like Top Trading Cycle Algorithm???

Envy-Cycle Elimination Algorithm runs in polynomial time and outputs an EF1 allocation.

EF1 and Pareto Optimal (PO) Allocations

Besides fair, another desideratum is efficiency.

(Caragiannis et al. 2019) found inherent connection between EF1, Pareto optimality and maximum Nash welfare (MNW).

Pareto optimal Allocations: An allocation AA is Pareto optimal if there is no allocation BB s.t. vi(Bi)vi(Ai)iNv_i(B_i)\ge v_i(A_i)\forall i\in N and vj(Bj)vj(Aj)v_j(B_j)\ge v_j(A_j) for some jNj\in N. Equivalently, we say such an allocation BB is not Pareto dominated by any other allocation.

MNW allocation: An allocation AA is MNW allocation if:

  1. It maximizes the number of agents with positive value
  2. It maximizes the Nash welfare (ivi(Ai)\prod_iv_i(A_i)) for the agents with positive value.

Theorem 2: Every MNW allocation is EF1 and PO.

There exist allocations that combine fairness with Pareto efficiency. (Yuan and Suksompong 2023) showed that Nash Welfare is the only welfarist function of agent valuations whose maximization leads to allocations that are EF1 and PO.

Computing MNW allocation is hard. In pseudo-polynomial time. Still remains unknown whether this can be done in polynomial time.

Open Problem 1: Can an EF1 and PO allocation be computed in polynomial time?

Envy-Freeness up to Any Good (EFX)

The existence of EFX is challenging open problem.

Existence and Computation of EFX Allocations for Special Cases

Identical Valuations

Plaut and Roughgarden 2020

Allocations that satisfy particular properties about the minimum value are EFX.

A leximin allocation is an allocation that first maximizes the minimum value among all bundles, then maximizes the second minimum value and so on.

leximin is not EFX, but add some slight refinement of it is in fact EFX:

  • After maximizing the minimum value, the allocation must maximize the size of the bundle with minimum value before maximizing the second minimum value and so on.
  • Called leximin++

Any leximin++ allocation AA must be EFX.

Ordered Valuations

Plaut and Roughgarden 2020

Envy-Cycle elimination algorithm returns an EFX allocation for the slightly more general class of ordered instances, where the agents have identical orderings, but possibly distinct cardinal valuations.

  • The ordering of the goods g1,,gmg_1,\cdots,g_m s.t. vi(g1)vi(gm)iNv_i(g_1)\ge \cdots\ge v_i(g_m)\forall i\in N.

Theorem 3: The Envy-Cycle Elimination Algorithm computes an EFX allocation for every ordered instance.

EFX for 2 and 3 Agents

We can compute EFX allocation using a divide-and-choose approach that exploits the existence of EFX allocations for agents with identical valuations.

Theorem 4: EFX allocations always exist for instances with 2 agents.

(Goldberg et al. 2023) showed that it’s possible to efficiently compute EFX allocations when there are only two agents for some more general valuation functions such as gross substitute or budget-additive, but problem becomes PLS-complete for sub-modular functions.

Computing EFX allocations for 3 agents in polynomial time is still an open problem.

Sub-modular function ff:

f(A{i})f(A)f(B{i})f(B)ABN and iNBf(A\cup\{i\})-f(A)\ge f(B\cup\{i\})-f(B)\forall A\subseteq B\subseteq N\text{ and }i\in N\diagdown B

“边际效用递减”

PLS-complete: Polynomial Local Search complete. A problem is PLS-complete if it is PLS and any problem in PLS can be reduced to it in polynomial time.

Bi-valued Valuation

Only 2 distinct possible values that an agent may have for the goods.

(Amandatidis et al. 2021) showed that EFX allocations exist and can be efficiently computed for any number of agents.

(Garg and Murhekar 2021) showed that this is possible even in conjunction with PO.

(Amandatidis et al. 2021) also demonstrated an interesting connection between EFX and MNW allocation for bi-valued instances. MNW allocations always satisfy EFX.

Discussion

Original definition of EFX is a bit weaker because it requires the removed good to be positively-valued.

Open Problem 2: Do EFX allocations exist for instance with n4n\ge4 agents and unrestricted additive valuations?

Relaxations of EFX

Family of Approximately EFX

α\alpha-EFX: Let α[0,1]\alpha\in[0,1], An allocation is α\alpha-EFX if for every pair of agents i,jNi,j\in N, vi(Ai)αvi(Aj{g})v_i(A_i)\ge\alpha \cdot v_i(A_j\diagdown\{g\}) for any gAjg\in A_j.

(Plaut and Roughgarden 2020) showed 12\frac{1}{2}-EFX allocations always exist even for sub-additive valuation functions.

Sub-additive function: v(AB)v(A)+v(B)v(A\cup B)\le v(A)+v(B)

(Chan et al 2019) showed that computing such allocations can be done in polynomial time.

Theorem 5: The Envy-Cycle Elimination algorithm computes a 121\over2-EFX allocation.

The approximation ratio for the additive case was improved by (Amandatidis et al. 2020) to 0.618 by combining Round-Robin and Envy-Cycle Elimination with some appropriate pre-processing.

Open Problem 3: What is the best possible α\alpha for which α\alpha-EFX allocations exist?

如果对于开放问题 3,α=1\alpha=1 成立,那么开放问题 2 也成立。如果开放问题 2 的答案是否定的,那么开放问题 3 就有重大意义。

Additionally, as is the case for all of these notions, the next natural question is whether existence can be paired with polynomial-time algorithms for finding such allocations.

Another recent approach is that of relaxing the requirement to allocate all available goods. Clearly, if done without any constraints, this makes the problem trivial: simply leaving all good unallocated. Here objective is to only leave few goods unallocated or remove some goods without affecting the maximum possible Nash social welfare by too much.

(Caragiannis et al. 2019) showed that it is possible to compute an EFX allocation of a subset of the good the Nash welfare of which is at least half of the maximum Nash welfare on the original set.

(Chaudhury et al. 2021) presented an algorithm that computes a partial EFX allocation, but the number of unallocated goods is at most n1n-1.

(Berger et al. 2022) showed the unallocated goods can be decreased to n2n-2.

(Chaudhury et al. 2021) showed that a (1ϵ)(1-\epsilon)-EFX allocation with a sub-linear number of unallocated goods and high Nash welfare can be computed in polynomial time for every constant ϵ(0,0.5]\epsilon\in(0,0.5].

Open Problem 4: Is it possible to achieve an exact EFX allocation by donating a sub-linear number of goods?

Maximin Share Fairness (MMS)

MMS significantly weakens the requirement of PROP. But MMS are not guaranteed to exist.

The trend is focusing on approximate MMS allocations.

α\alpha-MMS: Let α[0,1]\alpha\in[0,1]. An allocation AA is α\alpha-MMS if vi(Ai)αμin(M)iNv_i(A_i)\ge\alpha\cdot \mu_i^n(M)\forall i\in N.

Monotonicity of the MMS values: remove one agent and one good from the instance, the MMS value of each of the remaining agents in the remaining instance does not increase.

Lemma 1: For any agent ii and any good gg, μin1(M{g})μin(M)\mu_i^{n-1}(M\diagdown\{g\})\ge\mu_i^n(M).

Lemma 1 suggests that if there is a large good gg that satisfies the desired approximation of MMS value for some agent ii, we can simply assign gg to ii and finalize the bundle Ai={g}A_i=\{g\} without hurting the remaining agents in the reduced instance.

Computing 121\over2-MMS Allocations

Consider simple algorithms for computing 121\over2-MMS Allocations in polynomial time. (Better approximation can be achieved by variants and extensions of the techniques employed by these algorithms)

The monotonicity of the MMS value allows us to focus only on the case when the agents have sufficiently small value for the goods, in particular, vi(g)μin2v_i(g)\le\frac{\mu_i^n}{2} for every iN,gMi\in N,g\in M. As long as there is an agent ii and a good gg s.t. vi(g)>μin2v_i(g)\gt\frac{\mu_i^n}{2}, we can allocate gg to ii so that ii obtains half of her MMS value, and never consider ii to gg again. If we guarantee 121\over2-MMS for the remaining agents in the reduced instance, the same guarantee must also hold in the original instance by Lemma 1.

One way to achieve this is by using Round-Robin.

Lemma 2: If vi(g)<μin2v_i(g)\lt\frac{\mu_i^n}{2} for eveery iN,gMi\in N,g\in M, the Round-Robin algorithm returns an allocation that is 121\over2-MMS.

Theorem 6: The Envy-Circle Elimination algorithm computes a 121\over2-MMS allocation.

Theorem 7: The Bag-Filling Algorithm returns a 121\over2-MMS allocation.

Bag here means donation bag.

就是保留某些物品不分配给任何一个玩家(相当于直接捐给慈善机构)

Better Approximations

(Kurokawa et al. 2018) showed how to find 232\over3-MMS allocation (but not in polynomial time)

(Amanatidis et al. 2017) matched this guarantee in polynomial time.

Simpler algorithms rely on important property that the hardest case is when the agents have the same order of preference over the goods:

Given any instance I=(N,M,v)I=(N,M,v) which may not be ordered, we can construct corresponding ordered instance I=(N,M,v)I'=(N,M,v'). Based on an ordering \succ of the goods, for each agent iNi\in N, we find a permutation σi:MN\sigma_i:M\rightarrow N s.t. vi(σi(g))vi(σi(g))v_i(\sigma_i(g))\ge v_i(\sigma_i(g')) for every ggg\succ g'. Then we define a new valuation function viv_i' with vi(g)=vi(σi(g))v_i'(g)=v_i(\sigma_i(g)) for every gMg\in M; hence, the new value of ii for good gg that ranked ll-th in \succ equals the ll-th highest value of ii in original valuation. Hence, if II' admits MMS then II admits an MMS as well (same holds for approximate MMS allocations).

Lemma 3: Let I=(N,M,v)I=(N,M,v) be any instance, II' be its corresponding instance, and A=(A1,,An)A'=(A_1',\cdots,A_n') be an allocation for II' s.t. vi(Ai)αiv_i'(A_i')\ge\alpha_i for every iNi\in N. Then, we can construct in polynomial time an allocation A=(A1,,An)A=(A_1,\cdots,A_n) for II s.t. vi(Ai)αiv_i(A_i)\ge\alpha_i for every iNi\in N.

(Barman and Krishnamurthy 2020) showed the Envy-Cycle Elimination algorithm returns a 232\over3-MMS allocation for ordered instances, thus 232\over3-MMS fair allocation can be found in polynomial time for every instance due to Lemma 3.

(Ghodsi et al. 2021) designed an (34ϵ)(\frac{3}{4}-\epsilon)-approximation algorithm.

(Garg and Taki 2021) improved approximation guarantee of 34+112n\frac{3}{4}+\frac{1}{12n}.

(Feige et al. 2021) showed that it’s impossible to achieve an approximation bound better than 394039\over40.

Open Problem 5: Is it possible to improve upon the bound of 34+112n\frac{3}{4}+\frac{1}{12n} for additive valuations? Is there a stronger inapproximability bound than 394039\over40?

Restricted Instances

By restricting the number of agents or the space of the valuation functions, one can get stronger results.

MMS for four or fewer agents.

  • Two agents: a simple cut-and-choose-type protocol always produce an MMS allocation.

    The first agent partitions the set of goods as equally as possible and the second agent decides who gets each of these sets.

    • The first step is computationally hard but producing a (1ϵ)(1-\epsilon)-MMS allocation in polynomial time.
  • (Kurokawa et al. 2018) guarantees a approximation of 232\over3, for three or four agents it guarantees 343\over4 approximation.

  • (Amanatidis et al. 2017) improved approximation factor for three agents to 787\over8. (Gourvès and Monnot 2019) improved to 898\over9. (Feige and Norkin 2022) improved to 111211\over12.

  • (Ghodsi et al. 2021) improved approximation factor for four agents to 454\over5.

MMS for restricted valuations.

  • All agents have the same valuation functions.
  • (Bouveret and Lemaître 2016) showed that unlike EFX, the hardest instances for MMS are the ordered instances.
  • MMS allocations always exist and can be computed efficiently for ternary valuation function(三元估值函数) (Amanatidis et al. 2017) and for bi-valued valuation functions (Feige 2022)
  • (Ebadian et al. 2022) showed that this is also the case when there are at most two values per agent and for general instances where the value of each good is at least as much as the value of all less valuable goods combined.
  • MMS allocations are known to exist is that of matroid-rank valuations

Open Problem 6: Are there other classes of structured valuations for which MMS is guaranteed to exist, e.g., when there are only a few possible values?

Further Notable Fairness Notions

Other notable fairness beyond EF, PROP, EF1, EFX, MMS.

EFL, EFR, and Epistemic Notions

EFL aka envy-freeness up to one less-preferred good (Barman et al. 2018)

  • EFL is between EF1 and EFX.

  • An agent ii does not envy another agent jj if either AjA_j contains at most one good that ii values positively, or thee envy of ii can be eliminated by the hypothetical removal of a good gAjg\in A_j s.t. vi(Ai)vi(g)v_i(A_i)\ge v_i(g)

  • EFL always exists, and can be computed using a variant of the Envy-Circle Elimination algorithm.

EFR aka envy-freeness up to a random good (Farhadi et al. 2021)

  • The envy of agent ii towards another agent jj can be eliminated in expectation after the hypothetical removal of a randomly chosen good from AjA_j.
  • 0.730.73-EFR allocation can be computed in polynomial time.

Open Question 7: Do EFR allocations always exist?

Epistemic Fairness

  • Agents do not have complete knowledge about the computed allocation.

  • (Aziz et al. 2018) considered a setting where the agents are connected via a social network and do not know the bundles allocated to the agents who are not their neighbor. They introduced epistemic EF under which an agent is satisfied only if there are a redistribution of the goods she is not aware of s.t. the resulting allocation is EF to her.

    (Caragiannis et al 2022) proved the existence of epistemic EFX allocations for additive valuations when the underlying social network contains only isolated nodes.

PMMS and GMMS

Variations of MMS

PMMS aka pairwise maximin share fairness (Caragiannis et al 2019)

  • Every pair of agents ii and jj, ii’s value for AiA_i must be at least as much as the maximum she could obtain by redistribution the set of goods in AiAjA_i\cup A_j into two bundles and picking the worst of them.
  • PMMS requires that it is achieved for any pair of agents.

α\alpha-PMMS: Let α[0,1]\alpha\in[0,1]. An allocation AA is α\alpha-PMMS if vi(Ai)αμi2(AiAj)i,jNv_i(A_i)\ge\alpha\cdot\mu_i^2(A_i\cup A_j)\forall i,j\in N. When α=1\alpha=1, the allocation is called PMMS.

Open Problem 8: Do PMMS allocations always exist?

Any PMMS allocation must be EFX, thus showing the existence of PMMS allocations would also imply the existence of EFX allocations. For approximate PMMS, the best known result is 0.7810.781 by (Kurokawa 2017).

GMMS aka groupwise maximin share fairness (Barman et al. 2018)

  • Stronger notion
  • The maximin share guarantee is simultaneously achieved for any possible subset of agents.

α\alpha-GMMS: Let α[0,1]\alpha\in[0,1]. An allocation AA is α\alpha-GMMS if vi(Ai)αGMMSiv_i(A_i)\ge\alpha\cdot\text{GMMS}_i for all iNi\in N, where

GMMSi=maxSN:iSμiS(jSAj)\text{GMMS}_i=\max_{S\subseteq N:i\in S}\mu_i^{|S|}(\bigcup_{j\in S}A_j)

when α=1\alpha=1, the allocation is called GMMS.

  • (Barman et al. 2018) showed that GMMS allocations exist for some restricted settings, such as when the agents have binary or identical values. EFL allocation is 121\over2-GMMS, such an allocation can be computed efficiently.
  • Best known approximation of GMMS is 474\over7 (Amanatidis et al. 2020; Chaudhury et al. 2021)

Open Problem 9: What is the best possible α\alpha for which α\alpha-GMMS allocations exist?

Prop1, PropX and PropM

Relaxation of proportionality.

Prop1 aka proportionality up to one good (Conitzer et al. 2017)

  • Each agent could obtain her proportional share if given one extra good.
  • An allocation AA is Prop1 if for every agent iNi\in N, there exists a good gMAig\in M\diagdown A_i s.t. vi(Ai{g})vi(M)nv_i(A_i\cup\{g\})\ge\frac{v_i(M)}{n}.

PropX aka proportionality up to any good (Aziz et al. 2020)

  • Each agent could obtain her proportional share when given the least positively-valued good among those allocated to other agents.
  • An allocation AA is PropX if for every agent iNi\in N and any good gMAig\in M\diagdown A_i, we have vi(Ai{g})vi(M)nv_i(A_i\cup\{g\})\ge\frac{v_i(M)}{n}.

An allocation that is Prop1 and PO always exists (Conitzer et al. 2017) and can be computed in polynomial time. (Barman and Krishnamurthy 2019)

PropX is rather demanding and it can not always be guaranteed. (Aziz et al. 2020)

PropM aka proportionality up to maximin good (Baklanov et al 2021)

  • Middle-ground between Prop1 and PropX.

  • Given an allocation AA, the value of a maximin good for agent ii is

    di(A)=maxjimingAjvi(g),d_i(A)=\max_{j\neq i}\min_{g\in A_j}v_i(g),

    and AA is called PropM if vi(Ai)+di(A)vi(M)nv_i(A_i)+d_i(A)\ge\frac{v_i(M)}{n}.

  • PropM always exists and can be computed in polynomial time.

Equitability and its Relaxations

Besides envy-freeness and proportionality, another important fairness notion is that of equitability according to which all agents must derive the same value from the bundles they are allocated.

Definition of Equitability (EQ) (Brams and Taylor 1996): An allocation A=(A1,,An)A=(A_1,\cdots,A_n) is equitable if vi(Ai)=vj(Aj)v_i(A_i)=v_j(A_j) for every pair of agents i,jNi,j\in N.

  • EQ allocation may not exist. similarly to EF1 and EFX, we can relax EQ1 and EQX.

EQ1: An allocation AA is equitable up to one good if, for every pair of agents i,jNi,j\in N, it holds that vi(Ai)vj(Aj{g})v_i(A_i)\ge v_j(A_j\diagdown\{g\}) for some gAjg\in A_j.

EQX: An allocation AA is equitable up to any good if, for every pair of agents i,jNi,j\in N, it holds that vi(Ai)vj(Aj{g})v_i(A_i)\ge v_j(A_j\diagdown\{g\}) for any gAjg\in A_j.

Obviously EQX is EQ1.

(Gourvès et al. 2014) showed that EQX allocation under the nearly jealousy-free always exist and can be computed in polynomial time.

Beyond Fairness: Efficiency and Incentives

Relation between fairness and efficiency. Possibility of achieving fairness when the agents are strategic.

Fair and Pareto Optimal Allocations

Whether it is possible to simultaneously achieve fairness and efficiency.

Common type of efficiency: Pareto Optimality, can be guaranteed in conjunction with some fairness notions like EF1 and Prop1.

(Caragiannis et al. 2019) showed that any allocation that maximizes the Nash welfare is EF1 and PO. But computation of Nash welfare maximizing allocations is NP-hard.

For computation of allocations that are fair and PO, a commonly used technique is to exploit the connection between fair division and market equilibria in Fisher markets (Budish 2011), which has been widely used in the design of approximation algorithms for maximizing the Nash welfare (Cole and Gkatzelis 2018; Cole et al. 2017).

A Fisher market consists of a set of agents NN, a set of goods MM, and each agent iNi\in N has a value vi(g)v_i(g) for every good gMg\in M. In contrast to discrete fair division, each agent ii also has a budget bi0b_i\ge0, and the goods can be fractionally allocated. A fractional allocation is a tuple of vectors X=(xi)iNX=(x_i)_{i\in N}, where xi=(xi1,,xim)x_i=(x_{i1},\cdots,x_{im}); in particular, xig[0,1]x_{ig}\in[0,1] denotes the fraction of gg that is allocated to ii, s.t. iNxig1\sum_{i\in N}x_{ig}\le1 for every gMg\in M.

Focusing on Fisher markets with linear utilities, vi(xi)=gMxigvi(g)v_i(x_i)=\sum_{g\in M}x_{ig}\cdot v_i(g). A market outcome is a tuple (X,p)(X,p), where XX is a fractional allocation and p=(p1,,pm)p=(p_1,\cdots,p_m) defines the price pjp_j for item jj.

An outcome (X,p)(X,p) is a market equilibrium if it satisfies the following conditions:

  1. The market clears (all items are completely allocated): iNxig=1\sum_{i\in N}x_{ig}=1 for every gMg\in M with pg0p_g\ge0.
  2. The budgets of all agents are exhausted: gMpgxig=bi\sum_{g\in M}p_g\cdot x_{ig}=b_i for every iNi\in N.
  3. The agents only spend money on the goods with maximum value per unit of money spent (bang-per-pack): For any gMg\in M, xig>0x_{ig}\gt0 implies vi(g)pgvi(g)pg\frac{v_i(g)}{p_g}\ge\frac{v_i(g')}{p_{g'}} for every gMg'\in M.

Fractional Pareto Optimal (fPO): An allocation is fPO if it’s not Pareto dominated by any fractional allocation.

An fPO allocation is also PO.

When all agents have the same budget (i.e., a competitive equilibrium from equal income, CEEI), the allocation is EF (Varian 1974).

(Barman et al. 2018) compute allocations by perturbing the budgets or the values in the market so that they admit market equilibria with integral allocations.

(Barman et al. 2018) designed a pseudo-polynomial time algorithm to compute an allocation that is EF1 and PO.

Pseudo-polynomial aka 伪多项式时间复杂度,比如 01 背包的动态规划算法就是伪多项式时间复杂度的。

(Barman and Krishnamurthy 2019) designed a strongly polynomial time algorithm to compute an allocation that is PROP1 and PO.

(Garg and Murhekar 2021) showed that in bi-valued instances, an EFX and PO allocation can be computed in polynomial time, but in instances with 3 distinct values, EFX and PO are incompatible.

(Freeman et al. 2019) showed that if all values are strictly positive, there always exists a EQX and PO allocation. But there do not exist EQ1 and PO allocations when the values can be 0.

(Garg and Murhekar 2022) provided a pseudo-polynomial time algorithm to compute an EQ1 and PO allocation.

Approximating the Nash Welfare

MNW are both EF1 and PO.

Worthy probelm: Efficiently computing approximate maximum Nash welfare allocations

(Garg et al. 2017) showed that approximating the Nash welfare within a ratio better than 1.0691.069 is NP-hard, even for additive valuation functions with only four values; in fact it is APX-hard to approximate the Nash welfare even when there only two values (Akrami et al. 2022).

APX

aka Polynomial-time approximation algorithms with approximation ratio bounded by a constant.

For additive valuations, the best known approximation is e1e+ϵ1.45e^{\frac{1}{e}}+\epsilon\approx1.45. (Barman et al. 2018)

For all agents have submodular valuation functions, the best known approximation of Nash welfare is 6+ϵ6+\epsilon (Garg et al. 2022) and the best known lower bound is 1.58191.5819 (Garg et al. 2020).

Under the value oracle model, asymptotically tight approximation ratio of Θ(n)\Theta(n) for both XOS and subadditive functions. (Barman et al. 2020; Chaudhury et al. 2021)\

Value oracle

XOS (aka XOR of Sum)

A set function f:2NRf:2^N\rightarrow\mathbb R is considered XOS if it can be represented as the XOR (exclusive OR) of linear threshold functions. Mathematically, a XOS function can be written as

f(S)=i=1kgi(S)f(S)=\bigoplus_{i=1}^kg_i(S)

  • SS is a subset of elements from the ground set NN.

  • \bigoplus denotes the XOR operation.

  • gi(S)g_i(S) represents a linear threshold function on subset NN.

    gi(S)={1,Sθi0,otherwiseg_i(S)=\begin{cases} 1,|S|\ge\theta_i\\ 0,\text{otherwise} \end{cases}

With stronger oracle assumptions, a sublinear approximation ratio is possible for XOS functions (Barman et al. 2021)

Whether sublinear approximation ratios are possible for subadditive functions with stronger oracle assumption remains unknown.

Egalitarian Welfare

Egalitarian welfare is the minimum utility among all agents.

To maximize the egalitarian welfare is a known APX-hard problems.

While egalitarian welfare maximizing allocations are clearly PO, they may not achieve any constant approximation of important relaxations of EF and PROP, such as EF1 and MMS.

Price of Fairness (PoF)

Another natural goal is to approximately maximize some objective function of the values of the agents such as social welfare, i.e. total value of the agents for the goods they receive(上课讲过).

Social welfare of an allocation AA:

SW(A)=iNvi(Ai)SW(A)=\sum_{i\in N}v_i(A_i)

(Bertsimas et al. 2011) and (Caragiannis et al. 2012) defined the Price of Fairness

  • Similar to approximation ratio in worst-case analysis which measures the deterioration of the objective due to the fairness requirement.
  • Given an instance II, we denote by OPT(I)OPT(I) the maximum social welfare over all allocations of II. Let FF be a fairness criterion (such as EF1 and MMS) and F(I)F(I) be the set of all allocations satisfying FF.

Definition of PoF:

PoF=supIminAF(I)OPT(I)SW(A)=maxDDivisionsSW(D)maxDFair DivisionsSW(S)PoF=\sup_{I}\min_{A\in F(I)}\frac{OPT(I)}{SW(A)}\\ =\frac{\max_{D\in Divisions}SW(D)}{\max_{D\in Fair\ Divisions}SW(S)}

If no fair allocation can achieve non-zero welfare, the PoF is infinite.

The price of fairness w.r.t. fairness criterion FF is also called the price of FF.

(Bei et al. 2021) first consider the PoF w.r.t. relaxations of EF. For instances with 2 agents, the price of EF1 is at least 878\over7.

An upper bound on the price of EF1 follows by a variant of the Adjusted-Winner algorithm (Brams and Taylor 1996). The idea is to sort the goods according to the ratios between the values that they yield to the 2 agents:

v1(g1)v2(g1)v1(g2)v2(g2)v1(gm)v2(gm)\frac{v_1(g_1)}{v_2(g_1)}\ge\frac{v_1(g_2)}{v_2(g_2)}\ge\cdots\ge\frac{v_1(g_m)}{v_2(g_m)}

Intuitively, the first good is more valuable to agent 1 while the last good is more valuable to agent 2. If a minimal set of consecutive goods from left is allocated to the first agent s.t. the allocation is EF1 for her and the remaining goods are given to agent 2, then the allocation is EF1 with social welfare that is within a 32\frac{\sqrt 3}{2}-fraction of the optimal social welfare.

For arbitrary number of agents

  • (Bei et al. 2021) showed that a lower bound of Ω(n)\Omega(\sqrt n) on the price of EF1.
  • (Barman et al. 2020) managed to give a tight upper bound of O(n)O(\sqrt n), also showed tight bounds for other fairness notions, for 121\over2-MMS and Prop1.
  • (Halpern and Shah 2021) showed tight bounds on the price of EF1 and of approximate MMS under the constraint of having only ordinal information about the agent values.
  • A typical assumption made in the context of distortion in social choice (Anshelevich et al. 2021).

Fair Division with Strategic Agents

In the strategic version of the problem, an agent may intentionally misreport the values of goods in order to end up with a better bundle.

This introduces an additional layer of difficulty as goal is to produce fair allocations according to the true values of the agents while declarations might be not true.

This version of problem is considered mostly from a mechanism design without payment perspective, in which the utility of an agent is defined as her true value for her bundle.

Direction 1: Both truthful and fair mechanism.

  • (Caragiannis et al. 2009) showed that no truthful mechanism for 2 agents and 2 goods can always output allocations of minimum envy.
  • (Amanatidis et al. 2016) revisited the problem for the case of 2 agents and any number of goods, and showed that no truthful mechanism can always output α\alpha-MMS allocations for α>2m\alpha\gt\frac{2}{m}.
  • Truthfulness and fairness are incompatible (Amanatidis et al. 2017) This conclusion does not apply to restricted cases.
  • For binary valuations, maximizing the Nash welfare results in a polynomial-time truthful mechanism that outputs EF1 and PO allocations. Analogous result w.r.t. MMS.
  • (Babaioff et al) also showed that for the submodular analog of binary valuations, there is a truthful mechanism that always outputs EFX allocations.

The impossibility results led to different directions.

Direction 2: Stable states of non-truthful mechanisms.

  • (Amanatidis et al. 2021) studied mechanisms that always have pure Nash equilibria, and showed that every allocation that corresponds to an equilibrium of Round-Robin is EF1 w.r.t. the true value of the agents.
  • Similar results for approximate pure Nash equilibria, even for agents with submodular valuation functions (Amanatidis et al. 2023)
  • Strategic setting for general sequential allocation algorithms. (Bouveret and Lang 2014; Aziz et al. 2017)

Open Problem 10: Are there mechanisms that always have pure Nash equilibrium allocations with stronger guarantees than EF1?

Direction 3: Relaxing the requirements of truthfulness

In order to escape from the impossibility.

Not obviously manipulability (Psomas and Verma 2022)

  • A mechanism is not obviously manipulable (NOM) if no agent can increase her best- and worst-case value by lying.

Fortunately, Round-Robin is NOM thus EF1 and NOM are compatible.

EF1, PO and NOM can be achieved simultaneously.

Different Setting

Further meaningful discrete fair division settings.

Limited Information

Only ordinal information is available.

Given only the ordinal preferences of the agents: Envy-Cycle Elimination not works. Sequential-picking algorithm instead.

Round-Robin algorithm can obtain EF1 only needs to know which of the available goods every agent values the most in each round.

Harder to compute approximate MMS allocations.

Let Hn=i=1n1iH_n=\sum_{i=1}^n\frac{1}{i}, (Halpern and Shah 2021) showed that with only ordinal information, it is impossible to achieve better than 1Hn\frac{1}{H_n}-MMS

(Amanatidis et al. 2016) showed that 12Hn\frac{1}{2H_n}-MMS allocations can be computed.

(Hosseini et al. 2021) showed the existence of PO and MMS or EFX allocations when agents have lexicographic preferences.

Another question: Query complexity of unknown valuations.

  • The algorithm can access the valuations by making queries to an oracle.
  • (Oh et al. 2021) proved that Θ(logm)\Theta(\log m) queries suffice to define an algorithm that returns EF1 allocations.
  • It’s an important research direction to explore the relation between the amount of information and fairness guarantees.

General Valuations

Variant of additive valuations

submodular, fractional subadditive, subadditive

Submodular: vi(S)+vi(T)vi(ST)+vi(ST)v_i(S)+v_i(T)\ge v_i(S\cup T)+v_i(S\cap T)

Subadditive: vi(S)+vi(T)vi(ST)v_i(S)+v_i(T)\ge v_i(S\cup T)

XOS: finite number of additive functions a1,,aka_1,\cdots,a_k s.t. vi(S)=maxl[k]al(S)v_i(S)=\max_{l\in[k]}a_l(S)

Any additive function is submodular, any submodular function is XOS, any XOS function is subadditive.

The Envy-Cycle Elimination algorithm returns an EF1 allocation even when the valuation functions of the agents are as general as possible.

MMS

For MMS allocations, if the functions are not restricted, no approximation guarantee can be achieved.

Some literature focus on structured valuations:

  • (Barman and Krishnamurthy 2020) proved that the Round-Robin algorithm returns a 0.210.21-approximate MMS fair allocation for submodular valuations.

    The guarantee was improved to 131\over3 by (Ghodsi et al. 2022), who complemented with an upper bound of 343\over4.

  • For XOS valuations, (Ghodsi et al. 2022) proved the existence of 151\over5-MMS allocations, and designed a polynomial-time algorithm to compute 181\over8-MMS allocations.

    The existence result was improved to 14.61\over4.6 by (Seddighin and Seddighin 2022)

    (Ghodsi et al 2022) showed that no algorithm can do better than 121\over2-approximation for all XOS valuations.

  • For subadditive valuations, (Seddighin and Seddighin 2022) proved the existence of a Ω(1lognloglogn)\Omega(\frac{1}{\log n\log\log n})-MMS allocation, later improved the Ω(1logm)\Omega(\frac{1}{\log m}) guarantee by (Ghodsi et al. 2022).

Best known approximations of MMS for general valuations:

lower boundupper bound
Additive34+112n\frac{3}{4}+\frac{1}{12n}394039\over40
Submodular131\over3343\over4
XOS14.61\over4.6121\over2
SubadditiveΩ(1lognloglogn)\Omega(\frac{1}{\log n\log\log n})121\over2

EFX

  • (Plaut and Roughgarden 2020) proved that 121\over2-EFX allocations always exist for general valuations.

    (Chan et al. 2019) showed that computing such allocations can be done in polynomial time.

  • (Akrami et al. 2022) proved that, for instances with three agents, if one of them has an additive valuation and the others have general valuations, an exact EFX allocation always exists.

Arbitrary Entitlements

Fairness of an allocation must be considered w.r.t. asymmetric entitlements. In many inheritance scenarios, closer relatives have higher entitlements than distant ones.

Formally, in weighted and asymmetric setting, each agent ii has an entitlement 0<si<10\lt s_i\lt1 s.t. iNsi=1\sum_{i\in N}s_i=1

The traditional setting with symmetric agents is a special case when si=1ns_i=\frac{1}{n} for every ii.

Generalized fair notions like weighted EF1, weighted MMS

  • An allocation is weight envy-free (WEF) if vi(Ai)sivi(Aj)sj\frac{v_i(A_i)}{s_i}\ge\frac{v_i(A_j)}{s_j} for every pair of agents i,jNi,j\in N.
  • An allocation is weighted envy-free up to one good (WEF1) if vi(Ai)sivi(Aj{g})sj\frac{v_i(A_i)}{s_i}\ge\frac{v_i(A_j\diagdown\{g\})}{s_j} for every pair of agents i,jNi,j\in N and some gAjg\in A_j.

(Chakraborty et al. 2021) proved that WEF1 allocations always exist and can be computed by a weight-dependent sequential picking algorithm that generalizes the Round-Robin algorithm.

Adapting MMS to the weighted setting (Not straightforward as WEF1):

  • Underlying idea is to define a fairness ratio for each agent. Ideally when the items are divisible, the fairest partition for agent ii is such that vi(Aj)=sjvi(M)v_i(A_j)=s_j\cdot v_i(M) for all jj. However since the items are indivisible, it’s inevitable to induce some some degree of unfairness and the best fairness ratio for agent ii is:

    Fi=maxAAn(M)minjN{vi(Aj)sjvi(M)}F_i=\max_{A\in\mathcal A_n(M)}\min_{j\in N}\left\{\frac{v_i(A_j)}{s_j\cdot v_i(M)}\right\}

  • An allocation AA is weighted maximin share fairness (WMMS) if vi(Ai)μin=Fisivi(M)v_i(A_i)\ge\mu_i^n=F_i\cdot s_i\cdot v_i(M) for every agent iNi\in N. For any α[0,1]\alpha\in[0,1], an allocation AA is α\alpha-WMMS if vi(Ai)αμinv_i(A_i)\ge\alpha\cdot\mu_i^n for every agent iNi\in N.

    Fi1,μinsivi(N)F_i\le1,\mu_i^n\le s_i\cdot v_i(N)

  • When agents are symmetric, WMMS is MMS.

  • (Farhadi et al. 2019) proved that with arbitrary entitlements, the best approximation ratio of WMMS is 1n1\over n, which is somewhat surprisingly guaranteed by the Round-Robin algorithm.

Some novel fairness notions highlight different perspectives of the weighted setting

  • ll-out-of-dd share

  • AnyPrice (APS)

    Maximum value an agent can guarantee to herself if she has a budget equal to her entitlement and the goods are adversarially priced.

    In unweighted setting, the APS value is at least as much as that of MMS, sometimes strictly larger.

    (Babaioff et al. 2021) showed efficiently computing an allocation where every agents gets value no less than 353\over5 of her APS.

    (Aziz et al. 2020) considered weighted PROP1 and presented an algorithm for computing a weighted PROP1 and PO allocation for indivisible items.

Group Fairness

Focus on group-wisely fair.

For divisible items, (Berliant et al. 1992) defined the notion of group envy-freeness (GEF) by restricting envy-freeness to hold for groups of agents with equal size. (strictly stronger than requirement for EF)

(Conitzer et al. 2019) extended GEF for indivisible items, leading to the notion of group-fairness (GF), which take into account groups of different size.

An allocation is group-fair if for any non-empty subset of agent S,TNS,T\subseteq N and every partition (Bi)iS(B_i)_{i\in S} of jTAj\bigcup_{j\in T}A_j, ((ST)vi(Bi))iS((\frac{|S|}{|T|})\cdot v_i(B_i))_{i\in S} does not Pareto dominate (vi(Ai))iS(v_i(A_i))_{i\in S}.

When S=T=1|S|=|T|=1 and S=T=n|S|=|T|=n imply the traditional requirements of EF and PO.

(Conitzer et al. 2019) and (Aziz and Rey 2020) introduced different variants of “up to one” relaxations of GEF/GF and proved existential and hardness results.

(Suksompong 2018) focused on a setting where each agent drives full value from all the goods allocated to the group she belongs to, and showed bounds on the best possible approximation of MMS.

(Kyropoulou et al. 2020) considered EF1 and EFX allocations in the same setting, as well as in settings with dynamic group formation.

Randomness in Fair Division

Randomization can be used as a tool to circumvent impossibilities in the task of allocating indivisible resources.

Best of Both Worlds

Envy-freeness w.r.t. the expected values (ex-ante EF)

In Round-Robin, agents have an advantage over those who are ordered after them. To eliminate this unfair advantage, we consider a randomized version where the ordering of the agents is picked at random.

(Freeman et al. 2020) showed that this randomized Round-Robin guarantees ex-ante PROP but not ex-ante EF.

The Probabilistic-Serial (PS) algorithm (Bogomolnaia and Moulin 2001) is a randomized algorithm for allocating indivisible items in an ex-ante EF manner. Agents eat their most preferred good at a uniform rate and, once consumed, move on to the next available good. The algorithm terminates when all goods have been consumed.

(Freeman et al. 2020) presented a variant of this procedure, the recursive probabilistic serial algorithm that maintains the ex-ante EF property. Moreover every realized allocation is ex-post EF1.

(Aziz 2020) showed that the random allocation generated by the original probabilistic serial algorithm is equivalent to lottery over a set of EF1 allocations.

(Aziz and Brandl 2020) presented an eating algorithm that is suitable for any type of feasibility constraint and allocation problem with ordinal preferences.

(Caragiannis et al. 2021) studied interim envy-freeness, a notion which lies between ex-ante and ex-post envy-freeness.

Stochastic Settings

When the values are randomly drawn from some probability distributions, an envy-free allocation is likely to exist as long as the number of items is sufficiently large compared to the number of agents.

(Dickerson et al 2014) showed that when the values of the agents are independently drawn from an identical distribution, the social welfare maximizing allocation is EF with high probability when m=Ω(nlogn)m=\Omega(n\log n).

(Manurangsi and Suksompong 2020, 2021) improved the lower bound on the existence of envy-free allocations, and showed that the Round-Robin algorithm produces an envy-free allocation for a slightly lower mm. (Bai and Gölz\ 2022) extended this result to the case of asymmetric distributions.

(Bai et al. 2022) showed that given a worst-case instance that does not admit any envy-free allocation, randomly perturbing the values of each agent leads to the existence of envy-free allocations with high probability.

Online Fair Division

Online fair division consider settings where the agents or the goods arrive in an online manner.

TT items arrive online; when an item arrives, the values of the agents for it are realized and based on these we need to decide immediately and irrevocably how to allocate it, typically without knowing future events. (don’t know how many items and value of these items)

Let EnvyT\text{Envy}_T be the cumulative envy until time TT, i.e., the maximum difference between any agent’s value for goods allocated to another agent and to herself in the first TT rounds. It is desired that the envy can vanish as time goes on limT+EnvyTT0\lim_{T\rarr+\infty}\frac{\text{Envy}_T}{T}\rarr0.

(Benade et al. 2018) proved that by allocating the new good to an agent chosen uniformly at random, EnvyT=O~(Tn)\text{Envy}_T=\tilde O(\sqrt\frac{T}{n}), thus we can indeed eliminate the envy over time. They also showed that there exists a deterministic polynomial-time algorithm with the same envy bound as the random allocation algorithm, this bound is asymptotically optimal against an adaptive adversary meaning that the allocation is far from being EF1.

(He et al. 2019) relaxed the requirement of irrevocable decision by allowing the algorithm to reallocate previously allocated items. (If we reallocate all goods at each time i.e., Θ(T2)\Theta(T^2), we can surely achieve EF1. meaningless!) They showed that with 2 agents we actually only need Θ(T)\Theta(T) allocations; for more than 2 agents, O(T32)O(T^\frac{3}{2}) reallocation are sufficient and Ω(T)\Omega(T) are necessary.

It remains to open question whether there exist competitive online algorithm for the computation of approximately MMS or Prop1/PropX allocations. For the case of identical valuation functions, approximate MMS allocation correspond to maximizing the minimum load on the job scheduling problem.

The alternative model that considers a fixed set of resources and agents who arrive or depart over time has not been considered for indivisible resources, partially because it is very challenging to achieve positive results.

Subsidies

Consider the question of whether it is possible to pay the agents just a small amount of money on top of a given allocation in order to make it envy-free.

Allocations for which this can be done are called envy-freeable.

A pair (A,p)(A,p) consisting of an allocation AA and a payment profile p=(p1,,pn)p=(p_1,\cdots,p_n) where pi0p_i\ge0 for every ii, is envy-free if vi(Ai)+pivi(Aj)+pjv_i(A_i)+p_i\ge v_i(A_j)+p_j. An allocation AA is envy-freeable if there are payments pp s.t. (A,p)(A,p) is envy-free.

(Halpern and Shah 2019) noted that not all allocations are envy-freeable. AA is envy-freeable only if AA maximize the utilitarian welfare across all reassignments of its bundles to agents.

A natural question in this setting: Quantifying the minimum total amount of subsidy ipi\sum_ip_i required to find an envy-free allocation.

  • (Halpern and Shah 2019) showed that if a fixed envy-freeable allocation is given, the minimum total subsidy can be computed in polynomial time. However, finding the envy-freeable allocation with overall minimum total subsidy is an NP-hard problem.
  • Deciding the existence of an envy-free allocation without any subsidy is NP-hard (Boveret and Lang 2008)
  • (Caragiannis and Ioannidis 2021) provided additive approximation guarantees and hardness results for computing an envy-freeable allocation that minimizes the total amount of subsidies.

To bound the minimum subsidy required in the worst case over allocations,

  • (Halpern and Shah 2019) proved that any envy-freeable allocation requires no more than (n1)mv(n-1)m\cdot v^* total subsidy, where vv^* is the maximum value of an agent for a good.
  • If we are able to choose the allocations, the n1n-1 factor cannot be removed.

Mixtures of Indivisible and Divisible Items

Scenarios involved both indivisible and divisible goods.

(Bei et al. 2021) proposed a new fairness notion called envy-freeness for mixed goods (EFM), which is a generalization of both EF and EF1 to the mixed goods setting.

Key idea behind EFM

  1. An agent ii’s envy towards another agent jj vanishes if an indivisible good is removed from consideration when jj only gets indivisible goods,

    or

  2. Agent ii does not envy agent jj when jj gets some divisible goods.

They proved that an EFM allocation always exists for any number of agents with additive valuations.

They examined the same setting and explored approximations of MMS.

(Bhaskar et al. 2021) showed that for a mixed resources model consisting of indivisible items and a divisible, undesireble heterogeneous resource, an EFM allocation always exists.

Chores and Mixed Manna

Consider similar questions when items can be seen as chores (can be negatively valued) or mixed manna (a mixture of both goods and chores)

The definition of EF, PROP and MMS remain the same. As in the case of goods, the existence of EF or PROP allocations is rarely guaranteeed.

  • For additive valuations, (Aziz et al. 2017) proved that the Round-Robin algorithm returns a 22-MMS allocation. Later improved to 434\over3 and 11911\over9. On the negative side, (Feige et al. 2021) proved that no algorithm can ensure an approximation factor better than 444344\over43.

  • If the algorithm has access only to the ordinal preferences of agents, the best approximation of MMS can be guaranteed between 757\over5 and 535\over3 (Aziz et al. 2022).

  • When the valuations are submodular, (Li et al. 2022) proved that no algorithm guarantees a better than nn-MMS allocation. (Aziz et al. 2019) considered the case when the agents have asymmetric entitlements and extended the notion of weighted MMS to chores, but the tight approximation ratio is still unknown.

  • Relaxations of EF and PROP need to be changed a bit to capture the fact that the agents have negative values for chores. Essentially, instead of removing goods from bundles of other agents to eliminate the envy of an agent, we nned to remove chores from the bundle of the agent her self.

Definition for EF1 and EFX for chores: For chores, an allocation AA is α\alpha-EF1 if vi(Ai{g})αvi(Aj)v_i(A_i\diagdown\{g\})\ge\alpha\cdot v_i(A_j) for any pair of agents i,ji,j and some gAg\in A; AA is α\alpha-EFX if the inequality holds for any gAg\in A.

  • For additive valuations, an EF1 allocation can be easily computed by Round-Robin algorithm.

  • (Bhaskar et al. 2021) noted that the allocation returned by Ency-Cycle Elimination algorithm may not be EF1 if the cycles are resolved arbitrarily. Instead, the top-trading technique must be used to preserve EF1.

    In contrast to the case of goods where EF1 and PO can be satisfied simultaneously, the compatibility of EF1 and PO is still unknown for chores.

  • (Ebadian et al. 2022; Garg et al. 2022; Chaudhury et al. 2022) proved that for bi-valued instances, EF1+PO allocations always exist and can be found efficiently; this is the only known result so far.

  • The existence of EFX allocations for chores also remains open, with the only positive result being the computation of O(n2)O(n^2)-EFX allocations due to (Zhou and Wu 2022).

Other Settings

Some allocations may not be feasible due to various restrictions, such as connectivity, cardinality, separation or budet constriants.

  • (Suksompong 2021) discuss this part in detail.
  • (\Sheddighin et al. 2021) and (Aziz et al. 2021) studied externalities in fair division, where agents not only have value for what they get but also for what others get.
  • (Conitzer et al. 2017; Fain et al. 2018; Garg et al. 2021) related to public resource allocaation whre the items can be shared by the agents.