Yagil Engel

IJCAI Conference 2019 Conference Paper

Cap-and-Trade Emissions Regulation: A Strategic Analysis

• Frank Cheng
• Yagil Engel
• Michael P. Wellman

Cap-and-trade schemes are designed to achieve target levels of regulated emissions in a socially efficient manner. These schemes work by issuing regulatory credits and allowing firms to buy and sell them according to their relative compliance costs. Analyzing the efficacy of such schemes in concentrated industries is complicated by the strategic interactions among firms producing heterogeneous products. We tackle this complexity via an agent-based microeconomic model of the US market for personal vehicles. We calculate Nash equilibria among credits-trading strategies in a variety of scenarios and regulatory models. We find that while cap-and-trade results improves efficiency overall, consumers bear a disproportionate share of regulation cost, as firms use credit trading to segment the vehicle market. Credits trading volume decreases when firms behave more strategically, which weakens the segmentation effect.

AAAI Conference 2013 Conference Paper

Posted Prices Exchange for Display Advertising Contracts

• Yagil Engel
• Moshe Tennenholtz

We propose a new market design for display advertising contracts, based on posted prices. Our model and algorithmic framework address several major challenges: (i) the space of possible impression types is exponential in the number of attributes, which is typically large, therefore a complete price space cannot be maintained; (ii) advertisers are usually unable or reluctant to provide extensive demand (willingnessto-pay) functions, (iii) the levels of detail with which supply and demand are specified are often not identical.

AAAI Conference 2011 Conference Paper

Planning for Operational Control Systems with Predictable Exogenous Events

• Ronen Brafman
• Carmel Domshlak
• Yagil Engel
• Zohar Feldman

Various operational control systems (OCS) are naturally modeled as Markov Decision Processes. OCS often enjoy access to predictions of future events that have substantial impact on their operations. For example, reliable forecasts of extreme weather conditions are widely available, and such events can affect typical request patterns for customer response management systems, the flight and service time of airplanes, or the supply and demand patterns for electricity. The space of exogenous events impacting OCS can be very large, prohibiting their modeling within the MDP; moreover, for many of these exogenous events there is no useful predictive, probabilistic model. Realtime predictions, however, possibly with a short lead-time, are often available. In this work we motivate a model which combines offline MDP in- finite horizon planning with realtime adjustments given specific predictions of future exogenous events, and suggest a framework in which such predictions are captured and trigger real-time planning problems. We propose a number of variants of existing MDP solution algorithms, adapted to this context, and evaluate them empirically.

AAAI Conference 2010 Conference Paper

Decomposed Utility Functions and Graphical Models for Reasoning about Preferences

• Ronen Brafman
• Yagil Engel

Recently, Brafman and Engel (2009) proposed new concepts of marginal and conditional utility that obey additive analogues of the chain rule and Bayes rule, which they employed to obtain a directed graphical model of utility functions that resembles Bayes nets. In this paper we carry this analogy a step farther by showing that the notion of utility independence, built on conditional utility, satisfies identical properties to those of probabilistic independence. This allows us to formalize the construction of graphical models for utility functions, directed and undirected, and place them on the firm foundations of Pearl and Paz’s axioms of semi-graphoids. With this strong equivalence in place, we show how algorithms used for probabilistic reasoning such as Belief Propagation (Pearl 1988) can be replicated to reasoning about utilities with the same formal guarantees, and open the way to the adaptation of additional algorithms.

AAMAS Conference 2010 Conference Paper

Incentive Analysis of Approximately Efficient Allocation Algorithms

• Yevgeniy Vorobeychik
• Yagil Engel

We present a series of results providing evidence that the incentive problem with approximate VCG-based mechanismsis often not very severe. Our first result uses average-caseanalysis to show that if an algorithm can solve the allocationproblem well for a large proportion of instances, incentivesto lie essentially disappear. We next show that even if suchincentives exist, a simple enhancement of the mechanismmakes it unlikely that any player will find an improving deviation. Additionally, we offer a simulation-based techniqueto verify empirically the incentive properties of an arbitraryapproximation algorithm and demonstrate it in a specificinstance using combinatorial auction data.

AAAI Conference 2010 Conference Paper

Transferable Utility Planning Games

• Ronen Brafman
• Carmel Domshlak
• Yagil Engel
• Moshe Tennenholtz

Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.

IJCAI Conference 2009 Conference Paper

• Ronen I. Brafman
• Carmel Domshlak
• Yagil Engel
• Moshe Tennenholtz

We introduce planning games, a study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of planning games and adapt game-theoretic solution concepts to these models. In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure.

AAMAS Conference 2008 Conference Paper

Incorporating User Utility Into Sponsored-Search Auctions

• Yagil Engel
• David Maxwell Chickering

We study principled methods for incorporating user utility into the selection of sponsored search ads. We describe variations of the GSP allocation/pricing mechanism that accommodate these user utility functions, we provide interesting and useful parallels of some of the theoretical properties from the traditional GSP mechanisms in the new GSP variations, and we present simulation results that exemplify the use of the ranking system.

AAAI Conference 2006 Conference Paper

CUI Networks: A Graphical Representation for Conditional Utility Independence

• Yagil Engel

We introduce CUI networks, a compact graphical representation of utility functions over multiple attributes. CUI networks model multiattribute utility functions using the well studied and widely applicable utility independence concept. We show how conditional utility independence leads to an effective functional decomposition that can be exhibited graphically, and how local, compact data at the graph nodes can be used to calculate joint utility. We discuss aspects of elicitation and network construction, and contrast our new representation with previous graphical preference modeling.