HEYMANN Benjamin

Our paper concerns the computation of Nash equilibria of first-price auctions with correlated values. While there exist several equilibrium computation methods for auctions with independent values, the correlation of the bidders' values introduces significant complications that render existing methods unsatisfactory in practice. Our contribution is a step towards filling this gap: inspired by the seminal fictitious play process of Brown and Robinson, we present a learning heuristic-that we call fictitious bidding (FB)-for estimating Bayes-Nash equilibria of first-price auctions with correlated values, and we assess the performance of this heuristic on several relevant examples.

Pearl's d-separation is a foundational notion to study conditional independence between random variables. We define the topological conditional separation and we show that it is equivalent to the d-separation, extended beyond acyclic graphs, be they finite or infinite.

Pearl's d-separation is a foundational notion to study conditional independence between random variables on directed acyclic graphs. Pearl defined the d-separation of two subsets conditionally on a third one. We show how the d-separation can be extended beyond acyclic graphs and can be expressed and characterized as a binary relation between vertices.

We propose an alternative to the tree representation of extensive form games. Games in product form represent information with σ-fields over a product set, and do not require an explicit description of the play temporality, as opposed to extensive form games on trees. This representation encompasses games with a continuum of actions, randomness and players, as well as games for which the play order cannot be determined in advance. We adapt and prove Kuhn's theorem-regarding equivalence between mixed and behavioral strategies under perfect recall-for games in product form with continuous action sets.

Optimally solving a multi-armed bandit problem suffers the curse of dimensionality. Indeed, resorting to dynamic programming leads to an exponential growth of computing time, as the number of arms and the horizon increase. We introduce a decompositioncoordination heuristic, DeCo, that turns the initial problem into parallelly coordinated one-armed bandit problems. As a consequence, we obtain a computing time which is essentially linear in the number of arms. In addition, the decomposition provides a theoretical lower bound on the regret. For the two-armed bandit case, dynamic programming provides the exact solution, which is almost matched by the DeCo heuristic. Moreover, in numerical simulations with up to 100 rounds and 20 arms, DeCo outperforms classic algorithms (Thompson sampling and Kullback-Leibler upper-confidence bound) and almost matches the theoretical lower bound on the regret for 20 arms.

Inferring the potential consequences of an unobserved event is a fundamental scientific question. To this end, Pearl's celebrated do-calculus provides a set of inference rules to derive an interventional probability from an observational one. In this framework, the primitive causal relations are encoded as functional dependencies in a Structural Causal Model (SCM), which are generally mapped into a Directed Acyclic Graph (DAG) in the absence of cycles. In this paper, by contrast, we capture causality without reference to graphs or functional dependencies, but with information fields and Witsenhausen's intrinsic model. The three rules of do-calculus reduce to a unique sufficient condition for conditional independence, the topological separation, which presents interesting theoretical and practical advantages over the d-separation. With this unique rule, we can deal with systems that cannot be represented with DAGs, for instance systems with cycles and/or 'spurious' edges. We treat an example that cannot be handled-to the extent of our knowledge-with the tools of the current literature. We also explain why, in the presence of cycles, the theory of causal inference might require different tools, depending on whether the random variables are discrete or continuous.

Inferring the potential consequences of an unobserved event is a fundamental scientific question. To this end, Pearl's celebrated do-calculus provides a set of inference rules to derive an interventional probability from an observational probability. In this framework, the primitive causal relations are encoded on a Directed Acyclic Graph (DAG), which can be limitative for some applications. In this paper, we capture causality without reference to a graph and we extend the rules of do-calculus to systems that do not possess a fixed causal ordering. For this purpose, we introduce a new framework which relies on the theory developed by Witsenhausen for multi-agent stochastic control. The mapping from graphs to so called Witsenhausen's intrinsic model is natural: the primitives of the problem are the agents' information fields. the random variables are synthesized by the agents whose strategies encode the informational constraints. All in all, our framework offers a richer language than DAGs and provides a generalized do-calculus.

