In online labor markets, millions of paid tasks are performed by workers every day. We solve the stable pricing problem, that is, given the information about tasks and workers, to find a revenue-maximizing mechanism — pricing and allocation — that is stable (where no worker or task is treated unfairly), and truthful (tasks reveal their true needs). We propose two truthful, stable mechanisms named SMUP and SMNP. In SMUP, we use randomized uniform pricing, and prove that it has (1 + log h)-guarantee on revenue where h is the maximum price of a task. In SMNP, we use randomized non-uniform pricing, and prove that it has (3+3 log h)-guarantee on revenue, slightly worse than SMUP analytically. However our experiments show, SMNP has much less variance than SMUP. For the online setting when tasks arrive over time, we present a truthful online stable mechanism with (2 + 2 log h)-guarantee on revenue.

Advertisers in online social networks (OSNs) like Facebook and LinkedIn have some preferred set of users they wish to reach by showing their ads. OSNs offer fine-grained sets of user characteristics - including their career, wealth, education information, etc - that advertisers can specify for targeting their audience, and each of these characteristics requires different amounts of money for targeting. The problem we address is what we call the targeting problem, that is, given a set STcharacteristics of interest to an advertiser (that is, the advertiser wishes to reach users who have these characteristics, i.e. U(ST)) and a budget b0he wishes to spend, how to split the budget among the user characteristics so that they can reach the most number of users in U(ST)?; OSN-perspective. OSNs have complete knowledge of each user and their characteristics. In this case, we propose a polynomial time algorithm for the targeting problem and prove that it is an 1-1/e approximation to the targeting that gets the optimal number of users. We define the marginal increment and iteratively maximize it.; Advertiser-perspective. No single advertiser has the mapping of users to their characteristics or the distribution of users over the characteristics, and hence they cannot use the algorithm from above. We show through empirical data analysis that the strategy of targeting subsets U(S) ⊆ U(ST) is their only feasible approach (in other words, targeting U(S) ⊈ U(ST) will be arbitrarily worse than the direct solution). For evaluation, we crawl and analyze more than one million suggested bids from Facebook and LinkedIn. Further, we propose a fast greedy algorithm for the targeting problem based on targeting subsets, that in empirical analysis, increases the number of reached preferred users by nearly 40% over directly targeting the characteristics of interest, and for a moderate budget, it increases the number of reached preferred users by nearly 20%.

Probabilistic latent semantic analysis is a topic modeling technique to discover the hidden structure in binary and count data. As a mixture model, it performs a probabilistic mixture decomposition on the co-occurrence matrix, which produces two matrices assigned with probabilistic explanations. However, the factorized matrices may be rather smooth, which means we may obtain global feature and topic representations rather than expected local ones. To resolve this problem, one of the solutions is to revise the decomposition process with considerations of sparsity. In this paper, we present an approach that provides direct control over sparsity during the expectation maximization process. Furthermore, by using the log penalty function as sparsity measurement instead of the widely used L2 norm, we can approximate the re-estimation of parameters in linear time, as same as original PLSA does, while many other approaches require much more time. Experiments on face databases are reported to show visual representations on obtaining local features, and detailed improvements in clustering tasks compared with the original process.