This seminar series is made possible in part by a donation from Yahoo! Research, as well as funding from
Duke's Fuqua School of Business and Department of Computer Science.
You can also see the upcoming events on our Google Calendar.
Upcoming and Recent Events
Date 
Time 
Place 
Speaker 
Topic 

20171117  12:0001:00  Gross Hall 304B  Markus Brill  Approval Voting, Proportional Representation, & Liquid Democracy  info 

Approval Voting, Proportional Representation, & Liquid Democracy In this talk, I will survey recent results concerning the proportional representation of voters in approvalbased committee elections. In this setting, voters express their preferences over a set of candidates by specifying, for each candidate, whether they approve ("like") that candidate or not. Based on these approval votes, a fixedsize subset of winning candidates needs to be selected. I will also discuss proportional rankings, where the goal is to rankorder the candidates in a way that is representative of voters' preferences. As an example application scenario where such rankings are desirable, I will briefly outline some ideas related to "liquid democracy", an exciting new paradigm for collective decision making with many participants. 

20171020  12:0001:00  Gross 304B  Hu Fu  The Value of Information Concealment  info 

The Value of Information Concealment We consider a revenue optimizing seller selling a single item to a buyer, on whose private value the seller has a noisy signal. We show that, when the signal is kept private, arbitrarily more revenue could potentially be extracted than if the signal is leaked or revealed. We then show that, if the seller is not allowed to make payments to the buyer, the gap between the two is bounded by a multiplicative factor of 3 when the value distribution conditioning on each signal is regular. We give examples showing that both conditions are necessary for a constant bound to hold.
We connect this scenario to multibidder singleitem auctions where bidders'values are correlated. Similarly to the setting above, we show that the revenue of a Bayesian incentive compatible, ex post individually rational auction can be arbitrarily more than that of a dominant strategy incentive compatible auction, whereas the two are no more than a factor of 5 apart if the auctioneer never pays the bidders and if each bidder's value distribution conditioning on the others' is regular. The upper bounds in both settings degrade gracefully when the distribution is a mixture of a small number of regular distributions. This is joint work with Chris Liaw, Pinyan Lu, and Zhihao Gavin Tang.


20170929  12:0001:00  Gross Hall 304B  Christian Kroer  Multiplicative Pacing Equilibria in Auction Markets  info 

Multiplicative Pacing Equilibria in Auction Markets Budgets play a significant role in realworld sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. This paper considers a smoothing procedure that relies on {\em pacing multipliers}: for each bidder, the platform applies a factor between 0 and 1 that uniformly scales the bids across all auctions. Looking at this process as a game between all bidders, we introduce the notion of {\em pacing equilibrium}, and prove that they are always guaranteed to exist. We demonstrate through examples that a market can have multiple pacing equilibria with large variations in several natural objectives. We go on to show that computing either a socialwelfaremaximizing or a revenuemaximizing pacing equilibrium is NPhard. Finally, we develop a mixedinteger program whose feasible solutions coincide with pacing equilibria, and show that it can be used to find equilibria that optimize several interesting objectives. Using our mixedinteger program, we perform numerical simulations on synthetic auction markets that provide evidence that, in spite of the possibility of equilibrium multiplicity, it occurs very rarely across several families of random instances. We also show that solutions from the mixedinteger program can be used to improve the outcomes achieved in a more realistic adaptive pacing setting. 

20170414  12:0001:00  Gross 318, Duke  Mathijs de Weerdt  Mechanism design and computational challenges in the smart grid  info 

Mechanism design and computational challenges in the smart grid Renewable energy sources are not as predictable and
controllable as carbonbased generators. Therefore, the future
electricity system requires flexible demand and more communication.
This brings a collection of novel and challenging mechanism design and computational questions. In this talk, I will survey these challenges
(e.g. from [3,4]), and elaborate on two of our contributions: an
online scheduling mechanism under uncertain supply and demand using consensus [5], and a cooperative algorithm for congestion management under uncertainty [1,2]. 

20170324  12:0001:00  Gross 318  Yu Cheng  Computational Aspects of Optimal Information Revelation
 info 

Computational Aspects of Optimal Information Revelation
Understanding the role of information in strategic interactions is becoming more and more important in the age of information we live in today. The design of information structures is emerging as a new area of mechanism design for information, an area that is still largely unexplored. In this talk, we are going to examine the optimization problem faced by an informed principal, who must choose how to reveal partial information in order to induce a desirable equilibrium, a task often referred to as signaling or persuasion. We settle the computational complexity of optimal signaling in two of the most fundamental gametheoretic scenarios: Bayesian zerosum games and network routing games. 

20170303  12:0001:00  North Bldg. 311 (directions below)  Simina Branzei  Computational Fair Division and Mechanism Design  info 

Computational Fair Division and Mechanism Design The emergence of online platforms has brought about a fundamental shift in economic thinking: the design of economic systems is now a problem that computer science can tackle. For the first time we are able to move from the study of economic systems as mainly natural systems to carefully designing and executing them on a computer. Prominent examples of digital market mechanisms include auctions for ads (run by companies such as Google) and electromagnetic spectrum (used by the US government).
I will discuss several recent developments in fair division and mechanism design. I will start with a dictatorship theorem for fair division (cake cutting), showing that requiring truthfulness gives rise to a dictator.
Next, I will turn to the paradigmatic model of multiunit markets, where I will show that truthfulness requires discarding resources, but this problem can be alleviated when the market is even mildly competitive.
More generally, I will discuss the theme of simplicity and complexity in mechanism design, and the interplay between economics and computation and learning.


20170224  12:0001:00  Gross 318  Jacob Leshno (Columbia)  The Simple Structure of Top Trading Cycles in School Choice: A Continuum Model (Joint with Irene Lo)  info 

The Simple Structure of Top Trading Cycles in School Choice: A Continuum Model (Joint with Irene Lo) Many cities determine the assignment of students to schools
through a school choice mechanism which calculates an assignment based on student preferences and school priorities. The prominent Top
Trading Cycles (TTC) algorithm is strategyproof and Pareto efficient,
but the combinatorial description of TTC makes it nontransparent to
parents and difficult to analyze for designers. We give a tractable
characterization of the TTC mechanism for school choice: the TTC
assignment can be simply described by n^2 cutoffs, where n is the
number of schools. We define TTC in a continuum model, in which these thresholds can be directly calculated by a differential equation.
The model also allows us to compute comparative statics, analyze
sequential trade procedures, and show that changes in the priority
structure can have nontrivial indirect effects on the allocation. We
also apply this model to solve for optimal investment in school
quality, and help explain empirical findings about the relation
between the TTC assignment and the Deferred Acceptance assignment. To validate the continuum model we show that it gives a good approximation for strongly converging economies. Our analysis draws on
an interesting connection between continuous trading procedures and
continuous time Markov chains. 
You can find more past talks here.