1
$\begingroup$

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 (Political marketing example). Specifically I am interested in any work on the following problem.

Suppose there is a set of candidates $C$ and set of voters $V$ where each candidate $c_i = <c_{i, 1}, ..., c_{i, l}>$, and each $v_j = <v_{j, 1}, ..., v_{j, l}>$ is a vector of real numbers over $l$ issues. And voters have some logistic probability to vote for each candidate depending on how much the candidate and voter "agree" on each of the $l$ issues, e.g. $v_j$ votes for $c_i$ with probability $\phi\big(-(c_i \bullet v_j)\big)$ where $\phi$ is just some sigmoidal function.

Assume all voters positions and all candidate positions are known and static, expect for $c_1$. The objective of the problem is to select the position on issues for $c_1$ such that $c_1$ has the highest probability of winning the plurality vote. That is select

$$\max_{c_1} \sum_{v_j} \phi\bigg(-(c_1 \bullet v_j)\bigg)$$

The paper discuss a general method of solving this problem using a branch and bound technique (which has a nonpolynomial runtime) for sigmoidal programing problems. However, the paper, and the references, do not give a hardness proof of this specific voting problem, and the references do not appear to mention any other techniques for solving this problem.

Any literature addressing the hardness of this problem, or more specific techniques for this problem would be greatly appreciated.

$\endgroup$
  • $\begingroup$ Are you interested in the theoretical worst-case complexity, or in practical solutions that might work well enough in practice? $\endgroup$ – D.W. Jan 1 at 23:12
  • $\begingroup$ @D.W. I am mainly interested in theoretical worst-case complexity. $\endgroup$ – marvin Jan 2 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.