Program
of
trackWeb Economics,
Monetisation, and Online Markets

List of accepted papers :

• Dynamic Mechanism Design in the Field
  Authors: Vahab Mirrokni, Renato Paes Leme, Rita Ren and Song Zuo

  Keywords: dynamic mechanism design, dynamic second price auction, ad auction, low regret, bank account mechanism

  Abstract:
  Dynamic mechanisms are a powerful technique in designing revenue-maximizing repeated auctions. Despite their strength, these types of mechanisms have not been widely adopted in practice for several reasons, e.g., for their complexity, and for their sensitivity to the accuracy of predicting buyers’ value distributions. In this paper, we aim to address these shortcomings and develop simple dynamic mechanisms that can be implemented efficiently, and provide theoretical guidelines for decreasing the sensitivity of dynamic mechanisms on the prediction accuracy of buyers’ value distributions. We prove that the dynamic mechanism we propose is provably dynamic incentive compatible, and introduce a notion of buyers’ regret in dynamic mechanisms, and show that our mechanism achieves bounded regret while improving revenue and social welfare compared to a static reserve pricing policy. Finally, we confirm our theoretical analysis via an extensive empirical study of our dynamic auction on real data sets from online adverting. For example, we show our dynamic mechanisms can provide a +17% revenue lift with relative regret less than 0.2%.

• Incentive-Compatible Diffusion
  Authors: Oren Dean, Yakov Babichenko and Moshe Tennenholtz

  Keywords: social networks, diffusion, incentive compatibility, mechanism design

  Abstract:
  Our work bridges the literature on incentive-compatible mechanism design and the literature on diffusion algorithms. We introduce the study of finding an incentive-compatible (strategy-proof) mechanism for selecting an influential vertex in a directed graph (e.g. Twitter’s network). The goal is to devise a mechanism with a bounded ratio between the maximal influence and the influence of the selected user, and in which no user can improve its probability of being selected by following or unfollowing other users. We introduce the Two Path mechanism which is based on the idea of selecting the vertex that is the first intersection of two independent random walks in the network. The Two Path mechanism is incentive compatible on directed acyclic graphs (DAGs), and has a finite approximation ratio on natural subfamilies of DAGs. Simulations indicate that this mechanism is suitable for practical uses.

• Incentive-Aware Learning for Large Markets
  Authors: Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni and Song Zuo

  Keywords: Incentives, Large Markets, Auctions, Learning

  Abstract:
  In a typical learning problem, the key step is to use training data to pick one model from a collection of models that optimizes an objective function. In many multi-agent settings, the training data is generated through the actions of the agents, and the model is used to make a decision (e.g., how to sell an item) that affects the agents. An illustrative example of this is the problem of optimizing the reserve price in an auction. In such cases, the agents have an incentive to influence the training data (e.g., by manipulating their bids in the case of an auction) to game the system and achieve a more favorable outcome. In this paper, we study such incentive-aware learning problem in a general setting and show that it is possible to approximately optimize the objective function under two assumptions: (i) each individual agent is a “small” (part of the market); and (ii) there is a cost associated with manipulation. For our illustrative application, this nicely translates to a mechanism for setting approximately optimal reserve prices in auctions where no individual agent has significant market share. For this application, we also show that the second assumption (that manipulations are costly) is not necessary since we can “perturb” any auction to make it costly for the agents to manipulate.

• Simple vs Optimal Contests with Convex Costs
  Authors: Amy Greenwald, Takehiro Oyakawa and Vasilis Syrgkanis

  Keywords: all-pay contests, optimal design, prior free, convex costs, non quasilinear utilities

  Abstract:
  We study an optimal contest design problem where contributors abilities are private, their costs are convex as a function of their effort, and the designer seeks to maximize their total effort. We address the design of approximately optimal mechanisms that are robust in that they are independent of the ability distribution and the precise form of the cost function. We show that a very simple all-pay contest where the prize is distributed equally among the top quartile of contributors is always a constant factor approximation to the optimal for a large class of convex cost functions, when the number of contributors is larger than some constant. This result stands in contrast to contests with linear costs, where awarding a prize to a single top contributor is approximately-optimal; when costs are convex, this latter allocation is far from optimal. Our result is enabled by novel results in the space of optimal mechanism design with convex costs, which could be of independent interest. Finally, we validate the performance of our approximately-optimal contests via simulation experiments, and portray much better empirical performance than the worst-case guarantees.

