Posts Tagged ‘social networks’


My gmail account got “buzzed” yesterday, and I checked it out.  (While I do work for Google part-time, I knew very little about this product previously.) My initial impression is that this is indeed the “social app” for my generation: the email generation.  I have to admit that I never caught up with the younger generation who feels at home at Facebook or Twitter (or, frankly,  even SMSing).  I know that for the young of today email is something that “your teacher uses to talk to your parents”, but, hey, I am these teacher and parents.  So while I wonder with everyone how the Google Buzz vs. Twitter/Facebook thing will go in general, Buzz seems to fit my demographic quite well.

To start with, it lives where I live — in the email.  Just this tiny fact may make a huge difference for me, since I rarely bother entering Twitter or Facebook neither to check things out, nor to write a trivial message.  Now, for example, I can follow Lance’s Twitter on Buzz.  The zero-effort of buzzing means that I can even see myself Buzzing (is this the term that’s go’na catch instead of tweeting?).  Second, as buzz was automatically populated with many of my email contacts, I almost immediately have stuff to look at.  So far certainly almost all buzz that I’ve seen is from the nerdier side of my contacts, but that can change very quickly, if I extrapolate from what I see so far.  Furthermore, as the default of the “profile” page is to show the list of those that you follow or that follow you, it’s easy to “browse the followship graph” and find even more interesting people t0 follow. (Tao is buzzing too, and once you follow him you also get the items he shares from the blogs he reads.)

A bunch of other design choices also seem appropriate for me: from the simplicity of it all, to the directed followship graph (a la twitter) which is easier to swallow for me than the undirected friendship graph of Facebook.  I haven’t tried yet the geo/mobile features (I’m still 2G), or the targeted buzzing to specific subgroups, but at least their description seems simple enough.

To conclude: so far I’m a fan, with two main worries: (1) the overload of information with its time-sink effect will certainly get worse, and (2) while I rarely felt the need to be careful about my privacy online previously, I do feel the need for care in handling my privacy with Buzz.


Read Full Post »

Facebook has announced a pretty nice graduate student fellowship program.  The first three reserach areas they mention are:

  • Internet Economics: auction theory and algorithmic game theory relevant to online advertising auctions.
  • Cloud Computing: storage, databases, and optimization for computing in a massively distributed environment.
  • Social Computing: models, algorithms and systems around social networks, social media, social search and collaborative environments.

(Hat tip to TechCrunch.)

Google has its own graduate Fellowship program (Nicolas Lambert got the 2009 Fellowship in “Market Algorithms”.)

Read Full Post »

Crowd sourcing has just been given a recent visibility boost with DARPA’s Red Balloon contest that was won by the MIT team.  At the same time, Amazon’s well-established (since 2005!) platform for crowd sourcing, the Mechanical Turk, is gaining attention as a platform for conducting behavioral experiments, especially in behavioral economics and game-theory.

Named after the 18th century human-powered chess-playing “machine” called “the Turk”, this platform allows “requesters” to submit “Human Intelligence Tasks” (HITs) to a multitude of human “workers” who solve them for money.  A sample of recent typical tasks include tagging pictures (for 3 cents), writing (and posting on the web) a short essay with a link (for 20 cents), or correcting spellings (for 2 cents, in Japanese).  This allows brief and cheap employment of hundreds and thousands of people to work on simple Internet-doable low-level knowledge tasks.  You may demand various “qualification exams” from these workers, and design such quals of your own.  Obviously workers are in it for the money, but apparently not just that.

Recently, the Mechanical Turk is being used to conduct behavioral experiments.  Gabriele Paolacci is methodologically repeating experiments of Kahneman and Tversky and reporting on them in his blog. Panos Ipeirotis reports on his blog studies of some aspects of the Mechanical Turk as well as results of various behavioral game-theory experiments on it.  I’ve seen others report on such experiments too.  Markus Jacobsson from PARC gives general tips for conducting such human experiments using the Mechanical Turk.

Turk-based behavioral experimentation has the immense appeal of being cheap, fast, and easy to administer.  There are obviously pitfalls such as getting a good grasp on the population, but so does any experimental setup.   Such a platform may be especially appropriate for Internet-related behavioral experiments such as figuring out bidding behavior in online auctions, or how to best frame a commercial situation on a web-page.  Could this be a tool for the yet not-quite-existent experimental AGT?

Read Full Post »

A large number of AGT researchers work in just three large companies: Google, Microsoft, and Yahoo, mostly working on ad auctions. From two or three data points, it seems that Facebook is now attempting to hire such researchers too (although maybe not in “research” roles). Looking in Facebook’s “careers” page, they are indeed looking for an “advertising auction expert” whose requirements include “Expert knowledge of algorithmic game theory, auction theory, mechanism design and their applications to online advertising” as well as a Ph.D. in CS or OR.

I can well see the potential for Algorithmic Mechanism Design research in Facebook. Facebook’s information about its users is enormous, detailed, and lives within the context of their complex social network. Making good use of this complex information seems to require another level of sophistication relative to today’s ad auctions. Privacy issues are always there, and while Facebook has already had problems in that department, it seems that its users do not consider their “identity” to be too private. I wonder if within a year or two we’ll start seeing research papers coming from Facebook too.

Read Full Post »

DARPA Netwrok Challenge

Despite my better judgement , I am fascinated by DARPA’s Network Challenge.  The basic idea is simple: on this Saturday, December 5th, at 10AM (EST),  ten large red weather balloons with be placed in various locations in the USA.  The first person to report the locations of all balloons wins $40K.  This seems to be an exercise in crowdsourcing, and it is not difficult to see various reasons why the US military may be interested in such an exercise.

