Cap-and-trade schemes are designed to achieve target levels of regulated emissions in a socially efficient manner. These schemes work by issuing regulatory credits and allowing firms to buy and sell them according to their relative compliance costs. Analyzing the efficacy of such schemes in concentrated industries is complicated by the strategic interactions among firms producing heterogeneous products. We tackle this complexity via an agent-based microeconomic model of the US market for personal vehicles. We calculate Nash equilibria among credits-trading strategies in a variety of scenarios and regulatory models. We find that while cap-and-trade results improves efficiency overall, consumers bear a disproportionate share of regulation cost, as firms use credit trading to segment the vehicle market. Credits trading volume decreases when firms behave more strategically, which weakens the segmentation effect.

We propose a new market design for display advertising contracts, based on posted prices. Our model and algorithmic framework address several major challenges: (i) the space of possible impression types is exponential in the number of attributes, which is typically large, therefore a complete price space cannot be maintained; (ii) advertisers are usually unable or reluctant to provide extensive demand (willingness-to-pay) functions, (iii) the levels of detail with which supply and demand are specified are often not identical.

Various operational control systems (OCS) are naturally modeled as Markov Decision Processes. OCS often enjoy access to predictions of future events that have substantial impact on their operations. For example, reliable forecasts of extreme weather conditions are widely available, and such events can affect typical request patterns for customer response management systems, the flight and service time of airplanes, or the supply and demand patterns for electricity. The space of exogenous events impacting OCS can be very large, prohibiting their modeling within the MDP; moreover, for many of these exogenous events there is no useful predictive, probabilistic model. Realtime predictions, however, possibly with a short lead-time, are often available. In this work we motivate a model which combines offline MDP infinite horizon planning with realtime adjustments given specific predictions of future exogenous events, and suggest a framework in which such predictions are captured and trigger real-time planning problems. We propose a number of variants of existing MDP solution algorithms, adapted to this context, and evaluate them empirically.

Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.

Recently, Brafman and Engel (2009) proposed new concepts of marginal and conditional utility that obey additive analogues of the chain rule and Bayes rule, which they employed to obtain a directed graphical model of utility functions that resembles Bayes nets. In this paper we carry this analogy a step farther by showing that the notion of utility independence, built on conditional utility, satisfies identical properties to those of probabilistic independence. This allows us to formalize the construction of graphical models for utility functions, directed and undirected, and place them on the firm foundations of Pearl and Paz's axioms of semi-graphoids. With this strong equivalence in place, we show how algorithms used for probabilistic reasoning such as Belief Propagation (Pearl 1988) can be replicated to reasoning about utilities with the same formal guarantees, and open the way to the adaptation of additional algorithms.

We develop multiattribute auctions that accommodate generalized additive independent (GAI) preferences. We propose an iterative auction mechanism that maintains prices on potentially overlapping GAI clusters of attributes, thus decreases elicitation and computational burden, and creates an open competition among suppliers over a multidimensional domain. Most significantly, the auction is guaranteed to achieve surplus which approximates optimal welfare up to a small additive factor, under reasonable equilibrium strategies of traders. The main departure of GAI auctions from previous literature is to accommodate non-additive trader preferences, hence allowing traders to condition their evaluation of specific attributes on the value of other attributes. At the same time, the GAI structure supports a compact representation of prices, enabling a tractable auction process. We perform a simulation study, demonstrating and quantifying the significant efficiency advantage of more expressive preference modeling. We draw random GAI-structured utility functions with various internal structures, generate additive functions that approximate the GAI utility, and compare the performance of the auctions using the two representations. We find that allowing traders to express existing dependencies among attributes improves the economic efficiency of multiattribute auctions.

We introduce CUI networks, a compact graphical representation of utility functions over multiple attributes. CUI networks model multiattribute utility functions using the well-studied and widely applicable utility independence concept. We show how conditional utility independence leads to an effective functional decomposition that can be exhibited graphically, and how local, compact data at the graph nodes can be used to calculate joint utility. We discuss aspects of elicitation, network construction, and optimization, and contrast our new representation with previous graphical preference modeling.

Multiattribute auction mechanisms generally either remain agnostic about traders' preferences, or presume highly restrictive forms, such as full additivity. Real preferences often exhibit dependencies among attributes, yet may possess some structure that can be usefully exploited to streamline communication and simplify operation of a multiattribute auction. We develop such a structure using the theory of measurable value functions, a cardinal utility representation based on an underlying order over preference differences. A set of local conditional independence relations over such differences supports a generalized additive preference representation, which decomposes utility across overlapping clusters of related attributes. We introduce an iterative auction mechanism that maintains prices on local clusters of attributes rather than the full space of joint configurations. When traders' preferencesare consistent with the auction's generalized additive structure, the mechanism produces approximately optimal allocations, atapproximate VCG prices.

We investigate the space of two-sided multiattribute auctions, focusing on the relationship between constraints on the offers traders can express through bids, and the resulting computational problem of determining an optimal set of trades. We develop a formal semantic framework for characterizing expressible offers, and show conditions under which the allocation problem can be separated into first identifying optimal pairwise trades and subsequently optimizing combinations of those trades. We analyze the bilateral matching problem while taking into consideration relevant results from multiattribute utility theory. Network flow models we develop for computing global allocations facilitate classification of the problem space by computational complexity, and provide guidance for developing solution algorithms. Experimental trials help distinguish tractable problem classes for proposed solution techniques.