Person: Lubin, Benjamin
Loading...
Email Address
AA Acceptance Date
Birth Date
Research Projects
Organizational Units
Job Title
Last Name
Lubin
First Name
Benjamin
Name
Lubin, Benjamin
7 results
Search Results
Now showing 1 - 7 of 7
Publication A Collaborative Approach to Newspaper Layout(1999) Lubin, BenjaminPublication Payment Rules through Discriminant-Based Classifiers(ACM Press, 2012) Dütting, Paul; Fischer, Felix; Jirapinyo, Pichayut; Lai, John Kwang; Lubin, Benjamin; Parkes, DavidIn mechanism design it is typical to impose incentive compatibility and then derive an optimal mechanism subject to this constraint. By replacing the incentive compatibility requirement with the goal of minimizing expected ex post regret, we are able to adapt statistical machine learning techniques to the design of payment rules. This computational approach to mechanism design is applicable to domains with multi-dimensional types and situations where computational efficiency is a concern. Specifically, given an outcome rule and access to a type distribution, we train a support vector machine with a special discriminant function structure such that it implicitly establishes a payment rule with desirable incentive properties. We discuss applications to a multi-minded combinatorial auction with a greedy winner-determination algorithm and to an assignment problem with egalitarian outcome rule. Experimental results demonstrate both that the construction produces payment rules with low ex post regret, and that penalizing classification errors is effective in preventing failures of ex post individual rationality.Publication Expressive Power-Based Resource Allocation for Data Centers(Morgan Kaufmann Publishers Inc., 2009) Lubin, Benjamin; Parkes, David; Kephart, Jeff; Das, RajarshiAs 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 mixedinteger program for computing optimal allocations. Experimental results demonstrate the robustness, flexibility, practicality and scalability of the architecture.Publication TBBL: A Tree-Based Bidding Language for Iterative Combinatorial Exchanges(2005) Cavallo, Ruggiero; Parkes, David; Juda, Adam I.; Kirsch, Adam; Kulesza, Alex; Lahaie, Sébastien; Lubin, Benjamin; Michael, Loizos; Shneidman, JefferyWe 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.Publication ICE: An Expressive Iterative Combinatorial Exchange(Morgan Kaufmann Publishers, 2008) Lubin, Benjamin; Parkes, David; Shneidman, Jeffrey; Lahaie, Sebastien; Cavallo, Ruggiero; Juda, AdamWe 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.Publication Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions(AUAI, CoRR, and ACM Digital Libraries, 2009) Lubin, Benjamin; Parkes, DavidStrategyproof 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 regret-based metrics are not, and can be used for online selection of an effective mechanism.Publication ICE: An Iterative Combinatorial Exchange(Association for Computing Machinery, 2005) Parkes, David; Cavallo, Ruggiero; Elprin, Nick; Juda, Adam; Lahaie, Sébastien; Lubin, Benjamin; Michael, Loizos; Shneidman, Jeffrey; Sultan, HassanWe 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.