Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof reference mechanism that solves a problem relaxation.Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regretbased metrics are not, and can be used for online selection of an effective mechanism.

As data-center energy consumption continues to rise, efficient power management is becoming increasingly important. In this work, we examine the use of a novel market mechanism for finding the right balance between power and performance. The market enables a separation between a buyer side that strives to maximize performance and a seller side that strives to minimize power and other costs. A concise and scalable description language is defined for agent preferences that admits a mixed-integer program for computing optimal allocations. Experimental results demonstrate the robustness, flexibility, practicality and scalability of the architecture.

We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies.

Combinatorial exchanges (CEs) facilitate trade between multiple buyers and sellers that need to express complex preferences on bundles of items. We present the first design for an iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language that is concise and expressive for CEs. Winner-determination is directly formulated in terms of the structure of this language. The main innovation is that bidders interact with proxy agents, and specify lower and upper valuations for trades by annotating the tree with value intervals. The design is entirely symmetric, handling buyers, sellers and mixed buyers and sellers. The proxy approach facilitates early price discovery and ensures useful preference elicitation even in early rounds. Constraint generation is used to generate linear prices without enumerating all possible trades. A proxied interpretation of a revealed-preference activity rule ensures progress. At termination, a VCG-based payment scheme that has been shown to reduce opportunities for bargaining and strategic behavior is used to determine payments. The exchange is fully implemented, running, and in a validation phase.

We present a novel tree-based logical bidding language, TBBL, for preference elicitation in combinatorial exchanges (CEs). TBBL provides new expressiveness for two-sided markets with agents that are both buying and selling goods. Moreover, the rich semantics of TBBL allow the language to capture new structure, making it exponentially more concise than OR* and LGB for preferences that are realistic in important domains for CEs. With simple extensions TBBL can subsume these earlier languages. TBBL can also explicitly represent partial information about valuations. The language is designed such that the structure in TBBL bids can be concisely captured directly in mixed-integer programs for the allocation problem. We illustrate TBBL through examples drawn from domains to which it can be (and is being) applied, and motivate further extensions we are currently pursuing.

The primary benefit of genetic schedulers is that they can often construct high quality schedules for long term scheduling. A common cost associated with genetic scheduling is that it may take tremendous amounts of time and computing power to produce high quality schedules, and these costs can make genetic scheduling impractical for many dynamic environments. The Air Crew Scheduler (ACS) system is built to crew tours for multiple squadrons in the United States Air Force. The system is built around a genetic scheduling engine that is designed to work alongside human schedulers to make crew assignments to tours. The crew scheduling problem itself is constraint laden and requires rapid schedule updates for changes to crew member information and tour changes. This paper provides a high-level overview of the problem and its constraints. We provide a design overview of the genetic scheduler that has been constructed to rapidly schedule in this dynamic setting.

Newspaper production is a complex task with numerous subtasks, each performed by different people. Many of these subtasks can be started independently, but cannot be finished without the completion of their dependent tasks. Because newspapers are produced under tight deadlines, taking advantage of this parallelism is important, but it comes at the price of many repeated changes to the layout. These changes occur when articles are added or dropped, lengths are changed, advertising space changes etc. This thesis presents a new approach to layout, where the user specifies constraints on the text boxes, rather than absolute position, allowing the layout to adapt highly sensitively to content changes. The constraints are represented in a mass-spring model that is evaluated in real time. This model is chosen (over other potentially more 'optimizing' solutions) so that immediate feedback can be provided to the user in an intuitive way, allowing him/her to update the constraints appropriately.