• Testing Incentive Compatibility in Display Ad Auctions
  Authors: Sebastien Lahaie, Andres Munoz Medina, Balasubramanian Sivan and Sergei Vassilvitskii

  Keywords: Display Advertising Auctions, Reserve Price Optimization, Incentive Compatibility

  Abstract:
  Consider a buyer participating in a repeated auction, such as those prevalent in display advertising. How would she test whether the auction is incentive compatible? To bid effectively, she is interested in whether the auction is single-shot incentive compatible—a pure second-price auction, with fixed reserve price—and also dynamically incentive compatible—her bids are not used to set future reserve prices. In this work we develop tests based on simple bid perturbations that a buyer can use to answer these questions, with a focus on dynamic incentive compatibility. There are many potential A/B testing setups that one could use, but we find that many natural experimental designs are, in fact, flawed. We show that additive perturbations can lead to paradoxical results, where higher bids lead to lower optimal reserve prices. We precisely characterize this phenomenon and show that reserve prices are only guaranteed to be monotone for distributions satisfying the Monotone Hazard Rate (MHR) property. The experimenter must also decide how to split traffic to apply systematic perturbations. It is tempting to have this split be randomized, however, we prove that unless the perturbations are aligned with the partitions used by the seller itself to compute reserve prices, the results are guaranteed to be inconclusive. We validate our results with experiments on real display auction data and show that a buyer can quantify both single-shot and dynamic incentive compatibility even under realistic conditions where only the cost of the impression is observed (as opposed to the exact reserve price). We analyze the cost of running such experiments, exposing trade-offs between test accuracy, cost, and underlying market dynamics.

• Bid-Limited Targeting
  Authors: Patrick Hummel and Uri Nadav

  Keywords: Targeting, Bid multipliers, Mechanism design, Online auctions

  Abstract:
  This paper analyzes a mechanism for selling items in auctions in which the auctioneer specifies a cap on the ratio between the maximum and minimum bids that bidders may use in the different auctions. Such a mechanism is widely used in online advertising through the caps that companies impose on the minimum and maximum bid multipliers that advertisers may use in targeting. When bidders’ values are independent and identically distributed, using this mechanism results in higher revenue than allowing bidders to condition their bids on the targeting information in an arbitrary way and also almost always results in higher revenue than not allowing bidders to target. Choosing the optimal cap on the ratio between the maximum bid and the minimum bid can also be more important than introducing additional competition in the auction. However, if bidders’ values are not identically distributed, pure-strategy equilibria may fail to exist.

• Optimizing Ad Refresh In Mobile App Advertising
  Authors: Florin Constantin, Christopher Harris, Samuel Ieong, Aranyak Mehta and Xi Tan

  Keywords: ad auctions, refresh rate, app advertising, user model

  Abstract:
  In-app advertising is a complex market worth billions of dollars per year, yet it has been studied significantly less than traditional web display ads. In this paper we investigate an important but often overlooked feature of ads in mobile apps (mostly absent in traditional web ads), that of ad refreshes: A user is shown a stream of banner ads during the app session, in which each ad is displayed in the ad slot for a certain amount of time (known as the refresh rate) before the ad-slot is refreshed to the next ad. Data analysis on our large-scale experiments that vary refresh rates reveals a surprising result, that cannot be explained by existing user click models: The total number of clicks is almost independent of the refresh rate. We propose a new, natural, two-phase click model for this setting that explains this independence, as well as our measurements of the click-through rate as a function of the impression’s time-on-screen and of ad-repeat counts. The new click model leads to a clean formulation of the problem of auctioning the entire user-session: i.e., determining online, both the sequence of winning ads as well as the amount of time to display each one. We complement the theoretical auction design with results from a live-traffic experiment with its implementation. Our experiments and analysis provide the theoretical foundation for Admob’s “”Google-optimized refresh rate”” feature, used by thousands of mobile apps for better monetization of ads shown to millions of users.

• Field-weighted Factorization Machines for Click-Through Rate Prediction in Display Advertising
  Authors: Junwei Pan, Jian Xu, Alfonso Lobos, Wenliang Zhao, Shengjun Pan, Yu Sun and Quan Lu

  Keywords: Factorization Machines, Click-through Rate Prediction, Display Advertising

  Abstract:
  Click-through rate (CTR) prediction is a critical task in online display advertising. The data involved in CTR prediction are typically multi-field categorical data, i.e., every feature is categorical and belongs to one and only one field. One of the interesting characteristics of such data is that features from one field often interact differently with features from different other fields. Recently, Field-aware Factorization Machines (FFMs) have been among the best performing models for CTR prediction by explicitly modeling such difference. However, the number of parameters in FFMs is in the order of feature number times field number, which is unacceptable in the real-world production systems. In this paper, we propose Field-weighted Factorization Machines (FwFMs) to model the different feature interactions between different fields in a much more memory-efficient way. Our experimental evaluations show that FwFMs can achieve competitive prediction performance with only as few as 4% parameters of FFMs. When using the same number of parameters, FwFMs can bring 0.92% and 0.47% AUC lift over FFMs on two real CTR prediction data sets.

