We updated our Swoopo paper, Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank, mostly making small writing improvements and typo fixes that came up when we were preparing our conference submission. It's still up on the arxiv. In an effort for student promotion, I'll point you to grad-student-co-author Giorgos Zervas's web site, which also contains links to our condensed submission version and our dataset.
Also now up on the arxiv is a preprint (submitted) by myself and Raissa D'Souza on Local cluster aggregation models of explosive percolation. We were looking at variations of the Achlioptas process. (I've promised myself I'll stop making fun of Dimitris for his keen ability to get a process named after himself -- sometime around 2020.) In the basic Achlioptas process you start with an empty graph of n nodes, and at each step you choose 2 edges at random, and add one to the graph according to some deterministic rule, such as add the edge that minimizes the size of the resulting merged component. Usually there is an associated goal, such as to delay (or speed up) the emergence of a giant component in the graph. As you might expect, the power of choosing an edge allows one to potentially delay or speed up the emergence of a giant component substantially. Our paper looks at what seem to be a simpler class of similar processes, the most basic of which is that at each step you choose 2 edges at random that are adjacent to some randomly chosen vertex v. That is, we look at local variations, where the choice can be thought of as the vertex v choosing which of 2 random edges to add to the graph. It doesn't seem these local variations have been analyzed previously. We look at differential equations that describe the underlying process and empirically examine whether such processes have discontinuous phase transitions, like the original Achlioptas process appears to have. We're promoting the idea that these "local variations" may prove simpler to analyze fully and rigorously than the original variations, for which there still remain many open questions.
Addendum: Just in case there's any confusion, I should add that Dimitris in no way named the Achlioptas process after himself. (I was just teasing him.) He was the first to suggest and promote the study of the process and when others wrote the first papers about it they nicely credited him by calling it an Achlioptas process. The name has rightfully stuck.
Subscribe to:
Post Comments (Atom)
2 comments:
I discussed these kinds of Achlioptas process variations with Po-Shen Loh back in 2008.
According to my notes, the most natural variation is to pick a k-star u.a.r. and get to keep an edge. (I wrote, "The advantage of this model is that it is 'clear' what the optimal strategy for avoiding the growth of a giant component ... should be: add the edge that connects to the smallest component.")
The next variation is to pick a random triangle, and get to keep two of the three edges.
The third variant in my notes, which seems to specialize the first, is to pick choose one of two edges that share one vertex, i.e., a uniformly random path P_2. This seems to be what you consider.
Finally, a last variation is to pick some subset of the edges of a random graph H. (And there is some sort of quantum version, too.)
As far as I could tell, the arguments didn't look sufficiently different from [Krivelevich, Loh, Sudakov 07] for any of these alternatives to be compelling, but I just thought I would mention them.
I think the compelling thing about these processes is that they appear to have a discontinuous phase transition which has yet to be well understood. (The same appears true for the standard Achlioptas process, but these variations seems potentially "easier", so there's hope we may understand these local variations first.) The preprint has more details.
Post a Comment