Amy Greenwald

AAMAS Conference 2026 Conference Paper

Bilevel Policy Optimization with Nyström Hypergradients

• Arjun Prakash
• Naicheng He
• Denizalp Goktas
• Amy Greenwald

The dependency of the actor on the critic in actor-critic (AC) reinforcement learning means that AC can be characterized as a bilevel optimization (BLO) problem, also called a Stackelberg game. This characterization motivates two modifications to vanilla AC algorithms. First, the critic’s update should be nested to learn a best response to the actor’s policy. Second, the actor should update according to a hypergradient that accounts for changes in the critic. Computing this hypergradient involves finding an inverse Hessian vector product, a process that can be numerically unstable. We thus propose a new algorithm, Bilevel Policy Optimization with Nyström Hypergradients (BLPO), which uses nesting to account for the nested structure of BLO, and leverages the Nyström method to compute the hypergradient. Theoretically, we prove BLPO converges to (a point that satisfies the necessary conditions for) a local strong Stackelberg equilibrium in polynomial time with high probability, assuming a linear parametrization of the critic’s objective. Empirically, we demonstrate that BLPO performs on par with or better than PPO on a variety of discrete and continuous control tasks.

NeurIPS Conference 2025 Conference Paper

A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning

• Zechen Wu
• Amy Greenwald
• Ronald Parr

In off-policy policy evaluation (OPE) tasks within reinforcement learning, Temporal Difference Learning(TD) and Fitted Q-Iteration (FQI) have traditionally been viewed as differing in the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Partial Fitted Q-Iteration (PFQI) performs a finite number. We show that this view is not accurate, and provide a new mathematical perspective under linear value function approximation that unifies these methods as a single iterative method solving same linear system, but using different matrix splitting schemes and preconditioners. We show that increasing the number of updates under the same target value function, i. e. , the target network technique, is a transition from using a constant preconditioner to using a data-feature adaptive preconditioner. This elucidates, for the first time, why TD convergence does not necessarily imply FQI convergence, and establishes tight convergence connections among TD, PFQI, and FQI. Our framework enables sharper theoretical results than previous work and characterization of the convergence conditions for each algorithm, without relying on assumptions about the features (e. g. , linear independence). We also provide an encoder-decoder perspective to better understand TD’s convergence conditions, and prove, for the first time, that when a large learning rate doesn’t work, trying a smaller one may help(for batch TD). Our framework also leads to the discovery of new crucial conditions on features for convergence, and shows how common assumptions about features influence convergence, e. g. , the assumption of linearly independent features can be dropped without compromising the convergence guarantees of stochastic TD in the on-policy setting. This paper is also the first to introduce matrix splitting into the convergence analysis of these algorithms.

JAIR Journal 2025 Journal Article

Empirical Game Theoretic Analysis: A Survey

• Michael P. Wellman
• Karl Tuyls
• Amy Greenwald

In the empirical approach to game-theoretic analysis (EGTA), the model of the game comes not from declarative representation, but is derived by interrogation of a procedural description of the game environment. The motivation for developing this approach was to enable game-theoretic reasoning about strategic situations too complex for analytic specification and solution. Since its introduction over twenty years ago, EGTA has been applied to a wide range of multiagent domains, from auctions and markets to recreational games to cyber-security. We survey the extensive methodology developed for EGTA over the years, organized by the elemental subproblems comprising the EGTA process. We describe key EGTA concepts and techniques, and the questions at the frontier of EGTA research. Recent advances in machine learning are accelerating progress in EGTA, and promise to significantly expand our capacities for reasoning about complex game situations.

AAMAS Conference 2024 Conference Paper

Banzhaf Power in Hierarchical Games

• John Randolph
• Amy Greenwald
• Denizalp Goktas