• Detecting Ponzi Schemes on Ethereum: Towards Healthier Blockchain Technology
  Authors: Weili Chen, Zibin Zheng, Jiahui Cui, Edith Ngai, Peilin Zheng and Yuren Zhou

  Keywords: Blockchain, Smart Contract, Ponzi Schemes, Ethereum

  Abstract:
  Blockchain technology becomes increasingly popular. It also attracts scams, for example, Ponzi scheme, a classic fraud, has been found making a notable amount of money on Blockchain, which has a very negative impact. To help dealing with this issue, this paper proposes an approach to detect Ponzi schemes on blockchain by using data mining and machine learning methods. By verifying smart contracts on Ethereum, we first extract features from user accounts and operation codes of the smart contracts and then build a classification model to detect latent Ponzi schemes implemented as smart contracts. The experimental results show that the proposed approach can achieve high accuracy for practical use. More importantly, the approach can be used to detect Ponzi schemes even at the moment of its creation. By using the proposed approach, we estimate that there are more than 400 Ponzi schemes running on Ethereum. Based on these results, we propose to build a uniform platform to evaluate and monitor every created smart contract for early warning of scams.

• A Short-term Intervention for Long-term Fairness in the Labor Market ★
  Authors: Lily Hu and Yiling Chen

  Keywords: fairness, game theory, labor market

  Abstract:
  The persistence of racial inequality in the U.S. labor market against a general backdrop of formal equality of opportunity is a troubling phenomenon that has significant ramifications on the design of hiring policies. In this paper, we show that current group disparate outcomes may be immovable even when hiring decisions are bound by an input-output notion of “”individual fairness.”” Instead, we construct a dynamic reputational model of the labor market that illustrates the reinforcing nature of asymmetric outcomes resulting from groups’ divergent access to resources and as a result, investment choices. To address these disparities, we adopt a dual labor market composed of a Temporary Labor Market (TLM), in which firms’ hiring strategies are constrained to ensure statistical parity of workers granted entry into the pipeline, and a Permanent Labor Market (PLM), in which firms hire top performers as desired. Individual worker reputations produce externalities for their group; the corresponding feedback loop raises the collective reputation of the initially disadvantaged group via a TLM fairness intervention that need not be permanent. We show that such a restriction on hiring practices induces an equilibrium that, under particular market conditions, Pareto-dominates those arising from strategies that employ statistical discrimination or a “”group-blind”” criterion. The enduring nature of equilibria that are both inequitable and Pareto suboptimal suggests that fairness interventions beyond procedural checks of hiring decisions will be of critical importance in a world where machines play a greater role in the employment process.

• Reinforcement Mechanism Design for e-commerce
  Authors: Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang and Yiwei Zhang

  Keywords: e-commerce, impression allocation, mechanism design, reinforcement learning

  Abstract:
  We study the problem of allocating impressions to sellers in e-commerce websites, such as Amazon, eBay or Taobao, aiming to maximize the total revenue generated by the platform. We employ a general framework of reinforcement mechanism design, which uses deep reinforcement learning to design efficient algorithms, taking the strategic behaviour of the sellers into account. Specifically, we model the impression allocation problem as a Markov decision process, where the states encode the history of impressions, prices, transactions and generated revenue and the actions are the possible impression allocations in each round. To tackle the problem of continuity and high-dimensionality of states and actions, we adopt the ideas of the DDPG algorithm to design an actor-critic gradient policy algorithm which takes advantage of the problem domain in order to achieve convergence and stability. We evaluate our proposed algorithm, coined IA(GRU), by comparing it against DDPG, as well as several natural heuristics, under different rationality models for the sellers – we assume that sellers follow well-known no-regret type strategies which may vary in their degree of sophistication. We find that IA(GRU) outperforms all algorithms in terms of the total revenue.

• Financing the Web of Data with Delayed-Answer Auctions
  Authors: Tobias Grubenmann, Abraham Bernstein, Dmitry Moor and Sven Seuken
  Presentation moved from track Web Content Analysis, Semantics and Knowledge

  Keywords: Web of Data, Slot Auctions, Delay, Sponsored Search Results, Vickrey-Clarke-Groves mechanism

  Abstract:
  The World Wide Web is a massive network of interlinked documents. One of the reasons the World Wide Web is so successful is the fact that most content is available free of any charge. Inspired by the success of the World Wide Web, the Web of Data applies the same strategy of interlinking to data. To this point, most of data in the Web of Data is also free of charge. The fact that the data is freely available raises the question of financing these services, however. As we will discuss in this paper, advertisement and donations cannot easily be applied to this new setting. To create incentives to subsidize data providers, we propose that sponsors should pay the providers to promote sponsored data. In return, sponsored data will be privileged over non-sponsored data. Since it is not possible to enforce a certain ordering on the data the user will receive, we propose to split up the data into different batches and deliver these batches with different delays. In this way, we can privilege sponsored data without withholding any non-sponsored data from the user. In this paper, we introduce a new concept of a delayed-answer auction, where sponsors can pay to prioritize their data. We introduce a new model which captures the particular situation when a user access data in the Web of Data. We show how the weighted Vickrey-Clarke-Groves auction mechanism can be applied to our scenario and we discuss how certain parameters can influence the nature of our auction. With our new concept, we build a first step to a free yet financial sustainable Web of Data.