If you want to win, the question seems to be how to get many potential balloon-sighters to report their findings to you rather than to someone else.  Offers of $1K for the first sighting of a balloon (conditioned on winning) came fast, soon to be trumped by $3K offers, which is within a factor of 4/3 from optimizing this approach.   Indeed the prize amount seems to be intentionally low, as to provide barriers to this natural monetary technique.  At this point, the edge of rationality, non-monetary rewards were started to be offered, like world peace or, my favorite, “use the winnings to create a giant flying cupcake built entirely out of balloons!“.  My own contribution (probably discovered independently by countless others) is the observation that the monetary technique is not really limited by the prize money: winning may have significant advertising value for the right kind of company, who may invest much larger amounts of money in attracting collaborators to its effort.

An analysis of possible approaches can be found here, including some thoughts on satellite or aerial surveys and on negative tactics (mis-report balloons to your competitors) and a link to a wiki.

Read Full Post »

The Netflix $1M collaborative filtering competition has ended with an outcome that is doubly-interesting.  First, there was a nice “photo-finish” with two separate groups passing the prize-winning mark and with the winner not yet announced.  More interesting is the fact that both contenders at this point are rather large coalitions each composed of several groups who were previously separately competing.  In fact, once the first such coalition passed the prize-wining mark, the second coalition formed, combined forces, and reached first place within the 30 days mandated by the rules.

Many have written about the significance of the fact that it is not one “magic bullet” that lets you win such a competition but rather the combination of many “small” ideas and much work.  What I am intrigued by is how such a fruitful combination of separately written pieces of software happens.  In the case of the first group, who have been working together for a while, one might take the point of view that it is just the usual miracle seen in any large software effort (open source or not) where a sound software architecture with well-defined interfaces lets many people contribute to a project.  (Just like Linux or Google Search keep getting better by the combined efforts of many programmers.)  However, in case of the second group, there seems to be something more interesting going on in the sense that the pieces were joined ex-post, seemingly with a very simple combination architecture. How can this be done?  Can it be done for other challenges as well?  (A competition to beat Google search?) Can competitions be designed with collaboration built in? (Maybe the second Netfilx competition?)

Let us look at an easy example for simple software collaboration: optimization given a set of constraints (such as Integer programming).  Here the input consists of a set of constraints on n variables, as well as an optimization goal defined on these variables.  The output should be an assignment of values to the variables that satisfies the constraints and with as high as possible a value for the optimization goal.  The nice thing about such problems is that collaboration is essentially built in by the problem definition.  Once clear input and output formats are defined, combining several optimizers is easy: just run all of them on the input instance, and output the best assignment returned by any of the component optimizers.  If the total measure of success of an algorithm is the average (say) value of the returned assignment over some distribution of problem instances, then the collaborative optimizer is certainly at least as good as any single component used, and if the different components used have distinct “strengths” then the collaborative optimizer is actually better than any single one.  This architecture naturally supports specialization: each optimizer focuses on some subset of instances and tries to do as good a job as possible on it, leaving other inputs for other optimization efforts.

Now back to Netflix-like machine learning challenges where the optimization goal is to produce a single predictor p that agrees as much as possible with the given target function t.  The natural ML tendencies would be, I suppose, to combine different p‘s using some kind of weighted voting or averaging, as indeed the second team seems to have done according to the Wired blog post:

To combine competitors’ algorithms, The Ensemble didn’t have to cut and paste much code together. Instead, they simply ran hundreds of algorithms from their 30-plus members (updated) and combined their results into a single set, using a variation of weighted averaging that favored the more accurate algorithms.

Thus the collaboration architecture is not different from the problem statement with the addition of a module that chooses the best weights for averaging.  When the aim is to minimize the sum-squares error, as was the case in the Netflix challenge, then the best coefficients for weighting the average can be efficiently obtained by linear regression which should be doable with these data set sizes (I think).

I can see many interesting theoretical and practical research issues in generalizing the scope of collaboration:

  • How can we easily allow more sophisticated combinations?  E.g. a component that specializes in figuring out “who to ask” among other algorithms? Or branch-n-bound algorithms that use partial results from other optimizers to control branching?  In the Netflix case, one researcher found a way to take temporal dynamics into consideration — can this be effortlessly used as a subroutine in other components?  What kind of meta-data will be useful here?
  • Can we get Organic-like growth with sub-algorithms constantly being added that utilize and then improve the previous state of affairs?  How do we best mimic natural-selection?  How do we avoid evolutionary dead-ends?
  • How do we incentivize partial algorithms?  How do we determine the contribution of a single component relative to others?  I can immediately think of two types of models here: one based on a cooperative games formalism where for each subset S of components we have the value v(S) that its combination can bring, and another taking a sequential approach where each contribution gets credited according to the marginal improvement that it brings relative to the previous combination.  This is somewhat like an intellectual property model when the first one to come up with an idea gets the credit for it, but then others can build upon it — a model that presumably encourages rapid progress.
  • What if we don’t have resources (say CPU time) to run all components, how do we choose which to use?  Obviously we want to take their cost-performance trade off into account.  Can we have components that specialize in such resource allocation?

Read Full Post »

A few interesting pieces that I recently came by:

  1. A new economic paper on open source byMichael Schwarz and Yuri Takhteyev (via Al Roth’s blog).
  2. A compendium of PPAD-complete problems from Shiva Kintali.
  3. Some interesting thoughts on graduate school from Noah Snyder.
  4. The WAA09 workshop on ad auctions (via Muthu’s blog) — deadline is May 22nd.
  5. A new paper on “feedback loops of attention in peer production” by Fang Wu, Dennis M. Wilkinson, and Bernardo Huberman added to the many social network papers by Huberman on the arXiv.
  6. Electronic voting workshop in Israel

Read Full Post »

%d bloggers like this: