The **algorithmic economics seminar** takes place at **Carnegie Mellon University**, and is generously supported by **Yahoo!** Academic Relations. The seminar's goal is to bring together computer scientists, economists, and social scientists (from Carnegie Mellon and the University of Pittsburgh) who are interested in research at the intersection of these disciplines. Each semester, **three distinguished speakers** are invited to speak at the seminar.

The seminar is organized by **Ariel Procaccia**. The talks usually take place on a Tuesday at noon (please check the schedule below). **Lunch is served** before every talk.

To receive announcements about the seminar, please join the **mailing list**.

**May 5, 2015 @ noon, Newell Simon Hall (NSH) 3305 [joint with crowdsourcing seminar]**

**Arpita Ghosh, assoc. prof. of information sciences, Cornell University**

**TBA**

**March 17, 2015 @ noon, Newell Simon Hall (NSH) 3305**

**Itai Ashlagi, asst. prof. of operations management, MIT Sloan**

**Unbalanced Random Matching Markets: The Stark Effect of Competition**

Stability is used often as a criterion in organizing clearinghouses for two-sided matching markets, where agents on both sides of the market have preferences over potential matches. We study competition in matching markets with random heterogeneous preferences by considering markets with an unequal number of agents on either side.
We show that even the slightest imbalance leads to competition that yields an essentially unique stable matching. We further show that each agent on the short side of the market is matched to one of his top preferences, and each agent on the long side does almost no better than being matched to a random partner.
Our results suggest that any matching market is likely to have a small core, explaining why empirically small cores are ubiquitous.

This is joint work with Yash Kanoria and Jacob Leshno

**January 14, 2015 @ noon, Gates Hillman Center (GHC) 6115 [joint w. theory lunch]**

**Eva Tardos, prof. of computer science, Cornell University**

**Composable Mechanisms, Learning, and Price of Anarchy in Auctions**

Selfish behavior can often lead to suboptimal outcome for all participants, a phenomenon illustrated by classical examples in game theory, such as the prisoner's dilemma. Over the last decade we have developed a good understanding of how to quantify the impact of strategic user behavior on overall performance in some concrete games. In this talk, we will consider online auctions from this perspective. A key property of this environments is that players typically participate in multiple auctions, have valuations that are complex functions of multiple outcomes, and are using learning strategies to deal with an uncertain environment. In this talk we show how to provide robust guarantees for the performance of many simple auctions even in such complex environments.

**[CANCELLED] November 18, 2014 @ noon, Gates Hillman Center (GHC) 6115**

**Arpita Ghosh, assoc. prof. of information sciences, Cornell University**

**Incentives in Online Contribution: A game-theoretic framework**

**October 29, 2014 @ noon, Gates Hillman Center (GHC) 6115 [joint w. theory lunch]**

**Noga Alon, prof. of mathematics and computer science, Tel Aviv University**

**The Complexity of Forming an Effective Government**

The theory of Social Choice investigates procedures to combine the
preferences of individuals in order to reach a collective decision.
This often leads to intriguing combinatorial and algorithmic problems.
I will illustrate this phenomenon by discussing two recent examples. The
first deals with the complexity of the problem of deciding whether or not
it is possible to form an agenda supported by a majority of the members
of a parliament with known individual preferences. The second studies
the possibilities to bias the decisions in judgment aggregation over
multiple independent issues by bundling several issues together.
Based on joint papers with Bredereck, Chen, Kratsch, Niedermeier and
Woeginger, and with Falik, Meir and Tennenholtz.

**September 23, 2014 @ noon, Gates Hillman Center (GHC) 6115 [joint w. CSD distinguished lecture series]**

**Christos Papadimitriou, prof. of electrical engineering and computer science, UC Berkeley**

**Computational Ideas and the Theory of Evolution**

