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.

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.

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.

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.

A prevalent theme in the economics and computation literature is to identify natural price-adjustment processes by which sellers and buyers in a market can discover equilibrium prices. An example of such a process is tâtonnement, an auction-like algorithm first proposed in 1874 by French economist Walras in which sellers adjust prices based on the Marshallian demands of buyers, i.e., budget-constrained utility-maximizing demands. A dual concept in consumer theory is a buyer's Hicksian demand, i.e., consumptions that minimize expenditure while achieving a desired utility level. In this paper, we identify the maximum of the absolute value of the elasticity of the Hicksian demand, i.e., the maximum percentage change in the Hicksian demand of any good w.r.t. the change in the price of some other good, as an economic parameter sufficient to capture and explain a range of convergent and non-convergent tâtonnement behaviors in a broad class of markets. In particular, we prove the convergence of tâtonnement at a rate of O((1+ε2)/T), in homothetic Fisher markets with bounded price elasticity of Hicksian demand, i.e., Fisher markets in which consumers have preferences represented by homogeneous utility functions and the price elasticity of their Hicksian demand is bounded, where ε is the maximum absolute value of the price elasticity of Hicksian demand across all buyers. Our result not only generalizes known convergence results for CES Fisher markets, but extends them to mixed nested CES markets and Fisher markets with continuous, possibly non-concave, homogeneous utility functions. Our convergence rate covers the full spectrum of nested CES utilities, including Leontief and linear utilities, unifying previously existing disparate convergence and non-convergence results. In particular, for ε = 0, i.e., Leontief markets, we recover the best-known convergence rate of O(1/T), and as ε → ∞, e.g., linear Fisher markets, we obtain non-convergent behavior, as expected.

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.

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.

Driven by recent successes in two-player, zero-sum game solving and playing, artificial intelligence work on games has increasingly focused on algorithms that produce equilibrium-based strategies. However, this approach has been less effective at producing competent players in general-sum games or those with more than two players than in two-player, zero-sum games. An appealing alternative is to consider adaptive algorithms that ensure strong performance in hindsight relative to what could have been achieved with modified behavior. This approach also leads to a game-theoretic analysis, but in the correlated play that arises from joint learning dynamics rather than factored agent behavior at equilibrium. We develop and advocate for this hindsight rationality framing of learning in general sequential decision-making settings. To this end, we re-examine mediated equilibrium and deviation types in extensive-form games, thereby gaining a more complete understanding and resolving past misconceptions. We present a set of examples illustrating the distinct strengths and weaknesses of each type of equilibrium in the literature, and prove that no tractable concept subsumes all others. This line of inquiry culminates in the definition of the deviation and equilibrium classes that correspond to algorithms in the counterfactual regret minimization (CFR) family, relating them to all others in the literature. Examining CFR in greater detail further leads to a new recursive definition of rationality in correlated play that extends sequential rationality in a way that naturally applies to hindsight evaluation.

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.

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.

