Consider a multiset $S$ containing $n$ positive integers $\{s\_1, s\_2, \ldots, s\_n\}$. For the purpose of this question, assume that (some of) the integers are very large with respect to $n$, i.e. much larger than $2^n$ such that the number of bits to describe them is not polynomial in $n$. I am interested in whether we can reduce the size of the numbers in $S$ without changing the total ordering on the sums of subsets of $S$, or more formally:


Given such a multiset $S$, does there exist a function $f : S \rightarrow \mathbb{N}$ such that for all subsets $S', S'' \subseteq S$ it holds that $\sum \_{x \in S'} x \leq \sum\_{x \in S''} x$ if and only if $\sum \_{x \in S'} f(x) \leq \sum\_{x \in S''} f(x)$, and such that the number of bits needed to represent the numbers $f(s\_i)$ is polynomial in $n$?


If such a function $f$ exists for all multisets $S$, can we compute $f$ in time polynomial in the bitrepresentation of $S$?


It is not hard to verify that if we take $S$ to be the sequence $2^0, 2^1, 2^2, \ldots, 2^n$ then we cannot shrink these numbers any further: the smallest possible number we may assign is 1, so $f(2^0) \geq 1$. Then $f(2^1)$ needs to be strictly greater than $f(2^0)$, so $f(2^1) > f(2^0) \geq 1$ hence $f(2^1) \geq 2$. Now $f(2^3)$ must be strictly greater than $f(2^0) + f(2^1)$ so $f(2^3) > 1 + 2$ so $f(2^3) \geq 4$; and so on, and so on.


Thanks in advance for any insights. Since I am new to this area, it would also be nice to get some pointers to the literature, if related questions have been studied.



Decreasing the size of integers in a multiset while maintaining the total order on sums of subsets
Here is a much expanded answer. the old answer is below.


There are some very interesting questions here. What I say here is far from answering them completely but does go a certain distance. The sequence [A009997](http://oeis.org/A009997) in the OEIS and its references turns out to be very relevant. I suggest looking for books and articles about **Threshold Logic** (perhaps a hotter topic before 1980 than after). My remarks grow from a paper of mine *Maximal Intersecting Families* European Journal of Combinatorics Volume 16, Issue 5, September 1995, Pages 491-501. 


Indulge me in some terminology first (skip to the next paragraph if you wish) : A **voting scheme** consists of a set $S$ of $n$ elements (voters) and a way to decide for each partition $S=A \cup B$ into disjoint sets (coalitions) which of $A$ or $B$ wins. (If $A$ wins then each set containing $A$ should also win). To specify this it is enough to know the minimal winning coalitions, those $A$ which beat their complement, but fail to do so if any one voter changes sides (these form an *intersecting antichain*.) One way to specify a voting scheme is to assign each voter an integer weight with the total weight odd and taking weighted majority rules. Up to 5 voters, every voting scheme is of this type (for $n \ge 6$ only some are). Before I go on let me say that the question here is more structured, I might say that it concerns voting systems where some voters can abstain (just not every last voter) and if the remaining voters form two coalitions one must be the winner (As asked, one could perhaps have ties between sets but I think that small pertubations would only make it harder without changing the existing orders.) With 5 voters and no abstentions there are 5 weight functions: 10000 (dictator) 31111 (near dictator) 21110 32211 22111 and 11111(pure democracy). For 6 voters there are 30 voting schemes (up to isomorphism) of which 21 can be obtained by weights. The most complicated is 543221. There is a sense in which these are the optimal integer weight functions: The $2^n$ subsets can be identified with the corners of the standard cube of side 1 in $\mathbb{R}^n$. The corners corresponding to the winning coalitions in a voting scheme (or any other family of subsets) span a convex polytope of affine dimension $n$ or less. A voting scheme can be given by a weight function exactly if all but one of the supporting hyperplanes of this polytope are also supporting hyperplanes of the hypercube. Then the weight fuction can be given by the components of the appropriately scaled normal vector to that hyperplane. 


I will take the problem as this: suppose that we have a linear order on the power-set of a given $n$ element set which respects set containment and that some weight function gives that order, find an efficient weight function achieving this. Here are ad hoc results up to $n=5$ then thoughts on a method. 


In case $n=2$ use weights 21. For $n=3$ use either 421 or 432. for $n=4$ there are 3 voting schemes with weight functions 1000 1110 and 2111. This becomes 14 cases with abstentions allowed and the minimal weight functions are 7653, 8421, 8432, 8542, 8641, 8643, 8654, 8742, X432, X632, X742, X762, X843, X863 (here X stands for 10). Doing a massive number of random integer weight assignments for $n=5$ lead me to suspect (and later confirm from the OEIS) that there are 516 orders arising from weights. Finding the minimal weight assignments (just by looking at all cases of $0<e<d<c<b<a<32$ ) lead to these frequencies for the largest weight:


$$[13, 2], [14, 8], [15, 5], [16, 62], [17, 21], [18, 47], [19, 32], [20, 97]$$ $$ [22, 91], [23, 18], [24, 42], [25, 17], [26, 46], [28, 14], [30, 14]$$


The numbers 2,14,516 were enough to go to the OEIS and that lead to [Number of comparative probability orderings on all subsets of n elements that can arise by assigning a probability distribution to the individual elements.](http://oeis.org/A009997) Maybe the references there will help find out about the weight/probability distributions which leading to these orders. 


It seems that one might be able to do the following: First find the minimal winning coalitions as described above and find *the* integer weight function giving them, it determines a hyperplane. A parallel hyperplane contains maximal losing coalitions. Take the plane parallel to these and running through the center of the cube. Now we want to slightly tilt it but not so much that it strictly crosses any corner of the cube. To do this, look at the subsets of one (or more) of the minimal winning coalitions. We have a linear order on them and a smaller voting scheme, find a weight function which works there and use it to perturb the weights (say multiply all the old weights by some factor and add in the new weights.) There are a hyper-exponential number of (isomorphism types) of voting schemes so we can't list them all, let alone the linear orders. Still it might be easy to process any one (though saying this is less convincing than doing it.) Alternately, set aside the lightest (or heaviest as seems easier) element. Solve the problem for the other $n-1$ elements. Then adjust to give a weight to the missing element.




---


**old answer** You have a system of inequalities which you could solve by linear programing getting rational weights. Then you have the problem of efficiently scaling to integers. The information is highly redundant. Maybe something like this could work: Looking at the order on singleton sets you can find the lowest weight. Set it aside. Solve the problem for the other n-1 weights. Now try to assign an appropriate weight to the minimum .


Another idea and an interesting question in itself is this: assume for now that no set is equal in weight to its complement. Then the inclusion minimal sets with this property are pairwise intersecting but none contains any other. These are the minimal winning coalitions in some voting scheme. Find weights which do this.


