As smartphones and other mobile computing devices have increased in ubiquity, advertisers have begun to realize a more effective way of targeting users and a promising area for revenue growth: location-based advertising. This trend brings to bear new questions about whether or not users will adopt products involving this potentially invasive form of advertising and what sorts of protections they should be given. Our real-world user study of 27 participants echoes earlier findings that users have significant privacy concerns regarding sharing their locations with advertisers. However, we examine these concerns in more detail and find that they are complex (e.g., relating not only to the quantity of ads, but the locations and times at which they are received). With advanced privacy settings, users stated they would feel more comfortable and share more information than with a simple opt-in/opt-out mechanism.

We provide a series of algorithms demonstrating that solutions according to the fundamental game-theoretic solution concept of closed under rational behavior (CURB) sets in two-player, normal-form games can be computed in polynomial time (we also discuss extensions to n-player games). First, we describe an algorithm that identifies all of a player’s best responses conditioned on the belief that the other player will play from within a given subset of its strategy space. This algorithm serves as a subroutine in a series of polynomial-time algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set in a game. We then show that the complexity of finding a Nash equilibrium can be exponential only in the size of a game’s smallest CURB set. Related to this, we show that the smallest CURB set can be an arbitrarily small portion of the game, but it can also be arbitrarily larger than the supports of its only enclosed Nash equilibrium. We test our algorithms empirically and find that most commonly studied academic games tend to have either very large or very small minimal CURB sets.

No abstract available.

No abstract available.

In this paper, we examine the problem of choosing discriminatory prices for customers with probabilistic valuations and a seller with indistinguishable copies of a good. We show that under certain assumptions this problem can be reduced to the continuous knapsack problem (CKP). We present a new fast ε-optimal algorithm for solving CKP instances with asymmetric concave reward functions. We also show that our algorithm can be extended beyond the CKP setting to handle pricing problems with overlapping goods (e.g.goods with common components or common resource requirements), rather than indistinguishable goods.We provide a framework for learning distributions over customer valuations from historical data that are accurate and compatible with our CKP algorithm, and we validate our techniques with experiments on pricing instances derived from the Trading Agent Competition in Supply Chain Management (TAC SCM). Our results confirm that our algorithm converges to an ε-optimal solution more quickly in practice than an adaptation of a previously proposed greedy heuristic.

Supply chains are a central element of today's global economy. Existing management practices consist primarily of static interactions between established partners. Global competition, shorter product life cycles and the emergence of Internet-mediated business solutions create an incentive for exploring more dynamic supply chain practices. The Supply Chain Trading Agent Competition (TAC SCM) was designed to explore approaches to dynamic supply chain trading. TAC SCM pits against one another trading agents developed by teams from around the world. Each agent is responsible for running the procurement, planning and bidding operations of a PC assembly company, while competing with others for both customer orders and supplies under varying market conditions. This paper presents Carnegie Mellon University's 2005 TAC SCM entry, the CMieux supply chain trading agent. CMieux implements a novel approach to coordinating supply chain bidding, procurement and planning, with an emphasis on the ability to rapidly adapt to changing market conditions. We present empirical results based on 200 games involving agents entered by 25 different teams during what can be seen as the most competitive phase of the 2005 tournament. Not only did CMieux perform among the top five agents, it significantly outperformed these agents in procurement while matching their bidding performance.

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.