# Mechanism Design without Money for Fair Allocations

Manisha Padala and Sujit Gujar<EMAIL_ADDRESS><EMAIL_ADDRESS>Machine Learning Lab, International Institute of
Technology, HyderabadIndia

(2018)

###### Abstract.

Fairness is well studied in the context of resource allocation. Researchers
have proposed various fairness notions like envy-freeness (EF), and its
relaxations, proportionality and max-min share (MMS). There is vast literature
on the existential and computational aspects of such notions. While computing
fair allocations, any algorithm assumes agents’ truthful reporting of their
valuations towards the resources. Whereas in real-world web-based applications
for fair division, the agents involved are strategic and may manipulate for
individual utility gain. In this paper, we study strategy-proof mechanisms
without monetary transfer, which satisfies the various fairness criteria.

We know that for additive valuations, designing truthful mechanisms for EF,
MMS and proportionality is impossible. Here we show that there cannot be a
truthful mechanism for EFX and the existing algorithms for EF1 are
manipulable. We then study the particular case of single-minded agents. For
this case, we provide a Serial Dictatorship Mechanism that is strategy-proof
and satisfies all the fairness criteria except EF.

Fair Allocation, Mechanism Design

††copyright: acmcopyright††journalyear: 2018††doi:
10.1145/1122445.1122456††conference: Woodstock ’18: ACM Symposium on Neural
Gaze Detection; June 03–05, 2018; Woodstock, NY††booktitle: Woodstock ’18: ACM
Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Theory of computation Algorithmic
mechanism design

##  1\. Introduction

Fair division of resources is critical in various situations like division of
inheritance or land and allocation of rooms to housemates, jobs to workers,
time slots to courses. In a typical scenario, the agents involved report their
valuations for the resources available. The central aggregator or the
underlying software aggregates these reported valuations to output a fair
allocation. Various web-based applications like Spliddit 111www.spliddit.org,
Fair Proposals System 222www.fairproposals.com, Coursematch
333www.coursematch.io, Divide Your Rent Fairly
444https://www.nytimes.com/interactive/2014/science/rent-division-
calculator.html, etc offer such solutions readily. Often the participants are
strategic and misreport their valuations to improve their utility. The party
that strictly adheres to the protocol and reveals its true valuation (while it
can misreport and achieve more utility) may find it unfair if others misreport
for their benefit even though the underlying algorithm is fair for the
reported types. In auction settings, one prevents such strategic manipulations
through monetary transfers. Whereas in resource allocation, no monetary
transfers are allowed. Hence, it is essential to look for truthful mechanisms
that ensure fairness without payments.

In this paper, we focus on indivisible resources and the fairness notions of
_envy freeness_ (EF), _proportionality_ and _maxi-min share_ (MMS).
Proportionality (Steihaus, 1948) is the first concept of fairness ever
proposed. It ensures that each agent receives a fair share of its utility.
Another popular notion is envy-freeness (EF). An allocation is EF when no pair
of agents exist such that one of the agents increases its utility by
exchanging their allocated goods (Foley, 1967). For divisible goods, EF
allocations always exist (Stromquist, 1980), and complete allocation may not
exist for indivisible goods. It is also NP-hard to compute an approximation to
EF (Lipton et al., 2004). When the valuations are sub-additive, EF implies
proportionality (Bouveret and Lemaître, 2016). Although proportionality is a
weaker notion, its existence is still not guaranteed for indivisible goods.

Given the above results, in (Lipton et al., 2004; Budish, 2011), the authors
relax EF and introduce EF up to the most-valued good or EF1. An EF1 allocation
is always guaranteed to exist even for indivisible goods and can be computed
in polynomial time by the cycle-elimination algorithm (Lipton et al., 2004).
It is interesting to consider EFX, which is EF up to the least-valued good
(Caragiannis et al., 2019). It is stronger than EF1. EFX always exists for up
to three agents (Chaudhury et al., 2020). For indivisible goods, another
fairness criteria considered is MMS (Budish, 2011), where each agent’s utility
is at least its MMS guarantee. The MMS guarantee is the worst-case value an
agent receives when partitioning the goods and others choose before it. MMS
allocation is guaranteed to exist for up to two agents (Procaccia and Wang,
2014).

The above existential and complexity results assume that each agent’s
preferences (determined using their valuations for each bundle) are known. In
this work, we are interested in preference elicitation to prevent
manipulations. Hence we study the existence of truthful or SP (Strategy-Proof)
mechanisms that ensure fairness or _Strategy-Proof Fair_ (SPF).

Property | Single-Minded | Identical | Additive
---|---|---|---
|  | Additive (NSP) | ($n=2$) | ($n\geq m$)
EF |  |  | ✗(Lipton et al., 2004) |
Proportionality | ✓(SD)555Only when proportionality exists |  | ✗(Amanatidis et al., 2016) ( alternate proof) |
EFX | ✓(SD) |  | ✗(Theorem 3.2) (even for $m=4$ ) |
EF1 | ✓(SD) | ✓(RSD) | ✗(Amanatidis et al., 2017) ($m\geq 5$) | ✓(RSD)
MMS | ✓(SD) |  | ✗(Amanatidis et al., 2016) |
Table 1. Existence of SPF Mechanisms for Various Types of Valuations

###  1.1. Strategy-Proof Fair

A direct-revelation mechanism takes all the input valuation functions and
returns an allocation. A direct-revelation mechanism is SPF if it ensures fair
allocation when no agent can gain higher utility by misreporting. In mechanism
design literature, it is standard to introduce payments to design truthful
mechanisms, especially in auction settings (Goldberg and Hartline, 2003; Cohen
et al., 2011; Tang and Zhang, 2015). In this paper, we focus on the basic
model of fair mechanism design without money. When the goods are divisible,
the authors in (Menon and Larson, 2017; Bei et al., 2017) prove that no
deterministic SP mechanism (without monetary transfers) is proportional or
even approximately proportional for complete allocation. Since EF is stronger
than proportionality, having an SP mechanism for EF is also impossible. It is
known that there exist randomized SP mechanisms which ensure EF when the goods
are divisible (Mossel and Tamuz, 2010). There are other works like (Cole et
al., 2013; Chen et al., 2013; Brânzei et al., 2017) which give SPF mechanisms
without money for divisible goods. In (Bouveret and Lang, 2011), the authors
show that sequential allocation is strategy-proof when agents have identical
rankings. This way of allocation is referred to as _Picking Sequences_.

#### SPF Mechanism for Indivisible goods

In Lipton et al. (Lipton et al., 2004), the authors prove that it is
impossible to design a truthful mechanism that achieves minimum envy or EF by
providing a counterexample. When there are two agents ($n=2$) and the number
of goods ($m$) are greater than 5, there cannot be a deterministic SP
mechanism with complete allocation for EF1 even for additive valuations
(Amanatidis et al., 2017). There are impossibility results for MMS in
(Amanatidis et al., 2016), the authors prove that for 2 agents, there is no
truthful mechanism that ensures better than $\frac{1}{m/2}$ -MMS allocation.

###  1.2. Our Contribution

Given the above limiting results, we explore the following in this paper

  1. (1)

We study the EFX property for two agents, where it is guaranteed to exist.
From (Amanatidis et al., 2017), it is impossible to have SP mechanism for EF1
with two agents and more than $5$ goods. EFX being a stronger property also
follows the same result for the given setting. This paper provides an example
that proves that designing an SP mechanism for EFX is impossible even when the
number of goods is $4$.

  2. (2)

Aligning with the results of (Amanatidis et al., 2017), we provide examples to
show that greedy round-robin algorithm and cycle-elimination algorithm for
finding EF1 are manipulable. When agents have identical additive allocations,
greedy round robin provides allocations that is EF1 as well as strategy-proof.

  3. (3)

Given that the valuations can be very complex to represent in general, we
restrict ourselves to the simpler case of (SM) _single-minded_ agents. SM
bidders is very common in the auction literature multi-item setting (Rassenti
et al., 1982; McMillan, 1994). In such a setting, we provide (SD) _(Serial
Dictatorship Mechanism)_ that again extends greedy to obtain SP mechanism for
EFX, EF1, MMS. SD also provides proportional allocations when they exist.

In Table 1, we summarize all the results for the existence of an SP mechanism
for various fairness criteria. (Blue ones are the results in this paper.) When
the agents are single-minded, SD is a direct SP mechanism that also ensures
EF1, EFX, MMS and proportionality when it exists. When the valuations are
(additive) identical, RSD is an SP mechanism that ensures EF1. Additive
valuations are the most well-studied in literature. For EF, proportionality,
EFX, there are counter-examples when there are $2$ agents for proving that an
SP mechanism cannot exist when valuations are additive. Even for MMS and EF1
under additive valuations, the results are for $2$ agents.

##  2\. Preliminaries

###  2.1. Notation

Consider the problem of division of indivisible resources. We represent each
instance by $\langle N,M,V\rangle$ which are formally defined below,

  * •

