d4-conf-ijcai-2016-0330

My lead is Proposition 5, proved in this paper. It says that when some customers do not vote, an \(O\)-rating strategy is weakly dominant if and only if it is \(O\)-greedy: it spends the available budget on existing voters, without pushing their ratings above \(1\). The paper also proves that paying a non-voter is strictly dominated, and explains that one such dominant strategy can be computed in polynomial time. The result is a structural characterization with an algorithmic consequence, rather than an NP-hardness or complexity-classification theorem; the paper contains no named hardness result to anchor a continuous mirror on.

Lead problem: \(O\)-Rating Mass Bribery. Take a unit-mass population with rational type masses \(\mu_t\). Each type has either a rational rating \(a_t\in[0,1]\) or no rating, denoted \(\ast\). A type records everything relevant to this problem, so members share their initial rating or abstention status. Let \(v\) be the mass of existing voters and \(A\) their total rating mass. Assume \(0<v<1\). Initial per-capita utility, and thus the per-capita budget, is \(B_0=A/v\).

A strategy may assign different bribes to different infinitesimal agents, including abstainers. A bribe \(s\) changes a voter’s rating to \(\min(1,a+s)\); an abstainer who receives a positive bribe becomes a voter with rating \(s\). Feasible strategies spend at most \(B_0\) per capita. The question is to return a strategy maximizing
\[ \frac{\text{total rating mass after bribery}}{\text{voter mass after bribery}} \;-\; \text{total bribe expenditure}. \]
A solution can be represented by \(x_t\), the total spend on each existing voter type, with \(0\le x_t\le\mu_t(1-a_t)\), \(\sum_t x_t\le B_0\), and no bribes to abstainers. A dominant solution spends \(\min(B_0,\sum_t\mu_t(1-a_t))\) on existing voters, filling their remaining rating capacity in any order. This is computable by a scan over the types. It mirrors the paper’s full dominant-strategy claim: every \(O\)-greedy allocation is optimal against all feasible strategies, including those that would pay abstainers.

The regime is a large review platform with millions of potential customers, a small set of review values, and many people who have not yet reviewed. Here \(\tau\), the number of rating and abstention types, can be small compared with the population. The normalized mass and budget are natural for asking how much of the customer base can be influenced. This mirror preserves the paper’s \(O\)-rating objective and its choice to allow bribes to create new voters; it does not replace the society with a lottery or make outcomes continuous instead. The paper’s authors should recognize it as their problem with counts replaced by proportions.

A second, more conditional anchor is Corollary 9, also proved in this paper from Proposition 8 and Algorithm 1. It says that with all customers voting and the network known, the \(P\)-greedy strategy is weakly dominant: compute each customer’s influence weight \(w_c\), order customers by decreasing weight, and spend the budget only on customers with \(w_c>1\), up to their rating capacity. The surrounding text states that computing such a dominant strategy is polynomial time.

\(P\)-Rating Block-Mass Bribery gives a continuous question for that result. Its input is rational masses \(\mu_t\), initial ratings \(a_t\), and a known matrix \(q_{ts}\), where \(q_{ts}\) is the fraction of a type-\(t\) customer’s trusted neighborhood belonging to type \(s\). All members of a type share their rating and neighborhood profile; the matrix must be realizable by a limiting undirected network. All types vote. An action chooses total spend \(x_t\) on type \(t\), with \(0\le x_t\le\mu_t(1-a_t)\) and \(\sum_t x_t\le B_P\), where
\[ B_P=\sum_r\mu_r\sum_s q_{rs}a_s \]
is initial per-capita utility. Define
\[ \lambda_t=\frac{\sum_r\mu_r q_{rt}}{\mu_t}. \]
The underlying question is to maximize the change in per-capita utility over these mass transfers. The mirrored result predicts an optimum that orders types by decreasing \(\lambda_t\), spends on types with \(\lambda_t>1\), and respects each type’s capacity. The resulting finite optimization is tractable: compute the weights and sort the \(\tau\) types. This model keeps the paper’s personalized network influence in the problem; a type includes its network role, rather than just its rating.

Both anchors predict tractable continuous problems. The first needs only a short allocation over rating types; the second needs a type-level network profile and a sort. For either, the further computational questions include what happens with non-voters under \(P\)-rating, where the voting mass and local averages change, and how the answers extend to unknown network positions. Those are outside the anchors I would rely on here.

My weakest point is that Proposition 5’s continuous version is a particularly clean mirror, but the discrete proposition already gives a polynomial-time algorithm. It therefore supports a sensible high-multiplicity model more strongly than it supports a claim that continuization removes hardness. The network mirror is closer to the paper’s distinctive \(P\)-rating contribution, but assumes a finite block structure with shared neighborhood mixtures; in a real sparse social network, preserving each person’s local influence profile could require nearly one type per person. The case for a continuous mirror survives on the \(O\)-rating result and the explicit large-platform regime, while the more ambitious network version should be treated as conditional on that compression being credible.