We address the problem of improving bidders' strategies in prior-dependent revenue-maximizing auctions. We introduce a simple and generic method to design novel bidding strategies if the seller uses past bids to optimize her mechanism. This strategy works with general value distributions, with asymmetric bidders and for different revenue-maximizing mechanisms. Furthermore, it can be made robust to sample approximation errors on the seller part. This results in a large increase in utility for bidders whether they have a full or partial knowledge of their competitors. In the case where the buyer has no information about the competition, we propose a simple and agnostic strategy that is robust to mechanism changes and local (as opposed to global) optimization of e.g. reserve prices by the seller. In textbook-style examples, for instance with uniform value distributions and two bidders, this no-side-information and mechanism-independent strategy yields an enormous 57% increase in buyer utility for lazy second price auctions with no reserves. In the i.i.d symmetric case, we show existence and uniqueness of a Nash equilibrium in the class of strategy we consider for lazy second price auctions, as well as the corresponding explicit shading strategies. Our approach also works for Myerson auctions for instance. At this Nash equilibrium, buyer's utility is the same as in a second price auction with no reserve. Our approach also yields optimal solutions when buyer are constrained in the class of shading strategies they can use, a realistic constraint in practical applications. The heart of our approach is to see optimal auctions in practice as a Stackelberg game where the buyer is the leader, as he is the first one to move (here bid) when the seller is the follower as she has no prior information on the bidder.

We state and prove Kuhn's equivalence theorem for a new representation of games, the intrinsic form. First, we introduce games in intrinsic form where information is represented by σ-fields over a product set. For this purpose, we adapt to games the intrinsic representation that Witsenhausen introduced in control theory. Those intrinsic games do not require an explicit description of the play temporality, as opposed to extensive form games on trees. Second, we prove, for this new and more general representation of games, that behavioral and mixed strategies are equivalent under perfect recall (Kuhn's theorem). As the intrinsic form replaces the tree structure with a product structure, the handling of information is easier. This makes the intrinsic form a new valuable tool for the analysis of games with information.

In display advertising auctions, a unique display opportunity may trigger many bid requests being sent to the same buyer. Bid request duplication is an issue: programmatic bidding agents might bid against themselves. In a simplified setting of unified second-price auctions, the optimal solution for the bidder is to randomize the bid, which is quite unusual. Our results motivate the recent switch to a unified first-price auction by showing that a unified second-price auction could have been detrimental to all participants.

A large portion of online display advertising inventory is sold through real time auctions. The bidding algorithms need to estimate precisely the value of each display. Many bidding models estimate this value as the probability that a sale is attributed to this display, but this approach does not capture that a user may be shown a sequence of several displays. By mixing tools from causal reasoning and reinforcement learning to model this sequence of auctions, we derive a simple rule to improve this estimate. We test the change online in a production environment and the results validate the approach. We believe this methodology could be adapted to tackle the notoriously difficult problem of building an incremental bidder.

Attribution-the mechanism that assigns conversion credits to individual marketing interactions-is one of the foremost digital marketing research topic. Indeed, attribution is used everywhere in online marketing whether for budget decisions or for the design of algorithmic bidders that the advertiser relies on to buy inventory. Still, an attribution definition over which everyone in the marketing community agrees upon is yet to be found. In this paper, we focus on the problem faced by a bidder who is subject to an attribution black box decided by the advertiser and needs to convert it into a bid. This naturally introduces a second level of attribution, performed internally by the bidder. We first formalize an often implicitly used solution concept for this task. Second, we characterize the solution of this problem which we call the core internal attribution. Moreover, we show it can be computed using a fixed-point method. Interestingly, the core attribution is based on a notion of marginality that differs from previously used definitions such as the counterfactual marginality.

We present an algorithm to handle the optimization over a long horizon of an electric microgrid including a battery energy storage system. While the battery is an important and costly component of the microgrid, its aging process is often not taken into account by the Energy Management System, mostly because of modeling and computing challenges. We address the computing aspect by a new approach combining dynamic programming, decomposition and relaxation techniques. We illustrate this ’adaptive weight’ method with numerical simulations for a toy microgrid model. Compared to a straightforward resolution by dynamic programming, our algorithm decreases the computing time by more than one order of magnitude, can be parallelized, and allows for online implementations. We believe that this approach can be used for other applications presenting fast and slow variables.

—We propose a novel method for the microgrid energy management problem by introducing a continuous-time, rolling horizon formulation. The energy management problem is formulated as a deterministic optimal control problem (OCP). We solve (OCP) with two classical approaches: the direct method [1], and Bellman's Dynamic Programming Principle (DPP) [2]. In both cases we use the optimal control toolbox BOCOP [3] for the numerical simulations. For the DPP approach we implement a semi-Lagrangian scheme [4] adapted to handle the optimization of switching times for the on/off modes of the diesel generator. The DPP approach allows for an accurate modeling and is computationally cheap. It finds the global optimum in less than 3 seconds, a CPU time similar to the Mixed Integer Linear Programming (MILP) approach used in [5]. We achieve this performance by introducing a trick based on the Pontryagin Maximum Principle (PMP). The trick increases the computation speed by several orders and also improves the precision of the solution. For validation purposes, simulation are performed using datasets from an actual isolated microgrid located in northern Chile. Results show that DPP method is very well suited for this type of problem when compared with the MILP approach.

We present some key aspects of wholesale electricity markets modeling and more specifically focus our attention on auctions and mechanism design. Some of the results arising from those models are the computation of an optimal allocation for the Independent System Operator, the study of the equilibria (existence and unicity in particular) and the design of mechanisms to increase the social surplus. From a more general perspective, this field of research provides clues to discuss how wholesale electricity market should be regulated. We start with a general introduction and then present some results the authors obtained recently. We also briefly expose some undergoing related work. As an illustrative example, a section is devoted to the computation of the Independent System Operator response function for a symmetric binodal setting with piece-wise linear production cost functions.

We propose a novel method for the microgrid energy management problem by introducing a nonlinear, continuous-time, rolling horizon formulation. The method is linearization-free and gives a global optimal solution with closed loop controls. It allows for the modelling of switches. We formulate the energy management problem as a deterministic optimal control problem (OCP). We solve (OCP) with two classical approaches: the direct method and Bellman's Dynamic Programming Principle (DPP). In both cases we use the optimal control toolbox Bocop for the numerical simulations. For the DPP approach we implement a semi-Lagrangian scheme adapted to handle the optimization of switching times for the on/off modes of the diesel generator. The DPP approach allows for accurate modelling and is computationally cheap. It finds the global optimum in less than one second, a CPU time similar to the time needed with a Mixed Integer Linear Programming approach used in previous works. We achieve this result by introducing a 'trick' based on the Pontryagin Maximum Principle. The trick reduces the computation time by several orders and improves the precision of the solution. For validation purposes, we performed simulations on datasets from an actual isolated microgrid located in northern Chile. The result shows that the DPP method is very well suited for this type of problem.Project iCODE: "Large-scale systems and Smart grids: distributed decisionmaking" Gaspar Monge Program for Optimization and Operation Research (PGMO) laboratory Dauphine CREST EDF R&D Finance des Marches d'Energies CONICYT/FONDAP/1511001.

We propose a novel stochastic control formulation for the microgrid energy management problem and extend previous works on continuous time rolling horizon strategy to uncertain demand. We modelize the demand dynamics with a stochastic differential equation. We decompose this dynamics into three terms: an average drift, a time-dependent mean-reversion term and a Brownian noise. We use BOCOPHJB for the numerical simulations. This optimal control toolbox implements a semi-Lagrangian scheme and handle the optimization of switching times required for the discrete on/off modes of the diesel generator. The scheme allows for an accurate modelling and is computationally cheap as long as the state dimension is small. As described in previous works, we use a trick to reduce the search of the optimal control values to six points. This increases the computation speed by several orders. We compare this new formulation with the deterministic control approach introduced in [1] using data from an isolated microgrid located in northern Chile.

