Person:

Lubin, Benjamin

We present the first design for a fully expressive iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language that is concise and expressive for CEs. Bidders specify lower and upper bounds on their value for different trades. 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 ensures progress across rounds. A VCG-based payment scheme that has been shown to mitigate opportunities for bargaining and strategic behavior is used to determine final payments. The exchange is fully implemented 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.

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.