The Banzhaf Power Index (BPI) is a method of measuring the power of voters in determining the outcome of a voting game. Some voting games exhibit a hierarchical structure, including the US electoral college and ensemble learning methods; we call such games hierarchical voting games. It is generally understood that BPI in hierarchical voting games can be computed via a recursive decomposition of the hierarchy, which can substantially reduce the calculation’s complexity. We identify a key (previously undocumented) assumption on which this decomposition is based, namely balance, meaning one group of voters has enough votes to win whenever the complementary group of voters does not, and vice versa. We then introduce a generalization of BPI that we call Extended BPI (EBPI) for all voting games, including those that are not balanced, which simplifies to BPI in balanced games. We show that BPI in unbalanced hierarchical voting games decomposes in terms of EBPI at each level in the hierarchy, which yields computational savings analogous to those achieved in the balanced case. As a sample application, we take advantage of the compositionality of language, and model the impact of individual words on a sentence’s sentiment as a voting game. As the complement of a phrase in a sentence does not necessarily have the opposite sentiment, this voting game is unbalanced and requires our decomposition of BPI in terms of EBPI. Our results suggest that EBPI is an effective proxy for BPI (because the meaning of a sentence is not always 100% compositional), and demonstrate a dramatic improvement in run time.

ICLR Conference 2024 Conference Paper

Efficient Inverse Multiagent Learning

• Denizalp Goktas
• Amy Greenwald
• Sadie Zhao
• Alec Koppel
• Sumitra Ganesh

In this paper, we study inverse game theory (resp. inverse multiagent learning) in which the goal is to find parameters of a game’s payoff functions for which the expected (resp. sampled) behavior is an equilibrium. We formulate these problems as generative-adversarial (i.e., min-max) optimization problems, which we develop polynomial-time algorithms to solve, the former of which relies on an exact first- order oracle, and the latter, a stochastic one. We extend our approach to solve inverse multiagent simulacral learning in polynomial time and number of samples. In these problems, we seek a simulacrum, meaning parameters and an associated equilibrium that replicate the given observations in expectation. We find that our approach outperforms the widely-used ARIMA method in predicting prices in Spanish electricity markets based on time-series data.

NeurIPS Conference 2023 Conference Paper

Convex-Concave Zero-Sum Markov Stackelberg Games

• Denizalp Goktas
• Arjun Prakash
• Amy Greenwald

Zero-sum Markov Stackelberg games can be used to model myriad problems, in domains ranging from economics to human robot interaction. In this paper, we develop policy gradient methods that solve these games in continuous state and action settings using noisy gradient estimates computed from observed trajectories of play. When the games are convex-concave, we prove that our algorithms converge to Stackelberg equilibrium in polynomial time. We also show that reach-avoid problems are naturally modeled as convex-concave zero-sum Markov Stackelberg games, and that Stackelberg equilibrium policies are more effective than their Nash counterparts in these problems.

AAAI Conference 2023 Conference Paper

Fisher Markets with Social Influence

• Jiayi Zhao
• Denizalp Goktas
• Amy Greenwald

A Fisher market is an economic model of buyer and seller interactions in which each buyer’s utility depends only on the bundle of goods she obtains. Many people’s interests, however, are affected by their social interactions with others. In this paper, we introduce a generalization of Fisher markets, namely influence Fisher markets, which captures the impact of social influence on buyers’ utilities. We show that competitive equilibria in influence Fisher markets correspond to generalized Nash equilibria in an associated pseudo-game, which implies the existence of competitive equilibria in all influence Fisher markets with continuous and concave utility functions. We then construct a monotone pseudo-game, whose variational equilibria and their duals together characterize competitive equilibria in influence Fisher markets with continuous, jointly concave, and homogeneous utility functions. This observation implies that competitive equilibria in these markets can be computed in polynomial time under standard smoothness assumptions on the utility functions. The dual of this second pseudo-game enables us to interpret the competitive equilibria of influence CCH Fisher markets as the solutions to a system of simultaneous Stackelberg games. Finally, we derive a novel first-order method that solves this Stackelberg system in polynomial time, prove that it is equivalent to computing competitive equilibrium prices via tâtonnement, and run experiments that confirm our theoretical results.

AAMAS Conference 2023 Conference Paper

Learning Properties in Simulation-Based Games

