Let $\mathcal{S}_{mn}\subset\mathbb{R}^{m\times n}$ be the set of stochastic matrices, i.e., those matrices whose entries are in $[0,1]$ and whose rows sum up to $1$.
Let $A\in \mathcal{S}_{mn}$ be given.
(i) Does the minimization problem
$$ \min_{X\in \mathcal{S}_{nm}} \operatorname{trace}(AX)\\ \text{s.t. the diagonal of } AX \text{ is constant} $$
have an explicit solution or an obvious (more obvious than, say, the simplex algorithm) way to arrive at one (or almost at one)? If not, are there any other qualitative insights into this problem?
(ii) Let $\tilde{A}$ be a stochastic matrix that differs from $A$ in the $i$th row only. Do we have $$ (AX)_{ii}\leq (A\tilde{X})_{ii} $$ for all minimizers $X$ of the problem for $A$ and minimizers $\tilde{X}$ of the problem for $A$? Note that this is not trivial, since the diagonal of $A\tilde{X}$ may not be constant, thus $\tilde{X}$ may not be in the feasible set for the problem for $A$. This question is essential to the practical interpretation of the problem, see below!
Interpretation
Assume $m$ siblings have to complete $n$ chores and each sibling has their own opinion on how difficult each chore is.
A distributes of chores among the siblings amounts to a matrix $X=(x_{ij})\in\mathbb{R}^{n\times m}$ that specifies for each chore $i\in\{1,\dots,n\}$ the fraction of the chore's workload that is done by sibling $j\in\{1,\dots,m\}$. Obviously, each $x_{ij}$ must be in $[0,1]$ (one cannot do less than nothing and more than the full chore) and each row must sum up to 1 (each chore must be completed); hence, $X$ is a stochastic matrix.
Finding a fair distribution of chores requires each sibling to first specify how much effort each chore means to him. To do this, each sibling chooses an effort vector $a_{i,\cdot}\in \mathbb{R}^{+}$ that is normalized to sum up to $1$. The matrix $A=(a_{i,j})$ is then also a stochastic matrix. For any $X\in\mathcal{S}_{nm}$, the $i$th diagonal entry of $AX$ now represents how much of the total work is done by sibling $i$, according to his own opinion. Forcing the diagonal to be constant thus means that no one feels discriminated against, and minimizing the trace (which is simply $m$ times the constant diagonal value) amounts to maximizing the overall family happiness.
Question 2) asks whether a sibling can profit from lying about his effort vector. Indeed, if the stated inequality is true, the work required by a given sibling will only increase if that sibling provides an effort vector $\tilde{a}_i$ differing from his true effort vector $a_i$. Intuitively, the stated inequality should be true since the problem is set up to give each chore to the sibling least affected by it (see 3. below)
Preliminary results
- A solution exists and the minimum is at most 1:
To prove this, it suffices to show that the feasible set is non-empty, since obviously it is compact. A feasible matrix is given by the constant matrix whose entries are $1/m$, which achieves $\operatorname{trace}(AX) = 1$. This solution amounts to equal distribution of each chore among all $m$ siblings.
- The above solution is optimal if $A$ has rank $1$:
In this case, let $a$ be the unique row vector of $A$. For an arbitrary stochastic matrix $X$ we then have $\operatorname{trace}(AX)=(aX)\mathbf{1}=a(X\mathbf{1}) = a\mathbf{1} = 1$.
- It is not always optimal
Assume Alice and Bob, have to do the dishes and mow the lawn. Alice likes to be outside in the sun, whereas Bob likes to be inside and watch TV. Their effort matrix is thus the identity, and feasible solutions are those where Alice does as much of the dishes (in percent) as Bob mows the lawn. Among those feasible solutions, the one where Alice mows all the lawn and Bob does all the dishes is clearly optimal and has $\operatorname{trace}(AX) = 0$.
- Optimal solutions may not be unique
If $m=n$ and $A$ is constant, then $X$ constant and $X$ equal to the identity both achieve the minimum $1$. (The second solution amounts to splitting the set of chores instead of sharing each chore).
Summary
The fraction of work done by each sibling (each judging their own efforts) does not have to be larger than $1/m$, which it would be if each chore was shared equally (1.). However, by solving the minimization problem, one can achieve that each sibling does less work than $1/m$ (3.)! This is only possible if the siblings have different preferences (2.), because then each can do what the others don't like.
The last sentence could be taken as a starting point of a heuristic algorithm, where each sibling is assigned his most favorite chores until all chores are completed, but I wasn't able to turn this into an algorithm that actually finds a feasible solution, let alone a provably optimal one.