F Davoudi

D M Jassur

Analysis of the Gravity Mode of a Pulsating 𝐆𝐚𝐦𝐦𝐚 Doradus-type Star

Keywords:

In recent decades, asteroseismology has become a powerful tool in checking models for the structure and evolution of stars. From the perspective of asteroseismology, pulsating stars are invaluable. For this type of star, 𝛾 Doradus-type stars have a special feature. Since the atmosphere of such stars is in the transition phase from radiant state to convection state, gravity mode oscillations are visible in these stars. Since gravity modes are originated from central stellar regions, detecting them provides valuable information about these regions.

In this study, photometric data of KIC11826272 provided by the Kepler satellite has been analyzed. The gravity mode's pattern and the average period have been determined. Deviation from the uniform ∆𝑃 in the form of a pattern is due to the mean rotation of the star. The rotational frequency splitting effect has increased the gravity mode's frequency. A decaying deviation found in the pattern represents prograde modes that are moving in the direction of rotation of the star. Finally, the degree of gravity mode has been determined.

Introduction

Uncertainties happen for the theoretical modeling of structure and evolution of stars near the intersection of the red edge of the classical instability strip and the main sequence in the Hertzsprung-Russell diagram. Theoretical modeling of the evolution of stars depends on the chemical composition of stars and their interfacial processes [START_REF] Miglio | Probing the properties of convective cores through g modes: high-order g modes in SPB and γ Doradus stars[END_REF]. This applies to those main sequence stars with an intermediate mass ( 1𝑀 ⨀ 𝑀 * 2𝑀 ⨀ ). This is the transition range from low mass stars with a radiative core and a convective envelope to high mass stars with a convective core and a radiative envelope (Van Reeth et al. 2015). A good way to calibrate and improve upon the existing stellar structure and evolution theories in this mass range is to conduct a detailed seismological study of 𝛾 Dor pulsators. Such stars are slightly more massive (1.4-2.5 𝑀 ⨀ ) and more luminous than the Sun and exhibit non-radial gravity mode pulsations [START_REF] Kaye | γ Doradus stars: defining a new class of pulsating variables[END_REF]. The pulsations, which have a typical period between 0.3 and 3 days and are excited by the convective flux blocking mechanism at the bottom of the convective envelope, probe the internal stellar structure of the stars up to the edge of the convective core [START_REF] Guzik | Driving the gravity-mode pulsations in γ Doradus variables[END_REF].

In this study we looked at a star of this type named KIC11826272. We used the four-year high-precision Kepler photometry; the details of photometry are mentioned in Data Sets section below. In the Method section we described the basis of the study and the methodology. In the Data Analysis section we summarized the analysis of the star. Finally, in the Conclusion section the degree of gravity mode has been determined and the realized decaying deviation in the pattern represents prograde modes that are moving in the direction of rotation of the star.

Data Sets

KIC11826272 (also known as BD + 493115) is one of the stars that has been observed by the Kepler mission. Kepler light curves for this star are long cadence, i.e., with an integration time of 29.4 minutes. Data has been collected over a time interval of 1470.46248 days and marked for 18 quarters from 𝑄 to 𝑄 . Each light curve contains a set of 429 frames. The time that the camera remained open to collect flux from a target sample is 6.02 seconds for this star. The time it takes for each data set to be logged is 0.52 seconds with a frequency equivalent to the time of sampling of the landing flux 𝑓 283 μHz and power of frequency separation 𝑓 0.00068 𝑑 .

Method

In this project we used the traditional signal-to-noise ratio (SNR) method with code written on the target pixel file of the star. The file contains approximately 90,000 data points and was obtained based on the observed time and relative magnitude. Then, the possible oscillating frequencies from 90,000 frequencies have been found by the "prewhitening method". The prewhitening method is based on the Lomb-Scargle periodogram method; the details were provided by Timothy Van Reeth and his colleagues in 2015 (Van Reeth et al. 2015). The result has been the introduction of 511 possible oscillatory frequencies [START_REF] Ershadi | Thesis: Studying the pulsations of KIC 11826272, a 𝛾 Dor star of the Kepler Space Telescope[END_REF]. After determining the frequencies, the next step was to interpret them which will then lead to finding the oscillating modes of the star.

A Fourier transform was applied in the interval 0-3 days for the period and in the interval of 0 3 for the frequency are shown in Figure 1 and Figure 2; that includes 90,000 frequencies in the background (blue lines) and 511 frequencies selected on it (black lines). The vertical axis is the amplitude (Amp) and the horizontal axis is the frequency or period.

Data Analysis

Since these stars are at the lowest part of the unstable strip they can be observed in both pressure mode and gravity mode [START_REF] Aerts | Asteroseismology. Astronomy and Astrophysics Library[END_REF]). In our case, the target star has only significant frequency changes in the low-frequency region, gravity mode. High-frequency areas were also investigated and no significant peak exceeding 100 ppm was observed. In addition, to ensure that the other peaks observed are not related to pressure mode they can be examined if they are other than synthetic frequencies. Below we showed that no oscillation frequency occurred in the region exceeding 1.7 days. So again we conclude that there are only gravity modes.

Nonlinear pulsation effects can manifest themselves in the Fourier spectrum as combination frequencies and harmonics of a few parent frequencies. There is a formula for hybrid frequencies where n and m are small integers, 𝑓 and 𝑓 are the parent frequencies, and 𝑓 the combination frequency [START_REF] Schmid | KIC 10080943: An eccentric binary system containing two pressure-and gravitymode hybrid pulsators[END_REF]:

𝑛𝑓 𝑚𝑓 𝑓 𝑛 𝑚 2 1 𝑛𝑓 𝑚𝑓 𝑓 𝑓 2
To find hybrid frequencies, we selected frequencies with 𝑆𝑁𝑅 3.8 and amplitudes above 800 ppm as the source frequencies. We applied relation (1) by applying the condition of relation ( 2 ) where k and j are members of the source frequencies, while i can be the residual member of the frequencies. We found 394 hybrid frequencies, which we illustrate as their equivalent periods in Figure 3. The vertical axis is the amplitude and the horizontal axis is the period.

The Fourier transform, which is the basis for the prewhitening method, generates harmonic frequencies that are multiples of the basic pulse frequencies. These multiples can be from two to four times the original frequency according to relation (1); eight harmonic frequencies are shown in Figure 4. The vertical axis is the amplitude (Amp) and the horizontal axis is the frequency. In the first-order asymptotic approximation of a non-rotating star the periods of high order (𝑛 ≫ 𝑙) gravity modes in stars with a convective core and a radiative envelope [START_REF] Tassoul | Asymptotic approximations for stellar nonradial pulsations[END_REF]) are defined as

𝑃 𝑛 𝛼 , , (3)
Here 𝛼 , depends on the boundaries of the trapping region, P is the oscillation period, r the distance from the stellar center, and N the Brunt-Väisälä frequency. Following this relation modes with the same degree 𝑙, but consecutive orders 𝑛, are equidistantly spaced in the period. Their spacing value ∆𝑃 is then given by ∆𝑃 𝑃 𝑃 (4)

