Many applications of collaborative filtering (CF), such as news item recommendation and bookmark recommendation, are most naturally thought of as one-class collaborative filtering (OCCF) problems. In these problems, the training data usually consist simply of binary data reflecting a user's action or inaction, such as page visitation in the case of news item recommendation or webpage bookmarking in the bookmarking scenario. Usually this kind of data are extremely sparse (a small fraction are positive examples), therefore ambiguity arises in the interpretation of the non-positive examples. Negative examples and unlabeled positive examples are mixed together and we are typically unable to distinguish them. For example, we cannot really attribute a user not bookmarking a page to a lack of interest or lack of awareness of the page. Previous research addressing this one-class problem only considered it as a classification task. In this paper, we consider the one-class problem under the CF setting. We propose two frameworks to tackle OCCF. One is based on weighted low rank approximation; the other is based on negative example sampling. The experimental results show that our approaches significantly outperform the baselines.

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e., without knowledge) of other bidders' prices and/or click-through-rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.

We study vindictive bidding, a strategic bidding behavior in keyword auctions where a bidder forces his competitor to pay more without affecting his own payment. We show that most Nash equilibria (NE) are vulnerable to vindictive bidding and are thus unstable. There always exists a pure strategy Nash equilibrium (PSNE) if there is only one pair of vindictive players; however PSNE may not exist when there are at least three players who are all vindictive with each other. Given the set of vindictive bidding pairs, we show how to compute a PSNE if one exists. Preliminary data analysis suggests that vindictive bidding is prevalent in real-world keyword auctions. As an ongoing work, we also propose several interesting open problems related to vindictive bidding.

A computationally enhanced message contains some embedded programmatic components that are interpreted and executed automatically upon receipt. Unlike ordinary text email or instant messages, they make possible a number of useful applications. In this paper, we describe a general and flexible messaging system called SHOCK that extends the functionality of prior computational email systems by allowing XML-encoded SHOCK messages to interact with an automatically created profile of a user. These profiles consist of information about the most common tasks users perform, such as their Web browsing behavior, their conventional email usage, etc. Since users are sensitive about such data, the system is designed with privacy as a central design goal, and employs a distributed peer-to-peer architecture to achieve it. The system is largely implemented with commodity Web technologies and provides both a Web interface as well as one that is tightly integrated with users ordinary email clients. With SHOCK, users can send highly targeted messages without violating others privacy, and engage in structured conversation appropriate to the context without disrupting their existing work practices. We describe our implementation in detail, the most useful novel applications of the system, and our experiences with the system in a pilot field test.