• Cyrus Cousins
• Bhaskar Mishra
• Enrique Areyan Viqueira
• Amy Greenwald

Empirical game-theoretic analysis (EGTA) is primarily concerned with learning equilibria of simulation-based games. Recent statistical approaches have tackled this problem by first learning a uniform approximation of the game’s utilities, and then applying precision-recall theorems: i. e. , all equilibria of the true game are approximate equilibria in the estimated game, and vice-versa. In this work, we generalize this approach to all game properties that are well-behaved (i. e. , Lipschitz continuous in utilities), including regret (which defines Nash and correlated equilibria), adversarial values, power-mean welfare, and Gini social welfare. We show that, given a well-behaved welfare function, while optimal welfare is well-behaved, the welfare of optimal (i. e. , welfare-maximizing or minimizing) equilibria is not well behaved. We thus define a related property based on a Lagrangian relaxation of the equilibrium constraints that is well behaved. We call this property Λ-stable welfare. As determining the welfare of an optimal equilibrium is an essential step in computing the price of anarchy, we conclude with a discussion of an alternative, more stable notion of anarchy based on Λ-stable welfare, which we call the anarchy gap.

NeurIPS Conference 2022 Conference Paper

Exploitability Minimization in Games and Beyond

• Denizalp Goktas
• Amy Greenwald

Pseudo-games are a natural and well-known generalization of normal-form games, in which the actions taken by each player affect not only the other players' payoffs, as in games, but also the other players' strategy sets. The solution concept par excellence for pseudo-games is the generalized Nash equilibrium (GNE), i. e. , a strategy profile at which each player's strategy is feasible and no player can improve their payoffs by unilaterally deviating to another strategy in the strategy set determined by the other players' strategies. The computation of GNE in pseudo-games has long been a problem of interest, due to applications in a wide variety of fields, from environmental protection to logistics to telecommunications. Although computing GNE is PPAD-hard in general, it is still of interest to try to compute them in restricted classes of pseudo-games. One approach is to search for a strategy profile that minimizes exploitability, i. e. , the sum of the regrets across all players. As exploitability is nondifferentiable in general, developing efficient first-order methods that minimize it might not seem possible at first glance. We observe, however, that the exploitability-minimization problem can be recast as a min-max optimization problem, and thereby obtain polynomial-time first-order methods to compute a refinement of GNE, namely the variational equilibria (VE), in convex-concave cumulative regret pseudo-games with jointly convex constraints. More generally, we also show that our methods find the stationary points of the exploitability in polynomial time in Lipschitz-smooth pseudo-games with jointly convex constraints. Finally, we demonstrate in experiments that our methods not only outperform known algorithms, but that even in pseudo-games where they are not guaranteed to converge to a GNE, they may do so nonetheless, with proper initialization.

AAMAS Conference 2022 Conference Paper

Robust No-Regret Learning in Min-Max Stackelberg Games

• Denizalp Goktas
• Jiayi Zhao
• Amy Greenwald

The behavior of no-regret learning algorithms is well understood in two-player min-max (i. e, zero-sum) games. In this paper, we investigate the behavior of no-regret learning in min-max games with dependent strategy sets, where the strategy of the� rst player constrains the behavior of the second. Such games are best understood as sequential, i. e. , min-max Stackelberg, games. We consider two settings, one in which only the� rst player chooses their actions using a no-regret algorithm while the second player best responds, and one in which both players use no-regret algorithms. For the former case, we show that no-regret dynamics converge to a Stackelberg equilibrium. For the latter case, we introduce a new type of regret, which we call Lagrangian regret, and show that if both players minimize their Lagrangian regrets, then play converges to a Stackelberg equilibrium. We then observe that online mirror descent (OMD) dynamics in these two settings correspond respectively to a known nested (i. e. , sequential) gradient descent-ascent (GDA) algorithm and a new simultaneous GDA-like algorithm, thereby establishing convergence of these algorithms to Stackelberg equilibrium. Finally, we analyze the robustness of OMD dynamics to perturbations by investigating online min-max Stackelberg games. We prove that OMD dynamics are robust for a large class of online min-max games with independent strategy sets. In the dependent case, we demonstrate the robustness of OMD dynamics experimentally by simulating them in online Fisher markets, a canonical example of a min-max Stackelberg game with dependent strategy sets.