As a result, the expected period spacings for different 𝑙 -values will have fixed ratios.

For this work we found periods with 𝑆𝑁𝑅 3.8 which had distinct intervals from their next period and then we looked for a regular iterative pattern. This procedure is performed by examining each period and is repeatedly tested to confirm or reject the obtained ∆𝑃. The relationship between the found 𝑙 is proportional to the ∆𝑃 ratio of spherical degrees 1 and 3. On the other hand, according to the same theory, the ratio of smaller degree modes to larger degree modes should be greater than one, so smaller degree modes have a larger ∆𝑃. Two patterns are evident for the star's gravity mode, which are shown in Figure 5, with separate intervals.

Conclusion

The combination of frequencies was determined by two degrees of mode 𝑙 1 and 𝑙 3 for star pulsations. For 𝑙 1, eight gravity mode frequencies are involved in the pattern whose ∆𝑃 is 2870. For 𝑙 3, eleven gravity mode frequencies are involved in the pattern whose ∆𝑃 is 1032.

The deviation from the constant ∆P is due to the star's rotation or different layouts of star's density. If the star's rotation speed is too low and the star layering is almost uniform in the structure the gravity modes of the star do not frequency shift. But if this deflection is affected by the medium to fast rotation of the star or the star layering does not have a uniform structure, the gravity modes of the star do frequency shift. Consequently, the from the constant ∆𝑃 intensifies and the pattern will appear in ascending or descending form (Van Reeth et al. 2015). The descending pattern of our star (prograde mode) is due to placing the mode in the lower frequencies.

Figure 1 .

 1 Figure 1. Period spectrum of KIC 11826272. Fourier transform applied in the interval 𝟎 𝟑 𝒅𝒂𝒚𝒔.

Figure 2 .

 2 Figure 2. Frequency spectrum of KIC11826272; Fourier transform applied in the interval 𝟎 𝟑 𝟏 𝒅 .

Figure 3 .

 3 Figure 3. Hybrid frequencies of KIC11826272.

Figure 4 .

 4 Figure 4. Harmonic frequencies of KIC11826272.

Fig 5 .

 5 Fig 5. The prograde period spacing patterns of KIC11826272.

Acknowledgments

This research was supported by Department of Theoretical Physics and Astrophysics, Tabriz University, Tabriz, Iran. We would also like to show our deep gratitude to Timothy Van Reeth (Institute of Astronomy, KU Leuven) for the permission he has given us to use the relevant Python code for this project. Furthermore, thanks Atila Poro (The President of IOTA/ME) for his guidance and assistance to publish this paper.


Sylvain Bouveret

Katarína Cechlarova

Julien Lesca

Katarína Cechlárová

Chore division on a graph

est destinée au dépôt

Introduction

Fair division of goods and resources is a practical problem in many situations and a popular research topic in Economics, Mathematics and Computer science. Sometimes, however, the objects that people have to deal with are undesirable, or, instead of utility create some cost. Imagine that a cleaning service firm allocates to its teams a set of offices, corridors, etc in a building. Each team has some idea of how much effort each room requires. The cost of the whole assignment for a team may be in the form of time the team will have to spend on the job, and this might depend on whether the work in all assigned rooms can start simultaneously or whether they have to be treated one after another. Moreover, for practical reasons, it is desirable that each team's assignment is a contiguous set of rooms. As another example consider a firm that supervises the operation of the computer network during a conference. Each of its employees has to choose one of the possible shifts, but shifts scheduled at different times of the conference may incur different opportunity cost for various persons. Moreover, we can assume that everybody prefers to have just one uninterrupted period to spend at work. The constraints described above could be represented by an undirected graph whose vertices are rooms or time intervals and there is an edge between two vertices if the respective rooms are adjacent; or the corresponding time periods immediately follow each other. Each agent should obtain a connected piece of the underlying neighborhood graph. Complete graphs correspond to the 'classical' case with no connectivity constraints. By contrast, paths and stars represent the simplest combinatorial structures, and yet such graphs can be used to model a rich variety of situations. For example, a path may represents successive time intervals and a star corresponds to a building with a central foyer and mutually non-connected rooms accessible from this foyer.

Related work

The mathematical theory of fair division started with the seminal paper of [START_REF] Steinhaus | The problem of fair division[END_REF]. Although originally most researchers focused on divisible items (the topic is also known as the cake-cutting problem), fair division of indivisible goods has also received a considerable amount of attention in the traditional and computational social choice literature. The interested reader can for instance read the survey by [START_REF] Bouveret | Fair allocation of indivisible goods[END_REF] for an overview of this topic.

Several recent papers combine graphs and fair division of indivisible items by assuming that agents are located in the vertices of a graph. For instance, [START_REF] Chevaleyre | Allocating goods on a graph to eliminate envy[END_REF] and [START_REF] Gourvès | Object allocation via swaps along a social network[END_REF] consider the case where each agent has an initial endowment of goods and can trade with her neighbors in the graph. The authors study outcomes that can be achieved by a sequence of mutually beneficial deals.

In the paper by [START_REF] Bouveret | Fair division of a graph[END_REF] for the first time a graph-based constraint on agents' bundles has been imposed. The authors model the items as vertices of a graph and they require that each agent should receive a bundle that forms a connected subgraph. They show that even if the underlying graph is a path the problems to decide whether there exist proportional or envyfree divisions with connected shares are NP-complete. In case of stars, envy-freeness is also intractable, but a proportional division can be found by a polynomial algorithm. In addition, [START_REF] Bouveret | Fair division of a graph[END_REF] study maximin (MMS) allocations, a fairness notion introduced by [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF]. They show that a MMS allocation always exists if the underlying graph is a tree, provide a polynomial algorithm to find one in this case and show that a cycle may admit no MMS allocation.

