Generalizing Envy-Freeness toward Group of Agents

1 Introduction

Fairness is an important criterion for analyzing mechanisms, and several concepts of it have been studied so far in economic theory. A concept called envy-freeness (or noenvy condition) has especially been widely discussed [Foley, 1967]. A mechanism is envy-free if no individual envies another individual. Recently, this concept has also been discussed in computer science to design fair task scheduling procedures in multi-machines models [Mu'Alem, 2009].

The traditional definition of envy-freeness only considers an individual envy toward another individual. However, in such domains as combinatorial auctions, it is natural to consider different types of envy. For example, assume agent 1 wants two items g1 and g2 together, where her valuation of {g1, g2} is 10. But g1 is allocated to agent 2 at payment 3, and g2 is allocated to agent 3 at payment 4. Then agent 1 feels envy; she obtains nothing, and a group of agents, i.e., agents 2 and 3 obtained g1 and g2 and paid only 7 in total.

She prefers the outcome of this group of agents to her own outcome.

In mechanisms without monetary transfer (e.g., cakecutting), avoiding such types of envy seems impossible. Certainly, an individual prefers obtaining the entire cake rather than having only a piece of it. On the other hand, in mechanisms with monetary transfer, such as combinatorial auctions or task scheduling, it would be fair to allocate a set of items/tasks to an agent who is willing to pay more. Thus, we need stronger concepts for fairness/envy-freeness.

In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group (ItGEFness) and envy-freeness of a group toward a group (GtGEFness), which are natural extensions of traditional envyfreeness. We refer to the traditional one as envy-freeness of an individual toward an individual (ItI-EFness).

In a sense, a Pareto efficient allocation is the best, since items are allocated to agents who are willing to pay the most in total. However, in many situations, we cannot achieve a Pareto efficient allocation, e.g., computing a Pareto efficient allocation is too time consuming, or the possibility of false-name bids prevents a Pareto efficient allocation [Yokoo, 2003]. In such cases, some itemmight remain unsold, or several items might be sold in a single bundle, even though selling them separately would be more efficient. Our new fairness concepts guarantee that the obtained allocation is locally efficient, i.e., most efficient within some alternatives.

We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize mechanisms that satisfy these concepts by focusing on their allocation rules (Theorems 2 and 3). Our characterization is an extension of the results by Haake et al. [2002]. Then we clarify the connections between these concepts and three other properties; the core, strategy-proofness, and false-name-proofness. A part of our obtained results is summarized in Figure 1.

As shown in the above example, an envy toward a group can naturally occur in environments with complementarities. Also, with monetary transfer, it is possible to design a mechanism that prevents such an envy. We believe that our new fairness concepts brings up a new interesting research direction in mechanism design.

1.1 RelatedWorks

There are lots of literature on envy-freeness in the fields of economics and computer science. Haake et al. [2002] characterized allocation rules of envy-free mechanisms by a property called local efficiency. Mu'Alem [2009] showed an efficient method to check whether an allocation is locally efficient. Othman and Sandholm [2010] discussed the connection between envy-freeness and the core in iterated combinatorial auctions. Cohen et al. [2010] provided a complete characterization for the allocation rules of envy-free and strategy-proof mechanisms in conjunction with cyclemonotonicity [Rochet, 1987].

Vind [1971] and Varian [1974] proposed an extension of envy-freeness called coalition fairness (or group no-envy), which requires that no group of agents envies any other group of the same size. Lahaie and Parkes [2009] discussed the link between the core and coalition fairness in fair package assignment model.

Coalition fairness (or group no-envy) is an old concept but it has been attracting less attention compared to standard envy-freeness. We suspect that coalition fairness might be too specific since it restricts the scope of envy-freeness within same-sized groups (although this restriction seems inevitable in mechanisms without monetary transfer). Our GtG-EFness puts no restriction on the size of groups. Thus, it can be considered as an extension of coalition fairness 1 . We believe this extension would make the old fairness concept more attractive in social choice and mechanism design.

Zhou [1992] proposed another version of envy-freeness called strict no-envy in the literature of fair allocation. Strict no-envy property requires that no agent envies the average of the allocation given to any group of agents, while our ItGEFness requires no agent envies the sum of the allocation given to any group.

Besides these works, the structure of our concepts closely resembles false-name-proofness, which is an extension of strategy-proofness. The concept considers the possibility that one agent pretends to be multiple agents (see e.g., [Yokoo, 2003]).

2 Preliminaries

We consider a set of items G (|G| = m) for sale and a set of agents (bidders) N = {1, . . . , n}. Each agent i ∈ N has her valuation function vi ∈ Vi that maps sets of items into R. Here Vi is the set of possible valuation functions. We assume a quasi-linear, private value model with no allocative externality; the utility of agent i, who obtains a set of items (bundle) B ⊆ G and pays p, is represented as vi(B) - p. vi is normalized so that vi(∅) = 0 holds.

To describe a mechanism, we sometimes use a concept called minimal bundle.

Definition 1 (Minimal Bundle). For agent i with valuation function vi, B is a minimal bundle for i, if ∀B′ ⊂ B and B′ ̸= B, vi(B′ ) < vi(B).

1 Note that coalition fairness does not overlap with our ItGEFness.

Figure 1: Summary of connections between ItG-EFness, GtG-EFness, the core, SPness, FNPness, and Pareto efficiency. Light shadowed area corresponds to core-selecting mechanisms (Theorem 7). Dark shadowed area is empty (Theorem 11).

We say agent i is single-minded if i has at most one minimal bundle with a positive value. We call such a bundle as a required bundle. In a general domain, agent i can have multiple minimal bundles. In some parts of this paper, we consider a single-minded domain, where all agents are single-minded. Let v = (v1, . . . , vn) ∈ V be a valuation profile and V = ×i∈NVi be a domain of mechanisms. A (direct revelation) combinatorial auction mechanismM(f, p) consists of an allocation rule and a payment rule. An allocation rule is defined as f : V → A, where A is a set of the possible assignment of items over N. For an assignment a ∈ A, let ai indicates the bundle allocated to agent i. Note that an assignment a ∈ A must satisfy allocation feasibility; ⋃i∈N ai ⊆ G and ∀i, j where i ̸= j, ai ∩ aj = ∅. A payment rule is defined as p : V →RN . For a valuation profile v, let fi(v) and pi(v) respectively denote the bundle allocated to agent i and the amount agent i must pay in a mechanism M(f, p). We use notations f(vi, v-i) and p(vi, v-i) to represent the allocation and payment when the declared valuation of agent i is vi and the declared valuation profile of other agents is v-i.

In this paper, we restrict our attention to deterministic mechanisms that satisfy individual rationality with nonnegative payment. Individual rationality (IR) means that no participant obtains negative utility by reporting her true valuation. Formally, ∀i ∈ N, ∀v, vi(fi(v)) - pi(v) ≥ 0. We also assume a mechanism is almost anonymous across agents; obtained results from a mechanism are invariant under the permutation of the identifiers of agents except for the case of ties. Furthermore, we assume that a bundle allocated to agent i must be one of her minimal bundles. This assumption does not affect the quality of outcome, e.g., the efficiency or the seller's revenue.

Also, in some part of this paper, we represent a mechanism as a price-oriented, rationing-free (PORF) mechanism [Yokoo, 2003]. A PORF mechanism defines a skeleton of a mechanism as follows: (i) for each agent, the price of each bundle of items is determined independently of her own valuation, and (ii) the mechanism allocates each agent a bundle that maximizes her utility independently of the allocations of other agents. Prices of bundles must be determined so that they satisfy allocation feasibility. In a PORF mechanism, when the valuation profile reported by j ̸= i is v-i, the price of agent i for a bundle Bi is described as p(v-i,Bi). Yokoo [2003] showed that the PORF representation is a complete characterization of mechanisms that satisfy an incentive property called strategy-proofness (discussed in detail in Section 5). Similar price-based representations of strategy-proof mechanisms have also been presented by others, including [Lavi et al., 2003].

Next, let us introduce a fairness concept called envyfreeness. To distinguish it from the other fairness concepts that we will introduce, we refer to it as envy-freeness of an individual toward an individual (ItI-EFness).

Definition 2 (Envy-Freeness of an Individual toward an Individual). A mechanismM(f, p) satisfies envy-freeness of an individual toward an individual (ItI-EFness) if ∀i, ∀j ̸= i, and ∀v, vi(fi(v)) - pi(v) ≥ vi(fj (v)) - pj (v).

In other words, a mechanism satisfies ItI-EFness (or is ItIEF) if no agent prefers the pair of the bundle and the price of another agent to her own bundle and price. Haake et al. [2002] proposed a property called locally efficient bundle assignment and characterized the allocation rules of ItIEF mechanisms. To introduce the property, let us define a notion of permutation. We say that an assignment a′ = (a′1, . . . , a′n) ∈ A is a permutation of another assignment a = (a1, . . . , an) ∈ A if ∀i, ∃j, such that a′i = aj holds.

Definition 3 (Locally Efficient Bundle Assignment). An allocation a is a locally-efficient bundle assignment (LEBA) with respect to v if ∀a′ , where a′ is a permutation of a, ∑i∈N vi(ai) ≥ ∑i∈N vi(a′i ) holds.

Theorem 1 (Haake et al. 2002). An allocation rule f is ItIEF-achievable, i.e., there exists a non-negative IR payment rule p such that the mechanismM(f, p) is ItI-EF, if and only if f(v) is an LEBA with respect to v for every v ∈ V .

To evaluate the performance of mechanisms, we focus on a worst-case analysis (competitive analysis). Such analysis is commonly used in recent mechanism design literature, especially by computer scientists.

Definition 4 (Competitive Ratio of Efficiency). A competitive ratio of efficiency for a mechanismM(f, p) is c if

3 Envy-Freeness Toward AGroup

In this section, we define two extensions of ItI-EFness.

Definition 5 (Envy-Freeness of an Individual toward a Group). A mechanismM(f, p) satisfies envy-freeness of an individual toward a group (ItG-EFness) if ∀i, ∀S ⊆ N, and ∀v,

In other words, a mechanism satisfies ItG-EFness (or is ItG-EF) if no agent envies a group of agents. Note that in Eq. (1), agent i can be included in S. Thus, this type of envy includes the situation that agent i feels, if I received j's items (as well as my current items) and additionally paid pj , I would be happier.

Next, First, let us define . Using this notation, let us define the competitive ratio of efficiency.

Definition 6 (Envy-Freeness of a Group toward a Group). A mechanism M(f, p) satisfies envy-freeness of a group toward a group (GtG-EFness) if ∀v, ∀S, S ′ ⊆ N,

Note that V ∗ (S, B) is a surplus for a set of agent S when a set of items B are optimally allocated to S:

where ⋃i∈S ai = B and ⋂i∈S ai = ∅.

GtG-EFness requires that no group of agents envies any other group of agents. Note that in Eq. 2, S and S ′ can overlap. Thus, this type of envy includes all agents feel that if items were allocated in a better way, everybody would be happier. From these definitions, a GtG-EF mechanism satisfies ItG-EFness, and an ItG-EF mechanism satisfies ItI-EFness.

In a single-minded domain, these inclusion relations are strict. The VCG mechanism is ItI-EF but not ItG-EF. If agent i wins bundle Bi, ∀j ̸= i, where j's required bundle is Bj ⊆ Bi, i's payment is at least vj(Bj). Thus, agent j has no envy toward i. On the other hand, consider the example described in Section 1. If agent 2's valuation for g1 is 6 and agent 3's valuation for g2 is 7, the allocation and payment of VCG are exactly the same as this example. Thus, VCG is not ItG-EF.

The SET mechanism, which sells the set of items G to a single agent using the Vickrey (second-price) auction, is ItGEF but not GtG-EF. In the above example, the SET mechanism allocates g1 and g2 to agent 1 at payment 7. Then, agents 2 and 3 as a group envy agent 1. Furthermore, a mechanism called the first-price combinatorial auction mechanism, which uses the Pareto efficient allocation rule and collects the winners' reported values as payment, satisfies GtG-EFness.

3.1 Characterizing ItG-EFness and GtG-EFness

In this subsection, we characterize ItG-EF/GtG-EF mechanisms by focusing on their allocation rules. First, let us define the property called ItG-EF/GtG-EF-achievability. We say an allocation rule is ItG-EF/GtG-EF-achievable if there exists a non-negative IR payment rule p such that the mechanism M(f, p) satisfies ItG-EFness/GtG-EFness.

To characterize ItG-EF/GtG-EF-achievable allocation rules, let us define two additional concepts:

• An assignment a′ is a permutation with merger of another assignment a if ∀i, ∃Si ⊆ N, a′i = ⋃j∈Si aj .
• An assignment a′ is a permutation with split/merger of another assignment a if ⋃i∈N a′i = ⋃i∈N ai.

By using these concepts, let us define two properties called LEBA with merger (LEBA-M) and LEBA with split/merger (LEBA-SM).

Definition 7 (LEBA with Merger). An allocation a is an LEBA with Merger (LEBA-M) with respect to v if ∀a′ , where a′ is a permutation with merger of a, ∑i∈N vi(ai) ≥ ∑i∈N vi(a′i ) holds.

Definition 8 (LEBA with Split/Merger). An allocation a is an LEBA with Split/Merger (LEBA-SM) with respect to v if ∀a′ , where a′ is a permutation with split/merger of a, ∑i∈N vi(ai) ≥ ∑i∈N vi(a′i ) holds.

In other words, an LEBA-SM a allocates a set of items ⋃i∈N ai ⊆ G optimally to N, while it allows some item to remain unsold. The idea of LEBA-SM is similar to a property called consistency, which was introduced in the literature of fair allocation [Tadenuma and Thomson, 1991]. The following theorems clarify the relation between ItG-EFness/GtGEFness and LEBA-M/SM. For space reasons, we only show the proof of Theorem 3.

Theorem 2. If an allocation rule f is ItG-EF-achievable, then f(v) is an LEBA-M with respect to v for every v ∈ V . Also, the converse is true in a single-minded domain.

Theorem 3. If an allocation rule f is GtG-EF-achievable, then f(v) is an LEBA-SM with respect to v for every v ∈ V . Also, the converse is true in a single-minded domain.

Proof (if part). In the definition of GtG-EFness, by choosing S = S ′ = N, we obtain

Thus,

holds. From the definition of V ∗ , ∀a′ , which is a permutation with split/merger of a,

holds. Thus,

holds.

Proof (converse part). Consider an allocation rule f that is LEBA-SM in a single-minded domain. We choose a payment rule p such that pi(v) = vi(fi(v)) and show that the mechanism M(f, p) satisfies GtG-EFness.

We derive a contradiction by assuming that ∃v, ∃S, S ′ ⊆ N, such that

where a = f(v), holds. Since pi(v) = vi(ai), we have

Here, we can assume ∀i ∈ S, vi(ai) = 0 holds; otherwise, such an agent i does not have a positive valuation in V ∗ (S, ⋃j∈S′ aj), since the required bundle ai is not included in ⋃j∈S′ aj . Thus, we have the same inequality for the set of agents S \ {i}.

Let us consider an assignment a′ , where ⋃j∈S′ aj are optimally allocated to S, items ⋃i∈S ai are optimally allocated to S′ \ S, and the rest of items are allocated in the same way as a. Note that a′ is a permutation with split/merger of a.

From the definition of a′ , we have

where X = N \ (S ∪ S ′ ). This violates the assumption that f(v) is an LEBA-SM.

3.2 Competitive Analysis

The following theorems show that when the domain is general, even if f satisfies LEBA-SM (more specifically, f is Pareto efficient), there exists no payment rule p such that M(f, p) satisfies ItG-EFness.

Theorem 4. The competitive ratio of efficiency for any ItGEF mechanism in a general domain is at most 3/4.

Proof. We derive a contradiction by assuming that mechanism M(f, p) satisfies ItG-EFness and its efficiency ratio is strictly more than 3/4. Consider three agents and two items g1, g2. Agent 1 values 2 for g1 and 3 + ϵ for g2. Agent 2 values 3 only for {g1, g2}. Agent 3 values 2 only for g2. Since f's efficiency ratio is strictly more than 3/4, agent 1 wins g1 and agent 3 wins g2. From IR, agent 3 pays at most 2. Also, from ItG-EFness for agent 2, the sum of their payments must be at least 3. Thus, agent 1's payment is at least 1. In this case, agent 1 envies agent 3, which contradicts ItG-EFness. Then, the best possible allocation is to allocate g2 to agent 1, where the efficiency ratio is (3 + ϵ)/4.

Theorem 5. The competitive ratio of efficiency for any GtGEFness mechanism in a general domain is at most 1/2.

Proof. We derive a contradiction by assuming that mechanismM(f, p) satisfies GtG-EFness and its efficiency ratio is strictly more than 1/2. Consider three agents and two items g1, g2. Agent 1 values 2 for g1 and 2 + 2ϵ for g2. Agent 2 values 4 - ϵ only for {g1, g2}. Agent 3 values 2 only for g2. Using a similar argument to Theorem 4, allocating g1 to agent 1 and g2 to agent 3 is impossible. Also, fromGtG-EFness, it is impossible to allocate both items to agent 2; otherwise, the group of agents 1 and 3 will envy. Then, the best possible allocation is to allocate g2 to agent 1, where the efficiency ratio is (1 + ϵ)/2.

3.3 Non-trivial GtG-EFMechanism

The previous subsection shows that the competitive ratio of a GtG-EF mechanism in a general domain is at most 1/2. This implies that even the first price combinatorial auction mechanism does not satisfy GtG-EFness. Thus, the GtGEFness condition seems very restrictive and one might imagine that developing a non-trivial GtG-EF mechanism in a general domain is impossible. However, we show that this pessimistic conjecture is not true; there exists a non-trivial GtGEF mechanism called the average-max minimal-bundle (AMMB) mechanism [Ito et al., 2005]. Quite surprisingly, this mechanism is also strategy-proof, while the first price combinatorial auction mechanism is not.

Definition 9 (Average-Max-Minimal-Bundle (AM-MB) mechanism). The Average-Max-Minimal-Bundle (AM-MB) mechanism is defined as a PORF mechanism, in which for agent i, the price of bundle Bi is defined as:

where Bi ∩Bj ̸= ∅ and Bj is a minimal bundle for agent j.

As stated in [Ito et al., 2005], the AM-MB mechanism is a strategy-proof, greedy allocation mechanism (i.e., easy to compute) and achieves better efficiency and revenue in expectation, although its worst-case efficiency ratio can be arbitrarily small.

We show that the AM-MB mechanism is GtG-EF.

Theorem6. The AM-MBmechanism is GtG-EF in a general domain.

Proof. Let us assume AM-MB is not GtG-EF and derive a contradiction. We assume, ∃v, ∃S, S ′ ⊆ N, the following inequality holds:

where a = f(v). Here, denote S ′I = S∩S ′ , and S′C = S ′\SI . In the left-hand side of Eq. (3), each term in the summation is non-negative. Thus,

holds. Assume agent i ∈ S receives Bi in V ∗ (S, ⋃j∈S′ aj). Then, the right-hand side of Eq. (3) can be re-written as:

Thus, we obtain:

From the definition of AM-MB, we can rewrite Eq. (4) as:

Each term within the summation of the right-hand side of Eq. (5) corresponds to an item g ∈ ⋃j∈S′ aj. Then, for each g ∈ ⋃j∈S′ aj, consider agent j who receives the item g in a = f(v). Agent j is either in S ′I or S ′C . If j ∈ S′I ,

holds for all i ∈ S such that Bi ∩aj ̸= ∅; otherwise, j cannot obtain aj. Note that vj(aj)/|aj| appears in the left-hand side of Eq. (5). Also, if j ∈ S ′C ,

holds (since vi(Bi)/|Bi| is used for calculating pj(v)). Note that pj(v)/|aj | also appears in the left-hand side of Eq. (5). In summary, for each term vi(Bi)/|Bi| in the right-hand side of Eq. (5), there also exists a corresponding term in the left-hand side, which is no less than vi(Bi)/|Bi|. Also, these left-hand terms are non-overlapping. This is a contradiction.

4 Connection with the Core

In this section, we discuss the connection between GtGEFness and the core. Let us introduce the definition of coreselecting auctions [Day and Milgrom, 2008].

Definition 10 (Blocking Coalition). For a mechanism M(f, p) and a valuation profile v, where a = f(v) and Gr = G \ ⋃i∈N ai, S ⊆ N is a blocking coalition if there exists S ′ ⊆ N, such that the following condition holds:

Here, Gr is a set of items that are not allocated to any agent. If S is a blocking coalition, the members of S can ask the seller to allocate Gr ∪ ⋃j∈S′ aj to them instead of S ′ by paying slightly more than ∑j∈S∪S′ pj(v). Then, both the seller and the members of S are better off. Thus, the outcome of this mechanism is unstable.

Definition 11 (Core-selecting mechanism). A mechanism M(f, p) is core-selecting if ∀v, there exists no blocking coalition.

The next theorem shows that the core selection implies GtG-EFness in a single-minded domain.

Theorem 7. In a single-minded domain, a mechanism is core-selecting if and only if it is Pareto efficient and GtG-EF.

Proof sketch. In a single-minded domain, wlog, we can assume each agent i in a blocking coalition S obtains ∅ (if not, S \ {i} is also a blocking coalition). Also, we can assume Gr = ∅ in a core-selecting or Pareto efficient mechanism. Thus, the left-hand side of the blocking coalition condition must be 0 and the condition is simplified to:

Also, in a single-minded domain, wlog, we can assume each agent i ∈ S in Eq. (2) obtains ∅. Then, the left-hand side of Eq. (2) must be 0, and the condition is simplified to:

It is clear that GtG-EFness is equivalent to the fact that there exists no blocking coalition.

Theorem 8. In a general domain, there exists no coreselecting ItG-EF mechanism.

Proof. From Theorem 4, there exists no Pareto efficient ItGEF mechanism. Also, a core-selecting mechanism must achieve a Pareto efficient allocation. Thus, there exists no core-selecting ItG-EF mechanism.

5 Connection with SPness

Strategy-proofness (SPness) is a property that deals with incentives of agents. A mechanism satisfies SPness (or is SP) if reporting true valuation vi is a weakly dominant strategy for any agent i and for any valuation profile v-i. First, let us clarify the connection between ItI-EFness and SPness. We omit the proof since it is almost identical to the proof of Theorem 13.

Theorem 9. Any SP mechanism is ItI-EF in a single-minded domain, but not vice versa.

Rochet [1987] proposed a property of allocation rules called cycle-monotonicity and characterized SP mechanisms. However, Cohen et al. [2010] showed that even if an allocation rule f is LEBA and cyclic-monotone, there might be no appropriate payment rule p such that M(f, p) is both ItI-EF and SP. Since ItG-EFness is more restrictive than ItI-EFness, this statement is also true for ItG-EFness. Indeed, although the Pareto efficient allocation rule is LEBA-M and cyclicmonotone, there is no appropriate payment rule even in a single-minded domain (see Theorem 11).

Our next objective is to obtain a complete characterization of ItG-EF SP mechanisms.

5.1 Characterization

As we stated in Section 2, Yokoo [2003] gave a complete characterization of SPness by introducing a class of PORF mechanisms. To characterize ItG-Ef SP mechanisms, let us define the following property.

Definition 12 (No-Envy Pricing Rule Toward A Group). A PORF mechanism satisfies no-envy pricing rule toward a group (NEP) if ∀v, ∀i ∈ N, and ∀S ⊆ N, if Bj maximizes j's utility ∀j ∈ S, then

holds.

By using this property, we obtain the following characterization theorem.

Theorem 10. In a single-minded domain, an SP mechanism M(f, p) is ItG-EF if and only if its prices satisfy NEP.

Proof sketch. In a single-minded domain, an agent whose utility is positive does not envy any group of agents. Then, the left-hand side of Eq. (1) becomes 0. Thus, the ItG-EFness condition is simplified to:

which is identical to NEP.

Neither the first-price combinatorial auction mechanism nor the VCG mechanism satisfy NEP. On the other hand, the SET mechanism satisfies NEP in a single-minded domain, since the winner's price equals maxj∈N\{i} vj(Bj), where Bj is j's required bundle.

5.2 Competitive Analysis

In this subsection, we discuss the competitive ratio achieved by an ItG-EF SP mechanism. Putting aside SPness, we already revealed that there exists a Pareto efficient ItG-EF mechanism in a single-minded domain. However, taking into account SPness, there no longer exist such Pareto efficient mechanisms even in a single-minded domain.

As an upper bound, we obtain the following result.

Theorem 11. The competitive ratio of efficiency for any ItGEF SP mechanism is at most 2/3.

Proof. Consider three agents and two items {g1, g2}. Agents 1 and 3 value 1 for g1 and g2, respectively. Agent 2 values 1 for a bundle {g1, g2}. Thus, if a mechanism achieves an efficiency ratio better than 2/3, both agents 1 and 3 must win. Let us define the payments of agents 1 and 3 as p1 and p3, respectively. From ItG-EFness, they must satisfy p1+p3 ≥ 1. Thus, either p1 or p3 must be greater than or equal to 1/2. Wlog, we assume p1 ≥ 1/2.

Next, consider the case where agent 1 has a valuation p1-ϵ. From SPness, the payment in which agent 1 wins the item g1 must be uniquely determined when the other agents' reports are fixed. Thus, from IR, agent 1 with valuation p1 - ϵ cannot win the item g1 and the efficiency is at most 1. In a Pareto optimal allocation, the efficiency is 1+p1-ϵ. Thus, efficiency ratio is 1/(1 + p1 - ϵ), which cannot be strictly more than 2/3.

Theorem12. In a single-minded domain, the lower bound of the competitive ratio of efficiency for an ItG-EF SP mechanism is 2/(m+ 1).

Proof. In a single-minded domain, the competitive ratio of a FNP mechanism called adaptive reserve price (ARP) mechanism [Iwasaki et al., 2010] is 2/(m+ 1). From Theorem 13, this mechanism is also ItG-EF.

6 Connection with FNPness

False-name-proofness (FNPness) generalizes strategyproofness by assuming a bidder can submit multiple bids under fictitious identifiers, e.g., multiple e-mail addresses [Yokoo, 2003]. A mechanism satisfies FNPness (or is FNP) if for each agent, reporting her true valuation using a single identifier (although the agent can use multiple identifiers) is a weakly dominant strategy. From the definition, a FNP mechanism is SP. We show that FNPness implies ItG-EFness in a single-minded domain.

Theorem 13. Any FNP mechanism is ItG-EF in a singleminded domain, but not vice versa.

Proof. First, we derive a contradiction by assuming that a FNP mechanism M(f, p) is not ItG-EF. We assume ∃v, ∃i, and ∃S ⊆ N, such that

holds. Then, the left-hand side of the above equation must be 0; if the left-hand side is positive, the right-hand side cannot exceed the left-hand side.

Next, let us consider the case where a set of agents S drops out and agent k, who has exactly the same valuation as i, joins. Since the mechanism is almost anonymous, the utilities of agents i and j must be the same. Since agents are singleminded, their utilities cannot be positive at the same time. Thus,

where vN\S indicates the valuation profile reported by a set of agent N \S. However, agent k can make the situation identical to the above case by using false identifiers and obtain the set of bundles ⋃j∈S fj(v) at payment ∑j∈S pj(v), which is strictly smaller than vk(⋃j∈S fj(v)). This violates FNPness.

The converse is not true since AM-MB is ItG-EF (GtG-EF) but not FNP even if the domain is single-minded.

7 Conclusions and Future Works

In this paper, we introduced two new concepts of fairness called envy-freeness of an individual toward a group and envy-freeness of a group toward a group, which are natural extensions of traditional envy-freeness. We characterized them and clarified their connections with the core, strategyproofness, and false-name-proofness.

Our new fairness concepts bring up a new interesting direction in mechanism design. Although we obtained a fair amount of initial results, there remain many interesting research questions. For example, we want to obtain the full characterization of allocation rules for ItG-EFness/GtGEFness with/without SPness in a general domain. Also, we want to narrow the gap between the lower/upper bounds of the competitive ratio. Furthermore, we hope to investigate the envy-freeness of a group toward an individual (GtI-EFness), which would be related to a manipulation that is symmetric to false-name bidding, i.e., a coalition of agents negotiates and sends one representative to a mechanism.

Acknowledgements

This research was partially supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Research (A), 20240015, 2008, and Grant-in-Aid for JSPS fellows. The authors would like to thank Daisuke Oyama and anonymous reviewers for helpful discussions.