Workshop on Risk Aversion in Algorithmic Game Theory and Mechanism Design
June 7, 2012, Valencia, Spain. (in conjunction with ACM-EC 2012)

[Synopsis] [Dates] [Schedule] [Plenary talk] [Abstracts] [CFP] [Organization]

Synopsis

The Von-Neumann Morgenstern expected utility theory addresses risk aversion by concave utility functions for wealth. Non-expected utility theories, originally posed because of various "paradoxes" such as the Allais paradox, provide alternative answers to human concerns. Finance has taken a different direction altogether, from the Markowitz mean-variance framework to the recent developments on coherent measures of risk.

The purpose of this workshop is to immingle different communities: (a) The CS oriented AGT community (b) The Finance oriented community, and (c) the non-EUT community such as those dealing with prospect theory. Hopefully, this will lead to profitable interaction between these (rather disjoint) communities.

The workshop will be held in conjunction with the ACM Conference on Electronic Commerce.

Dates

Submission DeadlineTuesday, April 10th
Acceptance NotificationMonday, April 30th
WorkshopThursday, June 7th

Schedule

9:00-9:50 Contributed Session. Various topics.
Othman, Sandholm: Inventory-based versus Prior-based Options Trading Agents
Chitnis, Hajiaghayi, Katz, Mukherjee: A Game-Theoretic Model Motivated by the DARPA Network Challenge
Coffee break
10:30-11:40 Plenary talk: Garud Iyengar: Optimizing with Risk Measures
11:40-12:30 Contributed Session. Network Routing.
Hoy: The concavity of atomic splittable congestion games with non-linear utility functions
Gui, Ergun: A Robustness Analysis of a Capacity Exchange Mechanism in Multicommodity Networks under Demand Uncertainty
Lunch break
2:00-3:15 Contributed Session. Mechanism Design.
Dughmi, Peres: Mechanisms for Risk Averse Agents, Without Loss
Bhalgat, Chakraborty, Khanna: Mechanism Design and Risk Aversion
Azar, Micali: Optimal Parametric Auctions

Abstracts

Mechanism Design and Risk Aversion (pdf)
by Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna.

We develop efficient algorithms to construct utility maximizing mechanisms in the presence of risk averse players (buyers and sellers) in Bayesian single parameter and multi-parameter settings. We model risk aversion by a concave utility function, and players play strategically to maximize their expected utility. Bayesian mechanism design has usually focused on maximizing expected revenue in a {\em risk neutral} environment, {\em i.e.} where all the buyers and the seller have linear utility, and no succinct characterization of expected utility maximizing mechanisms is known even for single-parameter multi-unit auctions.

We first consider the problem of designing optimal DSIC (dominant strategy incentive compatible) mechanism for a risk averse seller in the case of multi-unit auctions, and we give a poly-time computable deterministic sequential posted pricing mechanism (SPM) that for any $\eps > 0$, yields a $(1-1/e-\eps)$-approximation to the expected utility of the seller in an optimal DSIC mechanism. Our result is based on a novel application of a correlation gap bound, along with {\em splitting} and {\em merging} of random variables to redistribute probability mass across buyers. This allows us to reduce our problem to that of checking feasibility of a small number of distinct configurations, each of which corresponds to a covering LP. A feasible solution to the LP gives us the distribution on prices for each buyer to use in a randomized SPM. We get a deterministic SPM by sampling from this randomized SPM. Our techniques extend to the multi-parameter setting with unit demand buyers.

We next consider the setting when buyers as well as the seller are risk averse, and the objective is to maximize the seller's expected utility. We design a truthful-in-expectation mechanism whose utility is a $\left(\left(1-\frac{1}{e}\right)^2\times\max\left(1-\frac{1}{e}, 1-\frac{1}{\sqrt{2\pi k}}\right)\right)$-approximation to the optimal BIC mechanism under two mild assumptions: (a) ex post individual rationality and (b) no positive transfers. Our mechanism consists of multiple rounds. It considers each buyer in a round with small probability, and when a buyer is considered, it allocates an item to the buyer according to payment functions that are computed using stochastic techniques developed for DSIC mechanisms. Lastly, we consider the problem of revenue maximization for a risk neutral seller in presence of risk averse buyers, and give a poly-time algorithm to construct a truthful-in-expectation mechanism whose expected revenue is a $\max\left(1-\frac{1}{e}, 1-\frac{1}{\sqrt{2\pi k}}\right)$-approximation to the expected revenue of the optimal BIC mechanism, bounding the gap between these two classes of mechanisms.

We believe that the techniques developed in this work will be useful in handling other stochastic optimization problems with a concave objective function.

Optimal Parametric Auctions
by Pablo Azar and Silvio Micali.

We study the problem of an auctioneer who wants to maximize her pro ts. In our model, there are n buyers with private valuations drawn from independent distributions. When these distributions are known to the seller, Myerson's optimal auction [20] is a well known mechanism that maximizes revenue. However, in many cases it is too strong to assume that the seller knows these distributions.

We propose an alternative model where the seller only knows the mean and variance of each distribution. We call mechanisms that only use this information parametric auctions. We construct such auctions for settings where the seller only has one copy of the good to sell, and when she has an infinite number of identical copies of the good (digital auctions). For a very large class of distributions, including (but not limited to) distributions with a monotone hazard rate, our auctions achieve a constant fraction of the revenue of Myerson's auction.

When the seller has absolutely no knowledge about the distributions, it is well known that no auction can achieve a constant fraction of the optimal revenue when the players are not identically distributed. Our parametric model gives the seller a small amount of extra information, allowing her to construct auctions for which (1) she does not know the full distribution of valuations, (2) no two bidders need to be drawn from identical distributions and (3) the revenue obtained is a constant fraction of the revenue in Myerson's optimal auction.

In addition to being competitive with traditional benchmarks, our digital parametric auction is optimal in a new sense, which we call maximin optimality. Informally, an auction is maximin optimal if it maximizes revenue in the worst case over an adversary's choice of the distribution. We show that our digital parametric is maximin optimality among the class of posted price mechanisms.

Our techniques include using Chebyshev-type inequalities to give bounds on the optimal reserve prices. These techniques have not been used before in auction theory, and might be of independent interest.

A Game-Theoretic Model Motivated by the DARPA Network Challenge (pdf)
by Rajesh Chitnis, MohammadTaghi Hajiaghayi, Jonathan Katz, Koyel Mukherjee.

In this paper we propose a game-theoretic model to analyze events similar to the 2009 \emph{DARPA Network Challenge}~\cite{darpa-website}, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring the roles that the Internet and social networks play in incentivizing wide-area collaborations. The challenge was to form a group that would be the first to find the locations of ten moored weather balloons across the United States. We consider a model in which $N$ people are located in the space with a fixed coverage volume around each person's geographical location, and these people can join together to form groups. A balloon is placed in the space and a group wins if it is the first one to report the location of the balloon. A larger team has a higher probability of finding the balloon, but the prize money is divided equally among the team members and hence there is a competing tension to keep teams as small as possible. We analyze this model under a natural set of utilities, and under the assumption that the players are \emph{risk averse}. Risk aversion is the reluctance of a person to accept a bargain with an uncertain payoff rather than another bargain with a more certain, but possibly lower, expected payoff. We are interested in analyzing the structures of the groups in Nash equilibria for our model. We show if the game is played in the one-dimensional space (line), or more generally in the $d$-dimensional Euclidean space for any $d\geq 1$, then in any Nash equilibrium there always exists a group covering a constant fraction of the total volume. In the discrete version, the players are located at the vertices of a graph and each vertex can cover itself and all its neighbors. For the class of bounded-degree regular graphs, we show in any Nash equilibrium there always exists a group covering a constant fraction of the total number of vertices. Our techniques do not generalize to all graphs: we give explicit examples of graphs where our techniques fail. We believe for general graphs there exists a Nash equilibrium such that no group covers a constant fraction of the total number of vertices, and show this under the assumption that defecting to an empty group is not allowed.

Mechanisms for Risk Averse Agents, Without Loss (pdf)
by Shaddin Dughmi and Yuval Peres.

