lpage
Joined 13 years ago
Joined 13 years ago
unsafe impl<T: Send, const N: usize> Sync for WFQueue<T, N> {}
unsafe impl<T: Send, const N: usize> Send for WFQueue<T, N> {}Classical auctions aren't a good fit because they can't handle non-price factors. However, a combinatorial clock auction could handle non-price factors while also improving price discovery. But as Milgrom says (paraphrased), the best auction is the one people use, so the more realistic outcome is what OP describes: running your own (implicit) auction.
Raft is a simple algorithm, but as others have noted, the original paper includes many correctness details often brushed over in toy implementations. Furthermore, the fallibility of real-world hardware (handling memory/disk corruption and grey failures), the requirements of real-world systems with tight latency SLAs, and a need for things like flexible quorum/dynamic cluster membership make implementing it for production a long and daunting task. The commit history of etcd and hashicorp/raft, likely the two most battle-tested open source implementations of raft that still surface correctness bugs on the regular tell you all you need to know.
The tigerbeetle team talks in detail about the real-world aspects of distributed systems on imperfect hardware/non-abstracted system models, and why they chose viewstamp replication, which predates Paxos but looks more like Raft.
[1]: https://github.com/jepsen-io/maelstrom/
[2]: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
Vickery Auctions are one of many in the auction format bestiary, and like all classical formats, they predate both computers and modern auction theory. What's really cool these days (and I'm admittedly biased since it's my space) sits at the intersection of computer science and economics. Economic mechanisms and auction formats that use everything from SAT solving and combinatorial optimization to machine learning and function approximation to drive better real-world economic outcomes.
[1]: https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
[1] https://docs.imandra.ai/imandra-docs/notebooks/verifying-mer...
Some combinatorial auctions make this tradeoff, packaging goods either to deal with computational limitations or to concentrate bidding on a few packages. It can work if there's near total consensus on what the economically relevant packages are, but it doesn't work otherwise. US equities is an "otherwise" case given a huge diversity of needs. The chance of someone wanting the opposite side of even a pairs trade at any given point in time is vanishingly rare. It's far more likely that the person doing the pair would interact with two or more counterparties independently actively interested in or willing to for the right price sell FB and buy SNAP (perhaps conditional on hedging). The mechanism design game is more about giving every party the tools they need to communicate their value function to the auctioneer and creating the incentives to bid (close to) truthfully.
> However, if there are many expressive bids with various conditions (e.g. minimum quantities, conditional on execution of another leg, etc), they may not get "implied" into creating a reasonable market, creating exponentially more arbitrage opportunities if they become locked/crossed.
And this is why combinatorial auctions are a global optimization (as opposed to implied, which are effectively an iterative and greedy approximation) and, in our case, one that seeks to find uniform clearing prices. There are formats with price discrimination and others in which mechanical arbitrage within an auction is possible, but ours is not one of them. There isn't a separate price for {A}, {B}, and {A, B} — within each auction there's a uniform price for p_a and p_b, and p_{a,b} = p_a + p_b (and so on for any arbitrary linear combination). Theoretical point: linear prices don't always exist (in practice, they do for interdependent value goods that aren't strongly sub or superadditive, e.g., capital market goods), and they're not inherently desirable. We chose linear pricing largely because it's a natural fit for how capital markets work now, and perceived fairness/simplicity is itself a valid mechanism design consideration.
You can e-mail me at: echo "a2VsbHkubGl0dGxlcGFnZUBnbWFpbC5jb20K" | base64 --decode
[ my public key: https://keybase.io/klittlepage; my proof: https://keybase.io/klittlepage/sigs/rwf5jZM7Wj6iCWAfmRwBOcpf6yhp9-doldqP31CVOiA ]
YC Badge: 0x749c80964Ba6Ed43dC2c9ae4f14cD597795E72c3