NeurIPS Conference 2022 Conference Paper

Zero-Sum Stochastic Stackelberg Games

• Denizalp Goktas
• Sadie Zhao
• Amy Greenwald

Zero-sum stochastic games have found important applications in a variety of fields, from machine learning to economics. Work on this model has primarily focused on the computation of Nash equilibrium due to its effectiveness in solving adversarial board and video games. Unfortunately, a Nash equilibrium is not guaranteed to exist in zero-sum stochastic games when the payoffs at each state are not convex-concave in the players' actions. A Stackelberg equilibrium, however, is guaranteed to exist. Consequently, in this paper, we study zero-sum stochastic Stackelberg games. Going beyond known existence results for (non-stationary) Stackelberg equilibria, we prove the existence of recursive (i. e. , Markov perfect) Stackelberg equilibria (recSE) in these games, provide necessary and sufficient conditions for a policy profile to be a recSE, and show that recSE can be computed in (weakly) polynomial time via value iteration. Finally, we show that zero-sum stochastic Stackelberg games can model the problem of pricing and allocating goods across agents and time. More specifically, we propose a zero-sum stochastic Stackelberg game whose recSE correspond to the recursive competitive equilibria of a large class of stochastic Fisher markets. We close with a series of experiments that showcase how our methodology can be used to solve the consumption-savings problem in stochastic Fisher markets.

NeurIPS Conference 2021 Conference Paper

Convex-Concave Min-Max Stackelberg Games

• Denizalp Goktas
• Amy Greenwald