A Robustness Analysis of a Capacity Exchange Mechanism in Multicommodity Networks under Demand Uncertainty
by Luyi Gui and Ozlem Ergun.

We study the coordination of a decentralized multicommodity network system where the edge capacity is individually owned but can be accessed by all participants for their own routing operations. In particular, we consider designing a capacity exchange mechanism under which capacity is traded according to predetermined unit prices. The goal is to maximize the social efficiency, measured by the total routing revenue, of the flow composed by individual players selfish routing of their own commodities motivated by the mechanism. A practical challenge to do this arises from uncertainties in demand, as in many cases the mechanism is designed before the demand is revealed. Hence, it is desirable that the capacity exchange mechanism is robust, i.e., it can effectively coordinate the network under all potential demand scenarios using a fixed set of exchange prices. This task becomes more challenging as in practice, there often exists a certain level of information asymmetry between the mechanism designer and the players about demand. In this paper, we perform the following two studies on the robustness of the capacity exchange mechanism under demand uncertainty. First, we characterize how network structure affects the robustness of the mechanism. Second, we investigate the computational side of designing a robust capacity exchange mechanism in any given network. In particular, we propose a general pricing algorithm and quantify the routing performance under the resulting prices by providing bounds to the expected total revenue and the degree of potential capacity violation in the network.

The concavity of atomic splittable congestion games with non-linear utility functions
by Darrell Hoy.

Classical work in network congestion games assumes networks are deterministic and agents are risk-neutral. In many settings, this is unrealistic and players have more complicated preferences. When driving to work in the morning, a commuter may prefer a safer route, rather than the faster but riskier route. A website sending out streaming video packets may not care about packets once they are late or derive much bene t from packets arriving much earlier, but would rather prefer a more consistent delivery model.

We consider the atomic-splittable setting and model these preferences in two ways: when players have non-linear preferences over (i) the delay on every path, and (ii) on the total delay they experience over all paths. We ask - when are these games concave?

In the risk-neutral setting, the concavity of the setting underlies many results, including the existence of pure Nash equilibria. In setting (ii), when players have preferences over the total cost seen, the game is concave and pure Nash equilibria will always exist. In setting (i) however, we show that the game is no longer concave, and as a result we no longer know if pure Nash equilibria always exist. In both of these settings, we show that we can reduce questions about them in the stochastic setting to questions about them in the deterministic setting.

Inventory-based versus Prior-based Options Trading Agents
by Abraham Othman and Tuomas Sandholm.

Options are a basic, widely-traded form of financial derivative that offer payouts based on the future price of an underlying asset. The finance literature gives us option-trading algorithms that take into consideration information about how prices move over time but do not explicitly involve the trades the agent made in the past. In contrast, the prediction market literature gives us automated market-making agents (like the popular LMSR) that are event-independent and price trades based only on the inventories the agent holds. We simulate the performance of five trading agents inspired by these literatures on a large database of recent historical option prices. We find that a combination of the two approaches produced the best results in our experiments: a trading agent that keeps track of previously-made trades combined with a good prior distribution on how prices move over time. The experimental success of this synthesized trader has implications for agent design in both financial and prediction markets.

Call for papers

The conference is soliciting full papers on the topics outlined above. Submitted papers will be evaluated on significance, originality, technical quality, and exposition. The workshop will not have an archival proceedings and will consider papers simultaneously submitted for publication elsewhere subject to their expected publication being after June 8th, 2011 (the last day of the Conference on Electronic Commerce). To receive full consideration papers should be submitted to risk.workshop.2012@gmail.com by April 10. Notification of accepted papers will be on April 30.

Organization

Organizers: Amos Fiat (Tel Aviv University), Evdokia Nikolova (Texas A&M University), Nicolas Stier-Moses (Columbia University, Universidad di Tella)

Program Committee: Saeed Alaei (University of Maryland-College Park), Amos Fiat (Tel Aviv University), Evdokia Nikolova (Texas A&M University), Georgios Piliouras (Georgia Institute of Technology), Nicolas Stier-Moses (Columbia University, Universidad di Tella), Mukund Sundararajan (Google), Chaitanya Swamy (University of Waterloo).