Fair and Almost Truthful Mechanisms for Additive Valuations and Beyond

In recent years, the field of discrete fair division has received extensive attention. In the canonical model, $m$ indivisible goods, which are positively valued, are divided among a group of $n$ competing agents in a fair manner without disposal. Arguably, the most appealing fairness notion is envy-freeness (EF), which is defined as each agent weakly preferring his own bundle to any other agent’s bundle. However, in the indivisible regime, EF allocations may not exist, even approximately: Consider the instance with two agents competing for one good. Given the intractability of EF, some of its natural relaxations are envy-freeness up to one good (EF1) proposed by [LMMS04] and [Bud10], and envy-freeness up to any good (EFX) introduced by [CKM⁺19] and [GMT14]. In an EF1 (EFX) allocation, agent $i$ may envy agent $j$, but the envy can be eliminated by removing one (any) good from agent $j$’s bundle. It is known that EF1 allocations always exist and can be computed in polynomial time for general valuations [LMMS04], whereas the existence of EFX allocations remains open even for additive valuations. See the surveys by [ABFV22] and by [ALMW22] for more details of the non-strategic setting¹¹1These two surveys are later combined into one [AAB⁺23]..

Nevertheless, in most practical situations, agents have no incentive to faithfully report their preferences if misreporting leads to a better outcome from their perspective. This results in a game-theoretic perspective of the fair division problem, under which the quest for fairness becomes significantly less tractable. Given that malicious behaviors of agents can result in severe fairness and welfare losses, a large body of research papers focus on designing mechanisms that are both truthful and fair [LMMS04, CKKK09, MP11, ABM16]. Unfortunately, [ABCM17] shows that truthfulness is incompatible with any reasonable fairness concept if monetary transfers are prohibited, and this even holds for two agents with additive valuations.

Given the impossibility of combining fairness and truthfulness, the next direction to pursue is devising sufficiently fair mechanisms, which serves as the primary objective in our setting, while remaining close to truthfulness. Even though agents are still incentivized to manipulate under the relaxed requirement for truthfulness, there still exist reasons to settle for slight relaxation. Firstly, we measure agents’ incentive to manipulate, which will be specified later, in a worst-case sense, and thus, the incentive for misreporting is very likely to be even smaller in the concerned applications. Moreover, performing effective manipulations is costly since it requires knowing other agents’ preferences, which are usually difficult to acquire, and the best response turns out to be computationally intractable even for several elementary mechanisms including Round-Robin and cut-and-choose [ABLM17, ABF⁺21].

As a natural relaxation of truthfulness, the notion of incentive ratio has been widely studied under the contexts of Fisher markets [CDT⁺22], resource sharing [CDL20, CDLY22, CCD⁺19], housing markets [Tod19], and resource allocation [HWWZ24, XL20, BTWY23]. Informally, the incentive ratio of a mechanism is defined as the worst-case ratio between the utility that an agent gains by manipulation and his utility under truthful telling. The definition of incentive ratio is also closely related to the popular notion of approximate Nash equilibrium [Rub17, CFGS15].

In this paper, we explore the possibility of simultaneously achieving fairness and a small incentive ratio²²2This resembles the concept of price of fairness [BLMS21, BBS20], which captures the efficiency loss in fair allocations as opposed to the incentive loss.. In the most well-studied setting of additive valuations, [XL20] shows that Round-Robin, which satisfies EF1, admits an incentive ratio of $2$. Inspired by the recent focus on fair division for more general valuations in both the non-strategic setting [CGM21, BCFF22, BK20] and the strategic setting [ABL⁺23], we also consider valuation classes that largely generalize additivity. In particular, one of our main focuses is the class of cancelable valuations, which generalizes budget-additive, unit-demand, and multiplicative valuations [BCFF22] and has found its applications in various fair division results [BCFF22, ABL⁺23, AAC⁺23]. In addition, we also look into subadditive and submodular valuations, which constitute fundamental properties in combinatorial optimization and have been of recent interest in the fair division literature [ABL⁺23, CGM21, BK20].

As conventions, given a mapping $f:X\to Y$, let $f^{-1}(y)=\{x\in X\mid f(x)=y\}$ for every $y\in Y$ and $f(X^{\prime})=\{f(x)\mid x\in X^{\prime}\}$ for every $X^{\prime}\subseteq X$.

