10
$\begingroup$

Given are a positive integer $n$ and positive real numbers $a_1,\dots,a_n,b_1,\dots,b_n$. A subset $S\subseteq N=\{1,\dots,n\}$ is called $a$-good if $$\sum_{i\in S}a_i\geq \frac{1}{2}\left(\sum_{i\in N\backslash S}a_i-\min_{i\in N\backslash S}a_i\right),$$ and $b$-good if $$\sum_{i\in S}b_i\geq 2\left(\sum_{i\in N\backslash S}b_i-\min_{i\in N\backslash S}b_i\right).$$ Are there always two disjoint subsets, one $a$-good and the other $b$-good?

If $a_i = b_i$ for all $i$, this is true by a greedy algorithm.

Improve this question
$\endgroup$
1
  • $\begingroup$ I wrote a program checking random sequences for small $n$ (at most $15$). It found no counterexamples, so I conjecture that the answer is affirmative. $\endgroup$ Commented Jul 28, 2020 at 6:04

1 Answer 1

Reset to default
4
+50
$\begingroup$

An affirmative answer to your question would follow from a famous conjecture about envy-free allocations. It is also known that if you replace the '2' in $b$-goodness with '$\frac 12$', then it is true.

A good paper to read (first) on the topic is Almost Envy-Freeness with General Valuations.
An allocation of some items among some players is envy-free up to any good (EFX) if no player i would envy any other player j IF an arbitrary item of j was to be removed. (Note that players can value different items differently, but let's suppose that their valuation function is additive.)
The conjecture is that an EFX allocation always exists.

This would imply a positive answer to your question as follows.
Let player A evaluate $n$ items as $(a_i)$, while players B and B' as $(b_i)$.
Take an EFX allocation among these 3 players, then merge B and B'.
An easy calculation shows that the conditions of your question will be satisfied.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.