d4-conf-aaai-2010-0416 (d4-conf-aaai-2010-0416)

Given alternatives \(A\), a finite set \(T\) of rational normalized utility types \(u_t\), and a society distribution \(\mu\) over \(T\), apply the mass analogue of Theorem 4's embedding, \(p_t(x)=u_t(x)\). Characterize its Plurality winners and distortion against \(W_\mu(x)=\sum_{t\in T}\mu_t u_t(x)\) over all such societies.

Let \(A\) be a nonempty set of \(m\) alternatives. A utility type is a vector \(u_t\in\mathbb{Q}_{\geq0}^{A}\) with \(\sum_{x\in A}u_t(x)=1\); zero utilities and ties are allowed.
A society is given by its support: the list of the \(\tau\) distinct types with positive masses \(\mu_t\in\mathbb{Q}_{>0}\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
The mass embedding splits each type's mass among alternatives in proportions \(p_t(x)=u_t(x)\). Its Plurality score is \(S_\mu(x)=\sum_t\mu_t p_t(x)\), and its winner set is \(V_\mu=\operatorname{argmax}_{x\in A}S_\mu(x)\).
Define welfare \(W_\mu(x)=\sum_t\mu_tu_t(x)\) and distortion \(d(\mu)=\frac{\max_{y\in A}W_\mu(y)}{\min_{x\in V_\mu}W_\mu(x)}\), taking a positive numerator divided by zero as \(+\infty\). Let \(D(m)=\sup_\mu d(\mu)\), over all such finite-support rational societies.

What is the sharp worst-case distortion \(D(m)\) of this mass embedding, and how can its Plurality winner set be characterized for every society?

For independent discrete votes with probabilities equal to normalized utilities and \(n\geq m\), distortion is \(O(m^{2m/n})\) and \(O(\sqrt m)\); for \(n\geq3\) and \(\varepsilon=4\sqrt{m\ln n/n}<1\), it is at most \(1/(1-\varepsilon)\). [Caragiannis–Procaccia](https://econcs.seas.harvard.edu/sites/g/files/omnuum6346/files/econcs/files/caragiannis10.pdf).
No result settling the exact mass-splitting model above was identified in the literature search.

Exact distortion and winner characterization

For every positive integer \(m\), the sharp worst-case distortion is \(D(m)=1\). For every society, the Plurality winner set is exactly the set of welfare-maximizing alternatives, including all ties.

The decisive feature of the stated model is that the mass allocated to an alternative equals its utility contribution. Thus the full mass-splitting model can be settled directly.

Proof

Fix any admissible society. For every alternative \(x\in A\), the definition \(p_t(x)=u_t(x)\) gives
\[ S_\mu(x)=\sum_{t=1}^{\tau}\mu_t p_t(x) =\sum_{t=1}^{\tau}\mu_t u_t(x) =W_\mu(x). \]
Consequently,
\[ V_\mu=\operatorname{argmax}_{x\in A}W_\mu(x). \]
In particular, two alternatives tie for the highest Plurality score precisely when both attain the highest welfare.

To verify that the distortion denominator is positive, sum welfare over all alternatives:
\[ \sum_{x\in A}W_\mu(x) =\sum_{t=1}^{\tau}\mu_t\sum_{x\in A}u_t(x) =\sum_{t=1}^{\tau}\mu_t =1. \]
All welfare values are nonnegative. Since \(A\) contains \(m\) alternatives, its maximum welfare \(M_\mu\) therefore satisfies \(M_\mu\geq 1/m>0\). The finite, nonempty set \(A\) has a welfare maximizer, so \(V_\mu\) is nonempty. Every member of \(V_\mu\) has welfare \(M_\mu\). Hence
\[ d(\mu)=\frac{M_\mu}{\min_{x\in V_\mu}W_\mu(x)} =\frac{M_\mu}{M_\mu} =1. \]

This holds for every admissible society. The class of such societies is nonempty for every \(m\): take one type of mass \(1\), with utility \(1/m\) at every alternative. Thus the supremum is \(D(m)=1\), and it is attained.

Computing the complete winner set

Compute the \(m\) weighted sums \(W_\mu(x)\), find their maximum, and return every alternative attaining it. This uses \(O(m\tau)\) exact rational arithmetic operations.

An explicit implementation has bit complexity \(O(m\tau L^2)\) using schoolbook integer arithmetic. To justify this bound, write the input rationals as \(\mu_t=a_t/q_t\) and \(u_t(x)=b_{t,x}/r_{t,x}\), with positive denominators, and form
\[ Q=\left(\prod_{t=1}^{\tau}q_t\right) \left(\prod_{t=1}^{\tau}\prod_{x\in A}r_{t,x}\right). \]
The binary length of \(Q\) is \(O(L)\), because the sum of the input denominators’ binary lengths is at most \(L\). For each alternative, compute the integer
\[ N_x=\sum_{t=1}^{\tau}a_t b_{t,x}\frac{Q}{q_t r_{t,x}}. \]
Each division is exact, and \(W_\mu(x)=N_x/Q\). Nonnegativity and \(W_\mu(x)\leq1\) imply that every partial sum lies between \(0\) and \(Q\). Thus all integers involved have \(O(L)\) bits. There are \(O(m\tau)\) multiplications, divisions, additions, and comparisons, each costing at most \(O(L^2)\). Comparing the \(N_x\) values returns all winners exactly.

This computation uses only the \(\tau\) listed support types.

Relation to discrete voting

Independent discrete votes produce random realized scores. Here the entire mass is split according to the probabilities, making the score equal to welfare exactly. Consequently, sampling bounds involving a voter count \(n\) are unnecessary for this model.

⟨structured verdict parsed — rendered above⟩

The output fully resolves the task. The distortion proof and the polynomial running-time bound are correct; no mathematical gaps were found.

• Scores equal welfare. Substituting the stipulated identity \(p_t(x)=u_t(x)\) gives \(S_\mu(x)=W_\mu(x)\) for every alternative. The sums use precisely the \(\tau\) listed support types. No additional assumption is needed.

• Complete winner characterization. Equality of the score and welfare functions implies

\[ V_\mu=\operatorname{argmax}_{x\in A}W_\mu(x). \]
This includes every maximizing tie and excludes every alternative with smaller welfare. Zero utilities cause no difficulty.

• Positive distortion denominator. The normalization calculation \(\sum_{x\in A}W_\mu(x)=1\) is valid: all sums are finite, every utility vector sums to one, and the masses sum to one. Nonnegativity therefore implies \(M_\mu\geq1/m>0\). Finiteness and nonemptiness of \(A\) guarantee a maximizer. Every winner has welfare \(M_\mu\), so the denominator is exactly \(M_\mu\), and \(d(\mu)=1\). The convention concerning division by zero is never invoked.

• Sharpness and all allowed sizes. The argument holds for every admissible society and every positive integer \(m\), including \(m=1\). The proposed single-type uniform society has rational normalized utilities and positive mass one, so it establishes that the class of societies is nonempty. Consequently, \(D(m)=1\), with attainment.

• Arithmetic operation count. Computing all weighted sums requires \(O(m\tau)\) exact rational arithmetic operations. Finding the maximum and collecting all ties requires \(O(m)\) comparisons, already included because \(\tau\geq1\).

• Bit complexity. The common denominator \(Q\) has \(O(L)\) bits because its bit length is bounded by the sum of the input denominators’ bit lengths. Each \(q_t r_{t,x}\) divides \(Q\): its two factors occur in the defining product, even when their numerical values coincide. Hence every displayed division is exact, and \(N_x/Q=W_\mu(x)\).

The partial-sum bound is justified by nonnegative summands and \(W_\mu(x)\leq1\). Input numerators, denominator products, quotients, and multiplication intermediates also have \(O(L)\) bits. Constructing \(Q\) takes \(O(m\tau)\) multiplications; computing and comparing the numerators takes \(O(m\tau)\) further operations. Schoolbook arithmetic therefore supports the stated bound \(O(m\tau L^2)\).

• Discrete-voting comparison. The distinction is accurate: sampled votes have random realized scores, whereas the specified mass embedding has scores identically equal to welfare. The proof does not depend on the quoted literature bounds or require verification of them.

Repair feedback: None required. No cited theorem is used, and all relevant hypotheses and edge cases are handled.

⟨structured verdict parsed — rendered above⟩