we-solve (beta)

Econ-452 · economics · Economics

Fair chores with unequal time requirements

LLM status Partially solved unverified

Statement

Original subject group: Economic theory, equilibrium and social choice

Audit classification: Published research agenda. Dagstuhl §4.1 explicitly asks for suitable envy definitions with agent-dependent chore times. The displayed approximation requirement is editorial, not the paper’s adopted notion.

Definitions and precise research target

Model and research target. Let $N=\{1,\ldots,n\}$ be agents and $C$ a finite set of indivisible chores. Agent $i$ has additive nonnegative disutility $d_i$, person-dependent processing times $t_{ic}>0$, and time budget $B_i>0$. A complete assignment $A=(A_i)_{i\in N}$ partitions $C$ and is feasible when $\sum_{c\in A_i}t_{ic}\leq B_i$ for every $i$. Restrict inputs to those admitting some feasible complete assignment. For comparison, define a proposed budget-aware envy factor $\alpha\geq1$: whenever $i\ne j$ and $A_j$ would fit agent $i$'s budget, require either $A_i=\varnothing$, or some $c\in A_i$ satisfying \[ d_i(A_i\setminus\{c\})\leq\alpha d_i(A_j). \] Determine the smallest factor guaranteed over a specified domain of processing times, budgets, and disutilities, and characterize when the factor-one requirement is compatible with feasible completeness. Produce tight counterexamples when budgets prevent any finite guarantee, and identify minimally restrictive conditions restoring useful bounds. Evaluate whether the comparison above has an adequate welfare interpretation when agent-specific processing times differ, or propose and axiomatize a more appropriate comparison.

Definitions and maintained assumptions (editorial unless a source definition is named). For each $S\subseteq C$, set $d_i(S)=\sum_{c\in S}d_i(c)$ with $d_i(c)\ge0$, and $t_i(S)=\sum_{c\in S}t_{ic}$. Feasibility is $t_i(A_i)\le B_i$ for every assigned agent. The proposed budget-aware EF1 condition compares $i$ with $j$ only when $t_i(A_j)\le B_i$, and deletes a chore from $i$'s own bundle; deleting from the other bundle would be the goods convention and is inappropriate for chores. Define $\alpha(A)=\inf\{\alpha\ge1:A\text{ satisfies every such inequality}\}$, with $+\infty$ if none does. For an explicitly restricted instance class $\mathcal D$, its guarantee is $\sup_{I\in\mathcal D}\inf_{A\text{ complete feasible}}\alpha(A)$. Zero comparison disutility can make this infinite; positive processing times do not imply positive disutility. The research task is an axiomatized economically appropriate comparison and its domain-specific guarantee, not an unqualified universal factor.

Variants and assumption changes

  1. Common times (editorial benchmark). Impose $t_{ic}=t_c$ and equal budgets. Determine the feasibility--EF1 frontier for additive disutilities, specifying whether chores can be discarded or all must be assigned.
  2. Heterogeneous times (source agenda, editorial criterion). Impose a bounded ratio $t_{ic}/t_{jc}\le R$, positive disutilities and a stated workload-slack condition. Seek finite approximation guarantees, then test whether feasible-subset comparisons are normatively preferable to comparisons of full bundles.

References and source audit

  1. Dagstuhl §4.1. Supports the stated research area; exact displayed specification is editorial. https://drops.dagstuhl.de/storage/04dagstuhl-reports/volume14/issue09/24401/html/DagRep.14.9.145/DagRep.14.9.145.html
  1. Edith Elkind. 2024. Fair Division of Chores with Budget Constraints, in Fair Division: Algorithms, Solution Concepts, and Applications. Seminar report §4.1. https://drops.dagstuhl.de/storage/04dagstuhl-reports/volume14/issue09/24401/html/DagRep.14.9.145/DagRep.14.9.145.html. DOI: https://doi.org/10.4230/DagRep.14.9.145.

Common conventions: Source mathematical conventions

