Samuel Ieong

ICML Conference 2012 Conference Paper

Predicting Consumer Behavior in Commerce Search

• Or Sheffet
• Nina Mishra
• Samuel Ieong

AAAI Conference 2008 Conference Paper

Bayesian Coalitional Games

• Samuel Ieong

We introduce Bayesian Coalitional Games1 (BCGs), a generalization of classical coalitional games to settings with uncertainties. We define the semantics of BCG using the partition model, and generalize the notion of payoffs to contracts among agents. To analyze these games, we extend the solution concept of the core under three natural interpretations— ex ante, ex interim, and ex post—which coincide with the classical definition of the core when there is no uncertainty. In the special case where agents are risk-neutral, we show that checking for core emptiness under all three interpretations can be simplified to linear feasibility problems similar to that of their classical counterpart.

AAAI Conference 2007 Conference Paper

Near-Optimal Search in Continuous Domains

• Samuel Ieong
• Yoav Shoham

We investigate search problems in continuous state and action spaces with no uncertainty. Actions have costs and can only be taken at discrete time steps (unlike the case with continuous control). Given an admissible heuristic function and a starting state, the objective is to find a minimum-cost plan that reaches a goal state. As the continuous domain does not allow the tight optimality results that are possible in the discrete case (for example by A*), we instead propose and analyze an approximate forward-search algorithm that has the following provable properties. Given a desired accuracy, and a bound d on the length of the plan, the algorithm computes a lower bound L on the cost of any plan. It either (a) returns a plan of cost L that is at most more than the optimal plan, or (b) if, according to the heuristic estimate, there may exist a plan of cost L of length > d, returns a partial plan that traces the first d steps of such plan. To our knowledge, this is the first algorithm that provides optimality guarantees in continuous domains with discrete control and without uncertainty.

AAAI Conference 2005 Conference Paper

Fast and Compact: On A Simple Class of Congestion Games

• Samuel Ieong
• Eugene Nudelman

We study a simple, yet rich subclass of congestion games that we call singleton games. These games are exponentially more compact than general congestion games. In contrast with some other compact subclasses, we show tractability of many natural game-theoretic questions, such as finding a sample or optimal Nash equilibrium. For best- and better-response dynamics, we establish polynomial upper and lower bounds on the rate of convergence and present experimental results. We also consider a natural generalization of singleton games and show that many tractability results carry over.