Covertly computational ideas have influenced the Theory of Evolution from the very start. This talk is about recent work on Evolution that was inspired and informed by computation. Considerations about the performance of genetic algorithms led to a novel theory of the role of sex in Evolution based on the concept of mixability, while the equations describing the evolution of a species can be reinterpreted as a repeated game between genes. The complexity of local optimality informs the mystery of variation, and a theorem on Boolean functions helps us understand better the emergence of complex adaptations.

**May 13, 2014 @ noon, Newell Simon Hall (NSH) 1507**

**Michael Bowling, prof. of computer science, University of Alberta**

**Adversaries, Abstractions, and Algorithms**

The Computer Poker Research Group at the University of Alberta has for over a decade developed the strongest poker playing programs in the world. We have tested them in competition against other programs, winning 20 of 33 events since the inauguration of the AAAI Computer Poker Competition in 2006. We have also tested them against top professional players, becoming the first to beat professional poker players in a meaningful competition in 2008. Our success follows the modus operandi of the very pioneers of game theory: when facing an intractably complex game, abstract the game to a smaller one and reason in that game. "It seems to us... ", as Von Neumann and Morgenstern wrote, "its decisive properties will be conserved in our simplified form." Recently, this approach has been shown to be on shaky ground, or rather on no ground at all. In this talk, I'll be looking down to see what, if anything, the abstraction methodology can stand on; and what this line of research means for real-world applications where abstraction is step one, as well as applications that don't involve an apparent adversary.

**March 11, 2014 @ noon, Gates Hillman Center (GHC) 6115**

**Tim Roughgarden, assoc. prof. of computer science, Stanford University**

**Approximation in Algorithmic Game Theory**

Exact solutions are great when you can get them. When you
can't, allowing approximation can extend the reach of a theory.
We survey two genres of such results in algorithmic game theory:

