2 ms·

The thing about combinatorial auctions is that they are... I last looked about 2006 and I remember one problem with 11 participants on both sides requiring 2^3

by sgt101 9y ago

The thing about combinatorial auctions is that they are... I last looked about 2006 and I remember one problem with 11 participants on both sides requiring 2^38 steps to find a solution (make the set of bundles for the buyers that clear the auction at the best available price) within a not very strong bound from optimal. The details are vague as having sat down and done the sums I thought - well that's just not a goer is it - and dropped the issue like a hot spikey thing. So - many challenges.

alephnan 9y ago
> requiring 2^38 steps to find a solution Isn't the premise of the company to use "AI" to find a solution? I'm going to go out on a limb and assume AI here means deep learning. I took both an AI and ML course during college where the FAQ was "what's the difference?". At least from the way the courses were presented, the AI class focused on traversing these exponential search spaces. ML on the other hand searched for local maxima / approximations. Obviously, you seem more familiar with combinatorial auctions. I'd love to understand where an ML approach fits in here.
- sgt101 9y ago
  The thing is that if your deepnet makes a mistake and classifies a penguin as a panda it's just one of those things. If it clears an auction outside of the guarantees that you have given then everyone sues you. The reasoners that people build for auctions and poker and so on are constructed to have well understood properties so that they can be used in applications like stocks and shares, organ transplants and other critical systems.
  - sebastos 9y ago
    Based on the responses I'm seeing from user lpage elsewhere in the thread, it sounds like you can establish lower bounds external to the AI aspect of the settlement layer, making it "at least as good". So perhaps the optimization is, in some sense, all upside?

2 ms·

The thing about combinatorial auctions is that they are... I last looked about 2006 and I remember one problem with 11 participants on both sides requiring 2^3

by sgt101 9y ago

alephnan 9y ago
> requiring 2^38 steps to find a solution Isn't the premise of the company to use "AI" to find a solution? I'm going to go out on a limb and assume AI here means deep learning. I took both an AI and ML course during college where the FAQ was "what's the difference?". At least from the way the courses were presented, the AI class focused on traversing these exponential search spaces. ML on the other hand searched for local maxima / approximations. Obviously, you seem more familiar with combinatorial auctions. I'd love to understand where an ML approach fits in here.
- sgt101 9y ago
  The thing is that if your deepnet makes a mistake and classifies a penguin as a panda it's just one of those things. If it clears an auction outside of the guarantees that you have given then everyone sues you. The reasoners that people build for auctions and poker and so on are constructed to have well understood properties so that they can be used in applications like stocks and shares, organ transplants and other critical systems.
  - sebastos 9y ago
    Based on the responses I'm seeing from user lpage elsewhere in the thread, it sounds like you can establish lower bounds external to the AI aspect of the settlement layer, making it "at least as good". So perhaps the optimization is, in some sense, all upside?