d4-conf-sagt-2021-0018 (d4-conf-sagt-2021-0018)

Given a finite type set \(T\), binary-rational masses \(\mu_t\) summing to \(1\), utilities \(u_{ts}\in[0,1]\), and \(\epsilon\in[3/4,1]\), compute a type-symmetric policy \(q\). Each type-\(t\) agent votes herself with probability \(q_{t,\bot}\); otherwise she selects type \(s\) with probability \(q_{ts}\), and a proxy is sampled from that type’s mass. Delegation continues until a self-voting guru is reached, with utility \(u_{ts}\) for a type-\(t\) agent whose guru has type \(s\), and zero if no guru is reached. Require every agent’s expected utility to be at least \(1-\epsilon\) times her best unilateral-deviation utility, and normalized welfare \(\sum_t\mu_t U_t(q)\) to be at least \(1-\epsilon\) times the supremum welfare over measurable delegation policies.

A society is an atomless probability space partitioned into a finite nonempty type set \(T\). It is given by its support: the \(\tau=|T|\) positive masses \(\mu_t\), encoded as binary rationals with \(\sum_t\mu_t=1\); \(\tau\) counts supported types, not possible types. Here \(m=\tau\) is the number of available proxy types, and \(L\) is the total input bit length.
Utilities \(u_{ts}\in[0,1]\) and \(\epsilon\in[3/4,1]\) are binary rationals. A type-symmetric policy has nonnegative rational entries satisfying \(q_{t,\bot}+\sum_{s\in T}q_{ts}=1\): \(\bot\) means voting oneself, while action \(s\) means delegating to an independently sampled agent from the normalized mass of type \(s\), including when \(s=t\).
Each agent independently samples her action and proxy once; delegation follows these choices until a self-voting guru is reached. Repeated types do not terminate delegation; a cycle or infinite chain without a guru gives zero utility. A type-\(t\) agent represented by a type-\(s\) guru receives \(u_{ts}\), including \(u_{tt}\) when voting herself.
Let \(U_t(q)\) be expected utility and \(B_t(q)\) the supremum utility obtainable by changing only one type-\(t\) agent's mixed action, holding everybody else's policy fixed. Such a deviation has zero mass and does not change the population policy; abstention is also allowed and gives zero.
Let \(\operatorname{OPT}\) be the supremum normalized expected welfare over all measurable agent-dependent mixed policies using the same type-selection and proxy-sampling mechanism; these policies need not be type-symmetric and may abstain.
The required policy satisfies \(U_t(q)\geq(1-\epsilon)B_t(q)\) for every \(t\), and \(\sum_t\mu_tU_t(q)\geq(1-\epsilon)\operatorname{OPT}\).

Can these simultaneous incentive and welfare approximation guarantees be obtained in time polynomial in \(m,\tau,L\), or is computing a policy with these guarantees NP-hard?