We present some key aspects of wholesale electricity markets modeling and more specifically focus our attention on auctions and mechanism design. Some of the results arising from those models are the computation of an optimal allocation for the Independent System Operator, the study of the equilibria (existence and unicity in particular) and the design of mechanisms to increase the social surplus. From a more general perspective, this field of research provides clues to discuss how wholesale electricity market should be regulated. We start with a general introduction and then present some results the authors obtained recently. We also briefly expose some undergoing related work. As an illustrative example, a section is devoted to the computation of the Independent System Operator response function for a symmetric binodal setting with piece-wise linear production cost functions.

Motivated by market power in electricity market we introduce a mechanism design in [1] for simplified markets of two agents with linear production cost functions. In standard procurement auctions, the market power resulting from the quadratic transmission losses allow the producers to bid above their true value (i.e.

We propose a novel stochastic control formulation for the microgrid energy management problem and extend previous works on continuous time rolling horizon strategy to uncertain demand. We modelize the demand dynamics with a stochastic differential equation. We decompose this dynamics into three terms: an average drift, a time-dependent mean-reversion term and a Brownian noise. We use BOCOPHJB for the numerical simulations. This optimal control toolbox implements a semi-Lagrangian scheme and handle the optimization of switching times required for the discrete on/off modes of the diesel generator. The scheme allows for an accurate modelling and is computationally cheap as long as the state dimension is small. As described in previous works, we use a trick to reduce the search of the optimal control values to six points. This increases the computation speed by several orders. We compare this new formulation with the deterministic control approach introduced in [1] using data from an isolated microgrid located in northern Chile.

We present our contribution on the optimization and regulation of electricity produc- tion.The first part deals with a microgrid Energy Management System (EMS). We formulate the EMS program as a continuous time optimal control problem and then solve this problem by dynamic programming using BocopHJB, a solver developed for this application. We show that an extension of this formulation to a stochastic setting is possible. The last section of this part introduces the adaptative weights dynamic programming algorithm, an algorithm for optimization problems with different time scales. We use the algorithm to integrate the battery aging in the EMS.The second part is dedicated to network markets, and in particular wholesale electricity markets. We introduce a mechanism to deal with the market power exercised by electricity producers, and thus increase the consumer welfare. Then we study some mathematical properties of the agents’ optimization problems (producers and system operator). In the last chapter, we present some pure Nash equilibrium existence and uniqueness results for a class of Bayesian games to which some networks markets belong. In addition we introduce an algorithm to compute the equilibrium for some specific cases.We provide some additional information on BocopHJB (the numerical solver developed and used in the first part of the thesis) in the appendix.

We present our contribution on the control and optimization of electricity production. The first part concerns the optimization of the management of a micro grid. We formulate the management program as an optimal control problem in continuous time, then we solve this problem by dynamic programming using a solver developed for this purpose: BocopHJB. We show that this type of formulation can be extended to a stochastic modeling. We end this part with the adaptive weights algorithm, which allows a management of the micro network battery integrating its aging. The algorithm exploits the two time scale structure of the control problem. The second part concerns networked market models, and in particular those of electricity. We introduce an incentive mechanism to decrease the market power of energy producers, to the benefit of the consumer. We study some mathematical properties of the optimization problems faced by market agents (producers and regulators). The last chapter studies the existence and uniqueness of Nash equilibria in pure strategies of a class of Bayesian games to which some network market models belong. For some simple cases, an equilibrium computation algorithm is proposed. An appendix gathers a documentation on the numerical solver BocopHJB.

The original Bocop package implements a local optimization method. The optimal control problem is approximated by a finite dimensional optimization problem (NLP) using a time discretization (the direct transcription approach). The NLP problem is solved by the well known software Ipopt, using sparse exact derivatives computed by Adol-C. The second package BocopHJB implements a global optimization method. Similarly to the Dynamic Programming approach, the optimal control problem is solved in two steps. First we solve the Hamilton-Jacobi-Bellman equation satisfied by the value fonction of the problem. Then we simulate the optimal trajectory from any chosen initial condition. The computational effort is essentially taken by the first step, whose result, the value fonction, can be stored for subsequent trajectory simulations.