6 ms·
Solving a linear optimization problem on incentive allocation
- s_Hogg 7y agoIt's not the most accessible, but it's pretty interesting. Turning a problem into its dual has always been a bit of a dark art to me, but this article makes the benefits of doing so reasonably clear.
- LolWolf 7y agoTurning a problem into a dual version is mostly a mechanical thing—you can immediately write it down in the case of LPs, for example[0], and many other convex cases [1]. —— [0] https://en.m.wikipedia.org/wiki/Dual_linear_program https://en.m.wikipedia.org/wiki/Dual_linear_program [1] http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf http://www.seas.ucla.edu/~vandenbe/236C/lectures/conj.pdf slide 23 on down.
- joker3 7y agoThe procedure is mechanical, but understanding why it works is quite a bit harder.
- LolWolf 7y agoOh sure, I agree with that. For more context, I highly recommend chapter 5 in B&V.[0] —— [0] http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page229 http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page229
- benrbray 7y agoI really recommend Tim Roughgarden's notes for understanding duality! * L7 (Intro): http://timroughgarden.org/w16/l/l7.pdf http://timroughgarden.org/w16/l/l7.pdf * L8 (Duality I): http://timroughgarden.org/w16/l/l8.pdf http://timroughgarden.org/w16/l/l8.pdf * L9 (Duality II: http://timroughgarden.org/w16/l/l9.pdf http://timroughgarden.org/w16/l/l9.pdf
- ltbarcly3 7y agoIsn't this a textbook assignment problem? https://en.wikipedia.org/wiki/Assignment_problem https://en.wikipedia.org/wiki/Assignment_problem
- deleted 7y ago[deleted]
- jvanderbot 7y agoKnapsack version https://en.wikipedia.org/wiki/Knapsack_problem#Definition https://en.wikipedia.org/wiki/Knapsack_problem#Definition where "coupons" are items with costs and values.
- chaoxu 7y agoyeah, this problem is precisely the multiple-choice knapsack problem.
- greedyalgo 7y agoSince their budget is much larger than each individual incentive, isn't the greedy solution within epsilon of the optimal assignment? I.e. sort by v/c descending and take while sum(c) < B.
- jvanderbot 7y agoGiven there are no overlapping subproblems, I think greedy is optimal[1]. The point was to show primal I(L)P with dual decomposition. 1. You're right, a counter example for greedy (with 2 appox) looks something like: c1=.5+eps, v1=1, c2=.5, v2=.5+eps, B=2.
- bo1024 7y agoI thought you were right but actually no, you'd need more assumptions. Consider this example: Type A: coupon a1 has cost 1, value 2. coupon a2 has cost 2, value 3.99. Type B: coupon b1 has cost 1, value 1. We have 100 people of Type A and 100 people of Type B. The total budget is 200. The optimal solution is to pick all Type A people, coupon a2, for a value of 399. Greedy picks all Type A people, coupon a1, and then all Type B people, coupon b1, for a value of 300.
- codesushi42 7y agoNot very interesting. You see allocation problems solved all of the time in finance, and this blog post doesn't have anything new. I also doubt that it's optimal. An implementation using Hierarchical Risk Parity for instance would be more interesting. I assume you can model risk/uncertainty here. By the way, Google has an OR tools framework that implements these kind of solvers for you: https://developers.google.com/optimization https://developers.google.com/optimization
- 1000units 7y agoUninteresting comment. You see critical, speculative comments that offer no technical insight on Hacker News all the time. I also doubt the article was read. Demonstrating actual effort and understanding would be more interesting.
- codesushi42 7y agoWhat kind of insight did you want? Simply Google "portfolio optimization" and you will find many more interesting techniques. This is a basic LP problem that you'll come across in a textbook.
- marktani 7y agoHow many HN readers read about OR before? Haven't read the blog post yet but it seems like a nice way to refresh my knowledge from some obscure lecture I attended about it ~5 years ago ;)
- 1000units 7y agoHere's an interesting comment with an interesting reply: https://news.ycombinator.com/item?id=21336687 https://news.ycombinator.com/item?id=21336687 By contrast, you effectively said, "Heh, I've seen fancier models. BTW, you can just plug your stuff into Google."
- codesushi42 7y agoBTW, you can just plug your stuff into Google Well, yeah, for something so rudimentary. Use a library. Nothing to see here.