When it comes to Web search, Microsoft is the undisputed underdog, a position it doesn't usually find itself in.

The company has anywhere from an eight percent to 13 percent market share in the US, depending on who is collecting the traffic data, putting it behind Yahoo (20 percent to 23 percent share) and far behind Google (54 percent to 64 percent share). And Microsoft's share seems to be slipping, nearly four percentage points from a year ago, according to Hitwise.

How does Microsoft propose to narrow the gap? Earlier this year, the company launched a program called Microsoft Search and Win that rewards people for using the Live Search site. The program bumped up Microsoft's market share this summer. But while compensating people to use your search engine may provide a temporary market share increase, it isn't a good long-term strategy to build market share.

Microsoft is hoping that it can catch up to rivals in overall search and find a few key areas where it can go into more depth, by offering tailored searches. For now, it is eyeing celebrities and entertainment, product searches, local search and healthcare as fertile areas worth having specialised results.

ZDNet Australia sister site CNET News.com talked to Satya Nadella, corporate vice president of search and advertising at Microsoft, about how the company plans to improve its market share and improve search for the long haul.

Q: How much of your search traffic is coming from search embedded within other Microsoft Internet properties versus people going directly to the main Live.com search page?
Nadella: The search bar on MSN is where we get a lot [of traffic], and we do get even a bunch from people who choose to use us as the default provider on their browser, as well as people who install our toolbar. So, those are the top three sources.

Some folks have said it's about one percent of your traffic that comes from people typing in the Live.com Web address?
Nadella: That's probably true. We've not really marketed Live.com. In fact, we've really focused, even with this release we'll be very, very focused on basically having the Live search experience power MSN, and that's a fairly explicit strategy of ours, if you will, because we feel that that's the place where we can gain a lot by showing a better search experience, and getting the customers and the consumers who are doing searches with us on top of MSN to do more.

So, you're not going to be trying to narrow the gap with Google and even Yahoo on just general Web search and trying to attract people to Live.com?
Nadella: Yahoo is very much like MSN. People type in Yahoo.com, and they go to a portal, and MSN is one such portal, so it has search, and we'll keep innovating on how to highlight that. Whereas when we think about Google as just a destination site, we have that with Live, and we think that with Windows Live and other places we'll start building some organic traffic. But I would say that in the fall you will see us, just because these 70 million users today are our lowest hanging fruit in terms of being able to increase the engagement with them, that we will put a lot of energy in just marketing ourselves through MSN.

Microsoft has turned to paid programs, either direct-to-consumer promotions or promotions with businesses, in the last year to gain share, or really recoup lost share. Is that something you expect to increase, stay level, or decrease in the coming year?
Nadella: We believe that we will sustain that. We built a generalised loyalty program/platform called the Live Search Club, which helps us raise awareness to the fact that we are in this search game and helps us get more engagement and then builds loyalty through things like prizes. We'll do more of that, and generally use this as a loyalty program going forward, and experiment with multiple ways to engage users.

What about paying businesses to use you?
Nadella: So, we have some pilots that you've seen us talk about. We will definitely move that. But I would say the core focus at least in the fall would be for the consumer push through MSN.

Some of the new features launched this week are already offered by your rivals. Is catching up really much of a game changer at this point?
Nadella: That's a good question. You have to be in the game with the core [relevance], and then you have to differentiate in these high-value vertical domains. If we have 70 million people using our search engine today, if we are getting better at core relevance, and delivering some differentiated experiences in verticals, what can our share position be?

In some sense, it's perhaps not the position we'd like to be in, but we are in a position where quite frankly we have nothing to lose. We want to be able to come out, take some risks, do some innovation, get to a place where we have parity on some of the table stakes, and differentiate. The 70 million users we have is a substantial number, and if we can get them to do more searches, we will have gains.

