We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. ...If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su–Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.
The Covid-19 pandemic revealed the difficulties of vaccinating a population under the circumstances marked by urgency and limited availability of doses while balancing benefits associated with ...distinct guidelines satisfying specific ethical criteria. We offer a vaccination strategy that may be useful in this regard. It relies on the mathematical concept of envy-freeness. We consider finding balance by allocating the resource among individuals that seem heterogeneous concerning the direct and indirect benefits of vaccination, depending on age. The proposed strategy adapts a constructive approach in the literature based on Sperner's Lemma to point out an approximate division of doses guaranteeing that both benefits are optimized each time a batch becomes available. Applications using data about population age distributions from diverse countries suggest that, among other features, this strategy maintains the desired balance, throughout the entire vaccination period. We discuss complementary aspects of the method in the context of epidemiological models of age-stratified Susceptible - Infected - Recovered (SIR) type.
Following a novel approach, where the emphasis is on configuration spaces and equivariant topology, we prove several results addressing the
envy-free division problem
in the presence of an ...unpredictable (secretive, non-cooperative) player, called
the dragon
. There are two basic scenarios. (1) There are
r
-
1
players and a dragon. Once the “cake” is divided into
r
parts, the dragon makes his choice and grabs one of the pieces. After that, the players should be able to share the remaining pieces in an envy-free fashion. (2) There are
r
+
1
players who divide the cake into
r
pieces. A ferocious dragon comes and swallows one of the players. The players need to cut the cake in advance in such a way that no matter who is the unlucky player swallowed by the dragon, the remaining players can share the tiles in an envy-free manner. We emphasize that in both settings, some players may prefer to choose degenerate pieces of the cake. Moreover, the players construct in advance both a cut of the cake and a
decision tree
, allowing them to minimize the uncertainty of what pieces can be given to each of the players.
We consider the problem of allocating students to project topics satisfying side constraints and taking into account students’ preferences. Students rank projects according to their preferences for ...the topic and side constraints limit the possibilities to team up students in the project topics. The goal is to find assignments that are fair and that maximize the collective satisfaction. Moreover, we consider issues of stability and envy from the students’ viewpoint. This problem arises as a crucial activity in the organization of a first year course at the Faculty of Science of the University of Southern Denmark. We formalize the student-project allocation problem as a mixed integer linear programming problem and focus on different ways to model fairness and utilitarian principles. On the basis of real-world data, we compare empirically the quality of the allocations found by the different models and the computational effort to find solutions by means of a state-of-the-art commercial solver. We provide empirical evidence about the effects of these models on the distribution of the student assignments, which could be valuable input for policy makers in similar settings. Building on these results we propose novel combinations of the models that, for our case, attain feasible, stable, fair and collectively satisfactory solutions within a minute of computation. Since 2010, these solutions are used in practice at our institution.
Four persons envy-free division: A case study Rahman, Farin; Mostafa, Mahjabeen; Hafizur Rahman, M. M.
The 5th International Conference on Information and Communication Technology for The Muslim World (ICT4M),
2014-Nov.
Conference Proceeding
In this paper we present an algorithm for 4 person envy free division. The theme of this division is that each and every person will not envious to other i.e. no one will receive larger piece. They ...will be satisfied with their own portion and will think that he or she received the largest piece. Here we present two possible procedures and we used as minimal cuts as possible.
Suppose that
n
is not a prime power and not twice a prime power. We prove that for any Hausdorff compactum
X
with a free action of the symmetric group
S
n
, there exists an
S
n
-equivariant map
X
→
...R
n
whose image avoids the diagonal
{
(
x
,
x
,
⋯
,
x
)
∈
R
n
∣
x
∈
R
}
. Previously, the special cases of this statement for certain
X
were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of
S
n
-equivariant maps from the boundary
∂
Δ
n
-
1
of
(
n
-
1
)
-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.
PDF
