Google regularly participates in the WINE conference: Workshop on Internet & Network Economics. WINE’12 just happened last week in Liverpool, UK, where there is a strong economics and computation group. WINE provides a forum for researchers across various disciplines to examine interesting algorithmic and economic problems of mutual interest that have emerged from the Internet over the past decade. For Google, the exchange of ideas at this selective workshop has resulted in innovation and improvements in algorithms and economic auctions, such as our display ad allocation.
Googlers co-authored three papers this year; here’s a synopsis of each, as well as some highlights from invited talks at the conference:
Budget Optimization for Online Campaigns with Positive Carryover Effects
This paper first argues that ad impressions may have some long-term impact on user behaviour, and refers to an older WWW ’10 paper. Based on this motivation, the paper presents a scalable budget optimization algorithm for online advertising campaigns in the presence of Markov user behavior. In such settings, showing an ad to a user may change their actions in the future through a Markov model, and the probability of conversion for the ad does not only depend on the last ad shown, but also on earlier user activities. The main purpose of the paper is to give a simpler algorithm to solve a constrained Markov Decision Process, and confirms this easier solution via simulations on some advertising data sets. The paper was written when Nikolay Archak, a PhD student at NYU business school, was an intern with the New York market algorithms research team.
On Fixed-Price Marketing for Goods with Positive Network Externalities
This paper presents an approximation algorithm for marketing “networked goods” and services that exhibit positive network externalities - for example, is the buyer's value for the goods or service influenced positively by other buyers owning the goods or using the service? Such positive network externalities arise in many products like operating systems or smartphone services. While most of previous research is concerned with influence maximization, this paper attempts to identify a revenue maximizing marketing strategy for such networked goods, as follows: The seller selects a set (S) of buyers and gives them the goods for free, then sets a fixed per-unit price (p), at which other consumers can buy the item. The strategy is consistent with practice and is easy to implement. The authors use ideas from non-negative submodular maximization to find the optimal revenue maximizing fixed-price marketing strategy.
The AND-OR game: Equilibrium Characterization
Yishay Mansour, former Visiting Faculty in Google New York, presented the results; he first argued that the existence and uniqueness of market equilibria is only known for markets with divisible goods and concave or convex utilities. Then he described a simple market AND-OR game for divisible goods. To my surprise, he showed a class of mixed strategies are basically the unique set of randomized equilibria for this market (up to minor changes in the outcome). At the end, Yishay challenged the audience to give such characterization for more general markets with indivisible goods.
Kamal Jain of Ebay Research gave an interesting talk about mechanism design problems, inspired by application in companies like Ebay and Google. In one part, Kamal proposed "coopetitive ad auctions" for settings in which the auctioneer runs an auction among buyers who may cooperate with some advertisers, and at the same time compete with others for sealing advertising slots. He gave context around "product ads"; for example, a retailer like Best Buy may cooperate with a manufacturer like HP to put out a product ad for an HP computer sold at Best Buy. Kamal argued that if the cooperation is not an explicit part of the auction, an advertiser may implicitly end up competing with itself, thus decreasing the social welfare. By making the cooperation an explicit part of the auction, he was able to design a mechanism with better social welfare and revenue properties, compared to both first-price and second-price auctions. Kamal also discussed optimal mechanisms for intermediaries, and “surplus auctions” to avoid cyclic bidding behavior resulted from running naive variants of first-price auctions in repeated settings.
David Parkes of Harvard University discussed techniques to combine mechanism design with machine learning or heuristic search algorithms. At one point David discussed how to implement a branch-and-bound search algorithm in a way that results in a "monotone" allocation rule, so that if we implement a VCG-type allocation and pricing rule based on this allocation algorithm, the resulting mechanism becomes truthful. David also presented ways to compute a set of prices for any allocation, respecting incentive compatibility constraints as much as possible. Both of these topics appeared in ACM EC 2012 papers that he had co-authored.
At the business meeting, there was a proposal to change the title of the conference from “workshop” to “conference” or “symposium” to reflect its fully peer-reviewed and archival nature, keeping the same acronym of WINE. (Changing the title to “Symposium on the Web, Internet, and Network Economics” was rejected: SWINE!) WINE 2013 will be held at Harvard University in Boston, MA, and we look forward to reconnecting with fellow researchers in the field and continuing to nurture new developments and research topics.
