I’ll discuss how kidney exchange has changed the behavior of big transplant centers in ways that have in turn changed the organization of kidney exchange and the algorithms that it deploys to create chains of transplants.
Monday, November 16th, 2015
No abstract available.
In this presentation we would see some applications of game-theory and economics in designing business models.
Reputation mechanisms used by platform markets suffer from two problems. First, buyers may draw conclusions about the quality of the platform from single transactions, causing a reputational externality. Second, reputation measures may be coarse or biased, preventing buyers from making proper inferences. We document these problems using eBay data and claim that platforms can benefit from identifying and promoting higher quality sellers. Using an unobservable measure of seller quality we demonstrate the benefits of our approach through a large-scale controlled experiment. Highlighting the importance of reputational externalities, we chart an agenda that aims to create more realistic models of platform markets.
A host of new platforms use dynamic prices as a key tool to balance supply and demand. Dynamic prices have at least two potential effects on the market: On the demand side, they allocate resources to those with the highest willingness to pay, throttling demand. On the supply side, they signal to potential suppliers that this is a time of high demand, potentially leading to an increase of services supplied. This latter effect distinguishes dynamic pricing in this context from our traditional notions of intertemporal price discrimination. We study the case of Uber, a platform that matches riders to drivers and uses ``surge pricing'' during periods of high demand. We present stylized facts consistent with both demand throttling and supply-side increases. We then use a structural model to decompose these effects and consider a counterfactual world with no surge pricing, quantifying the resulting inefficiencies.
Tuesday, November 17th, 2015
I will summarize several papers on machine learning in an exchange environment. The use at which ML is put matters, mainly through the errors.
Capacity or budget planning is an important component of any online ad serving platform. This has given rise to a rich and exciting line of work in online algorithms, and one of the most successful marriages of theory and practice. The practical aspects have directly influenced the theory and the theory has had significant impact on the design of modern advertising systems. The talk will give an overview of this interaction and some recent results on a very general problem called the online convex programming problem.
With over 1 million daily active users and over 2.5 million advertisers, Facebook runs one of the world’s largest online advertising marketplaces. Advertisers can choose to bid and pay for ad impressions, for clicks, for conversions or for a combination. The ranking and pricing of ads depends on the predicted probability of clicks and conversions. In this talk we give a brief overview of the algorithmic problems underlying the Facebook ads auction. We share some lessons learnt from building the scalable machine learning platform we use to tackle the prediction problem, and discuss challenges in optimization and mechanism design.
Wednesday, November 18th, 2015
The ability to computationally solve imperfect-information games has a myriad of future applications ranging from auctions, negotiations, and (cyber)security settings to guiding evolution and adaptation in medical domains. A dramatic scalability leap has occurred in the capability to solve such games over the last nine years, fueled in large part by the Annual Computer Poker Competition. I will discuss the key, domain-independent, techniques that enabled this leap, including automated abstraction techniques and approaches for mitigating the issues that they raise, new equilibrium-finding algorithms, safe opponent exploitation methods, techniques that use qualitative knowledge as an extra input, and endgame solving techniques. Time permitting, I will include new results on 1) developing the world’s best Heads-Up No-Limit Texas Hold'em poker program, 2) theory that enables abstraction that gives solution quality guarantees, 3) techniques for warm starting equilibrium finding, 4) simultaneous abstraction and equilibrium finding, 5) lossless tree pruning algorithms for incomplete-information settings, and 6) theory that improves prior best gradient-based equilibrium-finding algorithms. I will also cover the Brains vs AI competition that I recently organized where our AI, Claudico, challenged four of the top-10 human pros in Heads-Up No-Limit Texas Hold'em for 80,000 hands. The talk covers joint work with many co-authors, mostly Noam Brown, Sam Ganzfried, and Christian Kroer.
Thursday, November 19th, 2015
No abstract available.
This talk will discuss the FCC’s “incentive auction”, which proposes to give television broadcasters an opportunity to sell their broadcast rights, to repack remaining broadcasters into a smaller block of spectrum, and to resell the freed airwaves to telecom companies. The stakes for this auction are huge—projected tens of billions of dollars in revenue for the government—justifying the design of a special-purpose descending-price auction mechanism, which I’ll discuss. An inner-loop problem in this mechanism is determining whether a given set of broadcasters can be repacked into a smaller block of spectrum while respecting radio interference constraints. This is an instance of a (worst-case intractable) graph coloring problem; however, stations’ broadcast locations and interference constraints are all known in advance. Early efforts to solve this problem considered mixed-integer programming formulations, but were unable to reliably solve realistic, national-scale problem instances. We advocate instead for the use of a SAT encoding, paired with a wide range of techniques: constraint graph decomposition; novel caching mechanisms that allow reuse of partial solutions from related, solved problems; algorithm configuration; algorithm portfolios; and the marriage of local-search and complete solver strategies. We show that our approach solves virtually all of a set of problems derived from auction simulations within the short time budget required in practice.
We propose formal definitions of substitutes and complements for information in the context of decision making under uncertainty. A decision maker needs to take an action to maximize his expected utility. Two pieces of information are substitutes (complements) for the decision problem if the more the decision maker knows about one decreases (increases) his marginal value of learning the other. Interestingly, a special class of decision problems — prediction problems where the decision maker predicts the distribution of a random variable and is rewarded for his prediction according to a proper scoring rule — is complete for understanding the value of information, in the sense that every decision problem has an “equivalent” prediction problem where the value of information is the same. Using the understanding of informational substitutes and complements, we characterize the game-theoretic equilibria of strategic play in prediction markets for any market scoring rule.
This talk is based on joint work with Bo Waggoner.
Friday, November 20th, 2015
No abstract available.
Ride-sharing platforms such as Lyft and Uber are among the fastest growing online marketplaces. A key feature of these platforms is the implementation of fine-grained, fast-timescale dynamic pricing --- where prices can react to instantaneous system state, and across very small geographic areas. In this talk, we explore the value of such fast-timescale dynamic pricing. To do so, we develop a new queueing model for ride-sharing platforms, which combines the stochastic dynamics of the platform's operations with strategic models of both passenger and driver behavior. Using this model, we demonstrate that dynamic pricing may not be better than the optimal quasi-static price in most settings. However, finding the optimal static price requires exact knowledge of system parameters; we show that dynamic pricing is much more robust to fluctuations in these parameters as compared to static prices. Thus, dynamic pricing does not necessarily buy more than static pricing, but in fact, it lets platforms realize the benefits of optimal static pricing with imperfect knowledge of system parameters.
Joint work with Siddhartha Banerjee (Cornell) and Carlos Riquelme (Stanford).