Finite set of agents $N=\\{1,\ldots,n\\}$

  * •

Finite set of indivisible goods $M=\\{1,\ldots,m\\}$.

  * •

Valuation functions $V$ where $v\in V$ denotes a particular profile and
$\forall i\in N$, $v_{i}:2^{M}\rightarrow\mathbb{R}_{+}$. Let $v_{-i}$ be the
valuation profile of all agents excluding $i$.

  * •

We assume $v_{i}$ is monotonic, $\forall i\in N,\forall S\subseteq T\subseteq
M,v_{i}(S)\leq v_{i}(T)$

  * •

Additive valuations imply for any $S\subseteq M,v_{i}(S)=\sum_{j\in
S}v_{i}(\\{j\\})$

  * •

Identical valuations imply $\forall i,j\in N,\forall S\in
M,v_{i}(S)=v_{j}(S)$. Identical additive valuations imply $v_{i}$ is both
identical and additive.

  * •

Single minded agents with desirable bundles $D=(D_{1},\ldots,D_{m})$. The
valuation of an agent $i\in N$ is given by, for a $c\in\mathbb{R}_{+}$

(1) $\forall S\in M,\ v_{i}(S)=\begin{cases}c,&\text{if }S\supseteq D_{i}\\\
0,&\text{otherwise}\end{cases}$

  * •

The set of all possible complete allocations, $\mathcal{A}$. Given
$A\in\mathcal{A}$ denotes a specific allocation and $A_{i}$ is allocation per
agent. By complete allocation we mean if there are $m$ goods then $\forall
A,\sum_{i}|A_{i}|=m$, assuming each resource can be allocated only to a single
agent.

###  2.2. Important Definitions

We define the relevant fairness notions below with examples,

###### Definition 2.1 (Proportionality).

Given an instance $\langle N,M,V\rangle$, the allocation $A$ is proportional
_iff_ $\forall i\in N$,

$v_{i}(A_{i})\geq\frac{1}{n}v_{i}(M)$

####  2.2.1. Example.

Consider two agents $1$ and $2$ and three goods $a,b,c$. $v_{i}$ is given
below where $(x,y)\in\\{(a,b),(b,c),(c,a)\\}$.

| $v(a)$ | $v(b)$ | $v(c)$ | $v(x,y)$ | $v(a,b,c)$
---|---|---|---|---|---
1 | 10 | 20 | 15 | 30 | 30
2 | 10 | 20 | 15 | 30 | 30

Possible proportional allocations are when 1 receives item $b$ and 2 receives
goods $\\{a,c\\}$ or vice versa. Also when agent 1 receives $c$ and agent 2
receives goods $\\{a,b\\}$ or vice versa.

###### Definition 2.2 (Envy-freeness (EF)).

For $\langle N,M,V\rangle$ an allocation $A$ is envy-free _iff_ ,

$\forall i,j\in N\ \ v_{i}(A_{i})\geq v_{i}(A_{j})$

####  2.2.2. Example.

Consider 2 agents $1$ and $2$, two goods $a$, $b$. For agent 1,
$v_{1}(a)=20,v_{1}(b)=10$ and for agent 2, $v_{2}(a)=10,v_{2}(b)=20$. It is
envy-free to allocate $a$ to agent 1 and $b$ to agent 2.

Both the notions of proportionality and EF are too strong in the case of
indivisible goods and are not guaranteed to exist. Consider the case when
there are two agents and only one item, it is impossible to have any
allocation that is either EF or even proportional. When the valuations are
sub-additive, every EF allocation is proportional as shown in Figure 1. In
(Lipton et al., 2004), the authors define the following notion weaker than EF.

###### Definition 2.3 (EF1).

For $\langle N,M,V\rangle$ an allocation $A$ is EF1 _iff_ $\forall i,j\in N,$
$\exists a\in A_{j}$ such that,

$v_{i}(A_{i})\geq v_{i}(A_{j}\backslash\\{a\\})$

EF1 allocation always exists for general monotone valuations. Another
relaxation of EF stronger than EF1 is defined below,

###### Definition 2.4 (EFX).

For $\langle N,M,V\rangle$ an allocation $A$ is EFX _iff_ , $\forall i,j\in
N,$ $\forall a\in A_{j}$ such that,

$v_{i}(A_{i})\geq v_{i}(A_{j}\backslash\\{a\\})$

####  2.2.3. Example.

We saw before in Example 2.2.2 that EF allocation is not possible when there
are two agents and only one item. But an allocation where the item is assigned
to either 1 or 2 is both EF1 and EFX.

Unlike EF1, EFX is guaranteed to exist only for three agents or when agents
have identical valuations. The relations between EF, EFX and EF1 is
represented in Figure 1 for any general monotonic valuations.

In (Budish, 2011), the author defines another threshold based definition of
fairness where each agent is guaranteed at least as much valuation as a risk-
averse agent would guarantee itself. By risk-averse we mean an agent who
assumes that given a partition of the bundles it might end up in receiving the
bundle with minimum valuation. Hence, if the agent decides the partition, it
would do so to maximize the value of the minimum bundle. This is in the same
spirit of a cut-and-choose protocol.

###### Definition 2.5 (Maximin Share (MMS)).

For $\langle N,M,V\rangle$ an allocation $A$ is MMS _iff_ $\forall i\in N$,

$v_{i}(S_{i})\geq\mu_{i}$

where

$\mu_{i}=\max_{A\in\Pi_{n}(M)}\min_{A_{j}\in A}v_{i}(A_{j})$

Figure 1. Relation between Various Fairness Criteria (Bouveret and Lemaître,
2016)

####  2.2.4. Example.

Consider there are two agents $1$ and $2$, three goods $a,b,c$. We consider
additive valuations for both agents. Let the valuation of each item be given
as follows,

| $v(a)$ | $v(b)$ | $v(c)$
---|---|---|---
1 | 10 | 20 | 40
2 | 10 | 40 | 20

In this example $\mu_{1}=\mu_{2}=30$. Agent 1 gets $c$ and 2 gets $a,b$ would
be an MMS allocation.

There is no straight forward relation between EF1/EFX and MMS allocations; for
two agents MMS implies EFX. Although any allocation which is proportional is
also MMS when the valuations are sub-additive, Figure 1. There exists an MMS
allocation for 2 agents but it may not exist for more than two agents.

###  2.3. Strategy-Proof Mechanisms

In mechanism design, we assume the agents are self-interested and strategic.
The agents have private information (valuation over goods) that is
indispensable for the desired outcome. The agents may or may not reveal their
private information based on their individual utility. Mechanism design deals
with the two-fold problem of i) _Preference Elicitation_ and ii) _Preference
Aggregation_. In the former, one explores the specific mechanism in which the
agents’ best interest lies in revealing their true valuations. The latter,
nonetheless challenging, is the problem of obtaining the desired outcome, once
the true valuations are known. In our case, this would be finding the fair
allocation. There are two kinds of approaches for solving the problem of
preference elicitation. 1)Direct Mechanism 2) Indirect Mechanism. We focus on
direct mechanism which is defined as follows,

###### Definition 2.6 (Direct Mechanism).

The direct mechanism ($\mathbb{M}$) maps true valuations of the agents to the
desired outcome. It is a mapping from the valuations of the agents to the
space of allocations $\mathbb{M}:V\rightarrow\mathcal{A}$.

A direct mechanism is strategy-proof (SP) if the agents do not have any
incentive to misreport, more formally,

###### Definition 2.7 (Deterministic SP Mechanism).

A deterministic mechanism $\mathbb{M}$ is strategy-proof (SP), if $\forall v$,
$\forall i\in N$,

$v_{i}(\mathbb{M}(v_{i},v_{-i}))\geq
v_{i}(\mathbb{M}(v^{\prime}_{i},v_{-i})),\ \forall v^{\prime}_{i}\ \forall
v_{-i}$

where $v^{\prime}_{i}$ is a misreported valuation.

We also look for little weaker mechanism, in the context of identical
valuations.

###### Definition 2.8 (Deterministic NSP Mechanism).

A deterministic mechanism $\mathbb{M}$ is Nash strategy-proof (NSP), if
$\forall v$, $\forall i\in N$ when other agents report truthfully,

$v_{i}(\mathbb{M}(v_{i},v_{-i}))\geq
v_{i}(\mathbb{M}(v^{\prime}_{i},v_{-i})),\ \forall v^{\prime}_{i}$

where $v^{\prime}_{i}$ is a misreported valuation.

Note that, in NSP, it is best response to each agent to report truthfully if
others are reporting truthfully. SP is stronger notion of truthfulness – no
matter what others are reporting, it is a best response for each agent to
report truthfully.

###### Definition 2.9 (strategy-proof Fair Mechanism (SPF)).

A mechanism $\mathbb{M}$ is SPF _iff_ $\mathbb{M}$ is SP or NSP and fair (for
the given fairness condition).

Before we discuss the existence of SPF mechanisms for various fairness
criteria, we would like to state an observation that makes our search easier.
The observation is based on the relationship between the various fairness
criteria given in Figure 1,

