# EconCS Fall 2013

We meet on **Tuesdays at 12:30** during the Fall 2013 semester, in **531 Cory Hall** (the Wang Room).

Feel free to join the mailing list at lists.berkeley.edu.

If you would like to speak, please contact the organizers: ` {alexpsomi,aviad}@cs.berkeley.edu`

The Econ-CS lunch is sponsored by Yahoo! Labs !!

**
Dec 3 |
Inbal Talgam Cohen (Stanford)
on
showInterdependent Values and Robustness in Optimal and Near-Optimal Mechanism Design.
**

The algorithmic game theory community has largely focused on independent and private values (IPV) as a model for bidders' values in an auction. A more general model is the classic model of interdependent values [Milgrom and Weber, '82], which better captures many real-life, high-stake auctions. We make first steps towards extending the rich IPV-based theory to interdependent values. In the context of revenue-optimal mechanism design, we show conditions under which Myerson's optimal mechanism can be applied to interdependent values. One of these conditions is robustness of the truthfulness and individual rationality guarantees, in the sense that they are required to hold ex post. We then consider an even more robust class of mechanisms called "prior independent" (a.k.a. "detail free"), and show that by simply using one of the bidders to set a reserve, it's possible to extract near-optimal revenue in an interdependent values setting. This shows that a considerable level of robustness is achievable for general values in single-parameter settings.

**
Nov 26 |
Bill Zame (UCLA)
on
showLearning Through Actions.
**

The radio spectrum is a scarce resource. Cognitive radio stretches this resource by enabling secondary stations to operate in portions of the spectrum that are reserved for primary stations but not currently used by the primary stations. As it is whenever stations share resources, coordination is a central issue in cognitive radio networks: absent coordination, there may be collision, congestion or interference, with concomitant loss of performance. Cognitive radio networks require coordination of secondary stations with primary stations (so that secondary stations should not interfere with primary stations) and of secondary stations with each other. Coordination in this setting is especially challenging because of the various types of sensing errors. This paper proposes novel protocols that enable secondary stations to learn and teach with the goal of coordinating to achieve a round-robin Time Division Multiple Access (TDMA) schedule. These protocols are completely distributed (requiring neither central control nor the exchange of any control messages), fast (with speeds exceeding those of existing protocols), efﬁcient (in terms of throughput and delay) and scalable. The protocols proposed rely on cooperative learning, exploiting the ability of stations to learn from and condition on their own histories while simultaneously teaching other stations about these histories. Analytic results and simulations illustrate the power of these protocols.

**
Nov 19 |
Hal Varian(Google)
on
showWhat machine learning and econometrics can learn from each other. ( video )
**

This talk reviews the major themes in econometrics and machine learning and lays out the research opportunities that seem to be the most promising. Assuming the audience is mostly computer scientists, I will focus primarily on the econometrics side. Note: this talk is highly preliminary and I look forward to an animated discussion.

**
Nov 12 |
Vasilis Gkatzelis(Stanford)
on
showMechanism Design for Fair Division.
**

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option. For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1/e \approx 0.368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0.5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design.

Joint work with Richard Cole and Gagan Goel that appeared at ACM EC 2013 and AAMAS 2013

**
Nov 5 |
Christos Papadimitriou(UC Berkeley)
on
showSome complexity conjectures between P and NP.
**

While waiting for progress in P vs NP, it is worthwhile to look at some interesting questions lying between the two. In this talk I review complexity classes such as PPAD and CLS, containing many problems related to economics, games, and sophisticated optimization. I will point out a few fruits which appear from a distance to be hanging not too high, involving both completeness and the development of polynomial algorithms.

**
Oct 29 |
No talk. Overlap with FOCS.
**

**
Oct 22 |
Paul Dütting(Stanford)
on
showExpressiveness and Robustness of First-Price Position Auctions.
**

Since economic mechanisms are often applied to very different instances of the same problem, it is desirable to identify mechanisms that work well in a wide range of circumstances. We pursue this goal for a position auction setting and specifically seek mechanisms that guarantee good outcomes under both complete and incomplete information. A variant of the generalized first-price mechanism with multi-dimensional bids turns out to be the only standard mechanism able to achieve this goal, even when types are one-dimensional. The fact that expressiveness beyond the type space is both necessary and sufficient for this kind of robustness provides an interesting counterpoint to previous work on position auctions that has highlighted the benefits of simplicity. From a technical perspective our results are interesting because they establish equilibrium existence for a multi-dimensional bid space, where standard techniques break down. The structure of the equilibrium bids moreover provides an intuitive explanation for why first-price payments may be able to support equilibria in a wider range of circumstances than second-price payments.

Joint work with Felix Fischer and David C. Parkes

**
Oct 15 |
Bo Cowgill(UC Berkeley)
on
showCorporate Prediction Markets: Evidence from Google, Ford, and [Acme] Industries.
**

Despite the popularity of prediction markets among economists, businesses and policymakers have been slow to adopt them in decision making. Most studies of prediction markets outside the lab are from public markets with large trading populations. Corporate prediction markets face additional issues, such as thinness, weak incentives, limited entry and the potential for traders with ulterior motives – raising questions about how well these markets will perform. We examine data from prediction markets run by Google, Ford and [Acme] Industries. Despite theoretically adverse conditions, we find these markets are relatively efficient, and improve upon the forecasts of experts at all three firms by as much as a 25% reduction in mean squared error. The most notable inefficiency is an optimism bias in the markets at Google and Ford. The inefficiencies that do exist generally become smaller over time. More experienced traders and those with higher past performance trade against the identified inefficiencies, suggesting that the markets’ efficiency improves because traders gain experience and less skilled traders exit the market.

**
Oct 8 |
Vijay Kamble(UC Berkeley)
on
showDynamic Relevance Maximization in Online Advertisement with User Feedback.
**

We propose a generic ad allocation mechanism that effectively utilizes the targeted user tracking that is possible in online video in order to optimize user experience. A common feature observed in this setting is that a user is being successively presented with ads during a play session and the service either explicitly or implicitly elicits a binary feedback about the relevance while showing each ad. We consider the twofold objective of maximizing the expected number of relevant ads shown to the user during a session while at the same time generating revenue from strategic advertisers. A separation is achieved in these two goals by assuming that ads can be divided into categories (e.g. cars, insurance etc.) and user preferences are sensitive to categories rather than individual ads. This inspires a two layered mechanism: the lower layer adaptively selects categories of advertisers to optimize the relevance feedback from the user and the upper layer is a truthful auction mechanism that allots ad opportunities to advertisers in the categories chosen by the lower layer, charging them contingent on relevance.

The main focus of our work is the analysis of relevance optimization problem solved by the lower layer. This is a multi-armed bandit type problem that is computationally prohibitive to solve exactly. Nevertheless, using probabilistic interchange arguments, we prove key structural properties of the optimal policy. Using these properties, we prove our main result that in the case where the dynamics of the user in a session is memoryless, an appropriately defined greedy algorithm achieves a constant factor of the optimal payoff. We finally discuss other scenarios where our mechanism and its analysis can be easily extended.

**
Oct 1 |
Aviad Rubinstein (UC Berkeley)
on
showIntractability of Course Match.
**

Course Match is a course allocation mechanism based on the concept of Approximate Competitive Equilibrium from Equal Incomes (A-CEEI), and it is currently used by Wharton's MBA Program. Course Match uses a heuristic to search for an A-CEEI, and the plausibility of finding an algorithm remained unsettled. We prove that finding an A-CEEI is computationally intractable. In particular, we prove that: (1) it is PPAD-Complete to find an A-CEEI; and (2) it is NP-Complete to decide whether there exists an exact CEEI.

Joint work with Abe Othman.

**
Sep 24 |
Ron Lavi
on
showConditional Equilibrium Outcomes via Ascending Price Processes with Applications to Combinatorial Auctions with Item Bidding.
[ paper ]
**

A Walrasian equilibrium in an economy with non-identical indivisible items exists only for small classes of players' valuations (mostly "gross substitutes" valuations), and may not generally exist even with decreasing marginal values. This paper studies a relaxed notion, "conditional equilibrium", that requires individual rationality and "outward stability", i.e., a player will not want to add items to her allocation, at given prices. While a Walrasian equilibrium outcome is unconditionally stable, a conditional equilibrium outcome is stable if players cannot choose to drop only some of their allocated items.

With decreasing marginal valuations, conditional equilibrium outcomes exhibit three appealing properties: (1) An approximate version of the first welfare theorem, namely that the social welfare in any conditional equilibrium is at least half of the maximal welfare; (2) A conditional equilibrium outcome can always be obtained via a natural ascending-price process; and (3) The second welfare theorem holds: any welfare maximizing allocation is supported by a conditional equilibrium. In particular, each of the last two properties independently implies that a conditional equilibrium always exists with decreasing marginal valuations (whereas a Walrasian equilibrium generally does not exist for this common valuation class). Additional strategic foundation is provided via a strong connection to Nash equilibria of combinatorial auctions with item bidding, which enables us to strengthen results of Bhawalkar and Roughgarden (2011) for this auction game.

Given these appealing properties we ask what is a maximal valuation class that ensures the existence of a conditional equilibrium and includes unit-demand valuations. Our main technical results provide upper and lower bounds on such a class. The lower bound shows that there exists such a class that is significantly larger than gross-substitutes, and that even allows for some (limited) mixture of substitutes and complements. For three items or less our bounds are tight, implying that we completely identify the unique such class. The existence proofs are constructive, and use a "exible-ascent" auction that is based on algorithms previously suggested for "fractionally subadditive" valuations. This auction is slightly different from standard ascending auctions, as players may also decrease prices of obtained items in every iteration, as long as their overall price strictly increases.

**
Sep 17 |
Yang Cai
(UC Berkeley)
on
showAlgorithmic Multi-Dimensional Mechanism Design.
**

In his seminal paper, Myerson [1981] provides a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient. Our solution proposes a novel framework for mechanism design by reducing mechanism design problems (where one optimizes an objective function on "rational inputs") to algorithm design problems (where one optimizes an objective function on "honest inputs"). Our reduction is generic and provides a framework for many other mechanism design problems.