There is a perspective that you guys have perhaps pushed search as much as you can on the base of users that you have -- it's integrated in every possible MSN thing. Is the gaining really to be had among the people that are already using MSN, or have you tapped them pretty well, and you actually need to gain more users?
Nadella: Our data shows we have a higher share of users than our search share, and they use multiple search engines. So, it's not primarily a switching issue; it's an issue of a product and the experience being compelling enough to earn a higher share of their searches.

So, I would say I get your feedback, I get your comment, but my only comeback on that one would be that there is a little bit of a perspective here about, hey, we've been in this game for four years, and we've been trying to get to a place where our search experience is, one, good, and has differentiation. We feel like we've gotten to a point where last year's release got us to a good state and we're able to compete, and this year we will get that to even be further.

Then the other thing I would say is our own network in MSN -- I talk about 70 million users, whereas MSN has 500 million unique users a month. So, even within our own network, if our product and our experience improves, people will probably not type in Google.com. So, that's another opportunity as well.

It seems like you might be able to have a conversation around the differentiation points, but you'd have a tough time winning over general search queries just by catching up.
Nadella: Whenever I look at my traffic, I look at the people who do a search query and abandon our search engine and go somewhere else. So, that's kind of where I feel if we get to a place where people find what they are looking for on our search engine, they will keep coming back.

And when you think about shopping, entertainment, local and health searches, they will add up to a substantial portion of the general Web queries where we will have more differentiated experiences as well.

When we have a conversation a year from now, what types of results do you expect to be able to have shared? What are some markers that we can say a year from now, if you've done this, this and this, you've been successful?
Nadella: I think at the end of the day we absolutely think market share is an important metric. So, from a year from now I believe that MSN searchers, basically the 70 million and even the 500 million unique users that MSN has, will be searching more with us.

What are your plans in terms of marketing?
Nadella: Our core priority for the fall will be on the network on MSN. Obviously the word of mouth and the engagement and the satisfaction of the customers who are doing those searches are going to be a critical factor.

So, it sounds like the primary audience or effort is basically the people that you reach already and not so much the people that aren't using Microsoft in some way or another today?
Nadella: That's right. We want to be able to break through to them about the core relevance of our search experience, and also to show value and differentiation in some of these high interest domains.

I just want to make sure I understand. The new features and improvements you showed us today, many of which seem to really just catch up to what others are already doing, are going to be enough in your opinion to get those Microsoft network users, who are using other search engines and not Microsoft, or who are using other search engines in addition to Microsoft, to stop using those other search engines?
Nadella: Yes. The improvements in core relevance and the differentiated features in mobile search, image, video, shopping, health and entertainment, do create both the combination of being caught up, plus differentiated features that will cause those users to do more searches with us.

I've asked this question before, but to make sure that I'm understanding the answer, is it the case that you think you'll gain significant share without being better at the core? The features you showed on the core side were all features that Google has today. Don't you have to be better at the core to win?
Nadella: I do believe that there will be classes of queries where we will be marginally better in the core, and I would say our goal would be to keep at it, and as I said, this is a continuous game, so therefore we feel confident.

The fact that we caught up with somebody who was sort of the leader in the industry and started a lot before us should give us hope that we can do even better. But do I say that that would be the only time we'll gain the first point of share? I don't believe so, because one, we've proved that we can even gain share.

Let's sort of forget for a second that we lost share first. If I look at what we have done on the engagement side with the Live Club, and all these differentiated features we have, in addition to the core, I believe we can gain share.

Will we be number one instantly because we just caught up? That's a very debatable point. But at the same time, do I believe that we can do better than our current share position, given that we have these 70 million users and these 5 million users and [are] giving them a better search experience than the alternative? I believe so.

Elinor Mills and Ina Fried reported from San Francisco for CNET News.com.

Copyright © 2009 CBS Interactive, a CBS Company. All Rights Reserved.
ZDNET is a registered service mark of CBS Interactive. ZDNET Logo is a service mark of CBS Interactive.