###### Observation 1.

For any two fairness criteria $X$ and $Y$, if $X\implies Y$ from Figure 1,
i.e., every allocation that satisfies $X$ also satisfies $Y$. We can conclude
that, if there does not exist an SP mechanism for $Y$, then there will not
exist an SP mechanism for $X$.

With this background, we first present impossibilities of SP and fair
mechanisms for additive valuations.

##  3\. Impossibilities of Strategy-Proof and Fair Mechanisms for Additive
Valuations.

As we have discussed before, fair allocations may still cause unrest among
agents if some agents choosing to lie benefit when agents adhering to the
rules and revealing their true valuations forgo the benefits they could have
received. In this paper we are concerned about the existence of truthful
mechanisms that can implement the fairness definitions defined above.

###  3.1. EF

In (Lipton et al., 2004), the authors raise the question of the existence of
truthful mechanisms that implement EF.

###### Theorem 3.1.

(Lipton et al., 2004) Any mechanism that returns an allocation with minimum
possible envy cannot be truthful. The same is true for any mechanism that
returns an envy-free allocation whenever there exists one.

As a proof, the authors provide an example consisting of two agents with
additive valuation function, where every possible envy-free allocation can be
manipulated by either of the agents. An SP mechanism for EF,
($\mathbb{M}^{EF}$) would select from $\mathcal{A}^{EF}$, i.e, a set of all EF
allocations. If there exists a valuation profile $v$, where
$\mathcal{A}^{EF}_{v}$ be all possible EF allocations for $v$, $\forall
A^{EF}\in\mathcal{A}^{EF}_{v}$ and with strict inequality for atleast one
$A^{EF}$.

(2) $\exists i,\ \exists v^{\prime}_{i}\ s.t.,\ \
v_{i}(\tilde{A}^{EF}_{i})\geq
v_{i}(A^{EF}_{i}),\quad\forall\tilde{A}^{EF}\in\mathcal{A}^{EF}_{v^{\prime}}$

We know that for any deterministic SP mechanism that ensures EF,
$\mathbb{M}^{EF}(v)\subseteq\mathcal{A}^{EF}_{v}$, hence the Equation 2 holds
for $\mathbb{M}^{EF}(v)$ which implies that no matter the mechanism, it is
always manipulable by certain agent $i$ under the valuation profile, $v$.

###  3.2. Proportionality

For sub-additive valuations, proportionality is a stronger property than MMS
(Figure 1). In (Amanatidis et al., 2016), the authors prove that for 2 agents
there is no SP mechanism that ensures better than $\frac{1}{m/2}$-MMS
allocation. Hence, it is impossible to have SP mechanism which ensure MMS and
hence proportionality for 2 agents. We prove the same by constructing an
example guided by Equation 2.

Example. Consider $n=2$, $m=3$, we have agents $\\{1,2\\}$ and goods,
$\\{a,b,c\\}$. The true valuations $v$ are given by Table 2(a). For truthful
reporting, there are 2 possible proportional allocations
$\mathcal{A}^{prop}_{v}$ given by Table 2(b). For the first allocation
$A^{I}$, agent 1 obtains a value of $20$. If $1$ reports $v^{\prime}_{i}$ as
given in Table 2(c), then the only possible proportional allocation is given
in Table 2(d), the value for which is $30$, is strictly better than what she
was offered. Similarly for next allocation $A^{II}$, agent 2 has an incentive
to misreport.

| $v(a)$ | $v(b)$ | $v(c)$
---|---|---|---
1 | 20 | 10 | 5
2 | 5 | 10 | 20
(a) The true values

| 1 | 2
---|---|---
$A^{I}$ | a | bc
$A^{II}$ | ab | c
(b) $\mathcal{A}^{prop}_{v}$

| $v(a)$ | $v(b)$ | $v(c)$
---|---|---|---
1 | 10 | 10 | 10
2 | 5 | 10 | 20
(c) Agent 1 misreports

| $1$ | $2$
---|---|---
$\tilde{A}^{I}$ | ab | c
(d) $\mathcal{A}^{prop}_{v^{\prime}}$

Table 2. Counter Example for Proportionality

###  3.3. EFX

In (Amanatidis et al., 2017), they prove that it is impossible to design SP
mechanism for EF1 for $n=2$ and $m\geq 5$. Since EFX (Definition 2.4) is a
stronger property the same result holds when $m>=5$. We prove that it is also
impossible to have an SP mechanism for EFX when $m=4$.

###### Theorem 3.2.

Any mechanism that returns an allocation that is EFX cannot be truthful even
in the case of additive valuations.

###### Proof.

Consider an example where $n=2$, we have agents $\\{1,2\\}$ and $m=4$,
$\\{a,b,c,d\\}$. For truthful reporting $v$ as given in Table 3(a), there are
4 possible EFX allocations $\mathcal{A}^{EF}_{v}$ given by Table 3(b). For the
first two allocations $A^{I},A^{II}$, agent 1 receives $b$ which it values at
$100$ or $\\{b,c\\}$ which it values $120$. If agent $1$ reports
$v^{\prime}_{i}$ as given in Table 3(c), where the total valuation is same
i.e., 200. Under this misreport, the only possible EFX allocations are given
in Table 3(d) in which agent 1 receives at least $140$ which is at least as
good as the value it received for truthful reporting. Similarly for next two
allocations $A^{III},A^{IV}$ agent 2 has an incentive to misreport. Hence
there are only four possible EFX allocations and for each allocation at least
one agent has an incentive to misreport.

| $v(a)$ | $v(b)$ | $v(c)$ | $v(d)$
---|---|---|---|---
1 | 40 | 100 | 20 | 40
2 | 100 | 40 | 20 | 40
(a) The true values

| $1$ | $2$
---|---|---
$A^{I}$ | b | acd
$A^{II}$ | bc | ad
$A^{III}$ | bd | ac
$A^{IV}$ | bdc | a
(b) $\mathcal{A}^{EFX}_{v}$

| $v(a)$ | $v(b)$ | $v(c)$ | $v(d)$
---|---|---|---|---
1 | 90 | 70 | 15 | 25
2 | 100 | 40 | 20 | 40
(c) Agent 1 misreports

| $1$ | $2$
---|---|---
$\tilde{A}^{I}$ | bd | ac
$\tilde{A}^{I}$ | bdc | a
(d) $\mathcal{A}^{EFX}_{v^{\prime}}$

Table 3. Counter Example for EFX

∎

With this we can conclude, that under additive valuations, there is an
instance where no SP mechanism can be EFX.

###  3.4. EF1

In this subsection, we explore the existing algorithms that find EF1
allocations and prove that these are manipulable. We provide an instance with
$n=2$ for each case.

####  3.4.1. Greedy Round-Robin Algorithm

In (Caragiannis et al., 2016), the authors provide a simple algorithm for
obtaining EF1 allocations when the valuations are additive. It involves the
following steps,

  * •

Fix an arbitrary order on the agents

  * •

Allocate the first agent its most valuable good

  * •

The next agent is allocated its most valuable among the remaining goods

  * •

The algorithm terminates when all the goods are allocated

The following example shows that the above algorithm can be manipulated by the
agents.

###### Proposition 3.3.

Greedy round-robin algorithm is manipulable for additive valuations.

| $v(a)$ | $v(b)$ | $v(c)$ | $v(d)$ | $v(e)$
---|---|---|---|---|---
1 | 12 | 10 | 8 | 6 | 1
2 | 1 | 10 | 8 | 6 | 9
(a) The true values

| $1$ | $2$
---|---|---
$1\rightarrow 2$ | acd | be
$2\rightarrow 1$ | ac | bde
(b) EF1 allocations

| $v(a)$ | $v(b)$ | $v(c)$ | $v(d)$ | $v(e)$
---|---|---|---|---|---
1 | 10 | 12 | 8 | 6 | 1
2 | 1 | 10 | 8 | 6 | 9
(c) Agent 1 misreports

| $1$ | $2$
---|---|---
$1\rightarrow 2$ | abd | ce
(d) EF1 allocation

| $v(a)$ | $v(b)$ | $v(c)$ | $v(d)$ | $v(e)$
---|---|---|---|---|---
1 | 12 | 10 | 8 | 6 | 1
2 | 1 | 10 | 8 | 8 | 5
(e) Agent 2 misreports

| $1$ | $2$
---|---|---
$2\rightarrow 1$ | ad | bce
(f) EF1 allocation

Table 4. Greedy round-robin is manipulable

###### Proof.

Example. Consider $n=2$, $\\{1,2\\}$, $m=5$ , $\\{a,b,c,d,e\\}$ where the
valuations are additive and given by Table 4(a). When $n=2$, there is only two
possible orders among the agents. When applying greedy algorithm with 1
followed by 2 or $1\rightarrow 2$, agent 1 gets $\\{a,c,d\\}$ (Table 4(b))
with a value of $26$. If the agent misreports its value as given in Table
4(c), the allocation that agent 1 gets is $\\{a,b,d\\}$ which it values at
$28$ that is strictly more than when it was truthful. Similarly agent 2 can
misreport to an advantage when the order is $2\rightarrow 1$. It improves its
allocation from $\\{b,d,e\\}$ (Table 4(b)) that it values at $25$ to
$\\{b,c,e\\}$ whose value is $27$. ∎

####  3.4.2. Cycle-elimination Algorithm

Greedy method fails for general valuations, instead the cycle-elimination
algorithm (Lipton et al., 2004) provides EF1 solution in polynomial time in
general. The algorithm is as follows,

  * •

Goods are allocated in arbitrary order

  * •

An envy-graph is maintained where the agents are the vertices and a directed
edge $i\rightarrow j$ represents that agent $i$ envies agent $j$ under the
current allocation.

  * •

The next item is allocated to the agent with no incoming edge. If there is a
cycle, it can be eliminated by exchanging the goods of the agents that form
the cycle, with the ones they envy.

We show that the above algorithm is manipulable by the agents.

###### Proposition 3.4.

Cycle-elimination algorithm is manipulable even for identical valuations.

1 | 2 | graph
---|---|---
d |  | $1\leftarrow 2$
d | a | $1\leftarrow 2$
d | ab | $1\rightarrow 2$
dc | ab | $1\rightarrow 2$
(a) Cycle-elimination on $v$

1 | 2 | graph
---|---|---
d |  | $1\leftarrow 2$
d | a | $1\rightleftharpoons 2$
a | d | no envy
ab | d | $1\leftarrow 2$
ab | dc | $1\leftarrow 2$
(b) Cycle-elimination on $v^{\prime}$

1 | 2 | graph
---|---|---
d |  | $1\leftarrow 2$
d | a | $1\rightleftharpoons 2$
a | d | no envy
a | bd | $1\rightarrow 2$
ac | bd | $1\leftarrow 2$
(c) Cycle-elimination on $v^{\prime}$

Table 5. Cycle-elimination is manipulable

Consider $n=2$, $\\{1,2\\}$, and $m=4$, $\\{a,b,c,d\\}$. Let
$(x,y)\in\\{(a,b)(b,c),(a,c)\\}$ where the valuations $v$ of the agents are
identical and given below. The value of other subsets not mentioned below are
additive.

$v(a)$ | $v(b)$ | $v(c)$ | $v(d)$ | $v(x,y)$
---|---|---|---|---
5 | 5 | 5 | 10 | 16

When we run the cycle-elimination algorithm, the steps are as given in the
Table 5(a). It is easy to see that the agent who gets the item $d$ (w.l.o.g we
assume agent $1$ gets $d$) always ends up with a value $15$ and can try to
increase the utility by gaining the other bundle whose value is $16$. Now
consider the following misreported valuation by the agent who gets item $d$.

$v^{\prime}(a)$ | $v^{\prime}(b)$ | $v^{\prime}(c)$ | $v^{\prime}(d)$ | $v^{\prime}(x,y)$
---|---|---|---|---
5 | 5 | 5 | 4 | 16

With the misreported valuation, we again run the cycle-elimination algorithm
and there can be two possible outcomes as presented in Table 5(b), 5(c). We
see that in these cases the agent $1$ receives $\\{a,b\\}$ or $\\{a,c\\}$
which it values at $16$ i.e., strictly more than the previous value for
$\\{d,c\\}$ that is 15. In this example we prove that there is always an agent
that can manipulate to increase its utility.

In the above case, we considered an example for (general) identical
valuations. In fact it also possible to manipulate cycle-elimination for
(additive) identical valuations.

Example. Consider $n=2$ and $m=3$ where the agents have the following
(additive) identical valuation $v$ and the agent that does not receive the
good $c$ misreports the valuation to $v^{\prime}$ also given below.

$v(a)$ | $v(b)$ | $v(c)$
---|---|---
5 | 5 | 12
$v^{\prime}(a)$ | $v^{\prime}(b)$ | $v^{\prime}(c)$
4 | 5 | 12

For many orderings over $m$ that the algorithm chooses, the value obtained for
$v^{\prime}$ is as good as $v$. But when the ordering is chosen to be $a$ then
$b$ then $c$ or $(b,a,c)$, the agent manipulating ensures a value of $17$ as
opposed to just receiving $5$.

##  4\. Identical Additive Valuations

When valuations are identically additive, we know that picking sequences are
strategy-proof (Bouveret and Lang, 2011). Based on picking sequences, we
provide an algorithm, (RSD) _(Repeated Serial Dictatorship)_ to obtain
truthfulness while ensuring EF1.

1

2

Input : $\langle N,M,V\rangle$, $V$ is identical additive

Output : $(A_{1},A_{2},\ldots,A_{n})\in\mathcal{A}^{EF1}$

3

4Set an arbitrary but fixed order on the agents, w.l.o.g, $(1,2,\ldots,n)$ ;

5 $A_{i}=\phi,\quad\forall i$;

6 $R=M$ (goods remaining after each iteration) ;

7 $i=0$ (agent number);

8 while  _$R\neq\phi$_ do

9 $x\in\underset{j\in R}{argmax}\ v_{i}(j)$ ;

10 $A_{i}=A_{i}\bigcup x$ ;

11 $R=R\setminus x$ ;

12 $i=(i+1)\mod n$ ;

13

Algorithm 1 Repeated Serial Dictatorship Mechanism (RSD)

Repeated Serial Dictatorship is EF1 and (i) SP when $m\leq n$ and (ii) NSP
when the valuations are identical and additive. Given that RSD implements
greedy round-robin algorithm under additive valuations, the output allocation
$A$ is EF1.

(i) Case $m\leq n$: under this case, the while loop in Algorithm 1 runs for
$m$-iterations, given $m\leq n$, each agent only gets one chance to
participate and select the item $x$. The ordering chosen by the algorithm is
independent of the agent valuations hence cannot be manipulated. From the
algorithm we know that given the remaining goods $R$,

$A_{i}=x\in\underset{j\in R}{argmax}\ v_{i}(j)$

If the agent misreports s.t. $y\in\underset{j\in R}{argmax}\
v^{\prime}_{i}(j)$ and $x\neq y$. The agent receives $y$ s.t. under true
valuations, $v_{i}(y)\leq v_{i}(x)$ and hence cannot strictly increase its
utility.

(ii) Case $v$ is Identical (Additive): Let $v$ be the truthful report, we
assume $v^{1}\geq v^{2}\geq\ldots\geq v^{m}$ be the value all the agents have
for the $m$ goods in decreasing order. The Algorithm 1 will continue for $m$
rounds and assign the goods in this order itself. The goods remaining at round
$j$ is given by $R_{j}=\\{v^{j},\ldots,v^{m}\\}$. Let us assume an agent $i$
gets allocated $k$ items before the algorithm terminates, then it selects from
the following subsets and receives the items it values the most in each of
these,

$\\{R_{i},R_{i+n},\ldots,R_{i+kn}\\}$

Hence $A_{i}=\\{v^{i},v^{i+n},\ldots,v^{i+kn}\\}$. If the agent $i$ misreports
and the remaining agents report truthfully, in any of the rounds w.l.o.g,
$i^{th}$ round s.t., the relative ordering between the items changes, then the
agent might face the two possible sets in the next round ($i+n$),

  * •

Misreport s.t. agent $i$ gets item $p$ instead of $i$, $p\leq n+i-1$, then the
set it faces in the next rounds is $\\{R_{n+i},\ldots,R_{i+kn}\\}$. Hence the
items allocated are $A^{\prime}_{i}=\\{v^{p},v^{i+n},\ldots,v^{i+kn}\\}$. It
can be clearly verified that, $v_{i}(A_{i})\geq v_{i}(A^{\prime}_{i})$, hence
no incentive to misreport.

  * •

Misreport s.t agent $i$ gets item $p$ where,
$k^{\prime}n+i>p\geq(k^{\prime}-1)n+i$, $k^{\prime}\geq 2$ then the sets $i$
faces are

$\\{R_{n+i-1}\setminus\\{p\\},\ldots,R_{i+(k^{\prime}-1)n-1}\setminus\\{p\\},R_{i+k^{\prime}n},\ldots,R_{i+kn}\\}$

Hence the items allocated are

$A^{\prime\prime}_{i}=\\{v^{p},v^{n+i-1},\ldots,v^{i+(k^{\prime}-1)n-1},v^{i+k^{\prime}n},\ldots,v^{i+kn}\\}$

Using the fact that $p\geq i+(k^{\prime}-1)n$, we know that
$v^{i+(k^{\prime}-1)n}\geq v^{p}$. Hence we compare the sets $A_{i}$ and
$A^{\prime\prime}_{i}$ ($\succeq$ represents element-wise comparison) as
follows to obtain $v_{i}(A_{i})\geq v_{i}(A^{\prime\prime}_{i})$,

