TYPES
Towards transparency and privacy in the online advertising business

Online Truthful Mechanisms for Multi-Sided Markets

Billions of transactions are carried out via exchanges at every given day, and the number of transactions and exchanges continues to grow as the need for competitiveness promotes adoption. The design of one-sided truthful bidding mechanisms for exchanges is relatively well understood. However, truthful bidding for multi-sided mechanisms present a significantly more challenging problem as they introduce more sophisticated requirements such as budget balance. Moreover, it is often assumed in mechanism design that players interact directly with the mechanism computing the outcome. Yet, in many complex real world settings interactions pass through intermediaries acting on the players’ behalf.

One example for a setting demonstrating the above issues is an exchange accessed through brokers. There are sellers, each having a cost for selling a unit of a good (for example, a stock, an item or a piece of information). The sellers sell their units through brokers, where each broker may represent a different number of sellers. On the other side of the market there are buyers, each having a value for buying a unit of a good and a capacity determining the maximum number of units they are interested in buying. Buyers and sellers aim to maximize their personal utilities (gain), while each broker aims to maximize the difference between the payment made to him and the total costs of his sellers. The global goal is to maximize the gain from trade, i.e., the difference between the total value of the sold goods for the buyers and the total costs of these goods for the sellers. Towards this goal, the mechanism can make decisions based, exclusively, on the reports of the brokers and buyers. In particular, the mechanism has no direct interaction with the sellers, and the brokers are free to make arbitrary manipulations to the information they transfer to the mechanism about their sellers (if such manipulations help their clientele).

There are interesting design questions regarding the above setting. Can the exchange (mechanism) maintain simultaneously different economic properties such as: voluntary participation, truthful bidding, and avoiding deficit. Moreover, can the mechanism maintain these properties while suffering only a bounded lose compared to the optimal gain from trade? Finally, can this be done when all the parties have a multi-dimensional strategic space?

The framework outlined above is very general can be studied in the context of many specific settings. One such example is online advertising in its foreseeable future form. Online advertising currently supports some of the most important Internet services, including: search, social media and user generated content sites. However, the amount of information that companies collect about users increasingly creates concerns in society. As a result, there has been growing adoption of tools for blocking any transfer of information from end users towards the online advertising ecosystem. A massive adoption of these tools by end users may cause disruptions in the digital economy. To overcome the above, user information markets through information brokers were suggested by Horizon 2020 project TYPES. Such markets give users control over which data get shared in the online advertising exchange.

The above motivation is modeled by recent study (FG16, FG16b) as a market where advertisers are buyers, users are sellers (each willing to sell her own information portfolio through a broker) and information brokers are mediators representing the users. The objective of a mechanism for this setting is to end up with a match between users and advertisers maximizing the gain from trade. Towards that goal, the mechanism has to collect information from the mediators and advertisers; and thus, needs to incentivize the mediators and advertisers to report truthfully, which it can do by charging the advertisers and paying the mediators. Additionally, the mechanism can also recommend for the mediators to forward some of the payment they receive to the users, which allows the mechanism to affect the incentives of the users as well.

To better understand the design challenge of the problem at hand, one can observe that even if the setting is reduced to a single buyer-single seller exchange, still it is well known from Myerson and Satterthwaite 1983 work that maximizing gain from trade while maintaining voluntary participation and truthful bidding perforce to run into deficit.

In the framework of the Horizon 2020 project TYPES, we developed three solutions mechanisms, deterministic, randomized and online for the mediated multi-sided exchange. All three solutions involve multi-minded players (the advertisers and mediators), i.e., players with a multi-dimensional strategic space. Our mechanisms for this setting are the only known mechanisms, to date, which circumvent the impossibility result of Myerson and Satterthwaite 1983 in a model involving multi-minded players.

About the author

Rica Goen | The Open University of Israel

Leave a Reply