These conventions apply to each entry unless explicitly replaced.

Models and identification. A primitive model $m$ specifies all probability laws, feasible choices, information, equilibrium and measurement rules used by its target. The admissible class $\mathcal M$ is fixed independently of outcomes. If $P_O(m)$ is its observable probability law and $\tau(m)$ the target, its identified set at observable law $P$ is \[ \mathcal I_\tau(P)=\{\tau(m):m\in\mathcal M,\ P_O(m)=P\}. \] Point identification means that this set is a singleton. An empty set signals incompatibility of data and assumptions. Coordinate bounds need not describe the joint set. Bounds are sharp only if every retained target is attainable or arbitrarily approachable by compatible models. Finite bounds require explicit restrictions on unobserved quantities; unrestricted confounding, hidden wealth, extrapolation or arbitrary equilibrium selection can yield uninformative sets.

Causal interventions. A potential outcome $Y_i(p)$ is the outcome under a complete policy regime $p$, including timing, financing, information and market spillovers. The target population and units are fixed before treatment. With interference, use the complete assignment vector or a justified exposure mapping; individual no-interference notation alone cannot identify an economy-wide intervention. A difference of mean potential outcomes does not require the cross-world joint distribution. Conditioning on post-treatment migration, survival, enrollment or employment changes the estimand and needs separate justification.

Statistical statements. An estimator, confidence set, forecast or test specifies a sampling law, model class and loss/coverage criterion. Uniform $(1-\alpha)$-coverage means $\inf_{m\in\mathcal M}\Pr_m\{\tau(m)\in C_n\}\geq1-\alpha$, or an explicitly asymptotic version. The whole parameter space trivially has coverage, so informativeness requires a stated width, risk or power objective. A forecasting improvement is relative to a named benchmark, information set and evaluation population.

Equilibrium and optimization. An equilibrium comprises feasible plans, optimality, beliefs where needed, budget constraints and all market/resource clearing. The primitives or a stated benchmark define each correspondence $\mathcal E(p;m)$. Nonemptiness is assumed or proved, never inferred just from compact policy sets. A selected-equilibrium target uses a declared selection rule; a robust target quantifies over all permitted equilibria. Use suprema or infima unless attainment is established. An $\varepsilon$-optimal policy is feasible and within $\varepsilon$ of the finite optimum value. Report an empty feasible set separately.

Welfare and accounting. Normative utility, interpersonal normalization, social weights, numeraire, discounting and the use of public receipts are primitives. Behavioral utility need not coincide with the welfare criterion. Household welfare includes ownership income and rents once; adding profits again to compensating variation generally double-counts them. A monetary equivalent is defined by an explicit transfer and price convention, with monotonicity and range conditions. Average effects, mechanism contributions, transfers and welfare losses are different targets. Infinite sums require convergence and dynamic feasible plans require terminal or no-Ponzi conditions.

Source versions. A working-paper date, revision date and journal publication year are distinguished. A DOI for a journal version is not automatically the DOI of an earlier manuscript. Locators refer to the stated version and printed pages where specified. A metadata-only check does not verify a claim about a full-text conclusion. Every entry's source subsection narrows the provenance claim accordingly.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-452-A1 · Partial result · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-452

An unbounded-factor obstruction and an equal-duration EF1 theorem

Status: Partial; the full catalogue problem remains unresolved.

Abstract

The proposed budget-aware envy condition has no finite universal approximation factor even with common processing times, equal budgets, strictly positive identical disutilities, and substantial feasible workload slack. A three-chore construction proves this sharply. Equal-duration chores restore factor one through a feasible round-robin allocation. An exact finite-instance formula and a normatively different feasible-subset comparison clarify what remains to be classified.

The exact fairness requirement