$\begin{split}\\{v^{i},v^{i+n},&\ldots,v^{i+(k^{\prime}-2)n},v^{i+(k^{\prime}-1)n},v^{i+k^{\prime}n},\ldots,v^{i+kn}\\}\succeq\\\
&\\{v^{i+n-1},v^{i+2n-1},\ldots,v^{i+(k^{\prime}-1)n},v^{p},v^{i+k^{\prime}n},\ldots,v^{i+kn}\\}\\\
\end{split}$

This completes the proof for truthfulness for RSD under additive and identical
valuations.

##  5\. Single-Minded Agents

In this section, we restrict to a simpler valuation profile. We assume the
agents are (SM) single minded. SM agents are only interested in a single
bundle of goods $D$. Upon receiving the specific bundle or any super-set they
get a positive utility and zero value for any other bundle (Formally given by
Equation 1). The problem instance is denoted by $\langle N,M,D\rangle$.

###### Observation 2.

When all the agents are SM, any allocation is MMS and EF1. The $\mu_{i}$ in
Definition 2.5 is 0 in this setting when $n>1$. Hence, allocating all the
goods to one agent is also MMS. Similarly, all possible allocations satisfy
EF1. If an agent $i$ receives its desired bundle or super-set then it doesn’t
envy any agent. If an agent $j$ receives $D_{i}$, then removing any item $x\in
D_{i}$ would remove envy. If no agent receives $D_{i}$ as a whole, there is no
envy.

Based on the observation, we extend greedy round-robin algorithm to design a
SD _(Serial Dictatorship)_ mechanism is SP since it is also a picking
sequence. SD trivially satisfies EF1 and MMS and we prove that it also
satisfies EFX.

1

2

Input : $\langle N,M,D\rangle$, $D=(D_{1},D_{2},\ldots,D_{n})$

Output : $(A_{1},A_{2},\ldots,A_{n})$

3

4Order the agents s.t. $|D_{1}|\leq|D_{2}|\leq\ldots\leq|D_{n}|$ (Ties broken
arbitrarily);

5 $i=0$ (agent number);

6 $R=M$ (goods remaining after each iteration) ;

7 while  _$R\neq\phi$_ do

8 Let $D_{i}$ be the preferred set for the current agent $i$;

9 if  _$D_{i}\subseteq R$_ then

10 $A_{i}=D_{i}$;

11 $R=R\setminus D_{i}$, $i=i+1$ ;

12

13 else

14 if  _$i <n$_ then

15 $i=i+1$;

16 else

17 $A_{i}=R$;

18 $R=\phi$;

19

20

21

Algorithm 2 Serial Dictatorship Mechanism (SD)

We prove certain desirable properties of the Algorithm 2, which is a modified
version of greedy round-robin algorithm.

###### Theorem 5.1.

The Serial Dictatorship Mechanism is strategy-proof (SP) and also satisfies
EF1, MMS and EFX when the agents are single-minded.

###### Proof.

In the Algorithm 2, the while loop can run for a maximum of $n$ rounds. This
means each agent $i$ has only one round in which it can be allocated the
preferred bundle $D_{i}$. The ordering is according to the increasing
cardinality of $D_{i}$. An agent can manipulate the ordering by reporting its
desired bundle as $D^{\prime}_{i}$ s.t., $|D^{\prime}_{i}|<|D_{i}|$. This
means the agent will be allocated if at all a bundle that it does not desire.
If $|D^{\prime}_{i}|>|D_{i}|$ then the probability that the agent gets any
allocation is strictly less than when it reports truthfully. Hence the agent
does not have any incentive to manipulate the ordering.

Given that the agent cannot manipulate the ordering. At any round, it is
optimal for the agent to report truthfully the desired set $D_{i}$. Now we
prove that the allocation $A$ obtained from SD satisfy the following fairness
criteria,

  * •

(EF1 and MMS). This is trivially true due to Observation 2 which states that
any allocation is EF1 and MMS when we have SM agents.

  * •

(EFX). Let us assume $k$ agents, denoted by $L$ (lucky), are allocated their
desired sets hence do not have any envy. If $k\neq n$, then $n-k$ agents,
denoted by $U$ (unlucky), did not receive their desired subset. From the
algorithm we know that for any agent $i\in U$, $D_{i}\not\subseteq R_{i}$
where $R_{i}$ is the set of goods at the beginning of $i^{th}$ round.

    * –

$\forall i,j\in U$, $i$ does not envy $j$, because $j$ is allocated empty
bundle unless $j$ is the agent appearing at the last $n$ and receives the
items remaining. In this case since agent $i$ is given the chance to chose
before $j$ which clearly shows it cannot envy $j$.

    * –

$\forall i\in U$, $\forall\bar{i}\in L$, if $\bar{i}<i$, then
$|D_{\bar{i}}|<|D_{i}|$, hence agent $i$ cannot envy $\bar{i}$. If
$|D_{\bar{i}}|=|D_{i}|$ then removing any item from the bundle of $\bar{i}$
will remove envy. Hence it still satisfies EFX.

    * –

$\forall i\in U$, $\forall\bar{i}\in L$, if $\bar{i}>i$, then
$D_{\bar{i}}\subseteq R_{i}$ hence $D_{\bar{i}}\neq D_{i}$, hence the agent
$i$ does not envy $\bar{i}$

Hence the allocation is EFX.

This concludes the proof for the theorem. Hence SD is SP and provides
allocations that satisfy EF1, MMS and EFX.

_Note (Proportionality)._ When the agents are SM, proportional allocation
exists when the following is true,

$v_{i}(A_{i})\geq\frac{1}{n}v_{i}(D_{i})>0,\ \forall i\in N$

The above is true only when all the agents get their desired bundle. If such a
solution exists then it easily found by the SD. ∎

##  6\. Future Work and Conclusion

In the literature, there are many algorithms for finding fair division of
resources. Yet such algorithms may not be really fair, if one agent can
manipulate it by misreporting its value to obtain higher utility. We show that
greedy round-robin and cycle-elimination algorithms are manipulable. In
general, we study the possibility of having strategy-proof, deterministic
mechanisms without money which ensure various criteria of fairness like EF,
proportionality, EFX, EF1, MMS. It is known that, such a mechanism does not
exist for EF, proportionality and MMS under additive valuations. It also does
not exist for EF1 under additive valuations when the number of items are more
than $5$. We prove that it does not exist for EFX even when the number of
items are $4$.

Given these impossibility results, we look into settings where agents have
simpler valuation type like single minded bidders. Under this assumption we
provide a strategy-proof algorithm SD. SD satisfies all fairness criteria
except EF. RSD satisfies EF1. The results are summarized in Table 1. For
future work, it would be interesting to look into mechanisms to settle the
unfinished components in the table. Given the impossibility for general
valuations, it would be interesting to design mechanisms for more specific
valuation types for e.g., (general) identical etc.