1. Quantifying the inefficiency of equilibria. Equilibria are
generally sub-optimal (think Prisoner's Dilemma). But are they
ever guaranteed to be approximately optimal? The answer is "yes"
for a remarkably wide range of applications and equilibrium
concepts.

2. Reasoning about simple and practical auctions. Classical optimal
auction theory assumes knowledge of a common prior, and can
advocate unreasonably complex auctions. How much past data is
required to justify rigorously a Bayesian approach? Can simple
auctions, with little to no distributional dependence, perform
approximately as well?

**February 18, 2014 @ noon, Gates Hillman Center (GHC) 6115**

**Ruggiero Cavallo, research scientist, Yahoo! Research**

**Efficient Auctions with Public Budget Constraints**

In most real-world auction settings, bidders do not have unlimited money to spend on acquiring the goods they seek. In this talk I'll address how to maximize efficiency when bidders are subject to arbitrary publicly-known budget constraints. I'll start by presenting the optimal budget-feasible auction among those that make allocation decisions deterministically as a function of bids; notably, maximizing expected efficiency requires sometimes not allocating the good to an agent that is willing and able to pay more than all others. Then, expanding our scope to randomized mechanisms, I will introduce an auction that is optimal among all those that make allocation decisions based on the rank of each bid. Finally, I'll describe a simple auction that converges to perfect efficiency as the population size gets large, showing that budgets do not pose a significant obstacle to allocative efficiency in settings with lots of bidders.

**November 5, 2013 @ noon, Gates Hillman Center (GHC) 6115 [joint with CSD distinguished lecture series]**

**Jennifer Chayes, distinguished scientist, Microsoft Research New England**

**The Power of Locality for Network Algorithms**

Given the massive size of many networks, conventional algorithms which scale as polynomials in the network size are woefully inadequate. In the first part of this talk, we consider how to use locality to deliver much more efficient algorithms (quasi-linear or even sub-linear in the network size) for quantities and questions like pagerank, coverage, diffusion, and determining the most influential nodes. In this second part of this talk, we consider another aspect of locality, namely the question of local data access. Many large networks are encoded locally, e.g., with adjacency lists. How does the nature of the data access impact the efficiency of algorithms? Surprisingly, we show that small differences in data access can lead to very large differences in efficiency and approximability of network algorithms. As an example, we consider a covering problem which arises naturally for recruiters on social networks, and show how small differences between the information on neighbors in LinkedIn and Facebook lead to large differences in their utility to recruiters.

**October 15, 2013 @ noon, Gates Hillman Center (GHC) 6115**

**Steven Brams, prof. of politics, New York University**

**Fair Division: From Cake Cutting to Dispute Resolution**

I begin with an overview of the literature on the fair division of divisible goods--starting with the use of "I cut, you choose" in the Hebrew Bible--and then survey both 2-person and n-person more modern procedures, including Last Diminisher, Divide and Conquer, and Adjusted Winner.

I then turn to a new algorithm for the fair division of indivisible goods between two players, who strictly rank the goods from best to worst. Its allocations are Pareto-optimal, envy-free, and maximal. As the number of goods increases, the probability that all the goods are allocated approaches 1 if all possible rankings are equiprobable. The algorithm seems eminently applicable to real-world disputes, such as dividing the marital property in a divorce.

**September 17, 2013 @ noon, Gates Hillman Center (GHC) 6115 [joint with the Intelligence Seminar]**

**Joseph Halpern, prof. of computer science, Cornell University**

**Beyond Nash Equilibrium: Solution Concepts for the 21st Century**

Nash equilibrium is the most commonly-used notion of equilibrium in game
theory. However, it suffers from numerous problems. Some are well known
in the game theory community; for example, the Nash equilibrium of repeated
prisoner's dilemma is neither normatively nor descriptively reasonable.
However, new problems arise when considering Nash equilibrium from a
computer science perspective: for example, Nash equilibrium is not robust
(it does not tolerate "faulty" or "unexpected" behavior), it does not
deal with coalitions, it does not take computation cost into account, and
it does not deal with cases where players are not aware of all aspects of
the game. In this talk, I discuss solution concepts that try to address
these shortcomings of Nash equilibrium. This talk represents joint work
with various collaborators, including Ittai Abraham, Danny Dolev, Rica
Gonen, Rafael Pass, and Leandro Rego. No background in game theory will
be presumed.

**April 30, 2013 @ noon, Newell Simon Hall (NSH) 3305**

**Craig Boutilier, prof. of computer science, University of Toronto**

**Preference Elicitation for Social Choice: A Study in Voting and Stable Matching**

While the methods of social choice provide firm foundations for many decision
problem involving groups of individuals, their practical realization requires some means of eliciting, assessing, or learning the underlying preferences of
participants. This can impose a tremendous cognitive burden on participants,
who may be required provide precise rankings or utilities for dozens,
hundreds, or thousands of alternatives, only to discover that much of this
information has no impact on the ultimate decision.

In this talk, I will describe methods for robust optimization in social choice
problems given only partial user preference information, using the concept of
minimax regret. I will also describe techniques for effectively eliciting user
preferences, driven by the robust solutions of the partial preference
problems, that allow the computation of optimal decisions with relatively
little preference information. I will focus on the application of these
techniques to both voting and stable matching problems, emphasizing their
their use in distribution-free models, but also discussing how to exploit
probabilistic preference models to further reduce the elicitation burden. Time
permitting, I'll also briefly discuss the value of a more data-driven,
empirical perspective on social choice, and its impact on learning and the analysis of manipulation.

Joint work with Tyler Lu, Joanna Drummond.

**April 16, 2013 @ noon, Newell Simon Hall (NSH) 1507**

**Tuomas Sandholm, prof. of computer science, Carnegie Mellon University**

**Modern Dynamic Kidney Exchanges**

In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this is NP-hard. It was one of the main obstacles to a national kidney exchange. We developed an algorithm capable of clearing optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage.

Furthermore, clearing is actually a dynamic problem where patient-donor pairs and altruistic donors appear and expire over time. We first developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. Such algorithms tend to be too compute-intensive at run time, so recently we developed a general approach for giving batch algorithms guidance about the future without a run-time hit. It learns potentials of elements of the problem, and then uses them in each batch clearing.

I will share experiences from using our algorithms to run the UNOS US-wide kidney exchange and two regional ones. We introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I will present new results – both theoretical and experimental – on the role of long chains. I will also discuss a brand new optimal probabilistic planning algorithm for this domain that generates plans that are robust against last-minute execution failures.

The talk covers material from the following papers:

- Failure-Aware Kidney Exchange. EC-13. (With Dickerson, J. and Procaccia, A.)

- The Organ Procurement and Transplantation Network (OPTN) Kidney Paired Donation Pilot Program (KPDPP): Review of Current Results. American Transplant Congress (ATC), 2013. (With Leishman, R., Formica, R., Andreoni, K., Friedewald, J., Sleeman, E., Monstello, C., and Stewart, D.)

- Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. AAAI-12. (With Dickerson, J. and Procaccia, A.)

- Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. AAMAS-12. (With Dickerson, J. and Procaccia, A.)

- Online Stochastic Optimization in the Large: Application to Kidney Exchange. IJCAI-09. (With Awasthi, P.)

- A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), March 2009. (With Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Ünver, U., and Montgomery, R.)

- Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. EC-07. (With Abraham, D. and Blum, A.)

**February 26, 2013 @ noon, Newell Simon Hall (NSH) 3305**

**Vahab Mirrokni, staff research scientist, Google Research**

**Online Ad Allocation: Simultaneous Approximations, and Budget-constrained Mechanism Design**

As an important component of any ad serving system, online capacity (or budget) planning is a central problem in online ad allocation. I will survey primal-based and dual-based techniques borrowed from the online stochastic matching literature and report theoretical approximation guarantees and practical evaluations of these algorithms on real data sets. Finally, inspired by practical applications, I will discuss a two new results in the area:

(i) simultaneous approximation for both adversarial and stochastic models and recent theoretical results in this context, and (ii) computationally efficient mechanisms for dealing with budget constraints in the presence of strategic agents. Time permitting, I will conclude with some problems in advertising exchanges.

**November 27, 2012 @ noon, Newell Simon Hall (NSH) 3305**

**David Parkes, prof. of computer science, Harvard University**

**Mechanism Design as a Classification Problem**

How can machine learning be used for the design of mechanisms for
resource allocation in the presence of self-interested agents? In
this talk, I will outline a new methodology that takes as input an
allocation rule and leverages multi-class classification in order to
design a payment rule. The payment rule comes from the discriminant
function of the classifier. By defining an appropriate hypothesis
space, an exact classifier generates a strategyproof mechanism and
minimizing error corresponds to minimizing regret for truthful
participation. Given time, I will mention some challenges in extending
the approach to learn strategyproof allocation rules for use in
environments without money.

