#	Pagina
attuale pagina	/open-h2020/projects/216237/results.html

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - AMDROMA (Algorithmic and Mechanism Design Research in Online MArkets)

Teaser

Summary

We consider algorithmic questions that arise in three fields of application: 1. Algorithms and mechanisms for web Internet advertisement; 2. Algorithms for Internet Markets; 3. Algorithms for online labor marketplaces. These problems of great importance for the Internet economy and for society require an interdisciplinary approach and tools for a wide variety of research. In a first project objective we address fundamental and longstanding open questions in auction and market design that are non-trivial due to the very large scale, and numerous practical restrictions. In a second projective objective, we will address the research issues of copying with uncertainty in online markets. In a third Project Objective, we address research issues of large-scale data analysis and optimization for two-sided matching and clustering problems which provide fundamental primitives for many online market applications.

Work performed

One first contribution is about designing algorithms and mechanisms in two-sided markets that involve the interaction of strategic buyers with strategic sellers. We design simple and efficient mechanisms that require very limited information, one single sample from the distributions of buyers and sellers. A second paradigmatic problem in this area we consider is the one of devising an online efficient and truthful mechanisms for two-sided matching markets with bidders that arrive over time and the items that must be allocated as soon as the bidders arrive. In our work we are able to provide an optimal truthful mechanism for online matching markets. Thirdly, Auction mechanisms used in practice often fails to be truthful for reasons mostly related to the complexity of the auction ecosystem. We propose new metrics based on the concept of envy-freeness to measure with one single experiment how far from truthfulness is the mechanisms.

Our contribution on the second project objective is about the design of efficient and truthful pricing mechanisms in the cloud market in presence of uncertainty on the future arrivals and on the type of the agents. A second contribution addresses the problems of designing budget feasible strategies for the stochastic exploration of networks. Finally, we provide a new set of optimal and near optimal strategies for the Pandora\'s Box Problem, originally formalized by Weitzman in 1979, that models, for example, the problem of hiring one skilled worker, where the evaluation of each candidate is an expensive procedure.

For the third project objective we provide near optimal online algorithms for matching tasks to hired and freelance online workers. We also study the fair version of the team formation problem and of other fundamental classification and clustering methods, where we seek for example for a solution with good balance between genders. Finally, a number of computational issues for large-scale data analysis in markets have been considered for approximating k-means, perhaps the most used clustering methods, and for the efficient updating over time of near optimal solutions to a clustering or a matching problem.

Final results

In [Duetting et al., 2020] we show that for many fundamental markets it is possible to design near-optimal mechanisms with just a single sample from the priors. In fact, most of our results improve upon previous results that assume full knowledge of the distributions. We will study the challenging problem of optimizing gain from trade with 1 single sample. We have also studied the online truthful weighted matching problem where the item set is known beforehand, but bidders appear one after another in random order. In [ReiffenhÃ¤user 2019] it is presented an optimal, e-competitive truthful mechanism thus matching the ratio known for the original famous secretary for one single item on sale. The extension to matroid and combinatorial settings is a very challenging open problem.
Incentive compatibility is a fundamental property of auction mechanisms. Recent methods show that many counterfactual runs of the auction with different bids can be used to determine whether an auction is truthful. In [Colini-Baldeschi et al. 2020] we show that a similar result can be obtained for the setting of position auctions for sponsored search with one single execution of the auction by looking at the advertisers\' envy. We plan in the near future to study the Ad-type setting where different agents have different discount factors on the positions.

Project objective 2 is related to copying with uncertainty in mechanism design. We introduce in [Anagnostopoulos et al. 2019] the stochastic exploration of an undirected graph with stochastic edge costs drawn from a distribution, and rewards on vertices. The goal is to find a set of edges of total cost at most equal to a maximum budget, and maximizes the total reward. We show that logarithmic budget augmentation suffices to obtain constant approximation oblivious strategies that are competitive against the optimal adaptive strategy. A challenging problem is to devise strategies with constant approximation and constant budget augmentation. Finally, for the problem of information acquisition in markets, Weitzman in 1979 showed that the Pandora\'s Box problem admits an elegant and simple greedy solution. In [Boodaghians et al. 2020], we are able to design an optimal strategy for tree-like order constraints on the exploration of the alternatives. We plan to extend our study to the more general setting of dag-like order constraints.

For the large-scale optimization of online markets of project objective 3, we studied the problems of operating online marketplaces. In [Anagnostopoulos et al 2018] we provide algorithms for outsourcing and hiring workers, where workers form a team and contribute different skills to perform a task. We also extend our study to consider the fairness issues of overcoming the unintentional algorithmic discrimination that frequently arises in the job market on grounds of nationality or gender. For the future we plan to study the online problem with a hard limit on the maximum number of hired workers.
Fairness is also a natural requirement to impose for the fundamental machine learning primitives used for classification and recommendation in online markets. Previous work obtained a constant factor approximation for the fair version with 1 protected attribute (e.g., gender) of most center based k-clustering objectives. In [BÃ¶hm et al, 2020], we give the first constant factor approximations for all center based k-clustering objectives with any number of attributes. In the near future we plan to devise fair clustering methods based on coresets. For the issues related to computational efficient methods for large-scale data analysis, we study in [Becchetti et al. 2019] the problem of speeding up all k-means clusterings. We show that oblivious random projections onto a logarithmic number O(log k) of dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1Â±Îµ) factor. This closes a longstanding open problem. Finally, in [Gran