Let $G=\{g_{1},\ldots,g_{m}\}$ denote the set of $m$ goods and $N=[n]$ be the set of $n$ agents. A bundle is a subset of $G$. An allocation $A=(A_{1},\ldots,A_{n})$ is defined as a partition of $G$ satisfying $A_{i}\cap A_{j}=\emptyset$ for all $i\neq j$ and $\bigcup_{i=1}^{n}A_{i}=G$, where $A_{i}$ denotes the bundle received by agent $i$.

We assume that each agent $i$ is associated with a non-negative valuation $v_{i}(G^{\prime})$ for each set of goods $G^{\prime}\subseteq G$; for convenience, we write $v_{i}(g)$, $v_{i}(S-g)$ and $v_{i}(S+g)$ instead of $v_{i}(\{g\})$, $v_{i}(S\setminus\{g\})$ and $v_{i}(S\cup\{g\})$. We assume that every $v_{i}$ is normalized, i.e., $v_{i}(\emptyset)=0$, and monotone, i.e., $v_{i}(S)\leq v_{i}(T)$ for all $S\subseteq T\subseteq G$. We also adopt the shortcut $v_{i}(T\mid S)$ for the marginal value of a set of goods $T$ with respect to a set of goods $S$, i.e., $v_{i}(T\mid S)=v_{i}(T\cup S)-v_{i}(S)$. For each agent $i$, we say that $v_{i}$ is

• •

  subadditive, if $v_{i}(S\cup T)\leq v_{i}(S)+v_{i}(T)$ for all $S,T\subseteq G$.

• •

  submodular, if $v_{i}(g\mid S)\geq v_{i}(g\mid T)$ for all $S\subseteq T\subseteq G$ and $g\in G\setminus T$.

• •

  cancelable, if $v_{i}(S+g)>v_{i}(T+g)\implies v(S)>v(T)$ for all $S,T\subseteq G$ and $g\in G\setminus(S\cup T)$.

• •

  additive, if $v_{i}(S\cup T)=v_{i}(S)+v_{i}(T)$ for all $S,T\subseteq G$ with $S\cap T=\emptyset$.

Note that although both submodular and (subadditive) cancelable valuations are strict superclasses of additive valuations, neither one is a superclass of the other [ABL⁺23]. Given an allocation $A$, define the utility of agent $i$ as $v_{i}(A_{i})$.

We define the fairness notion considered in this paper as follows.

A mechanism $\mathcal{M}$ takes a valuation profile $\boldsymbol{v}=(v_{1},\ldots,v_{n})$ as input, and outputs an allocation $\mathcal{M}(\boldsymbol{v})=(\mathcal{M}_{1}(\boldsymbol{v}),\ldots,\mathcal{M}_{n}(\boldsymbol{v}))$, where $\mathcal{M}_{i}(\boldsymbol{v})$ denotes the bundle received by agent $i$. Each agent has an underlying true valuation and is required to report a (possibly fake) valuation to the mechanism. We adopt the notion of incentive ratio to quantify the degree of untruthfulness of a mechanism.

Observe that the incentive ratio of every mechanism is at least $1$ by setting $v_{i}^{\prime}=v_{i}$. If the incentive ratio of a mechanism is $1$, then we say that the mechanism is truthful.

In this section, we consider additive valuations and show an incentive ratio lower bound of $1.5$ for $(\frac{1}{2}+\epsilon)$-EF1 mechanisms, where $\epsilon>0$ can arbitrarily depend on $n$ and $m$.

The rest of this section is devoted to proving Theorem 3.1, for which we construct a series of profiles and show that $(\frac{1}{2}+\epsilon)$-EF1 and an incentive ratio of strictly smaller than $1.5$ cannot be simultaneously guaranteed in all these profiles. Assume for contradiction that a $(\frac{1}{2}+\epsilon)$-EF1 mechanism $\mathcal{M}$ for additive valuations exists with an incentive ratio of $\alpha$ satisfying $1\leq\alpha<1.5$. Suppose that there are $n=2$ additive agents and $m=7$ goods. For every $i\in[2]$, denote $N_{i}$ as the set of goods $\alpha$-controlled by agent $i$ with respect to $\mathcal{M}$. By Lemma 2.4, $(N_{1},N_{2})$ forms a partition of $G$. Without loss of generality, assume that $|N_{1}|\geq 4$ and $\{g_{1},g_{2},g_{3},g_{4}\}\subseteq N_{1}$. Denote $G^{\prime}=\{g_{1},g_{2},g_{3},g_{4}\}$, and every constructed additive valuation $v$ in the proof will satisfy $v(G\setminus G^{\prime})=0$. For simplicity, we assume goods in $G\setminus G^{\prime}$ always to be assigned to agent $1$, and we omit them when describing valuations and allocations.

