Author name cluster

Eric Sodomka

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

IJCAI Conference 2015 Conference Paper

Ranked Voting on Social Networks

Ariel D. Procaccia
Nisarg Shah
Eric Sodomka

Classic social choice theory assumes that votes are independent (but possibly conditioned on an underlying objective ground truth). This assumption is unrealistic in settings where the voters are connected via an underlying social network structure, as social interactions lead to correlated votes. We establish a general framework — based on random utility theory — for ranked voting on a social network with arbitrarily many alternatives (in contrast to previous work, which is restricted to two alternatives). We identify a family of voting rules which, without knowledge of the social network structure, are guaranteed to recover the ground truth with high probability in large networks, with respect to a wide range of models of correlation among input votes.

PDF Details

ICML Conference 2013 Conference Paper

Coco-Q: Learning in Stochastic Games with Side Payments

Eric Sodomka
Elizabeth Hilliard
Michael L. Littman
Amy Greenwald

Coco (""cooperative/competitive"") values are a solution concept for two-player normal-form games with transferable utility, when binding agreements and side payments between players are possible. In this paper, we show that coco values can also be defined for stochastic games and can be learned using a simple variant of Q-learning that is provably convergent. We provide a set of examples showing how the strategies learned by the Coco-Q algorithm relate to those learned by existing multiagent Q-learning algorithms.

Details

RLDM Conference 2013 Conference Abstract

Solving for Best Responses in Extensive-Form Games using Reinforcement Learning Methods

Amy Greenwald
Jiacui Li
Eric Sodomka

We present a framework to solve for best responses in extensive-form games (EFGs) with im- perfect information by transforming the games into Information-Set MDPs (ISMDPs), and then applying simulation-based reinforcement learning methods to the ISMDPs. We first show that, from the point of view of a single player, an EFG can be represented as an Information-Set POMDP (ISPOMDP) whose states correspond to the nodes in the EFG. This ISPOMDP can then be further represented as an ISMDP, whose states correspond to the information sets in the EFG. Because the transformations are lossless, every optimal policy in the ISMDP is a best response in the original EFG. Our approach to finding a best response in an EFG, therefore, is to first apply the aforementioned trans- formations, and to then use simulation to learn the ensuing ISMDP and standard techniques (e. g. , dynamic programming) to solve it. There are two challenges to effectively learning the ISMDP through simulation: the ISMDP state space is exponential in the horizon, and we cannot resample actions during simulation. We prove that simulation can still be guaranteed to learn near-optimal best responses with high probability, although the sample complexity depends explicitly on the size of the state space. Using our best-response finding algorithm as a subroutine, we further develop two algorithms, one that implements approximate best-reply learning dynamics, and another that approximates epsilon-factors of strategy profiles in EFGs. We evaluated these algorithms by applying them to several sequential auction domains.

PDF Details

AAMAS Conference 2013 Conference Paper

The Price of Independence in Simultaneous Auctions

BrandonA. Mayer
Eric Sodomka
Amy Greenwald

We present a computationally feasible method for predicting joint probability distributions over auction clearing prices, together with a bidding heuristic that exploits these price predictions. We demonstrate experimentally that our heuristic outperforms the state-of-the-art heuristic for bidding in simultaneous, second-price, sealed-bid (SimSPSB) auctions.

PDF

NeurIPS Conference 2012 Conference Paper

Approximating Equilibria in Sequential Auctions with Incomplete Information and Multi-Unit Demand

Amy Greenwald
Jiacui Li
Eric Sodomka

In many large economic markets, goods are sold through sequential auctions. Such domains include eBay, online ad auctions, wireless spectrum auctions, and the Dutch flower auctions. Bidders in these domains face highly complex decision-making problems, as their preferences for outcomes in one auction often depend on the outcomes of other auctions, and bidders have limited information about factors that drive outcomes, such as other bidders' preferences and past actions. In this work, we formulate the bidder's problem as one of price prediction (i. e. , learning) and optimization. We define the concept of stable price predictions and show that (approximate) equilibrium in sequential auctions can be characterized as a profile of strategies that (approximately) optimize with respect to such (approximately) stable price predictions. We show how equilibria found with our formulation compare to known theoretical equilibria for simpler auction domains, and we find new approximate equilibria for a more complex auction domain where analytical solutions were heretofore unknown.

PDF Details

UAI Conference 2012 Conference Paper

Self-Confirming Price Prediction Strategies for Simultaneous One-Shot Auctions

Michael P. Wellman
Eric Sodomka
Amy Greenwald

Bidding in simultaneous auctions is challenging because an agent’s value for a good in one auction may depend on the uncertain outcome of other auctions: the so-called exposure problem. Given the gap in understanding of general simultaneous auction games, previous works have tackled this problem with heuristic strategies that employ probabilistic price predictions. We define a concept of self-confirming prices, and show that within an independent private value model, Bayes-Nash equilibrium can be fully characterized as a profile of optimal priceprediction strategies with self-confirming predictions. We exhibit practical procedures to compute approximately optimal bids given a probabilistic price prediction, and near self-confirming price predictions given a price-prediction strategy. An extensive empirical game-theoretic analysis demonstrates that self-confirming priceprediction strategies are effective in simultaneous auction games with both complementary and substitutable preference structures.

Details

ECAI Conference 2010 Conference Paper

A Knapsack-Based Approach to Bidding in Ad Auctions

Jordan Berg
Amy Greenwald
Victor Naroditskiy
Eric Sodomka

We model the problem of bidding in ad auctions as a penalized multiple choice knapsack problem (PMCKP), a combination of the multiple choice knapsack problem (MCKP) and the penalized knapsack problem (PKP) [1]. We present two versions of PMCKPGlobalPMCKP and LocalPMCKP, together with a greedy algorithm that solves the linear relaxation of a GlobalPMCKP optimally. We also develop a greedy heuristic for solving LocalPMCKP. Although our heuristic is not optimal, we show that it performs well in TAC AA games.

Details

AAAI Conference 2007 Conference Paper

Efficient Statistical Methods for Evaluating Trading Agent Performance

Eric Sodomka

Market simulations, like their real-world counterparts, are typically domains of high complexity, high variability, and incomplete information. The performance of autonomous agents in these markets depends both upon the strategies of their opponents and on various market conditions, such as supply and demand. Because the space for possible strategies and market conditions is very large, empirical analysis in these domains becomes exceedingly difﬁcult. Researchers who wish to evaluate their agents must run many test games across multiple opponent sets and market conditions to verify that agent performance has actually improved. Our approach is to improve the statistical power of market simulation experiments by controlling their complexity, thereby creating an environment more conducive to structured agent testing and analysis. We develop a tool that controls variability across games in one such market environment, the Trading Agent Competition for Supply Chain Management (TAC SCM), and demonstrate how it provides an efﬁcient, systematic method for TAC SCM researchers to analyze agent performance.

PDF Details