4 ms·

> Human beings, especially in groups, can only reasonably make linear decisions. There are absolutely decisions that need to get made, and do get made, that ar

by addaon 2y ago

> Human beings, especially in groups, can only reasonably make linear decisions. There are absolutely decisions that need to get made, and do get made, that are not linear. Step functions are a great example. "We need to decide if we are going to accept this acquisition offer" is an example of a decision with step function utility. You can try to "linearize" it and then apply a threshold -- "let's agree on a model for the value at which we would accept an acquisition offer" -- but in many ways that obscures that the utility function can be arbitrarily non-linear.

mturmon 2y ago
A single decision could still be easily modeled by a 0/1 variable (as an input) and a real variable (as an output, like revenue for example). That 0/1 input variable could also have arbitrary interactions with other variables, which would also amount to “step function “ input effects. See for example the autism/age setup down thread.
- eru 2y ago
  Discrete linear optimisation is infinitely more complicated than continuous linear optimisation. The former is NP complete, the latter is in P.
  - naasking 2y ago
    Which seems almost ironic, because continuous linear optimization almost certainly doesn't exist really because real numbers can only be approximated, and so we're always doing discrete linear optimization at some level.
    - eru 2y ago
      Who cares about real numbers in this context? If all the numbers that appear in your constraints are rational (p/q with finite p and q), then any solution is also a rational number (with finite nominator and finite denominator). (Well, any finite solution. Your solution could also be unbounded, then you might have infinities in there.) A computer can represent finite rational numbers just fine. See eg https://docs.python.org/3/library/fractions.html https://docs.python.org/3/library/fractions.html or https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-Ratio.html https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-... for some libraries. Though in most cases, people just use floating point numbers in practice, but that's of no philosophical concern.
  - mturmon 2y ago
    No argument with that fact. But the parent comment is not talking about constrained optimization, just gradient following. In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” The question is not, “if I can only set M of these N variables to 1, which should I choose?” That’s a good question, and it leads to problems in NP, but that’s not what the comment was referring to.
    - eru 2y ago
      > In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” Yes, you are right in that abstract setting. If you always have the full hypercube of available, the problem is as easy as you describe. But if there are constraints between the variables, it gets hairier.

by addaon 2y ago

mturmon 2y ago

A single decision could still be easily modeled by a 0/1 variable (as an input) and a real variable (as an output, like revenue for example). That 0/1 input variable could also have arbitrary interactions with other variables, which would also amount to “step function “ input effects. See for example the autism/age setup down thread.

eru 2y ago
Discrete linear optimisation is infinitely more complicated than continuous linear optimisation. The former is NP complete, the latter is in P.
- naasking 2y ago
  Which seems almost ironic, because continuous linear optimization almost certainly doesn't exist really because real numbers can only be approximated, and so we're always doing discrete linear optimization at some level.
  - eru 2y ago
    Who cares about real numbers in this context? If all the numbers that appear in your constraints are rational (p/q with finite p and q), then any solution is also a rational number (with finite nominator and finite denominator). (Well, any finite solution. Your solution could also be unbounded, then you might have infinities in there.) A computer can represent finite rational numbers just fine. See eg https://docs.python.org/3/library/fractions.html https://docs.python.org/3/library/fractions.html or https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-Ratio.html https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-... for some libraries. Though in most cases, people just use floating point numbers in practice, but that's of no philosophical concern.
- mturmon 2y ago
  No argument with that fact. But the parent comment is not talking about constrained optimization, just gradient following. In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” The question is not, “if I can only set M of these N variables to 1, which should I choose?” That’s a good question, and it leads to problems in NP, but that’s not what the comment was referring to.
  - eru 2y ago
    > In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” Yes, you are right in that abstract setting. If you always have the full hypercube of available, the problem is as easy as you describe. But if there are constraints between the variables, it gets hairier.