We study an optimal contest design problem where contributors abilities are private, their costs are convex as a function of their effort, and the designer seeks to maximize their total productivity. We address the design of approximately-optimal mechanisms that are robust, in that they are independent of the ability distribution and the precise form of the cost function. We show that a very simple all-pay contest where the prize is distributed equally among the top quartile of contributors is a constant-factor approximation to the optimal, for a large class of convex cost functions, when the number of contributors is larger than some constant. This result stands in contrast to contests with linear costs, where awarding a prize to a single top contributor ("winner-takes-all»») is approximately-optimal; when costs are convex, winner-takes-all is far from optimal. We validate the performance of our approximately-optimal contest designs via simulation experiments, which uncover much better empirical performance than the worst-case guarantees. Our results are enabled by novel results in the space of optimal mechanism design with convex costs, which could be of independent interest.

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.

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.

Current autonomous bidding strategies for complex auctions typically employ a two phased architecture: first, the agent predicts a distribution over good prices, and then the agent generates bids given those predictions, usually using a heuristic. For computational reasons, previous state-of-the-art methods assumed prices were independent across goods, and then bid based on marginal price distributions. However, prices for goods are typically dependent, especially for complements and substitutes. We examine and bound the potential error from bidding with respect to marginal price distributions when good prices are in fact correlated. Then, to mitigate this error, we develop computationally feasible methods for predicting joint price distributions, and employing such predictions in bidding strategies. We also demonstrate experimentally that the state-of-the-art heuristic for bidding in simultaneous second-price sealed-bid auctions is outdone by the analog of this same heuristic bidding with respect to joint instead of marginal price predictions.

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.

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.

We study the problem of how to allocate m identical items among n > m agents, assuming each agent desires exactly one item and has a private value for consuming it. We assume the items are jointly owned by the agents, not by one uninformed center, so an auction cannot be used to solve our problem. Instead, the agents who receive items compensate those who do not.

In this paper, we describe our autonomous bidding agent, RoxyBot, who emerged victorious in the travel division of the 2006 Trading Agent Competition in a photo finish. At a high level, the design of many successful 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, RoxyBot builds a stochastic model of market prices by simulating simultaneous ascending auctions. To optimize, RoxyBot relies on the sample average approximation method, a stochastic optimization technique.

Quite a bit is known about minimizing different kinds of regret in experts problems, and how these regret types relate to types of equilibria in the multiagent setting of repeated matrix games. Much less is known about the possible kinds of regret in online convex programming problems (OCPs), or about equilibria in the analogous multiagent setting of repeated convex games. This gap is unfortunate, since convex games are much more expressive than matrix games, and since many important machine learning problems can be expressed as OCPs. In this paper, we work to close this gap: we analyze a spectrum of regret types which lie between external and swap regret, along with their corresponding equilibria, which lie between coarse correlated and correlated equilibrium. We also analyze algorithms for minimizing these regret types. As examples of our framework, we derive algorithms for learning correlated equilibria in polyhedral convex games and extensive-form correlated equilibria in extensive-form games. The former is exponentially more efficient than previous algorithms, and the latter is the first of its type.

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.

In this paper, we combine two approaches to handling uncertainty: we use techniques for finding optimal solutions in the expected sense to solve combinatorial optimization problems in an online setting. The problem we address is the scheduling component of the Trading Agent Competition in Supply Chain Management (TAC SCM) problem, a combinatorial optimization problem with inherent uncertainty (see www.sics.se/tac/). This problem is formulated as a stochastic program, and is solved using the sample average approximation (SAA) method in an online setting to find today's optimal schedule, given probabilistic models of the future. This optimization procedure forms the heart of Botticelli, one of the finalists in the TAC SCM 2003 competition. Two sets of experiments are described, using one and two days' worth of information about the future. In the two day experiments (using one day's worth of information about the future), it is shown that SAA outperforms the expected value method, which solves a deterministic variant of the problem assuming all stochastic inputs have deterministic values equal to their expected values. In the three day experiments (using two days' worth of information about the future), it is shown that SAA with look ahead outperforms greedy SAA. This approach generalizes to N days of lookahead, and since the problem setting is one of online optimization, the benefits of two day lookahead accrue rapidly.

Article Bid determination in simultaneous actions an agent architecture Share on Authors: Justin Boyan ITA Software, Cambridge, MA ITA Software, Cambridge, MAView Profile , Amy Greenwald Brown University, Providence, RI Brown University, Providence, RIView Profile Authors Info & Claims EC '01: Proceedings of the 3rd ACM conference on Electronic CommerceOctober 2001 Pages 210–212https://doi.org/10.1145/501158.501184Online:14 October 2001Publication History 12citation256DownloadsMetricsTotal Citations12Total Downloads256Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In the near future, dynamic pricing will be a common competitive maneuver. In this age of digital markets, sellers in electronic marketplaces can implement automated and frequent adjustments to prices and can easily imagine how this will increase their revenue by selling to buyers "at the right time, at the right price." But at present, most sellers do not have an adequate understanding of the performance of dynamic pricing algorithms in their marketplaces. This paper addresses this concern by analyzing the performance of two adaptive pricing algorithms. We study the behavior of these algorithms within the Learning Curve Simulator, a platform for analyzing dynamic pricing strategies in finite markets assuming various buyer behaviors. The goals of our research are twofold: (i) to explore the use of simulation as a tool to aid in the development of dynamic pricing strategies; and (ii) to explicitly identify the market conditions under which our example strategies, Goal-Directed and Derivative-Following, are successful.

This paper is concerned with computational problems that arise in the design of bidding agents for simultaneous auctions. Three natural bid determination (BD) problems are identi ed| allocation, acquisition, and completion. The rst part of the paper contains theoretical results. It is argued (i) BD in double auctions, where goods can be sold as well as bought, can be formally reduced to the problem of BD in single-sided auctions; and (ii) BD problems in simultaneous auctions are isomorphic to common variants of the winner determination problem.

Shopbots are software agents that automatically query multiple sellers on the Internet to gather information about prices and other attributes of consumer goods and services. Rapidly increasing in number and sophistication, shopbots are helping more and more buyers minimize expenditure and maximize satisfaction. In response at least partly to this trend, it is anticipated that sellers will come to rely on pricebots, automated agents that employ price-setting algorithms in an attempt to maximize profits. This paper reaches toward an understanding of strategic pricebot dynamics. More specifically, this paper is a comparative study of four candidate price-setting strategies that differ in informational and computational requirements: gametheoretic pricing (GT), myoptimal pricing (MY), derivative following (DF), and Q-learning (Q). In an effort to gain insights into the tradeoffs between practicality and pro tability of pricebot algorithms, the dynamic behavior that arises among homogeneous and heterogeneous collections of pricebots and shopbot-assisted buyers is analyzed and simulated. In homogeneous settings -- when all pricebots use the same pricing algorithm -- DFs outperform MYs and GTs. Investigation of heterogeneous collections of pricebots, however, reveals an incentive for individual DFs to deviate to MY or GT. The Q strategy exhibits superior performance to all the others since it learns to predict and account for the long-term consequences of its actions. Although the current implementation of Q is impractically expensive, techniques for achieving similar performance at greatly reduced computational cost are under investigation.