This work inspired other authors who also considered allocations on a graph with the additional constraint that each bundle has to be connected. [START_REF] Suksompong | Fairly allocating contiguous blocks of indivisible items[END_REF] considers only paths and studies approximately fair (proportional, envy-free and equitable) allocations up to an additive approximation factor. He shows that for all the three fairness notions there is a simple approximation guarantee derived from the maximum value of an item and that for proportionality, as well as equitability, an allocation achieving this bound can be computed efficiently. [START_REF] Biló | Almost envy-free allocations with connected bundles[END_REF] deal with two relaxations of envy-freeness: envy-free up to one good, briefly EF1 (an agent does not think that another agent's bundle, possibly with one of its outer items removed, is more valuable than her own bundle) and envy-free up to two outer goods, briefly EF2. They characterize graphs admitting allocations fulfilling these notions and provide efficient algorithms to find such allocations. [START_REF] Lonc | Maximin share allocations on cycles[END_REF] study MMS allocations of goods. For the underlying graph being a cycle they identify several cases when MMS-allocations always exist (e.g. at most three agents and at most 8 goods, the number of goods not exceeding twice the number of agents, fixed number of agent types) and provide results on allocations guaranteeing each agent a certain portion of her maximin share. [START_REF] Igarashi | Pareto-optimal allocation of indivisible goods with connectivity constraints[END_REF] study Pareto-optimality. They show that for paths and stars a Pareto optimal allocation can be found efficiently, but the problem is NP-hard even for trees of bounded pathwidth. They also show that it is NP-hard to find a Pareto-optimal allocation that satisfies maximin share even on a path.

It is worth noting that although the study of connected fair division is relatively recent in the context of indivisible items, there is an important literature on the contiguity requirement in the context of cake-cutting. From the great number of various results we consider among the most interesting ones the contrast between the proven existence of envy-free [START_REF] Stromquist | How to cut a cake fairly[END_REF] and equitable [START_REF] Aumann | The efficiency of fair division with connected pieces[END_REF][START_REF] Cechlárová | On the existence of equitable divisions[END_REF] divisions with connected pieces and, on the other hand, the nonexistence of finite algorithms for computing them [START_REF] Stromquist | How to cut a cake fairly[END_REF][START_REF] Cechlárová | On the computability of equitable divisions[END_REF].

Beyond considering the connectivity constraint, an important aspect in which our work departs from the mainstream literature on fair division is the fact that we consider negative items (chores).

Chore division of divisible goods was mentioned for the first time by [START_REF] Gardner | Aha! Insight[END_REF]. Al-though straightforward modifications of some algorithms for positive utilities can also be applied to the chore division context (e.g., the Moving Knife algorithm for proportional divisions), it happens more often that chore division problems are more involved than their fair division counterparts. For example, the discrete algorithm for obtaining an envy-free division of divisible chores for three persons by Oskui (Robertson and Webb, 1998, pages 73-75) needs nine cuts and the procedure based on using four moving knifes makes 8 cuts [START_REF] Peterson | Four-person envy-free chore division[END_REF], while in the Selfridge's algorithm for envy-free (positive) division [START_REF] Woodall | Dividing a cake fairly[END_REF] five cuts suffice. If the number of agents is 4, the moving-knife procedure by [START_REF] Brams | A moving knife solution to the four-person envyfree cake division problem[END_REF] needs 11 cuts, while the first algorithm for envy-free division of chores, given by [START_REF] Peterson | Four-person envy-free chore division[END_REF], needs 16 cuts.

The fact that chore division has been given much less attention in research is mirrored also in monographs on fair division. For example, [START_REF] Robertson | Cake-cutting Algorithms: Be Fair if You Can[END_REF] only deal with chores in Section 5.5; of Chapter 7 on cake cutting in the book Economics and Computation edited by [START_REF] Rothe | Economics and Computation: An Introduction to Algorithmic Game Theory[END_REF] only Section 7.4.6 treats chores and Chapter 12 on fair division of indivisible goods in the Handbook of Computational Social Choice by [START_REF] Bouveret | Fair allocation of indivisible goods[END_REF] does not mention chores at all.

Of the more recent works on chore division let us mention [START_REF] Caragiannis | The efficiency of fair division[END_REF] who deal with divisible and indivisible goods and chores from the point of view of the price of fairness for three fairness notions. [START_REF] Heydrich | Dividing connected chores fairly[END_REF] consider the price of fairness for the fair division of infinitely divisible chores. [START_REF] Aziz | Algorithms for max-min share fair allocation of indivisible chores[END_REF] also deal with chores; the considered fairness notion is maximin share guarantee. In the divisible chores setting, [START_REF] Dehghani | Envy-free chore division for an arbitrary number of agents[END_REF] give the first discrete and bounded protocol for envy-free chore division problem and [START_REF] Farhadi | On the complexity of chore division[END_REF] prove the Ω(n log n) lower bound for the number of queries in a proportional protocol for chores.

Finally, in the context of indivisible items, where the existence of fair allocations cannot be ensured, it is rather natural to study approximations of the fairness criteria. [START_REF] Markakis | On worst-case allocations in the presence of indivisible goods[END_REF] prove a worst case guarantee on the value that every agent can have and they propose a polynomial algorithm for computing allocations that achieve this guarantee. By contrast, they show that if P = NP there is no polynomial algorithm to decide whether there exists an allocation where each agent can get a bundle worth at least 1/cn for any constant c ≥ 1. [START_REF] Lipton | On approximately fair allocations of indivisible goods[END_REF] focus on the concept of envy-freeness. They show that there exists an allocation with maximum envy not exceeding the maximum marginal utility of a good. However, the problem of computing allocations with minimum possible envy is hard, even in the case of additive utilities.

Our contribution In this paper, we extend the work of [START_REF] Bouveret | Fair division of a graph[END_REF] about fair division of goods on a graph. We also use the connectivity constraints defined by a graph on the items. However, we deal with nondisposable undesirable items, often called chores. We use three classical fairness criteria, namely proportionality, envy-freeness and equitability, and two different individual disutility aggregation functions: additive and maximum based. We show that dealing with goods and chores is inherently different, in particular, it is impossible to transform a chore instance simply by negating the utility values and applying the algorithm that works for goods.

Then we investigate the complexity of the problems to find a fair allocation of chores. It is known that these problems are hard on complete graphs in the additive case, but the maximumbased case, as far as we know, has not been studied before. Therefore, we complement the picture by providing efficient algorithms for proportionality and equitability, and show that envy-freeness leads to an NP-complete problem. Further, we concentrate on two special classes of graphs: paths and stars.

In more detail, we provide a general reduction for paths that directly implies NP-completeness of the existence problems for all the considered fairness criteria and both disutility aggregations. Moreover, by a very small modification of the reduction we obtain that these problems are hard even in the binary case i.e., when disutility values for chores are either 0 or 1. By contrast, if the underlying graph is a star, we propose an efficient algorithm, based on bipartite matching techniques, to decide whether a valid allocation exists such that each agent has disutility 0. This in turn implies that envy-freeness and equitability criterion admit efficient algorithms for decision problems in the binary case. Matching techniques lead to efficient algorithms also in the maximum-based case, even when disutilities are not restricted to be binary. In the additive case we provide an efficient algorithm for proportionality. On the other hand, it is NP-complete to decide the existence of envy-free or equitable valid allocations on a star. This paper is organized as follows. In Section 2 we introduce the model of connected fair division of indivisible chores and the definitions of the various fairness criteria we use in the paper. Our technical results are presented in Sections 3, 4 and 5 which respectively deal with the cases where the underlying graph is a complete graph, a path and a star. Table 1 shows an overview of the results introduced in this paper. Finally, we discuss the results and some open problems in Section 6. An instance of CONNECTED CHORE DIVISION CCD is a triple I = (N, G, U ). When we shall occasionally talk about problems with positively interpreted utility, we shall call them CON-NECTED FAIR DIVISION problems, briefly CFD.

Any subset X ⊆ V is called a bundle. We consider two disutility aggregation functions. In the additive case the disutility agent i derives from bundle X is equal to the sum of the disutilities of the objects that form the bundle, i.e. u add i (X) = v∈X u i (v). In the maximum-based case the disutility of a bundle is derived from the maximum disutility of an object in the bundle, i.e.

u max i (X) = max{u i (v) | v ∈ X}.
If the aggregation function is not specified or if it is clear from the context, the superscript may be omitted. In the maximum-based extension we shall also consider an important binary case when the disutilities of agents for objects are either 1 or 0. The binary case represents the situation of agents finding some objects negative without expressing the "degree of negativity" and some other objects bring them neither nuisance nor joy.

We assume that the disutilities are normalized. This means that u add i (V ) = 1 and u max i (V ) = 1 for each agent i in the additive and in the maximum-based case, respectively.

An allocation is a function π : N → 2 V assigning each agent a bundle of objects. An allocation π is valid if:

• for each agent i ∈ N , bundle π(i) is connected in G;
• π is complete, i.e., i∈N π(i) = V and;

• no item is allocated twice, so that π(i) ∩ π(j) = ∅ for each pair of distinct agents i, j ∈ N .

We say that a valid chore allocation π is:

• proportional if u i (π(i)) ≤ 1 n for all i ∈ N ; • envy-free if u i (π(i)) ≤ u i (π(j)) for all i, j ∈ N ; • equitable if u i (π(i)) = u j (π(j)) for all i, j ∈ N .
Let us remind the reader that the corresponding notions of proportionality and envy-freeness for CFD are defined by reversing the respective inequalities. Equitability is defined in the same way in both cases, but since no results for goods with connected bundles have been published yet, we shall try to close this gap.

Notice that with maximum-based disutility aggregation, proportionality does not have a similar interpretation as in the additive case, where dividing the disutility by the number of agents corresponds to sharing the total burden. Still, we shall use this term also in the case when agents care for the worst item in their bundle, meaning that we seek an allocation that restricts the disutility by the same threshold for everybody.

Taking into account the large number of existing results concerning the fair division of goods, one could be tempted to try and adapt these results to the case of chores. First, observe that if in a fair division instance there are more agents than items, no proportional and envy-free allocation can exist, which is not necessarily the case with chores. Further, although it seems natural to transform a chore division instance to a 'dual' fair division instance simply by replacing each disutility u i (v) by a 'reverse' desirable utility Mu i (v) for each agent i and each object v (M is a sufficiently large real number), we show that the properties of the related instances do not translate.

Example 2.1. Let us consider the CCD instance I with three agents 1,2,3 and four vertices v 1 , v 2 , v 3 , v 4 arranged on a path in this order and disutilities given in the left half of Table 2. Its right half shows the utilities for the 'dual' CFD instance I ′ obtained for M = 10.

1 v 1 v 2 v 3 v 4 agent 1 6 4 0 0 agent 2 7 0 1 2 agent 3 5 0 0 5 v 1 v 2 v 3 v 4
agent 1 4 6 10 10 ⋆ agent 2 3 ⋆ 10 ⋆ 9 8 agent 3 5 10 10 ⋆ 5

Table 2: The CCD (left) and CFD (right) instances for proportionality notion A proportional chore allocation should give each agent a bundle of disutility at most 10/3. I does not admit a valid proportional allocation, as nobody is willing to take vertex v 1 . In the dual CFD instance I ′ a proportional valid allocation exists, simply give agent 1 vertex v 4 , agent 2 bundle {v 1 , v 2 } and agent 3 vertex v 3 . This allocation is depicted with stars in the right half of Table 2.

Example 2.2. Now slightly change the disutilities of agent 3; the new CCD instance and its dual CFD instance are given in Table 3. Now I has an envy-free valid allocation, namely π(1) = {v 3 , v 4 }, π(2) = {v 2 } and π(3) = {v 1 }, again depicted with stars in the left half of Table 3. However, there is no envy-free valid allocation

v 1 v 2 v 3 v 4 agent 1 6 4 0 ⋆ 0 ⋆ agent 2 7 0 ⋆ 1 2 agent 3 0 ⋆ 5 5 0 v 1 v 2 v 3 v 4
agent 1 4 6 10 10 agent 2 3 10 9 8 agent 3 10 5 5 10 in the dual fair division instance I ′ . To see this, let us first realize that as there are three agents and four items, exactly one of the agents has to receive a bundle consisting of two vertices. Since each allocated bundle has to be connected, there are exactly three such two-elements bundles: {v 1 , v 2 }, {v 2 , v 3 } and {v 3 , v 4 }. One can see that each such bundle has utility strictly greater than 10 for at least two agents, and as each agent values individual vertices at not more than 10, there will always be somebody envying the agent receiving the two-element bundle.

We see that similarly as in the 'classical' case of indivisible goods without connectivity constraints, the existence of allocations fulfilling the above definitions is not ensured in general. Therefore we shall deal also with approximate fairness. We can ask whether for a given c ≥ 1, a valid chore allocation π exists such that each agent i ∈ N receives a bundle such that u

i (π(i)) ≤ c • 1 n , or such that u i (π(i)) ≤ c • u i (π(j)) or u j (π(j))/c ≤ u i (π(i)) ≤ c • u j (π(j)
holds for each pair of agents i, j. Later in this paper we shall see that even for paths the problems to decide whether a valid allocation exists such that the disutility of each agent equals 0 is NP-hard. This immediately implies intractability of the just formulated problems for any c > 1.

We will consider the following computational problems that all take an instance I = (G, N, U ) of CCD as their input. PROP-CCD, EF-CCD and EQ-CCD ask whether I admits a proportional, envy-free and equitable allocation, respectively. If we want to stress which disutility aggregation functions is used, we insert prefix ADD or MAX to this notation.

It is easy to see that all the considered problems belong to the class NP, as given an allocation, it can be verified in polynomial time whether it is valid and also whether it is proportional, equitable (linear in the problem size) or envy-free (in time O(mn + n 2 )).

Complete graphs

Note that the classical case (without connectivity requirements) corresponds in our model to the underlying graph being complete. Then, all the problems studied are hard for the additive disutility aggregation. The intractability can be proved using a reduction from PARTITION (see e.g. [START_REF] Demko | Equitable distribution of indivisible items[END_REF].

Proposition 3.1. ADD-PROP-CCD, ADD-EF-CCD and ADD-EQ-CCD are NP-complete even for two agents with the same disutility function and even if the underlying graph G is bipartite. Now suppose that agents aggregate their disutilities using maximum and consider the following algorithm that we shall call greedy: assign each item v to agent i such that u i (v) = min j∈N u j (v). It is easy to see that the greedy algorithm produces a valid allocation π that minimizes max i∈N u max i (π(i)).

If we want to decide the existence of an equitable allocation, for each possible disutility target w we do the following. We create the bipartite graph H w = (N, V, L w ) with the two parts of the vertex set corresponding to the set of agents and to the set of chores, respectively, and with the edge set defined by (i, v) ∈ L w if u i (v) = w. Then we check whether H admits a matching that covers N . If the answer is no, there is no valid allocation π such that u max i (π(i)) = w for each agent. If the answer is yes, we try to assign the remaining chores greedily. We conclude that there exists an equitable allocation with the common disutility equal to w if and only if the greedy algorithm does not assigns to any agent a chore for which she has a disutility exceeding w. This can be summarized as follows.

Theorem 3.2. MAX-PROP-CCD and MAX-EQ-CCD can be solved in polynomial time.

By contrast, envy-freeness criterion leads to an intractable problem. In the following proof we provide a reduction from the NP-complete problem (2,2)-E3-SAT [START_REF] Berman | Approximation hardness of short symmetric instances of MAX-3SAT[END_REF] that asks, given a Boolean formula F in Conjunctive Normal Form, where each clause in F has size three, and each variable occurs exactly twice unnegated and exactly twice negated, whether F is satisfiable.

Theorem 3.3. MAX-EF-CCD is NP-complete even if the underlying graph G is complete.

Proof. Let formula F be given with a set of variables X = {x 1 , . . . , x s } and set of clauses C = {c 1 , . . . , c t }. Let L be the set of literals i.e., L = s j=1 {x 1 j , x 2 j , x1 j , x2 j } and for any ℓ ∈ L, let c(ℓ) denote the clause containing literal ℓ. Let L i denote the set of literals in clause c i .

For each formula F we construct an instance of MAX-EF-CCD as follows. The set of chores is

V = W ∪ Z ∪ Z ′ ∪ Y , where W = s j=1 W j with W j = {w 1 j , w 2 j , w1 j , w2 j } are literal chores, Z = {z 1 , z 2 , . . . , z s } are clause chores, Z ′ = {z ′ 1 , z ′ 2 , .
. . , z ′ s } are dummy clause chores and Y = s j=1 Y j , with Y j = {y 1 j , y 2 j , y 3 j , y 4 j } are dummy variable chores. The chore corresponding to literal ℓ ∈ L will be denoted w(ℓ).

We further assume that the set of chores is ordered W 1 , W 2 , . . . , W s , Z, Z ′ , Y 1 , Y 2 , . . . , Y s while the ordering within each subset is the same as the order in which the chores in the respective subset have been written above. The position β(v) of a chore v ∈ V in this ordering is equal to the disutility u i (v) derived by each agent i ∈ N from chore v, unless defined differently.

The set of agents is

N = B ∪ B ′ ∪ P ∪ Q, where B = {b 1 , b 2 , . . . , b t } are clause agents, B ′ = {b ′ 1 , b ′ 2 , .
. . , b ′ t } are dummy clause agents, P = {p 1 , p 2 , . . . , p s } are variable agents and Q = s j=1 Q j with Q j = {q 1 j , q 2 j , q 3 j , q 4 j } are dummy variable agents. The disutilities are defined in Table 4, where for each agent we list the chores with disutilities equal to 0 and to ε, where 0 < ε < 1 is fixed. The disutility of any chore v to agent who does not have v displayed in this table is equal to β(v).

agent disutility equal 0 disutility equal ε b i , i = 1, 2, . . . , t z i , {w(ℓ) |ℓ ∈ L i } - b ′ i , i = 1, 2, . . . , t z i z ′ i p j , j = 1, 2, . . . , s w 1 j , w 2 j , w1 j , w2 j - q 1 j , j = 1, 2, . . . , s w 1 j , w1 j y 1 j q 2 j , j = 1, 2, . . . , s w 1 j , w2 j y 2 j q 3 j , j = 1, 2, . . . , s w 2 j , w1 j y 3 j q 4 j , j = 1, 2, . . . , s w 2 j , w2 j y 4 j
Table 4: Disutilities in the proof of Theorem 3.3.

Let us briefly explain how the reduction works before proving that it is correct. Each variable agent will receive a subset of literal chores that correspond to her variable. Each dummy variable agent will receive her corresponding dummy variable chore and will envy the corresponding variable agent as soon as she does not receive a subset of literal chores containing either two positive literals or two negative literals. Each clause agent will receive a clause chore as well as at least one literal chore associated with one of her literals. Clause chores ensure that no variable agent will envy a clause agent. Furthermore, each dummy clause agent will receive her corresponding dummy clause chore and will envy her corresponding clause agent as soon as she does not receive at least one of her corresponding literal chores.

Assume first that f is a truth assignment that satisfies all clauses in C. We construct from f an assignment π as follows. For each variable x j , if x j is false according to f then π(p

j ) = {w 1 j , w 2 j }, otherwise π(p j ) = { w1 j , w2 j }. Furthermore, π(b i ) = {z i } ∪ {w(ℓ), ℓ ∈ L i and ℓ is true in f }. Finally, π(b ′ i ) = {z ′ i } for i = 1, 2, .
. . , t and π(q k j ) = {y k j } for j = 1, 2, . . . , s and k = 1, 2, 3, 4. Clearly, π is valid. It is easy to check that this allocation is envy free. Namely, the disutility agents of B ∪ P receive in π is 0, so they do not envy. Take a dummy agent a. This agent does not envy because u a (π(a)) = ε and for each agent a ′ = a the bundle π(a ′ ) contains a chore v such that u a (v) is a strictly positive integer.

Conversely, suppose that there is a valid assignment π such that no agent envies another one. In the first part of the proof we use mathematical induction on the reverse ordering β(v) of the chores in the following way: we take the next chore v and argue that v must belong to the bundle of a certain agent i. Let us say that agent i was treated treated.

As the disutility of y 4 s is maximum of all chores, if y 4 s ∈ π(a) for any agent a = q 4 s then a will envy any other agent. Therefore y 4 s ∈ π(q 4 s ). Now suppose that y k j ∈ π(q k j ) for each y k j ∈ Y such that β(y k j ) > u. Take y k j such that β(y k j ) = u. If y k j ∈ π(a) for some agent a = q k j then a will envy any other agent that was not treated yet.

Similarly, by induction for i = t, t -1, . . . , 1 we show that

z ′ i ∈ π(b ′ i ).
As the disutility of z ′ t is maximum of all chores that have not yet been assigned, if z ′ t ∈ π(a) for some agent a = b ′ t then a will envy any other agent in N \ Y . Therefore

z ′ i ∈ π(b ′ i ). Now suppose that z ′ i ∈ π(b ′ i ) for each i > k. Take z ′ k . If z ′ k ∈ π(a)
for any agent a = b ′ k then a will envy any agent not treated so far. By an analogical inductive argument we show that

z i ∈ π(b ′ i ) or z i ∈ π(b i )
for each i = t, t -1, . . . , 1 because otherwise the agent that gets this chore will envy any untreated agent (for example, an agent in P ). Now we know that the disutility of each agent q k j in π is at least ε and q k j does not envy agent p j . So we must have that either {w 1 j , w 2 j } ⊆ π(p j ) or { w1 j , w2 j } ⊆ π(p j ) for each j = 1, 2, . . . , s. Let us say that x j is false in the former case and that x j is true in the latter case. Finaly, so as no agent b ′ i envies b i , we get that π(b i ) must contain at least one chore w(ℓ) for ℓ ∈ L i , and due to the truth values and assignment of chores in W defined above, this chore must correspond to a true literal in clause c i . Hence we obtain an assignment of truth values that makes F true.

Paths

Even if the underlying graph is restricted to be a path then all the considered chore division problems are intractable, as we now show. All the proofs in this section are based on the same construction starting from an instance of (2,2)-E3-SAT.

So let a formula F as an instance of (2,2)-E3-SAT be given with variables X = {x 1 , . . . , x s } and clauses C = {c 1 , . . . , c t }. By L we denote the set of literals in F , i.e. L = ∪ s j=1 {x 1 j , x 2 j , x1 j , x2 j } and c(ℓ) for ℓ ∈ L denotes the clause that contains literal ℓ. Notice that the structure of the formula implies 3t = 4s and hence s = 3t/4.

Let c ≥ 1 be given. We construct an instance I of CCD with the set of chores V = Y ∪ Z ∪ D where Y = {y 1 , . . . , y t } are clause chores, Z = ∪ s j=1 {z 1 j , z 2 j , z1 j , z2 j } are literal chores and D = {d 1 , . . . , d s } are variable chores. The number of chores is thus m = 5s + t. The graph G defining the neighborhood relation between chores (illustrated in Figure 1) has the edges

• (y i , y i+1 ) for i = 1, 2, . . . , t -1; • (y t , z 1 1 ); • (z 1 j , z 2 j ); (z 2 j , d j ), (d j , z1 j ), (z 1 j , z2 j ) for j = 1, 2, . . . , s;
Now we use Lemma 4.1 in the following results.

Theorem 4.2. Let c ≥ 1 be arbitrary. If P = NP then there is no polynomial algorithm to decide if an instance of CCD admits a valid allocation such that u i (π(i)) ≤ c/n for each i ∈ N , even if G is a path. Hence, ADD-PROP-CCD is NP-complete.

Proof. As the number of agents in I is n = c(5s + t) + 1, the disutility of each agent in a cproportional allocation should be at most 1/(c(5s + t) + 1). However, each chore with a positive disutility brings each agent at least 1/(5s + t), so the result is directly implied by Lemma 4.1.

As m < n in I, at least one agent gets nothing. Hence in any envy-free or equitable allocation everybody has to get a bundle with disutility 0. So Lemma 4.1 directly implies also the following assertions.

Theorem 4.3. ADD-EF-CCD and ADD-EQ-CCD are NP-complete if G is a path.

For the maximum-based disutility extension, let us change the construction in the beginning of this section slightly. Namely, each positive disutility of an item will be set to 1. The same arguments as above are still valid, so we get the following assertion.

Theorem 4.4. MAX-EF-CCD and MAX-EQ-CCD are NP-complete if G is a path, even in the binary case.

Stars

Let c denote the center of the star. As each agent has to get a connected bundle, only the agent that is assigned c can get more than one chore. According to the fairness criterion used, there are necessary conditions that each agent has to fulfill, so as to be entitled to be assigned c; we shall call such an agent central. If there is no agent who fulfills these conditions then there is no valid allocation with the desired properties. If there exists such an agent, we still have to decide about the assignment of the leaves to the other agents. For this graph topology we first present efficient algorithms and then proceed to hard cases.

Easy cases

All the easy cases use a similar idea, borrowed from [START_REF] Bouveret | Fair division of a graph[END_REF]. First we guess a central agent c. This agent gets as many leaves as possible, and the assignment of the other leaves to other agents is found by employing an efficient matching algorithm in bipartite graphs.

We can also perform a similar complexity analysis for all the algorithms. The upper-bound on the number of steps depends on the matching algorithm used. The bipartite graph constructed in the algorithm has O(m + n) vertices and O(mn) edges. The Hopcroft-Karp matching algorithm applied to a graph with p vertices and q edges runs in O(q √ p) steps, which in our case thus means O(mn √ m + n) steps. Moreover, we might need to repeat the procedure for each agent, and that leads an overall complexity of O(mn 2 √ m + n).

Theorem 5.1. ADD-PROP-CCD is solvable in polynomial time if G is a star.

Proof. First, a central agent i must fulfill u i (c) ≤ 1/n. Let us check for each such agent i whether there is a proportional valid allocation π assigning c to i.

To this end, we create a bipartite graph H = (Z, Z ′ , L) with Z = N \ {i}, Z ′ = V \ {c} and {j, v} ∈ L if and only if u j (v) ≤ 1/n; the weight of this edge is u i (v).

We find a maximum weight matching M in H. A proportional valid allocation exists if and only if the weight of M is at least (n -1)/n. If this is the case, assign the objects to agents in Z according to M and all the unmatched leaves plus the central vertex to i. Now let us deal with a possibility that each agent gets a bundle with disutility 0. Proposition 5.2. If G is a star then the problem to decide the existence of a valid allocation where each agent gets a bundle with disutility 0 can be solved in polynomial time.

Proof. To be able to decide the existence of such an allocation, let us first realize that an agent i can be central only if u i (c) = 0. For such an agent i let X i = {v ∈ V ; u i (v) = 0}. Now create the bipartite graph H = (Z, Z ′ , L) where Z = N \{i}, Z ′ = V \X i and {j, v} ∈ L if u j (v) = 0. Clearly, a desired allocation exists if and only if H admits a matching M that covers all vertices in Z ′ .

Theorem 5.3. MAX-EQ-CCD is solvable in polynomial time if G is a star.

Proof. Proposition 5.2 helps in deciding the existence of a valid allocation such that everybody gets disutility 0. Now let us deal with the case when all agents receive bundles with positive disutility equal to η.

An agent i can be a central agent in an equitable allocation with the common disutility equal to η only if u i (c) ≤ η. Now we proceed differently when this inequality is fulfilled as equation and when it is strict.

If u i (c) = η we create a flow network H = (Z, L) as follows. Its vertices are the source s, sink t and one vertex for each agent and one vertex for each leaf of G. The source is connected to each agent vertex; capacities of arcs (s, j) for j = i are 1, capacity of arc (s, i) is mn. There is an arc of capacity 1 between the vertex corresponding to agent j = i and the vertex corresponding to leaf v if u j (v) = η and between i and leaf v if u i (v) ≤ η. Each leaf vertex is connected to t, the capacities of these arcs are also 1. A desired allocation exists if and only if there is a flow of size m -1 in this network, namely, the leaves are allocated to agents according to the agent-leaf arcs with nonzero flow.

If u i (c) < η we have moreover to ensure that agent i gets at least one leaf v such that u i (v) = η. The above construction of the flow network will be modified in the following way. Agent i will not be connected with leaves directly, but there will be two more vertices r 1 , r 2 and the following arcs: (i, r 1 ) with capacity m and arcs (r 1 , v) for each leaf v such that u i (v) = η; arc (i, r 2 ) with capacity mn -1 and arcs (r 2 , v) for each leaf v such that u i (v) < η. The construction of the flow network is shown in Figure 2. Again, a desired allocation in which agent i gets at least one leaf with disutility exactly η exists if and only if there is a flow of size m -1 in this network. As we shall see later, the problem of deciding the existence of an envy-free valid allocation in the additive case is in general NP-complete. However, there is a plausible efficiently solvable special case. We say that agents' preferences are strict on chores if u i (v) = u i (w) for any agent i and any pair of distinct vertices v, w.

s i j k r 1 r 2 v 1 v 2 v m t m - n m m -n -1 if u i (v ) = η if ui (v ) < η
Theorem 5.4. ADD-EF-CCD is solvable in polynomial time if G is a star and the agents' preferences are strict on chores.

Proof. If m < n then each agent has to get a bundle with disutility 0, and since preferences are strict, this is only possible if each agent gets at most one vertex, namely the one where she has disutility 0. We can easily verify whether this happens by matching techniques. Now let us proceed to the case when agents receive bundles positive disutility. Let us in turn check for each agent i whether she can be the central agent. To this end, order all the vertices in V according to i's disutility increasingly (we might possibly rename the the vertices in G)

u i (v 1 ) < • • • < u i (v m-n+1 ) < u i (v m-n+2 ) < • • • < u i (v m ) (1)
and notice that the central agent will receive exactly mn + 1 vertices. The necessary conditions a central agent i must therefore fulfill are:

(i) vertex c must be among the vertices v 1 , v 2 , . . . , v m-n+1 and

(ii)

m-n+1 k=1 u i (v k ) ≤ u i (v m-n+2 )
These conditions imply that when assigned the bundle X = {v 1 , v 2 , . . . , v m-n+1 }, agent i will not envy any other agent. We still have to ensure no envy among other agents.

Let us construct the bipartite graph H = (Z, Z ′ , L) with Z = N \{i}, Z ′ = V \X and {j, v} ∈ L if the following inequality is fulfilled:

u j (v) ≤ min{{u j (v ′ ); v ′ ∈ Z ′ }, u add j (X)}. (2)
Finally, there exists in I an envy-free assignment if and only if H admits a perfect matching M . Namely, agent i is assigned bundle X and the other agents chores according to M .

The proof of the previous theorem can easily be adapted also for the maximum based disutility aggregation.

Theorem 5.5. MAX-EF-CCD is solvable in polynomial time if G is a star and the preferences of agents are strict on chores.

Proof. When checking whether agent i cen be central, after we permute the vertices of G according to i's disutility increasingly, it is easy to see that it suffices to check just condition (i). Further, in the construction of the bipartite graph H condition (2) should be replaced by

u j (v) ≤ min{{u j (v ′ ); v ′ ∈ Z ′ }, u max j (X)} (3)
and the rest of the proof follows.

Hard cases

It turns out that the only intractable problems when the underlying graph is the star are connected with envy-freeness and equitability when the disutilities are aggregated additively.

Theorem 5.6. ADD-EF-CCD is NP-complete even if the underlying graph G is a star.

If d is not assigned to r then r will envy the agent who receives it. Hence, d is assigned to r in π. This in turn implies that each agent b i should receive chore z(ℓ) for some ℓ ∈ L i . This also implies that each variable agent should receive a chore for which she has disutility 0 or ε, which means that chore ỹi is either assigned to agent p i or q i . We now construct truth assignment f as follows. If ỹi is assigned to p i in π then set x i to be true, and otherwise (i.e. ỹi is assigned to q i ) set x i to be false. We will show that f satisfies each clause c i . Let ℓ be the literal of c i such that z(ℓ) is assigned to b i . Assume that ℓ is a positive literal of variable x j (the negative case can be treated in a similar way). If ỹj is assigned to agent q i then she will envy agent b i , leading to a contradiction. Therefore, ỹi is assigned to agent p i , x i is set to true and clause c i is true. which implies i∈P a i + i∈P ′ b i = K and hence (P, P ′ ) is a partition of [p] verifying that J is a yes instance of PARTITION.

Conclusion and open problems

In this paper we studied the computational complexity of the problem of finding a fair allocation of nondisposable undesirable items (chores) with the additional requirement that each agent has to receive a bundle of chores that is connected in the graph representing the relationship between items.

We have demonstrated that the chore division problems and their corresponding "dual" fair division problems do not necessarily have solutions that directly translate from one context to another, moreover, the computational complexity of the corresponding problems can differ.

We proposed polynomial algorithms for some existence problems and showed that other problems are NP-complete. Moreover, our construction for paths even leads to multiplicative inapproximability results.

Notice that Suksompong (2017) considered fair allocations on paths with contiguous bundles that are approximately fair up to an additive factor. It is easy to see that his constructions could be, with very minor modifications, applied also in the chore-division problem. However, we do not know how to construct additively approximately fair valid allocations for the other simple graph, the star.

Other natural open questions can be thought of. Is there any graph structure that could separate the polynomial problems from the intractable ones for various fairness criteria? When no valid fair allocation exists, one can think of some relaxations of the connectivity constraints. One could for example ask that the share of each agent should consist of not more than k disconnected pieces or that each diameter should be bounded.

Further, we have omitted the recently introduced fairness criteria maximin share guarantee and envy-freeness up to one good. We believe that they may lead to some more interesting results.

N

  = {1, 2, . . . , n} is the set of agents, G = (V, E) is an undirected graph. Vertices V represent objects, and they are interpreted as nondisposable chores. Each agent i ∈ N has a non-negative disutility (cost, regret) function u i : V → R + . The n-tuple of disutility functions is denoted by U . Let m denote the number of vertices of G (chores).

Figure 2 :

 2 Figure 2: All the thin arcs have capacity equal 1. Capacity of thick arcs is shown next to them. The condition for dotted arcs to be included is shown next to them.

Table 3 :

 3 The CCD (left) and CFD (right) instances for envy-freeness.

For typographical reasons, the disutilities of agents in this and the following example are not normalized to 1, but to 10 in the CCD instances (tables in the left) and to 30 in the corresponding dual CFG instances (tables in the right).

Powered by TCPDF (www.tcpdf.org)

Acknowledgements

This work has been supported by the bilateral Slovak-French project APVV SK-FR-2017-0022.

• (z 2 j , z 1 j+1 ) for j = 1, 2, . . . , s -1. The set of agents in I is N = B ∪ P ∪ Q ∪ R, where B = ∪ s j=1 {b 1 j , b 2 j , b1 j , b2 j } are literal agents, P = {p 1 , . . . , p s }, Q = {q 1 , . . . , q s } are variable agents and R = {r 1 , . . . , c c(5s+t)-6s+1 } are dummy agents (observe that c(5s + t) -6s + 1 > 0 for any c ≥ 1). So the total number of agents in I is n = c(5s + t) + 1.

Let us remark that each literal ℓ ∈ L from formula F has in I its 'corresponding' chore in Z and agent in B; they will be denoted by z(ℓ) and b(ℓ), respectively.

For each agent a ∈ N her disutility is 0 for some specific chores and the total disutility of 1 for agent a is distributed uniformly among the remaining chores, to achieve normalization. In more details:

If a = p j ∈ P then:

otherwise and for each agent a ∈ R we have u a (v) = 1/(5s + t) for each v ∈ V .

Lemma 4.1. If formula F is satisfiable then I admits a valid allocation π such that u a (π(a)) = 0 for each agent a ∈ N . If F is not satisfiable then for any valid allocation π there exists an agent whose bundle has disutility greater than c/n.

Proof. Assume first that f is a truth assignment of F that satisfies all clauses in C. We construct from f a valid assignment of chores in I as follows. Assign each d j to q j . For each variable x j assign agent p j the bundle {z 1 j , z 2 j } and the agents b1 j , b2 j objects z1 j and z2 j , respectively if x j is true and assign agent p j the bundle {z 1 j , z2 j } and the agents b 1 j , b 2 j chores z 1 j and z 2 j , respectively if x j is false. Finally, choose the first true literal ℓ in each clause c i ∈ C and assign the corresponding literal agent b(ℓ) chore y i . Each agent in R is assigned an empty bundle. It is easy to see that each agent receives a bundle whose disutility is 0, everybody receives a connected piece (if any) and that all chores are assigned.

Conversely, suppose that there is a valid assignment π of chores in I such that everybody receives a bundle with disutility at most c/n. As any nonzero disutility is at least 1/(5s+t) > c/n this implies that each agent's bundle is either empty of has disutility 0. We now construct a truth assignment f for F as follows. Note first that chore d j must be assigned to agent q j . Further, for each i, chore y i must be assigned to some agent b(ℓ) ∈ B that corresponds to a literal ℓ contained in clause c i . Now suppose that for some j, agents b k j as well as bk ′ j , for k, k ′ ∈ {1, 2} are assigned some clause chores. This means that chores z k j as well as zk ′ j must both be assigned to agent p j , but as chore d j is assigned to agent q j in any such assignment, agent p j gets a disconnected piece, which is a contradiction. Hence, set variable x j to be true if bundle {z 1 j , z 2 j } is assigned to agent p j in π and set x j to be false if bundle {z 1 j , z2 j } is assigned to agent p j . It is easy to see that this definition of truth values is consistent and makes formula F true.

Proof. The reduction is from (2,2)-E3-SAT. A boolean formula F has the set of variables X = {x 1 , . . . , x s } and the set of clauses C = {c 1 , . . . , c t }. By L we denote the set of literals, i.e. L = s j=1 {x 1 j , x 2 j , x1 j , x2 j } and c(ℓ) for ℓ ∈ L denote the clause that contains literal ℓ. Let L i denote the subset of literals appearing in clause c i .

We construct an instance of ADD-EF-CCD with m = 7s + 2 chores and n = 2s + t + 2 agents defined as follows. The set of chores is V = Y ∪ Z ∪ {c, d}, where c denotes the center of the star G, Y = s i=1 {y i , ȳi , ỹi } are variable chores and Z = s j=1 {z 1 j , z 2 j , z1 j , z2 j } are literal chores. Observe that each literal ℓ ∈ L has its corresponding chore which will be denoted z(ℓ).

The set of agents is N = B ∪ P ∪ Q ∪ {e, r}, where B = {b 1 , . . . , b t } are clause agents and P = {p 1 , . . . , p s }, Q = {q 1 , . . . , q s } are variable agents.

The utility functions are defined as follows.

If a = b i ∈ B is a clause agent then:

otherwise.

If a = p i ∈ P then:

where ε is such that ε < (1ε)/(7s -3).

If a = q i ∈ Q then:

otherwise.

If a = e then:

u e (v) = 1/(s + 1) if v = d or v = ỹi for some j ∈ {1, . . . , s} 0 otherwise.

If a = r then:

Assume first that f is a truth assignment that satisfies all clauses in C. We construct from f a valid assignment of chores as follows. For each variable x i , if x i is true, assign ỹi and ȳi to p i and q i respectively, and if x i is false, assign y i and ỹi to p i and q i . Furthermore, for each clause c i pick literal ℓ ∈ L i which is true and assign z(ℓ) to b i . Finally, assign d to r, and the remaining chores to e. It is easy to check that this allocation is envy-free.

Conversely, suppose that there is a valid assignment π of chores such that no agent envies another one. Only the central agent can receive strictly more than one chore, and, as a consequence, this central agent must receive at least 5st + 1 chores (otherwise some chores will be left unassigned). Suppose that the central agent is not e. Then this agent will receive at least two chores with the highest disutility, and hence will envy any other agent receiving just one chore. Therefore, only e can be the central agent.

Suppose that e receives a non-zero disutility. Then she will envy any other agent receiving either one chore other than d or one ỹi or no chore at all. It thus means that d and each chore ỹi must be assigned to some other agents.

Since ỹi provides a non-zero disutility to every agent, no agent can receive an empty bundle; otherwise each agent that receives chore ỹi will be envious.

The equitability criterion also leads to an NP-complete problem.

Theorem 5.7. ADD-EQ-CCD is NP-complete if G is a star.

Proof. We shall provide a polynomial reduction from the following version of the NP-complete problem PARTITION [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NPcompleteness[END_REF]; symbol [p] denotes the set {1, 2, . . . , p}.

Let us construct an instance I of ADD-EQ-CCD as follows. The set of chores is V = {c, d} ∪ V ′ , where V ′ = {v i , w i ; i ∈ [p]}. Chore c is the center of the star, the other chores are its leaves. The set of agents is N = {j 0 , j p+1 } ∪ N ′ , where N ′ = {j i ; i ∈ [p]}. The disutilities of agents are as follows and it can be easily checked that they are all normalized.

Now suppose that (P, P ′ ) is a partition witnessing that J is a yes instance; let us define a valid assignment in the following way. π(j

It is easy to see that π is a valid assignment and for each agent the disutility of her piece is 1/3.

Conversely, suppose that I admits a valid equitable assignment such that each agent gets the same disutility equal to η. First, let us realize that η = 0, as the agent who receives the central vertex c has a positive disutility. Further, η cannot be greater than 1/3. Namely, as exactly one agent can be assigned the central vertex c (and hence more than one chore), we would not be able to give to each agent in N ′ a piece with disutility greater than 1/3. This also immediately implies that the only agent who can receive chore c is agent j 0 and that η = 1/3. So agent j p+1 receives chore d and each agent in N ′ receives either chore v i or chore w i . This means that π(j 0 ) = {c}∪{v i ; i ∈ P }∪{w i ; i ∈ P ′ } where (P, P ′ ) is a partition of [p]; moreover, as disutility j 0 derived from π(j 0 ) is equal to 1/3, we must have