We present an algorithm for the penalized multiple choice knapsack problem (PMCKP), a combination of the more common penalized knapsack problem (PKP) and multiple choice knapsack problem (MCKP). Our approach is to converts a PMCKP into a PKP using a previously known transformation between MCKP and KP, and then solve the PKP greedily. For PMCKPs with well-behaved penalty functions, our algorithm is optimal for the linear relaxation of the problem.

Word-of-mouth, referral, or viral marketing is a highly sought-after way of advertising. In this paper, we investigate whether such marketing can be encouraged through incentive mechanisms, thus allowing an organisation to effectively crowdsource their marketing. Specifically, we undertake a field experiment that compares several mechanisms for incentivising social media shares in support of a charitable cause. Our experiment takes place on a website promoting a fundraising drive by a large cancer research charity. Site visitors who sign up to support the cause are asked to spread the word about it on Facebook, Twitter or other channels. They are randomly assigned to one of four treatments that differ in the way social sharing activities are incentivised. Under the control treatment, no extra incentive is provided. Under two of the other mechanisms, the sharers are offered a fixed number of points that help take the campaign further. We compare low and high levels of such incentives for direct referrals. In the final treatment, we adopt a multi-level incentive mechanism that rewards direct as well as indirect referrals (where referred contacts refer others). We find that providing a high level of incentives results in a statistically significant increase in sharing behaviour and resulting signups. Our data does not indicate a statistically significant increase for the low and multi-level incentive mechanisms.

In AI research, mechanism design is typically used to allocate tasks and resources to agents holding private information about their values for possible allocations. In this context, optimizing payments within the Groves class has recently received much attention, mostly under the assumption that agent's private information is single-dimensional. Our work tackles this problem in multi-parameter domains. Specifically, we develop a generic technique to look for a best Groves mechanism for any given mechanism design problem. Our method is based on partitioning the spaces of agent values and payment functions into regions, on each of which we are able to define a feasible linear payment function. Under certain geometric conditions on partitions of the two spaces this function is optimal. We illustrate our method by applying it to the problem of allocating heterogeneous items.

We model the problem of bidding in ad auctions as a penalized multiple choice knapsack problem (PMCKP), a combination of the multiple choice knapsack problem (MCKP) and the penalized knapsack problem (PKP) [1]. We present two versions of PMCKPGlobalPMCKP and LocalPMCKP, together with a greedy algorithm that solves the linear relaxation of a GlobalPMCKP optimally. We also develop a greedy heuristic for solving LocalPMCKP. Although our heuristic is not optimal, we show that it performs well in TAC AA games.

We study the problem of how to allocate m identical items among n > m agents, assuming each agent desires exactly one item and has a private value for consuming it. We assume the items are jointly owned by the agents, not by one uninformed center, so an auction cannot be used to solve our problem. Instead, the agents who receive items compensate those who do not.

In this paper, we describe our autonomous bidding agent, RoxyBot, who emerged victorious in the travel division of the 2006 Trading Agent Competition in a photo finish. At a high level, the design of many successful trading agents can be summarized as follows: (i) price prediction: build a model of market prices; and (ii) optimization: solve for an approximately optimal set of bids, given this model. To predict, RoxyBot builds a stochastic model of market prices by simulating simultaneous ascending auctions. To optimize, RoxyBot relies on the sample average approximation method, a stochastic optimization technique.

We model budget-constrained keyword bidding in sponsored search auctions as a stochastic multiple-choice knapsack problem (S-MCKP) and design an algorithm to solve S-MCKP and the corresponding bidding optimization problem. Our algorithm selects items online based on a threshold function which can be built/updated using historical data. Our algorithm achieved about 99% performance compared to the offline optimum when applied to a real bidding dataset. With synthetic dataset and iid item-sets, its performance ratio against the offline optimum converges to one empirically with increasing number of periods.

In this paper, we combine two approaches to handling uncertainty: we use techniques for finding optimal solutions in the expected sense to solve combinatorial optimization problems in an online setting. The problem we address is the scheduling component of the Trading Agent Competition in Supply Chain Management (TAC SCM) problem, a combinatorial optimization problem with inherent uncertainty (see www.sics.se/tac/). This problem is formulated as a stochastic program, and is solved using the sample average approximation (SAA) method in an online setting to find today's optimal schedule, given probabilistic models of the future. This optimization procedure forms the heart of Botticelli, one of the finalists in the TAC SCM 2003 competition. Two sets of experiments are described, using one and two days' worth of information about the future. In the two day experiments (using one day's worth of information about the future), it is shown that SAA outperforms the expected value method, which solves a deterministic variant of the problem assuming all stochastic inputs have deterministic values equal to their expected values. In the three day experiments (using two days' worth of information about the future), it is shown that SAA with look ahead outperforms greedy SAA. This approach generalizes to N days of lookahead, and since the problem setting is one of online optimization, the benefits of two day lookahead accrue rapidly.