For each agent $i$, let $A_i$ be its allocated bundle, with additive nonnegative disutility $d_i$ and processing time $t_i$. A complete allocation is feasible if $t_i(A_i)\le B_i$ for every agent. The proposed requirement compares $i$ with $j$ whenever $t_i(A_j)\le B_i$. Unless $A_i$ is empty, it asks for a chore $c\in A_i$ such that \[ d_i(A_i\setminus\{c\})\le\alpha d_i(A_j), \qquad \alpha\ge1. \tag{1} \] Deletion is from the potentially envious agent's own bundle, as appropriate for chores. It is not deletion from the comparison bundle.

The catalogue asks for domain-specific guarantees rather than an unsupported universal factor. Here the first result rules out several natural candidate domains, including one with no agent-dependent times at all. The second supplies a positive theorem for a genuinely narrower duration class.

Three chores are enough for an obstruction

There are two agents, both with budget one, and three chores $a,b,c$. Processing times are common: \[ t_a=t_b=0.4,\qquad t_c=0.7. \] Both agents have identical disutilities \[ d(a)=d(b)=1,\qquad d(c)=\varepsilon, \tag{2} \] where $0<\varepsilon\le1$.

Theorem: Every complete feasible allocation of this instance has \[ \alpha(A)=\frac1{\varepsilon}. \tag{3} \] For $\varepsilon=0$, every complete feasible allocation has infinite factor. Consequently there is no finite uniform guarantee even for equal budgets, common times, and strictly positive identical disutilities.
Proof: Chore $c$ cannot share an agent with $a$ or $b$, since either pair takes $1.1>1$ time. Therefore completeness with two agents forces the bundles $\{a,b\}$ and $\{c\}$, up to exchanging the agents. Both bundles are feasible and both fit either agent's budget.

The agent receiving $\{a,b\}$ has residual disutility one after either possible deletion. Its comparison bundle has disutility $\varepsilon$. Hence (1) requires $1\le\alpha\varepsilon$, or $\alpha\ge1/\varepsilon$. For that value its inequality holds. The agent receiving the singleton can delete that chore and has residual zero, so its inequality holds for every $\alpha\ge1$. This proves (3). At $\varepsilon=0$, the first inequality reads $1\le0$ for every finite factor, proving infinity. Taking positive $\varepsilon$ arbitrarily small proves unboundedness without zero disutilities. ∎

The forced allocation has workloads $0.8$ and $0.7$, so it leaves at least twenty percent of every budget unused. Bounded time ratios across agents do not help: their ratio is exactly one. Nor does identical disutility protect against the obstruction. The difficulty is indivisible packing combined with very cheap comparison chores.

The failure is stronger than finding one unfair allocation. The proof enumerates all feasible complete allocations, so no different algorithm can repair the factor on these inputs.

A parameterized slack result

Fix any $\sigma\in[0,1/3)$ and replace the processing times by \[ t_a=t_b=\frac{1-\sigma}{2},\qquad t_c=1-\sigma, \tag{4} \] keeping equal budgets one and disutilities (2). The bundles $\{a,b\}$ and $\{c\}$ each use exactly $1-\sigma$ time. But $t_a+t_c=\tfrac32(1-\sigma)>1$, so they remain the only feasible complete partition.

Thus no finite uniform factor is restored merely by requiring the existence of a complete allocation with a common unused-budget fraction $\sigma<1/3$. The optimum factor is still $1/\varepsilon$. At $\sigma=1/3$, mixed pairs become feasible, so this specific proof stops. That observation is not a theorem that one-third slack suffices for every instance; it marks the precise boundary of this construction.

With $\sigma=0.2$ and $\varepsilon=0.01$, each agent can be assigned at most eighty percent of its budget, yet every feasible complete assignment requires factor $100$. This numerical check isolates why strictly positive disutilities alone do not supply a quantitative approximation bound.

Equal-duration chores admit factor one

A stronger packing restriction does restore the proposed guarantee. Suppose every chore takes the same common time $t>0$, every agent has the same budget $B$, and $b=\lfloor B/t\rfloor$. Complete feasibility is equivalent to $m\le nb$, where $m$ is the number of chores. Disutilities may be arbitrary additive nonnegative numbers and differ across agents.