We start with the profile $\boldsymbol{v}^{(0)}=(v_{1},v_{2})$ where

Let $\delta$ be an arbitrary real number with $\delta\geq 5$, and we consider the next profile $\boldsymbol{v}^{(1)}=(v_{1}^{\prime},v_{2})$ where

We proceed to the next profile $\boldsymbol{v}^{(2)}=(v_{1}^{\prime\prime},v_{2})$ where

In the next profile, we modify the valuation of agent $2$. Define $\boldsymbol{v}^{(3)}=(v_{1}^{\prime},v_{2}^{\prime})$ where

In the next profile, we manage to allocate $g_{2}$ to agent $2$. Define $\boldsymbol{v}^{(4)}=(v_{1}^{\prime\prime},v_{2}^{\prime\prime})$ where

We present our final profile to derive a contradiction. Define $\boldsymbol{v}^{(5)}=(v_{1}^{\prime\prime},v_{2}^{\prime})$ where

In this section, we consider cancelable valuations and show that every $\epsilon$-EF1 mechanism admits an infinite incentive ratio, where $\epsilon>0$ can arbitrarily depend on $n$ and $m$.

The rest of this section is devoted to proving Theorem 4.1. In particular, we establish Theorem 4.1 by showing a stronger statement that every $\epsilon$-EF1 mechanism for multiplicative valuations, which constitute a subset of cancelable valuations [BCFF22], admits an infinite incentive ratio. Recall that a valuation $v$ is multiplicative if $v(S)=\prod_{g\in S}v(g)$ for every $S\subseteq G$ with $|S|\geq 1$. Moreover, since we assume valuations to be normalized and monotone, a multiplicative valuation $v$ should also satisfy $v(\emptyset)=0$ and $v(g)\geq 1$ for every $g\in G$.

Assume for contradiction that there exists an $\epsilon$-EF1 mechanism $\mathcal{M}^{c}$ for multiplicative valuations with an incentive ratio of $\alpha<\infty$, where $\alpha$ can arbitrarily depend on $n$ and $m$. We construct a mechanism $\mathcal{M}$ for additive valuations as follows, which we will show that satisfies $\frac{9}{10}$-EF1 with an incentive ratio of at most $1.1$, violating Theorem 3.1. Given $\delta>0$ and an additive valuation $v$, define $v^{\delta}$ as the multiplicative valuation satisfying $v^{\delta}(\emptyset)=0$ and $v^{\delta}(S)=\exp(\delta\cdot v(S))$ for every $S\subseteq G$ with $|S|\geq 1$, and it is easy to verify that $v^{\delta}$ is normalized and monotone. Given as input an additive valuation profile $(v_{1},\ldots,v_{n})$, let $\delta>0$ be a sufficiently large real number such that for all $i\in N$ and $S\subseteq G$ with $v_{i}(S)>0$,

and $\mathcal{M}$ outputs the allocation $\mathcal{M}^{c}(v_{1}^{\delta},\ldots,v_{n}^{\delta})$. Note that $\delta$ is a function of $(v_{1},\ldots,v_{n})$, $\epsilon$, and $\alpha$.

We first show that $\mathcal{M}$ satisfies $\frac{9}{10}$-EF1 for additive valuations.

Next, we show an incentive ratio upper bound of $1.1$ for $\mathcal{M}$ with additive valuations.

Finally, combining Lemma 4.2 and Lemma 4.3, it follows that $\mathcal{M}$ satisfies $\frac{9}{10}$-EF1 with an incentive ratio of at most $1.1$ for additive valuations, which contradicts Theorem 3.1, concluding the proof of Theorem 4.1.

We have shown in Theorem 4.1 that every EF1 mechanism for cancelable valuations admits an infinite incentive ratio. In this section, we show that this impossibility result can be bypassed with the additional property of subadditivity. In particular, for subadditive cancelable valuations, we show that Round-Robin, which satisfies EF1, admits an incentive ratio of $2$. Then, we complement our positive result by providing an incentive ratio lower bound of $\varphi=(1+\sqrt{5})/2\approx 1.618$ for $(\varphi-1)$-EF1 mechanisms with subadditive cancelable valuations, improving the lower bound of $1.5$ implied by Theorem 3.1.