Electronic-Commerce Day 2012

Learning Payment rules through Discriminant-Based Classification

By adopting the incentive criterion of minimizing expected regret in place of full incentive compatibility, the methods of statistical machine learning can be brought to bear on the challenges of computational mechanism design. One can train a classifier to predict the outcome of a given allocation rule, and obtain a payment rule from the discriminant function of the trained classifier. An exact classifier yields a payment rule that provides incentive compatibility, while a classifier that minimizes generalization error also minimizes expected ex post regret from truthful reports. Experimental results are presented for non-implementable allocation rules, namely greedy algorithms for multi-minded combinatorial auctions and an egalitarian outcome rule in an assignment problem.

View presentation ×

The Hypertext-based web interaction metaphor was invented more than two decades ago. This simple point and click web browsing metaphor has gained widespread acceptance for users to interact with the web. Website designers compose web page, associate them with hyperlink and hypertext, and have users follow the web structure to digest information. This simple interaction metaphor is website centric. Users are typically in the walled garden of each website. To complete their tasks, users have to navigate between and interact with various websites. To navigate to a different website, search is needed by simply typing a few keywords. Today, search and browsing are two distinctive web activities. With the fast adoption of mobile and touch-enabled devices, the web is now more accessible with richer contextual information. A new web interaction metaphor based on HyperTEC (Touch, Entity, Context) will enable user seamlessly integrate search and browsing experience. HyperTEC is more user-centric. A user can touch the device with predefined gesture to review and explore contextual results powered by the modern search engine. The browsing context and touched entity are taken into account for enhanced search results moving from traditional keyword-based search to entity-centric exploring. While display and search advertising played a key role for e-commerce, HypeTEC powered search and browsing could open a new chapter for e-commerce in the future. ×

Allocating Multiple Resources: things micro-economics never told me

The central motivation of Algorithmic Mechanism Design is the allocation of multiple interdependent resources. There are many variants, models, and settings for questions of such flavor, and one would naturally use existing economic theory and game theory as starting points for addressing such questions. In this talk I will present examples from my recent research where the main challenge lies in problems that are still open in economic theory. In these examples economic theory knows how to deal with the case of one resource or with the limit case of infinitely many resources , but not with the cases of interest in our settings, that of "m" resources. Our results shed some light on these open questions but mostly highlight that they are still very open even for m=2 and are of central interest in the study of electronic markets and auctions. Based on joint works with Avinatan Hassidim, Haim Kaplan, Yishay Mansour, with Sergiu Hart, and with Shahar Dobzinski. ×

Empirical Game-Theoretic Analysis of Bidding Strategies

Even moderately complex bidding scenarios 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 (TAC) events. The TAC Ad Auctions game in particular enables strategic exploration of sponsored-search bidding well beyond the standard one-shot analysis setting. Our most recent investigation, of simultaneous one-shot auctions, demonstrates the utility of EGTA for suggesting and evaluating theoretical characterizations of equilibrium bidding strategies. ×

Economics and Machine Learning

Internet advertising exchanges possess three characteristics—fast delivery, low values, and automated systems—that influence market design. Automated learning systems induce the winner’s curse when several pricing types compete. Bidders frequently compete with different data, which induces randomization in equilibrium. Machine learning causes the value of information to leak across participants. Discrimination may be used to induce efficient exploration, although publishers (websites) may balk at participating. The creation of “learning accounts,” which divorce payments from receipts, may be used to internalize learning externalities. Under some learning mechanisms the learning account eventually shows a surplus. The solution is illustrated computationally. ×