Min-max optimization problems (i. e. , min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald’s maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.

ICML Conference 2021 Conference Paper

Efficient Deviation Types and Learning for Hindsight Rationality in Extensive-Form Games

• Dustin Morrill
• Ryan D'Orazio
• Marc Lanctot
• James R. Wright
• Michael H. Bowling
• Amy Greenwald

Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.

AAMAS Conference 2021 Conference Paper

Learning Competitive Equilibria in Noisy Combinatorial Markets

• Enrique Areyan Viqueira
• Cyrus Cousins
• Amy Greenwald

We present a methodology to robustly estimate the competitive equilibria (CE) of combinatorial markets under the assumption that buyers do not know their precise valuations for bundles of goods, but instead can only provide noisy estimates. We first show tight lower- and upper-bounds on the buyers’ utility loss, and hence the set of CE, given a uniform approximation of one market by another. We then present two probably-approximately-correct algorithms for learning CE with finite-sample guarantees. The first is a baseline and the second leverages a connection between the first welfare theorem of economics and uniform approximations to adaptively prune value queries when it is determined that they are provably not part of a CE. Extensive experimentation shows that pruning achieves better estimates than the baseline with far fewer samples.

UAI Conference 2019 Conference Paper

Empirical Mechanism Design: Designing Mechanisms from Data

• Enrique Areyan Viqueira
• Cyrus Cousins
• Yasser Mohammad
• Amy Greenwald

We introduce a methodology for the design of parametric mechanisms, which are multiagent systems inhabited by strategic agents, with knobs that can be adjusted to achieve specific goals. We assume agents play approximate equilibria, which we estimate using the probably approximately correct learning framework. Under this assumption, we further learn approximately optimal mechanism parameters. We do this theoretically, assuming a finite design space, and heuristically, using Bayesian optimization (BO). Our BO algorithm incorporates the noise associated with modern concentration inequalities, such as Hoeffding’s, into the underlying Gaussian process. We show experimentally that our search techniques outperform standard baselines in a stylized but rich model of advertisement exchanges.

RLDM Conference 2019 Conference Abstract

Inverse Reinforcement Learning from a Learning Agent

• Vincent T Kubala
• George Konidaris
• Amy Greenwald

We consider the problem of inferring the reward function and predicting the future behavior of an agent that is learning. To do this, we generalize an existing Bayesian inverse reinforcement learning algorithm to allow the demonstrator’s policy to change over time, as a function of their experiences and to simultaneously infer the actor’s reward function and methods of learning and making decisions. We show experimentally that our algorithm outperforms its inverse reinforcement learning counterpart.

AAMAS Conference 2019 Conference Paper

Learning Simulation-Based Games from Data

• Enrique Areyan Viqueira
• Amy Greenwald
• Cyrus Cousins
• Eli Upfal

We tackle a fundamental problem in empirical game-theoretic analysis (EGTA), that of learning equilibria of simulation-based games. Such games cannot be described in analytical form; instead, a blackbox simulator can be queried to obtain noisy samples of utilities. Our approach to EGTA is in the spirit of probably approximately correct learning. We design algorithms that learn empirical games, which uniformly approximate the utilities of simulation-based games from finitely many samples. Our methodology learns all the equilibria of simulation-based games, as opposed to a single one.

RLDM Conference 2017 Conference Abstract

Generalized Inverse Reinforcement Learning

• Nakul Gopalan
• Amy Greenwald
• Michael Littman
• James MacGlashan

Inverse Reinforcement Learning (IRL) is used to teach behaviors to agents, by having them learn a reward function from example trajectories. The underlying assumption is usually that these trajectories represent optimal behavior. However, it is not always possible for a user to provide examples of optimal trajectories. This problem has been tackled previously by labeling trajectories with a score that indicates good and bad behaviors. In this work, we formalize the IRL problem in a generalized framework that allows for learning from failed demonstrations. In our framework, users can score entire trajectories as well as individual state-action pairs. This allows the agent to learn preferred behaviors from a relatively small number of trajectories. We expect this framework to be especially useful in robotics domains, where the user can collect fewer trajectories at the cost of labeling bad state-action pairs, which might be easier than maneuvering a robot to collect additional (entire) trajectories.

AAMAS Conference 2017 Conference Paper

On Approximate Welfare- and Revenue-Maximizing Equilibria for Size-Interchangeable Bidders

• Enrique Areyan Viqueira
• Amy Greenwald
• Victor Naroditskiy

This paper introduces a novel relaxation of Walrasian equilibrium (WE) which we call Restricted Envy-Free Pricing (REFP), an algorithm to compute this outcome for the case of size-interchangeable bidders (a generalization of singleminded bidders introduced in this paper), and a heuristic for searching among these outcomes for one that maximizes revenue. We provide theoretical bounds for our algorithms where possible, and run extensive experiments to evaluate their performance on both a synthetic distribution, and one obtained from real-world web-usage data. Compared to other benchmarks in the literature, our algorithms perform well on the metrics of revenue and efficiency, without incurring too many violations of the true WE conditions.

ECAI Conference 2014 Conference Paper

An Algorithm for the Penalized Multiple Choice Knapsack Problem

• Elizabeth Hilliard
• Amy Greenwald
• Victor Naroditskiy

We present an algorithm for the penalized multiple choice knapsack problem (PMCKP), a combination of the more common penalized knapsack problem (PKP) and multiple choice knapsack problem (MCKP). Our approach is to converts a PMCKP into a PKP using a previously known transformation between MCKP and KP, and then solve the PKP greedily. For PMCKPs with well-behaved penalty functions, our algorithm is optimal for the linear relaxation of the problem.

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.

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.

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.

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.

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.

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.

ICML Conference 2008 Conference Paper

No-regret learning in convex games

• Geoffrey J. Gordon
• Amy Greenwald
• Casey Marks

IJCAI Conference 2007 Conference Paper

• Seong Jae Lee
• Amy Greenwald
• Victor Naroditskiy

In this paper, we describe our entrant in the travel division of the 2006 Trading Agent Competition (TAC). At a high level, the design of many successful autonomous trading agents can be summarized as follows: (i)~price prediction: build a model of market prices; and (ii)~optimization: solve for an approximately optimal set of bids, given this model. To predict, we simulate simultaneous ascending auctions. To optimize, we apply the sample average approximation method. Both of these procedures might naturally be abbreviated SAA; hence the title of this paper. Our agent dominated the preliminary and seeding rounds of TAC Travel in 2006, and emerged as champion in the finals in a photo finish.

AIJ Journal 2007 Journal Article

A hierarchy of prescriptive goals for multiagent learning

• Martin Zinkevich
• Amy Greenwald
• Michael L. Littman

A great deal of theoretical effort in multiagent learning involves either embracing or avoiding the inherent symmetry between the problem and the solution. Regret minimization is an approach to the prescriptive, non-cooperative goal that explicitly breaks this symmetry, but, since it makes no assumptions about the adversary, it achieves only limited guarantees. In this paper, we consider a hierarchy of goals that begins with the basics of regret minimization and moves towards the utility guarantees achievable by agents that could also guarantee converging to a game-theoretic equilibrium.

UAI Conference 2005 Conference Paper

An Algorithm for Computing Stochastically Stable Distributions with Applications to Multiagent Learning in Repeated Games

• John R. Wicks
• Amy Greenwald

One of the proposed solutions to the equilibrium selection problem for agents learning in repeated games is obtained via the notion of stochastic stability. Learning algorithms are perturbed so that the Markov chain underlying the learning dynamics is necessarily irreducible and yields a unique stable distribution. The stochastically stable distribution is the limit of these stable distributions as the perturbation rate tends to zero. We present the first exact algorithm for computing the stochastically stable distribution of a Markov chain. We use our algorithm to predict the long-term dynamics of simple learning algorithms in sample repeated games.

NeurIPS Conference 2005 Conference Paper

Cyclic Equilibria in Markov Games

• Martin Zinkevich
• Amy Greenwald
• Michael Littman

Although variants of value iteration have been proposed for finding Nash or correlated equilibria in general-sum Markov games, these variants have not been shown to be effective in general. In this paper, we demon- strate by construction that existing variants of value iteration cannot find stationary equilibrium policies in arbitrary general-sum Markov games. Instead, we propose an alternative interpretation of the output of value it- eration based on a new (non-stationary) equilibrium concept that we call “cyclic equilibria. ” We prove that value iteration identifies cyclic equi- libria in a class of games in which it fails to find stationary equilibria. We also demonstrate empirically that value iteration finds cyclic equilibria in nearly all examples drawn from a random distribution of Markov games.

UAI Conference 2004 Conference Paper

Bidding under Uncertainty: Theory and Experiments

• Amy Greenwald
• Justin A. Boyan

This paper describes a study of agent bidding strategies, assuming combinatorial valuations for complementary and substitutable goods, in three auction environments: sequential auctions, simultaneous auctions, and the Trading Agent Competition (TAC) Classic hotel auction design, a hybrid of sequential and simultaneous auctions. The problem of bidding in sequential auctions is formulated as an MDP, and it is argued that expected marginal utility bidding is the optimal bidding policy. The problem of bidding in simultaneous auctions is formulated as a stochastic program, and it is shown by example that marginal utility bidding is not an optimal bidding policy, even in deterministic settings. Two alternative methods of approximating a solution to this stochastic program are presented: the first method, which relies on expected values, is optimal in deterministic environments; the second method, which samples the nondeterministic environment, is asymptotically optimal as the number of samples tends to infinity. Finally, experiments with these various bidding policies are described in the TAC Classic setting.

AAMAS Conference 2004 Conference Paper

Botticelli: A Supply Chain Management Agent

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

IJCAI Conference 2003 Conference Paper

Bidding Marginal Utility in Simultaneous Auctions

• Amy Greenwald

ICML Conference 2003 Conference Paper

Correlated Q-Learning

• Amy Greenwald
• Keith Hall

ICML Conference 2001 Conference Paper

On No-Regret Learning, Fictitious Play, and Nash Equilibrium

• Amir Jafari
• Amy Greenwald
• David Gondek
• Gunes Ercal