Run round robin in a fixed order. On each turn an agent takes a remaining chore of minimum disutility according to its own valuation; stop when all chores are allocated.

Theorem: If $m\le nb$, round robin is complete, feasible, and satisfies (1) with $\alpha=1$ for every ordered pair of agents.
Proof: Every agent receives at most $\lceil m/n\rceil\le b$ chores, so feasibility holds. Fix distinct agents $i,j$. If $A_i$ is empty there is nothing to prove. Otherwise delete the last chore selected by $i$.

If $i$ precedes $j$ in the round order, compare each retained $k$th choice of $i$ with the $k$th choice of $j$. The latter existed and was still available when $i$ chose: round-robin bundle sizes differ by at most one, and deleting $i$'s last choice leaves enough choices of $j$. Minimum-disutility selection gives $d_i(i_k)\le d_i(j_k)$. Summing and using nonnegativity bounds $i$'s residual by $d_i(A_j)$.

If $i$ follows $j$, compare each retained $k$th choice of $i$ with the $(k+1)$st choice of $j$. The latter occurs later and was available on $i$'s turn. Since an earlier agent receives at least as many chores as a later agent, every retained choice has such a match. The same minimum and summation argument applies. In cases with no retained choices the residual is zero. Thus the inequality holds for every ordered pair. All assigned bundles fit every budget under the common-time/equal-budget assumptions, so these are precisely all comparisons required by (1). ∎

This is the standard additive-chores round-robin argument with an explicit feasibility check. The equal-duration condition removes the bin-packing obstruction in the preceding example. It does not show that small perturbations of durations preserve factor one, because a small perturbation can change which bundles fit near a capacity boundary.

An exact finite-instance diagnostic

For a nonempty bundle define $r_i(A_i)=d_i(A_i)-\max_{c\in A_i}d_i(c)$, and set $r_i(\varnothing)=0$. Deleting a maximum-disutility chore minimizes the residual, so \[ \alpha(A)=\max\left\{1,\ \max_{\substack{i\ne j\\t_i(A_j)\le B_i}} \frac{r_i(A_i)}{d_i(A_j)}\right\}, \tag{5} \] where $0/0$ is interpreted as zero and a positive numerator divided by zero as infinity. Formula (5) follows directly by taking the strongest pairwise inequality after the optimal deletion. It makes zero-comparison pathologies explicit.

For any finite input, enumerating all $n^m$ assignments, discarding infeasible ones, and minimizing (5) gives the exact optimum factor. This proves decidability and a finite certificate procedure; it is not an efficient algorithm for large inputs. Evaluating one proposed assignment only requires computing bundle times, cross-agent disutilities, and maximum own chore disutilities.

An alternative comparison might ask about feasible subsets of another agent's bundle, or normalize burden by an agent's capacity. Those define different notions. Comparing with all feasible subsets without excluding the empty subset would be especially severe: the empty set has zero disutility, so every agent with positive residual after one deletion would fail. A suitable axiom system must decide which subsets are economically meaningful, rather than assume subset comparisons automatically repair fairness.

What remains open

The negative construction completely settles the lack of a uniform factor in the stated common-time domain and in every larger class containing it. The equal-duration theorem supplies a positive subdomain. The broader catalogue task remains unresolved: it asks for minimally restrictive conditions across heterogeneous times, budgets, and disutilities, as well as an economically justified envy notion. No such full classification or axiomatization is claimed here.

The source poses the time-dependent chores agenda. Its fairness definition is not silently replaced by the editorial inequality analyzed above; the exact guarantee proved here concerns (1).

Completion Estimate

75%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt proves an unbounded-factor obstruction even with common times and workload slack, and restores factor-one feasibility for equal-duration chores by round robin. Minimally restrictive heterogeneous-time conditions, the full feasibility and fairness frontier, and an economically justified envy axiomatization remain unclassified.

References

Go to contribution →