This talk is based in part on the paper "Payment Rules through Discriminant-Based Classifiers", Paul Duetting, Felix Fischer, Pichayut Jirapinyo, John K. Lai, Benjamin Lubin, and David C. Parkes, in Proc. 13th ACM Conference on Electronic Commerce (EC '12), 2012.

**November 6, 2012 @ noon, GHC 6115 [joint with the Intelligence Seminar]**

**Milind Tambe, prof. of computer science, University of Southern California**

**Security and Game Theory: Key Algorithmic Principles, Deployed Applications, Lessons Learned**

Security is a critical concern around the world, whether it is the
challenge of protecting ports, airports, and other critical national
infrastructure, or protecting wildlife and forests, or suppressing crime
in urban areas. In many of these cases, limited security resources prevent
full security coverage at all times. Instead, these limited resources must
be scheduled, avoiding schedule predictability, while simultaneously
taking into account different target priorities, the responses of the
adversaries to the security posture, and potential uncertainty over
adversary types.

Computational game theory can help design such unpredictable security
schedules. Indeed, casting the problem as a Bayesian Stackelberg game, we
have developed new algorithms that are now deployed over multiple years in
multiple applications for security scheduling: for the US coast guard in
Boston and New York (and potentially other ports), for the Federal Air
Marshals, for the Los Angeles Airport Police, with the Los Angeles
Sheriff's Department for patrolling metro trains, with further
applications under evaluation for the TSA and other agencies. These
applications are leading to real-world use-inspired research in the
emerging research area of security games. Specifically, the research
challenges posed by these applications include scaling up security games
to large-scale problems, handling significant adversarial uncertainty,
dealing with bounded rationality of human adversaries, and other
interdisciplinary challenges. This lecture will provide an overview of my
research group's work in this area, outlining key algorithmic principles
and research results, as well as a discussion of our deployed systems and
lessons learned.

**September 25, 2012 @ noon, Gates Hillman Center (GHC) 6115**

**Ehud Kalai, prof. of decision and game sciences, Northwestern University**

**Cooperation in Strategic Games Revisited**

Much of strategic interaction involves cooperation. Strategic players commit to cooperate through contracts, the use of third parties, reputation and more. But game theory does not provide a general solution to strategic games in which cooperation is allowed.
Building on foundational work of Nash, Raiffa and Selten from the 1950s, this paper offers a theory of cooperation in two-person incomplete-information strategic games with side payments. We present a closed-form expression, as a solution to such situations, together with an axiomatic justification and protocols that implement it.

**April 3, 2012 @ noon, Hamburg Hall (HBH) 1000 [joint with the iLab Seminar]**

**Duncan Watts, principal research scientist, Yahoo! Research**

**Using the Web to do Social Science**

Social science is often concerned with the emergence of collective behavior out of the interactions of large numbers of individuals, but in this regard it has long suffered from a severe measurement problem—namely that interactions between people are hard to observe, especially at scale, over time, and at the same time as observing behavior. In this talk, I will argue that the technological revolution of the Internet is beginning to lift this constraint. To illustrate, I will describe several examples of internet-based research that would have been impractical to perform until recently, and that shed light on some longstanding sociological questions. Although internet-based research still faces serious methodological and procedural obstacles, I propose that the ability to study truly “social” dynamics at individual-level resolution will have dramatic consequences for social science.

**Mar 13, 2012 @ noon, Newell Simon Hall (NSH) 3305**

**Michael Wellman, prof. of computer science and engineering, University of Michigan**

**Empirical Game-Theoretic Analysis for Canonical Auction Games**

Some canonical auction scenarios -- involving simultaneous markets or dynamic trading, for example -- are descriptively simple yet resist analytical game-theoretic solution. We gain traction on such problems by combining simulation, search, and machine learning with game-theoretic reasoning, in an approach we call "empirical game-theoretic analysis". EGTA studies have produced strategic insights and improved strategies for simultaneous ascending auctions and continuous double auctions, as well as the more complex domains presented by a series of Trading Agent Competition events. Our most recent investigation, of simultaneous one-shot auctions, demonstrates the utility of EGTA for suggesting and evaluating theoretical characterizations of equilibrium bidding strategies.

**Feb 28, 2012 @ noon, Newell Simon Hall (NSH) 3305**

**Michael Kearns, prof. of computer and information science, University of Pennsylvania**

**Behavioral Experiments in Networked Trading**

I will describe recent human-subject experiments in a detailed microeconomic model
of trading in networks. Players are divided into two types with symmetric incentives that
create mutual interest in trade, and are arranged in bipartite networks with varying
topologies that create potential asymmetries in negotiating power. Players can only
trade with their immediate neighbors, via a local limit order mechanism that permits
partial executions of orders.

An interesting aspect of this model is that it has a detailed equilibrium theory in which
any variation in individual wealth is directly related to global network structure. This
permits comparison between equilibrium and human subject wealth at the individual
and collective levels. We describe these findings along with a number of other analyses.

Joint work with Stephen Judd.