Michael Benisch

IJCAI Conference 2009 Conference Paper

• Michael Benisch
• Norman Sadeh
• Tuomas Sandholm

Mechanisms (especially on the Internet) have begun allowing people or organizations to express richer preferences in order to provide for greater levels of overall satisfaction. In this paper, we develop an operational methodology for quantifying the expected gains in economic efficiency associated with different forms of expressiveness. We begin by proving that the sponsored search mechanism (GSP) used by Google, Yahoo! , MSN, etc. can be arbitrarily inefficient. We then experimentally compare its efficiency to a slightly more expressive variant (PGSP), which solicits an extra bid for a premium class of positions. We generate random preference distributions based on published industry knowledge. We determine ideal strategies for the agents using a custom tree search technique, and we also benchmark using straightforward heuristic bidding strategies. The GSP’s efficiency loss is greatest in the practical case where some advertisers (“brand advertisers”) prefer top positions while others (“value advertisers”) prefer middle positions, and that loss can be dramatic. It is also worst when agents have small profit margins. While the PGSP is only slightly more expressive (and thus not much more cumbersome), it removes almost all of the efficiency loss in all of the settings we study.

AAAI Conference 2008 Conference Paper

A Theory of Expressiveness in Mechanisms

• Michael Benisch

A key trend in (electronic) commerce is a demand for higher levels of expressiveness in the mechanisms that mediate interactions. We develop a theory that ties the expressiveness of mechanisms to their efficiency in a domain-independent manner. We introduce two new expressiveness measures, 1) maximum impact dimension, which captures the number of ways that an agent can impact the outcome, and 2) shatterable outcome dimension, which is based on the concept of shattering from computational learning theory. We derive an upper bound on the expected efficiency of any mechanism under its most efficient Nash equilibrium. Remarkably, it depends only on the mechanism’s expressiveness. We prove that the bound increases strictly as we allow more expressiveness. We also show that in some cases a small increase in expressiveness yields an arbitrarily large increase in the bound. Finally, we study channel-based mechanisms, which subsume most combinatorial auctions, multi-attribute mechanisms, and the Vickrey-Clarke-Groves scheme. We show that our domain-independent measures of expressiveness appropriately relate to the natural measure of expressiveness of channel-based mechanisms: the number of channels allowed. Using this bridge, our general results yield interesting implications. For example, any (channel-based) multi-item auction that does not allow rich combinatorial bids can be arbitrarily inefficient—unless agents have no private information.

AAMAS Conference 2007 Conference Paper

Factoring Games to Isolate Strategic Interactions

• George B. Davis
• Michael Benisch
• Kathleen M. Carley
• Norman M. Sadeh

Game theoretic reasoning about multi-agent systems has been made more tractable by algorithms that exploit various types of independence in agents' utilities. However, previous work has assumed that a game's precise independence structure is given in advance. This paper addresses the problem of finding independence structure in a general form game when it is not known ahead of time, or of finding an approximation when full independence does not exist. We give an expected polynomial time algorithm to divide a bounded- payout normal form game into factor games that isolate independent strategic interactions. We also show that the best approximate factoring can be found in polynomial time for a specific interaction that is not fully independent. Once known, factors aide computation of game theoretic solution concepts, including Nash equilibria (or ε-equilibria for approximate factors), in some cases guaranteeing polynomial complexity where previous bounds were exponential.

AAAI Conference 2006 Conference Paper

Algorithms for Rationalizability and CURB Sets

• Michael Benisch

Significant work has been done on computational aspects of solving games under various solution concepts, such as Nash equilibrium, subgame perfect Nash equilibrium, correlated equilibrium, and (iterated) dominance. However, the fundamental concepts of rationalizability and CURB (Closed Under Rational Behavior sets have not, to our knowledge, been studied from a computational perspective. First, for rationalizability we describe an LP-based polynomial algorithm that finds all strategies that are rationalizable against a mixture over a given set of opponent strategies. Then, we describe a series of increasingly sophisticated polynomial algorithms for finding all minimal CURB sets, one minimal CURB set, and the smallest minimal CURB set. Finally, we give theoretical results regarding the relationships between CURB sets and Nash equilibria, showing that finding a Nash equilibrium can be exponential only in the size of the smallest CURB set. We show that this can lead to an arbitrarily large reduction in the complexity of finding a Nash equilibrium. On the downside, we also show that the smallest CURB set can be arbitrarily larger than the supports of the enclosed Nash equilibrium.

AAMAS Conference 2006 Conference Paper

Examining DCSP Coordination Tradeoffs

• Michael Benisch
• Norman Sadeh

AAMAS Conference 2004 Conference Paper

Botticelli: A Supply Chain Management Agent

• Michael Benisch
• Amy Greenwald
• Roger Lederman
• Victor Naroditskiy
• Michael Tschantz