For finite-agent liquid democracy, a linear-time algorithm provides these same bicriteria guarantees for \(\epsilon\in[3/4,1]\). [Source](https://arxiv.org/pdf/2105.05142v2)
No result settling this precise atomless, type-symmetric approximation problem was located.

Polynomial-time construction

Both guarantees are achievable in polynomial time. In fact, a single rational policy gives both guarantees with factor \(1/4\), and therefore works for every \(\epsilon\in[3/4,1]\).

The construction specializes the self-voting and greedy-delegation scheme in [Theorem 14 of the cited paper](https://arxiv.org/html/2105.05142v2#S4.SS2). The argument below verifies it directly for the stated atomless model and its agent-dependent welfare benchmark.

1. Universal upper bounds

For each supported type \(t\), define its largest possible guru utility by

\(M_t:=\max_{s\in T}u_{ts}\).

This maximum exists because \(T\) is finite and nonempty.

Under any admissible policy or unilateral deviation, a type-\(t\) agent either reaches a guru of some type \(s\), receiving \(u_{ts}\leq M_t\), or receives zero through abstention, a cycle, or an infinite chain. Because utilities are nonnegative, her realized utility always lies in \([0,M_t]\).

Consequently, for every population policy \(q\),

\(B_t(q)\leq M_t\).

The same pointwise bound applies to every measurable agent-dependent policy allowed in the definition of \(\operatorname{OPT}\). Integrating over agents, whose type masses are \(\mu_t\), gives normalized expected welfare at most \(\sum_{t\in T}\mu_tM_t\). Taking the supremum over all such policies yields

\(\operatorname{OPT}\leq\sum_{t\in T}\mu_tM_t\).

Neither bound requires the supremum to be attained.

2. The algorithm

Fix an ordering of the supported types. For every \(t\), choose the first maximizer

\(s_t\in\operatorname{argmax}_{s\in T}u_{ts}\).

Output the type-symmetric policy specified by

\(q_{t,\bot}=\tfrac12,\qquad q_{t,s_t}=\tfrac12,\qquad q_{ts}=0\quad\text{for }s\neq s_t.\)

Thus every agent independently votes herself with probability \(1/2\); otherwise she delegates to an independently sampled agent of type \(s_t\).

All entries are nonnegative rationals and each row sums to one. When \(s_t=t\), the two actions remain distinct: voting oneself and sampling a proxy of one’s own type.

3. Utility lower bound in the atomless model

Fix a type-\(t\) agent \(i\). Let \(E_t\) be the event that:

• \(i\) chooses delegation to type \(s_t\);
• her sampled proxy chooses to vote herself.

Since \(\mu_{s_t}>0\), the normalized sampling distribution on type \(s_t\) is atomless. Hence the sampled proxy is distinct from \(i\) with probability one, including when \(s_t=t\).

Conditional on delegation and the sampled proxy’s identity, that proxy votes herself with probability \(1/2\), independently of \(i\)’s action. This uses exactly the stipulated independent sampling of agents’ actions; no action is resampled during delegation. Therefore

\(\Pr(E_t)=\tfrac12\cdot\tfrac12=\tfrac14.\)

On \(E_t\), the sampled proxy is a self-voting guru of type \(s_t\). Agent \(i\) therefore receives

\(u_{t,s_t}=M_t.\)

On the complementary event, her utility is nonnegative. It follows that

\(U_t(q)\geq\Pr(E_t)M_t=\tfrac14M_t.\)

This bound counts only chains terminating at the first proxy. It neither treats repeated types as termination nor assumes anything about longer chains.

4. Both required guarantees

The assumed range of \(\epsilon\) gives

\(0\leq1-\epsilon\leq\tfrac14.\)

For every type \(t\), the utility lower bound and deviation upper bound imply

\(U_t(q)\geq\tfrac14M_t\geq(1-\epsilon)M_t\geq(1-\epsilon)B_t(q).\)

For welfare, multiplying the utility lower bounds by the positive type masses and summing gives

\(\sum_{t\in T}\mu_tU_t(q)\geq\tfrac14\sum_{t\in T}\mu_tM_t\geq\tfrac14\operatorname{OPT}\geq(1-\epsilon)\operatorname{OPT}.\)

Thus the output satisfies both guarantees simultaneously, including the endpoints of the specified interval.

5. Bit complexity

Computing all maximizers requires \(O(\tau m)\) exact rational comparisons. Comparing two binary rationals can be done by cross-multiplying their numerators and positive denominators; the resulting integer lengths and arithmetic costs are polynomial in \(L\).

Here \(m=\tau\), so the algorithm uses \(O(\tau^2)\) comparisons. Writing the full policy requires \(O(\tau(m+1))\) entries, each equal to zero or \(1/2\). Its output length is polynomial, and its total running time is polynomial in \(m,\tau,L\).

Hence the specified policy-construction problem is polynomial-time solvable.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The construction satisfies both guarantees for every permitted input, and its running time and output length are polynomial. No major or minor mathematical issues were found.

• Universal utility bounds are valid.

Because \(T\) is finite and nonempty, \(M_t=\max_{s\in T}u_{ts}\) exists for every supported type \(t\). Every realized payoff is either a guru utility \(u_{ts}\) or zero. Thus it belongs to \([0,M_t]\).

This bound applies to every unilateral mixed deviation, including abstention. Taking expectations and then the supremum establishes \(B_t(q)\leq M_t\); attainment is unnecessary.

The same bound applies to every agent under every admissible agent-dependent policy. Integrating over the type masses and taking the supremum establishes
\[ \operatorname{OPT}\leq\sum_{t\in T}\mu_tM_t. \]
In particular, the argument correctly bounds the full agent-dependent benchmark, rather than only type-symmetric policies.

• The output policy is admissible.

Each selected \(s_t\) exists, and the fixed ordering makes the selection unambiguous. Each policy row has exactly two distinct actions with probability \(1/2\): self-voting and delegation to type \(s_t\). All remaining entries are zero.

The entries are rational, nonnegative, and sum to one. When \(s_t=t\), delegation to one’s own type remains distinct from self-voting, as required by the task.

• The first-proxy event has the claimed probability.

Every selected type has positive mass because \(T\) contains only supported types. Its normalized sampling distribution is therefore defined and atomless. Consequently, the sampled proxy coincides with the initial agent with probability zero, including when \(s_t=t\).

For a distinct proxy, its self-voting action has probability \(1/2\), independently of the initial agent’s action and proxy sampling, under the stipulated independent sampling mechanism. Therefore the probability that the initial agent delegates and the first proxy self-votes is
\[ \Pr(E_t)=\frac12\cdot\frac12=\frac14. \]

On this event, delegation terminates at a guru of type \(s_t\), yielding \(M_t\). All other outcomes have nonnegative utility. Hence \(U_t(q)\geq M_t/4\).

This reasoning uses each agent’s action sampled once. It does not resample actions, identify repeated types with cycles, or require any assertion about longer chains.

• Both approximation inequalities follow with the correct constants.

The prescribed interval gives \(0\leq1-\epsilon\leq1/4\). Together with the verified bounds, this yields
\[ U_t(q)\geq\frac14M_t \geq(1-\epsilon)M_t \geq(1-\epsilon)B_t(q). \]

Multiplication by the positive masses and summation also yield
\[ \sum_t\mu_tU_t(q) \geq\frac14\sum_t\mu_tM_t \geq\frac14\operatorname{OPT} \geq(1-\epsilon)\operatorname{OPT}. \]
All inequality directions are correct.

• Degenerate cases and endpoints are covered.

The proof remains valid when a row has \(M_t=0\), when all utilities vanish, when maximizers tie, and when there is only one supported type. Neither guarantee divides by a utility or by \(\operatorname{OPT}\).

At \(\epsilon=3/4\), the construction gives exactly the required factor. At \(\epsilon=1\), both required lower bounds are zero. Arbitrarily small positive type masses do not affect the event probability because sampling is normalized within the selected type.

• The complexity claim and citation are consistent with the argument.

Finding all maximizers requires \(O(\tau m)\) rational comparisons. Cross-multiplication uses integers with bit lengths polynomial in \(L\), so the comparison cost is polynomial. The full output has \(O(\tau(m+1))\) constant-size rational entries. With \(m=\tau\), both running time and output length are polynomial in the requested parameters.

The cited [Theorem 14](https://arxiv.org/html/2105.05142v2#S4.SS2) does describe the finite-agent self-voting and greedy-delegation scheme with the stated parameter range. The prover does not apply that finite-agent theorem to the atomless setting without verification: Sections 1–4 supply an independent argument under the task’s assumptions.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