## References

  * (1)
  * Amanatidis et al. (2017) Georgios Amanatidis, Georgios Birmpas, George Christodoulou, and Evangelos Markakis. 2017.  Truthful allocation mechanisms without payments: Characterization and implications on fairness. In _Proceedings of the 2017 ACM Conference on Economics and Computation_. 545–562.
  * Amanatidis et al. (2016) Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. 2016.  On truthful mechanisms for maximin share allocations.  _arXiv preprint arXiv:1605.04026_ (2016).
  * Bei et al. (2017) Xiaohui Bei, Ning Chen, Guangda Huzhang, Biaoshuai Tao, and Jiajun Wu. 2017.  Cake Cutting: Envy and Truth. In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17_. 3625–3631.  https://doi.org/10.24963/ijcai.2017/507
  * Bouveret and Lang (2011) Sylvain Bouveret and Jérôme Lang. 2011.  A General Elicitation-Free Protocol for Allocating Indivisible Goods _(IJCAI’11)_. AAAI Press, 73–78.
  * Bouveret and Lemaître (2016) Sylvain Bouveret and Michel Lemaître. 2016.  Characterizing conflicts in fair division of indivisible goods using a scale of criteria.  _Autonomous Agents and Multi-Agent Systems_ 30, 2 (2016), 259–290.
  * Brânzei et al. (2017) Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. 2017\.  Nash social welfare approximation for strategic agents. In _Proceedings of the 2017 ACM Conference on Economics and Computation_. 611–628.
  * Budish (2011) Eric Budish. 2011\.  The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.  _Journal of Political Economy_ 119, 6 (2011), 1061–1103.
  * Caragiannis et al. (2016) Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2016.  The Unreasonable Fairness of Maximum Nash Welfare _(EC ’16)_. Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/2940716.2940726
  * Caragiannis et al. (2019) Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. 2019.  The unreasonable fairness of maximum Nash welfare.  _ACM Transactions on Economics and Computation (TEAC)_ 7, 3 (2019), 1–32.
  * Chaudhury et al. (2020) Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. 2020\.  EFX Exists for Three Agents. In _Proceedings of the 21st ACM Conference on Economics and Computation_ (Virtual Event, Hungary) _(EC ’20)_. Association for Computing Machinery, New York, NY, USA, 1–19.  https://doi.org/10.1145/3391403.3399511
  * Chen et al. (2013) Yiling Chen, John K Lai, David C Parkes, and Ariel D Procaccia. 2013\.  Truth, justice, and cake cutting.  _Games and Economic Behavior_ 77, 1 (2013), 284–297.
  * Cohen et al. (2011) Edith Cohen, Michal Feldman, Amos Fiat, Haim Kaplan, and Svetlana Olonetsky. 2011.  Truth, Envy, and Truthful Market Clearing Bundle Pricing. In _Internet and Network Economics_ , Ning Chen, Edith Elkind, and Elias Koutsoupias (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 97–108.
  * Cole et al. (2013) Richard Cole, Vasilis Gkatzelis, and Gagan Goel. 2013\.  Mechanism design for fair division: allocating divisible items without payments. In _Proceedings of the fourteenth ACM conference on Electronic commerce_. 251–268.
  * Foley (1967) Duncan Karl Foley. 1967\.  Resource allocation and the public sector.  (1967).
  * Goldberg and Hartline (2003) Andrew V. Goldberg and Jason D. Hartline. 2003.  Envy-Free Auctions for Digital Goods. In _Proceedings of the 4th ACM Conference on Electronic Commerce_ (San Diego, CA, USA) _(EC ’03)_. Association for Computing Machinery, New York, NY, USA, 29–35.  https://doi.org/10.1145/779928.779932
  * Lipton et al. (2004) Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004.  On approximately fair allocations of indivisible goods. In _Proceedings of the 5th ACM conference on Electronic commerce_. 125–131.
  * McMillan (1994) John McMillan. 1994\.  Selling spectrum rights.  _Journal of Economic Perspectives_ 8, 3 (1994), 145–162.
  * Menon and Larson (2017) Vijay Menon and Kate Larson. 2017.  Deterministic, Strategyproof, and Fair Cake Cutting. In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17_. 352–358.  https://doi.org/10.24963/ijcai.2017/50
  * Mossel and Tamuz (2010) Elchanan Mossel and Omer Tamuz. 2010.  Truthful fair division. In _International Symposium on Algorithmic Game Theory_. Springer, 288–299.
  * Procaccia and Wang (2014) Ariel D Procaccia and Junxing Wang. 2014.  Fair enough: Guaranteeing approximate maximin shares. In _Proceedings of the fifteenth ACM conference on Economics and computation_. 675–692.
  * Rassenti et al. (1982) Stephen J Rassenti, Vernon L Smith, and Robert L Bulfin. 1982\.  A combinatorial auction mechanism for airport time slot allocation.  _The Bell Journal of Economics_ (1982), 402–417.
  * Steihaus (1948) H Steihaus. 1948\.  The problem of fair division.  _Econometrica_ 16 (1948), 101–104.
  * Stromquist (1980) Walter Stromquist. 1980\.  How to cut a cake fairly.  _The American Mathematical Monthly_ 87, 8 (1980), 640–644.
  * Tang and Zhang (2015) Bo Tang and Jinshan Zhang. 2015.  Envy-Free Sponsored Search Auctions with Budgets. In _IJCAI_. 653–659.  http://ijcai.org/Abstract/15/098


# A Transient Overcooling in the Early Universe?
Clues from Globular Clusters Formation

Alvio Renzini1
1INAF - Osservatorio Astronomico di Padova, Vicolo dell’Osservatorio 5,
I-35122 Padova, Italy E-mail<EMAIL_ADDRESS>
(Accepted 2023 June 8. Received 2023, June 5; in original form 2023, May 22 )

###### Abstract

The mere existence of multiple stellar generations in Milky Way globular
clusters indicates that each generation was unable to stop star formation,
that instead persisted unimpeded for several million years. This evidence
argues for an extended stage of star formation within a forming globular
cluster, during which stellar feedback was substantially ineffective and the
nascent globular cluster was able to accrete processed gas from its
surrounding, and efficiently convert it into successive stellar generations.
It has been argued that such delayed feedback results from core collapse in
most massive stars failing to trigger an energetic supernova explosion, but
rather leading directly to black hole formation. Thus, globular clusters offer
a concrete phenomenological example for the lack of feedback in young
starbursts, an option that has been widely advocated to account for the
unexpected abundance of UV-luminous galaxies at $z=9-16$, as revealed by JWST
observations. The paper is meant to attract attention to this opportunity for
a synergic cooperation of globular cluster and high redshift research.

###### keywords:

Galaxy: formation – globular clusters: general – galaxies: evolution–
galaxies: formation

††pagerange: A Transient Overcooling in the Early Universe?  Clues from
Globular Clusters Formation–A Transient Overcooling in the Early Universe?
Clues from Globular Clusters Formation††pubyear: 2002

##  1 Introduction

On its first Cycle, the James Webb Space Telescope (JWST) has revealed an
unexpected abundance of UV-bright galaxies at $z=9-16$ (e.g., 2023, 2023,
2023, 2023a, 2023b and many others). Their finding was unexpected in the frame
of existing theoretical models of galaxy formation and evolution, that had
been fine tuned to reproduce observables in the lower redshift Universe, see
e.g., Figure 14 in (2023).

As a consequence, a number of possible alternatives to current assumptions in
cosmological simulations are being explored to cope with this discrepancy
(e.g., Boylan-Kolchin 2023; 2023). For example, (2023) discuss several options
to ease the factor $\sim\\!\\!30$ underprediction of their semianalytical
model at $z\sim\\!\\!13$ compared to the observed UV luminosity function.
These include a top heavy IMF, that automatically would bust the UV luminosity
function, exclude other possible limitations of their model such as a too
inefficient baryon cooling within halos and inefficient gas-to-stars
conversion. They conclude that too efficient stellar feedback is the main
ingredient that could be responsible for their model underpredicting the
number of luminous galaxies at these redshifts. Indeed, the abundance of UV
luminous galaxies appears to be consistent with the limiting case of (feedback
unimpeded) $\sim\\!\\!100$ per cent efficiency in converting baryons into
stars in dark matter halos at these redshifts (, 2023), as estimated by
(2018).

In alternative, (2023) appeal to intrinsic UV luminosity variability of dwarf
galaxies at high redshifts, such objects being likely dominated by a bursty
mode of star formation. Thanks to a kind of intrinsic Eddington bias, the
result of variability is to boost the top end of the luminosity function, with
consistency with the observed counts being achieved for a variability
described by a gaussian luminosity spread with $\sigma_{\rm UV}\simeq 2.5$
mag.

A top heavy IMF is also favoured by (2023a), who, for lack of evidence,
exclude AGN boosting the UV luminosity of $z\sim\\!\\!9-16$ galaxies. A lack
of suppression of star formation by the UV background in the pre-ionization
era is also mentioned as a possible contributor.

A specific case of feedback suppression at high redshifts is advocated by
(2023). Based on the Starburst99 models (, 1999), Dekel et al. argue that at
low metallicities, such as those prevailing at high redshifts, stellar winds
from massive stars convey little energy and momentum, hence prior to supernova
(SN) explosions stellar feedback is very inefficient, hence boosting star
formation and the UV luminosity function. This low-feedback phase lasts up to
$\sim\\!\\!3$ Myr since a burst of star formation, then coming to an end as
the most massive stars eventually undergo SN explosions and efficient feedback
begins. This assumes that all massive stars undergoing core collapse also end
with a SN display, hence ejecting $\sim\\!\\!10^{51}$ erg in kinetic energy.

While all these options are being currently considered, this paper expands on
the possibility of an even stronger reduction of stellar feedback, that can be
achieved by substantially extending the no-supernovae period, past a burst of
star formation. The justification for such a scenario comes from the multiple
stellar generation phenomenon in Galactic globular clusters (GC), which
suggests a substantially more extended period of inefficient feedback, up to
$\sim\\!\\!10$ Myr, as discussed in (2022, hereafter Paper I). Section 2
succinctly recaps the evidence on GC formation supporting the concept of an
extended feedback-free time at their formation. Section 3 then expands on the
consequences of such a delayed feedback for star formation in the early
Universe, and finally, Section 4 returns on the key issues and on the
plausibility of the whole scenario, including mentioning some caveats.

##  2 Globular Cluster Formation

Virtually all (Galactic) GCs host multiple stellar generations, with the first
generation (1G) reflecting the chemical composition of the ISM prior to the 1G
formation, whereas second generation (2G) stars are depleted, to various
degrees, in carbon and oxygen and enriched in helium, nitrogen and sodium
(e.g., 2012, 2017). Thus, the material having formed 2G stars had to be
exposed to proton-capture processes at high temperatures in stars of the first
generation, though their nature has been matter of debate ever since the
multiple generation phenomenon was discovered. In Paper I it is argued that
the most likely candidates are massive interacting binaries, as originally
suggested by (2009). The majority of massive stars are indeed members of
interactive binaries (, 2012) and, most of the nuclearly-processed material is
shed with low kinetic energy as a result of common-envelope events (, 2009).

It is worth emphasising that the fraction of 2G stars increases from
$\sim\\!\\!50$ per cent in lower mass GCs to over 80 per cent in the most
massive ones (, 2017). In all evidence, the formation of the first generation
did not stop star formation, which actually had to continue with an even
increasing rate and efficiency. In Paper I, this absence of feedback was
ascribed to a temporary lack of supernova explosions, as also required by most
2G stars having the same iron abundance of 1G ones, indicating no or very
small contamination by supernova ejecta (see also , 2017). This also
demonstrates that 2G stars had to form before SN explosions began to pollute
the ISM, hence all star formation had to be confined within a few (up to
$\sim\\!\\!10$) Myr. As discussed in Paper I, this can be due to stars more
massive than $\sim\\!\\!20\,\hbox{$M_{\odot}$}$ failing to produce a SN
display at their core collapse, but rather silently sinking into black holes
(see also , 2013). Thus, following a burst of star formation there would be no
supernova events for the first $\sim\\!\\!10$ Myr, while stars more massive
than $\sim\\!\\!20\,\hbox{$M_{\odot}$}$ complete their evolutionary cycle and
pollute the ISM with proton-capture products. Then supernovae begin and
continue for another $\sim\\!\\!25$ Myr, while stars from $\sim\\!\\!20$ down
to $\sim\\!\\!8\,\hbox{$M_{\odot}$}$ complete their evolution. Strong feedback
from these supernovae will then bring to an end star formation within the
young GC. Finally, no more core-collapse supernovae occur, from $\sim\\!\\!35$
Myr on after the burst, when stars less massive than
$\sim\\!\\!8\,\hbox{$M_{\odot}$}$ end their evolution as white dwarfs.

In most GCs there appears to be a small 1G-2G discontinuity in chemical
composition, suggesting a brief pause in star formation, then followed by a
number of successive bursts, each generating a 2G sub-population. Such number
increases with cluster mass (, 2017) and becomes as high as 15 in $\omega$ Cen
(, 2017), the most massive Galactic GC. Clearly, even successive (2G) bursts
were unable to stop star formation, before supernovae eventually succeeded. In
all evidence, feedback was ineffective also during most of the formation of
the second generations.

During this no-supernova phase, may stellar winds still provide sufficient
feedback to contrast this scenario? At low metallicity winds carry little
energy, as argued by (2023), but GCs exist with near-solar metallicity and
they still exhibit the multiple generation phenomenon (, 2022). However, for
the high ISM densities at GC formation, energy dissipation can be so high to
neutralize most of the feedback from stellar winds, while radiative feedback
or UV background may have only minor effects (, 2017, 2023). In any event, the
empirical fact remains, that, even in near-solar metalliciry GCs, the first
generation did not prevent the formation of second generation stars.

The dominance of 2G stars demands that the 1G population having processed the
material to form 2G stars had a substantially higher mass than that of the 1G
still bound to the clusters. This is known as the mass budget problem (e.g.,
2015), whereby the first generation returns only $\sim\\!\\!10$ per cent of
its mass with the required composition to form 2G stars. Hence, 1G stars still
bound to the cluster today fall short by at least a factor of $\sim\\!\\!10$
in producing enough material to build the 2G stars. This mismatch would be
even worse if star formation was restricted to the 3 Myr period prior to the
first core-collapse event, as only the most massive stars would have had time
to contribute, hence the necessity to extend longer the no-supernova phase,
indicatively to $\sim\\!\\!10$ Myr as justified in Paper I. As far as the mass
of the 1G contributors is concerned, in Paper I it is argued that, within the
(dwarf) galaxy hosting a nascent GC (e.g., as seen at high redshifts, 2019,
2023), this extended 1G feeder population inhabited a wide region around the
forming GC, that was also actively star forming and feeding the central
cluster with material to form the second generations. During this overcooling
phase, the young GC was actually the centre of a converging accretion flow,
lasting some 10 Myr, before supernovae finally brought it to a halt.

This extended feedback-free time is critical to ensure that a sufficient
number of 1G donor stars, down to $\sim\\!\\!20\,\hbox{$M_{\odot}$}$, had time
to evolve and shed enough processed materials to build the 2G stars in GCs.
Thus, the converging material had been processed inside stars of a first
generation that collectively was several times more massive then the final
mass of the bound GC (see also the GC formation models of 2017). It has been
suggested that the young cluster R136, and its surrounding 30 Dor star-forming
complex in LMC, may represent a local analog for GCs forming in high redshift
low-mass galaxies ((2018, Paper I). It is worth emphasizing that the dominance
of 2G stars requires that their formation had to take place with an extreme
efficiency in gas to stars conversion, close to 100 per cent, which was
actually promoted by the lack of supernova feedback (Paper I). Clearly, if
this is the way GCs formed, then the temporary lack of supernova explosions,
hence with the feedback delay promoting high star formation efficiency, ought
to have important consequences for star formation in general, and possibly so
for star formation in extremely high redshift galaxies.

In summary, the hypothesis of most massive stars
(${\mathrel{\mathchoice{\lower
2.9pt\vbox{\halign{$\m@th\displaystyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}{\lower
2.9pt\vbox{\halign{$\m@th\textstyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}{\lower
2.9pt\vbox{\halign{$\m@th\scriptstyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}{\lower
2.9pt\vbox{\halign{$\m@th\scriptscriptstyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}}}20\,\hbox{$M_{\odot}$}$)
failing to result in a SN explosion has five decisive advantages for GC
formation: 1) it promotes and extended, unimpeded formation of multiple
stellar generations, 2) It boosts star formation efficiency, up to
$\sim\\!\\!100$ per cent, with almost full conversion of gas into stars, 3) it
avoids contaminating 2G stars with heavy-element SN products, 4) it allows an
extended range of stellar masses (i.e., above
$\sim\\!\\!20\,\hbox{$M_{\odot}$}$) to provide processed material for the
formation of 2G stars, and 5) compared to the assumption of no delay in SN
feedback, the extended period of star formation (from $\sim\\!\\!3$ to
$\sim\\!\\!10$ Myr) allows a $\sim 30$ times bigger volume around the nascent
GC to contribute material for the 2G formation (Paper I). As such, it appears
to be promising to explore the consequences of this hypothesis for star
formation in the early Universe.

##  3 Overcooling in the Early Universe?

(1978) early noticed that cooling in the early Universe could be so effective
that most baryons in dark matter halos would quickly turn into stars, an
effect dubbed overcooling. Clearly, global overcooling did not happen, because
even by the present time not much more than 10 per cent of the cosmic baryons
now reside in stars (, 1998). Yet, if GCs formed as sketched above, with an
early overcooling phase promoting the accumulation of multiple stellar
generations in a short time interval, then an early overcooling as a generic
properties of star formation may help accounting for the excess of UV-bright
galaxies at $z{\mathrel{\mathchoice{\lower
2.9pt\vbox{\halign{$\m@th\displaystyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}{\lower
2.9pt\vbox{\halign{$\m@th\textstyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}{\lower
2.9pt\vbox{\halign{$\m@th\scriptstyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}{\lower
2.9pt\vbox{\halign{$\m@th\scriptscriptstyle\hfil#\hfil$\cr>\crcr\sim\crcr}}}}}9$.
Indeed, it offers an effective reduction of stellar feedback, invoked as the
single simplest way of boosting star formation at very high redshifts, as from
JWST observations (, 2023, 2023, 2023b, 2023). Indeed, compared to (2023), the
proposed scenario extends from $\sim\\!\\!3$ to $\sim\\!\\!10$ Myr the
“feedback free” time past a burst of star formation.

Besides this indirect role on the high-redshift Universe, where GC provide a
hint favoring delayed feedback and overcooling, young GCs and their immediate
environment may also play a direct role on global star formation at high
redshift. High-redshift globulars and their precursors, their possible
contribution to re-ionization and observational detectability, have been
considered for some time (see e.g., 2002, 2011, 2013, 2015, 2017; Boylan-
Kolchin 2018; 2019). Thus, nascent GCs, with their 1G feeding surrounding, may
contribute significantly to the stellar mass and luminosity in the very early
Universe. Given the old ages of most Galactic GCs, they had to form beyond
$z\sim\\!\\!3$, and the metal poor ones possibly well beyond it. Given the
mass of GCs in the local Universe, young GCs, along with their $\sim\\!\\!10$
times more massive star-forming environment, may have dominated over the whole
stellar mass if formed beyond $z\sim\\!\\!5$ (, 2017). Also, given the extreme
densities of typical GCs today, corresponding to some $\sim\\!10^{7}$ atoms
cm-3, the similarly high gas densities of forming GCs at very high redshift
may have contributed significantly to the total emission measure in emission
lines and nebular continuum.

The object GN-z11 at $z=10.6$ (, 2023) with density higher than $10^{6}$ cm-3
has been proposed as (hosting) a possible GC in formation (, 2023, 2023),
though the high density may rather refer to the broad line region of an AGN (,
2023). Worth noting is that its high N/O ratio is just what one expects for
the ISM of a globular cluster while forming its 2G stars, which indeed are
strongly enhanced in nitrogen and depleted in oxygen.

##  4 Discussion and Conclusions

It has been argued that GCs in the local Universe, with their ubiquitous
multiple stellar generations, offer strong evidence for a lack of feedback
during their formation in the early Universe. Stars more massive than
$\sim\\!\\!20\,\hbox{$M_{\odot}$}$ failing to produce an energetic supernova
would accomplish such effect, and delay feedback by some 10 Myr. If so, such
delayed feedback and corresponding transient overcooling phase, would result
in a major reduction in the stellar feedback, as now widely advocated as an
obvious way of accounting for the excess of UV-bright galaxies at $z=9-16$ (,
2023, 2023, 2023).

However, a few caveats are in order. For example, could such delayed feedback
result in an overproduction of stars in cosmological simulations, not only in
the early Universe but also all along cosmic times? It would certainly do so,
but this could be compensated by suitably increasing the feedback efficiency
past the $\sim\\!\\!10$ Myr delay. In any event, the overall star formation
history may change little, but star formation would be more bursty on short
timescales, and simulated galaxies may become more clumpy. It would be
instructive to see how simulated galaxies would react to such a different
recipe for feedback.

As already warned in Paper I, restricting core-collapse supernovae to below
$\sim\\!\\!20\,\hbox{$M_{\odot}$}$ would have the collateral effect of
reducing theoretical metal yields by roughly a factor of 2. Empirical yields,
of course, would remain the same. Still, how physically-based is the
assumption that the most massive stars fail to produce energetic SN events?
This is actually a widely entertained possibility (e.g., 2013, 2016, 2017,
2019, 2022 and references therein). From the theoretical point of view, the
opposite problem has, along the years, affected attempts of modelling the
outcomes of core-collapse events, namely the difficulty of producing
explosions, especially in more massive stars (, 2016).

Ultimately, how well established is the empirical scenario of GC formation
proposed in Paper I? Like most previous attempts of describing how GCs may
have formed, this is a phenomenological scenario, not a theoretical model.
Yet, it is based on the enormous progress in the study of multiple stellar
generations in GCs achieved mainly thank to HST imaging and VLT spectroscopy.
As such, it is built to comply, as well as possible, with all the resulting
observational constraints. In the end, for what matters for the feedback in
starbursts, the mere existence of multiple stellar generations in GCs is tell
tale evidence of inefficient feedback. Other details of the formation process
may be irrelevant as far as the consequences for star formation at high
redshifts are concerned.

Still, the empirical evidence of high, close to 100 percent efficiency in gas
to star conversion refers to the scale of forming globular clusters, whereas
the evidence for the $z=9-16$ Universe requires it at the scale of full young
galaxies. A supernova avoidance period extended to $\sim\\!\\!10$ Myr would
boost the star formation efficiency on all scales, but it remains to be seen
whether this can reach close 100 per cent also on galactic scales at those
redshifts. Nevertheless, supernova avoidance and ensuing overcooling favour
the formation of high density clumps, with further enhanced efficiency. The
mentioned case of GN-z11, the best known galaxy at these redshifts, exhibits a
very high gas density to the point of having the full galaxy line emission
being dominated by what has been proposed to be a globular cluster in
formation.

## Acknowledgments

I wish to thank Mauro Giavalisco for constructive comments and for his
encouragement to write this paper. I wish also to thank the anonymous reviewer
for their questions that helped to improve the manuscript..

## Data Availability

No new data were generated or analysed in support of this research.

## References

  * (1) Adams, S. M., Kochanek, C. S., Gerke, J. R. et al. 2017, MNRAS, 468, 4968
  * (2) Bellini, A., Milone, A. P., Anderson, J., Marino, A. F., Piotto, G. et al. 2017, ApJ, 844, 164
  * (3) Behroozi, P. & Silk, J. 2018, MNRAS, 477, 5382
  * (4) Belokurov, V. & Ktavtsov, A. 2023, ArXiv:2306.00060
  * Boylan-Kolchin (2018) Boylan-Kolchin, M. 2018, MNRAS, 479, 332
  * Boylan-Kolchin (2023) Boylan-Kolchin, M. 2023, NatAst.tmp.77
  * (7) Bunker, A.J., Saxena, A., Cameron, A.J., Willott, C.J., Curtis-Lake, E. et al. 2023, ArXiv:2302.07256
  * (8) Carlberg, R.G. 2002, ApJ, 573, 60
  * (9) Dekel, A., Sarkar, K.C., Birnboim, Y., Mandelker, N. & Li, Z. 2023, MNRAS, 523, 3201
  * (10) de Mink, S. E., Pols, O. R., Langer, N., & Izzard, R. G. 2009, A&A, 507, L1
  * (11) Donnan, C.T., McLeod, D.J., Dunlop, J.S., McLure, R.J., Carnall, A.C. et al. 2023, MNRAS, 518, 6011
  * (12) Eldridge, J.J. & Stanway, E.R. 2022, ARA&A, 60, 455
  * (13) Elmegreen, B.G. 2017, ApJ, 836, 80
  * (14) Finkelstein, S.L., Magley, M.B., Ferguson, H.C., Wilkinf, S.M., Kartalpepe, J.S. et al. 2023, ApJ, 946, L13
  * (15) Fukugita, M., Hogan, C.J. & Peebles, PJ.E. 1998, ApJ, 503, 518
  * (16) Gratton, R.G., Carretta, E. & Bragaglia, A. 2012, A&A Rev., 20, 50
  * (17) Harikane, Y., Ouchi, M., Oguri, M., Ono, Y., Nakajima, K. et al. 2023a, ApJS, 265, 5
  * (18) Harikane, Y., Nakajima, K., Ouchi, M., Umeda, H., Isobe, Y. et al. 2023b, ArXiv:2304.06658
  * (19) Kader, J.A., Pilachowski, C.A., Johnson, C.I., Rich, R.M., Young, M.D. et al. 2022, ApJ, 940, 76
  * (20) Katz, H. & Ricotti, M. 2013, MNRAS, 432, 3250
  * (21) Krause, M., Charbonnel, C. , Decressin, T., Meynet, G. , & Prantzos, N. 2013, A&A, 552, A121
  * (22) Leitherer, C., Schaerer, D., Goldader, J.D., Delgado, R.M.G., Robert, C. et al. 1999, ApJS, 123, 3
  * (23) Maiolino, R., Scholtz, J., Witstock, J., Carniani, S., D’Eugenio, F. et al. 2023, ArXive:2305.12492
  * (24) McLeod, D.J., Donnan, C.T., McLure, M.J., Dunlop, J.S., Magee, D. et al. 2023, ArXiv:2304. 01469
  * (25) Milone, A. P., Piotto, G., Renzini, A. et al. 2017, MNRAS, 464, 3636
  * (26) Pozzetti, L., Maraston, C. & Renzini, A. 2019, MNRAS, 485, 586
  * (27) Renzini, A., D’Antona, F., Cassisi, S. et al. 2015, MNRAS, 454, 4197
  * (28) Renzini, A. 2017, MNRAS, 469, L63
  * (29) Renzini, A., Marino, A.F. & Milone, A.P. 2022, MNRAS, 513, 2111 (Paper I)
  * (30) Sana, H., de Mink, S. E. & de Koter, A. 2012, Science, 337, 444
  * (31) Sander, A.A.C., Hamann, W., Todt, H. et al. 2019, A&A, 621, A92
  * (32) Schneider, F. R. N., Ramirez-Agudelo, O. H., Tramper, F. et al. 2018, A&A, 618, A73
  * (33) Schraerer, D. & Charbonnel, C. 2011, MNRAS, 413, 2297
  * (34) Shen, X., Vogelsberger, M., Boyan-Kolchin, M., Tacchella, S. & Kannan, R. 2023, ArXiv:2305.05679
  * (35) Senchyna, P., Plat, A., Stark, D.P. & Rudie, G.C. 2023, ArXiv:2303.04179
  * (36) Sukhbold, T., Erti, S., Woosley, S.E., Brown, J.M. & Janke, H.-T. 2016, ApJ, 821, 38
  * (37) Trenti, M., Padoan, P. & Jimenez, R. 2015, ApJ, 808, L35
  * (38) Vanzella, E., Calura, F., Meneghetti, M. et al. 2019, MNRAS, 483, 3618
  * (39) Vanzella, E., Claeyssens, A., Welch, B., Adamo, A., Coe, D. 2023, ApJ, 945, 53
  * (40) White, S.D.M. & Rees, M.J. 1978, MNRAS, 183, 341
  * (41) Wilkins, S.M., Vijayan, A.P., Lovell, C.C., Roper, W.J., Irodotou, D. et al. 2023, MNRAS, 519, 3118
  * (42) Yung, L.Y.A., Somerville, R.S., Finkelstein, S.L. & Wilkins, S.M. 2023, ArXiv:2304.04348

[0000-0002-7093-7355]A. Renzini