Author name cluster

Giulia Romano

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

1 author row

AAMAS Conference 2024 Conference Paper

Finding Effective Ad Allocations: How to Exploit User History

Matteo Castiglioni
Alberto Latino
Alberto Marchesi
Giulia Romano
Nicola Gatti
Chokha Palayamkottai

A primary source of revenue for web platforms is digital advertising. Platforms typically maximize the effectiveness of advertising campaigns by exploiting user features (i. e. , targeted advertising). However, performance can be further improved by leveraging user navigation history. In particular, the advent of new augmented reality platforms encourages users to spend a considerable amount of time in the same virtual environment, opening up the challenge of determining which ads to display and at which time of their experience. In this paper, we initiate the study of history-dependent advertising by providing a user model and optimized ad allocation algorithms. Our model assumes that users move through a series of scenes where they are exposed to ads. The performance of an ad may be influenced by various factors, such as the features of the scene in which it is displayed, the externalities of previously observed ads and the possibility that a user has already purchased the promoted product. We analyze the computational complexity of finding an optimal ad allocation for several model flavors and provide practical approximation algorithms with tight theoretical guarantees. We also discuss under which conditions our approximation algorithms are monotone according to Myerson’s definition, thus leading to truthful auction mechanisms.

PDF

AIJ Journal 2023 Journal Article

Increasing revenue in Bayesian posted price auctions through signaling

Matteo Castiglioni
Alberto Marchesi
Giulia Romano
Nicola Gatti

We study single-item single-unit Bayesian posted price auctions, where buyers arrive sequentially and their valuations for the item being sold depend on a random, unknown state of nature. The seller has complete knowledge of the actual state and can send signals to the buyers so as to disclose information about it. For instance, the state of nature may reflect the condition and/or some particular features of the item, which are known to the seller only. The problem faced by the seller is about how to partially disclose information about the state so as to maximize revenue. Unlike classical signaling problems, in this setting, the seller must also correlate the signals being sent to the buyers with some price proposals for them. This introduces additional challenges compared to standard settings. As a preliminary step, we show that, w. l. o. g. , the seller can deterministically propose a price to each buyer on the basis of the signal being sent to that buyer, rather than selecting prices stochastically and arbitrarily correlating them with signals sent to all the buyers. Next, we consider two cases: the one where the seller can only send signals publicly visible to all buyers, and the case in which the seller can privately send a different signal to each buyer. As a first step, we prove that, in both settings, the problem of maximizing the seller's revenue does not admit an additive FPTAS unless P = NP, even for basic instances with a single buyer. As a result, in the rest of the paper, we focus on designing additive PTASs. In order to do so, we first introduce a unifying framework encompassing both public and private signaling, whose core result is a decomposition lemma that allows focusing on a finite set of possible buyers' posteriors. This forms the basis on which our additive PTASs are developed. In particular, in the public signaling setting, our PTAS employs some ad hoc techniques based on linear programming, while our PTAS for the private setting relies on the ellipsoid method to solve an exponentially-sized LP in polynomial time. In the latter case, we need a custom approximate separation oracle, which we implement with a dynamic programming approach.

Details DOI

NeurIPS Conference 2022 Conference Paper

A Unifying Framework for Online Optimization with Long-Term Constraints

Matteo Castiglioni
Andrea Celli
Alberto Marchesi
Giulia Romano
Nicola Gatti

We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal of the decision maker is to maximize their total reward, while at the same time achieving small cumulative constraints violations across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class of problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown stochastic model, and in the case in which they are selected at each round by an adversary. Our algorithm is the first to provide guarantees in the adversarial setting with respect to the optimal fixed strategy that satisfies the long-term constraints. In particular, it guarantees a $\rho/(1+\rho)$ fraction of the optimal utility and sublinear regret, where $\rho$ is a feasibility parameter related to the existence of strictly feasible solutions. Our framework employs traditional regret minimizers as black-box components. Therefore, by instantiating it with an appropriate choice of regret minimizers it can handle both the full-feedback as well as the bandit-feedback setting. Moreover, it allows the decision maker to seamlessly handle scenarios with non-convex reward and constraints. We show how our framework may be applied in the context of budget-management mechanisms for repeated auctions in order to guarantee long-term constraints which are not packing (e. g. , ROI constraints).

PDF Details

AAAI Conference 2022 Conference Paper

Efficiency of Ad Auctions with Price Displaying

Matteo Castiglioni
Diodato Ferraioli
Nicola Gatti
Alberto Marchesi
Giulia Romano

Most of the economic reports forecast that almost half of the worldwide market value unlocked by AI over the next decade (up to 6 trillion USD per year) will be in marketing&sales. In particular, AI will enable the optimization of more and more intricate economic settings, in which multiple different activities need to be jointly automated. This is the case of, e. g. , Google Hotel Ads and Tripadvisor, where auctions are used to display ads of similar products or services together with their prices. As in classical ad auctions, the ads are ranked depending on the advertisers’ bids, whereas, differently from classical settings, ads are displayed together with their prices, so as to provide a direct comparison among them. This dramatically affects users’ behavior, as well as the properties of ad auctions. We show that, in such settings, social welfare maximization can be achieved by means of a direct-revelation mechanism that jointly optimizes, in polynomial time, the ads allocation and the advertisers’ prices to be displayed with them. However, in practice it is unlikely that advertisers allow the mechanism to choose prices on their behalf. Indeed, in commonly-adopted mechanisms, ads allocation and price optimization are decoupled, so that the advertisers optimize prices and bids, while the mechanism does so for the allocation, once prices and bids are given. We investigate how this decoupling affects the efficiency of mechanisms. In particular, we study the Price of Anarchy (PoA) and the Price of Stability (PoS) of indirect-revelation mechanisms with both VCG and GSP payments, showing that the PoS for the revenue may be unbounded even with two slots, and the PoA for the social welfare may be as large as the number of slots. Nevertheless, we show that, under some assumptions, simple modifications to the indirect-revelation mechanism with VCG payments achieve a PoS of 1 for the revenue.

PDF Details

IJCAI Conference 2022 Conference Paper

Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts

Giulia Romano
Andrea Agostini
Francesco Trovò
Nicola Gatti
Marcello Restelli

There is a rising interest in industrial online applications where data becomes available sequentially. Inspired by the recommendation of playlists to users where their preferences can be collected during the listening of the entire playlist, we study a novel bandit setting, namely Multi-Armed Bandit with Temporally-Partitioned Rewards (TP-MAB), in which the stochastic reward associated with the pull of an arm is partitioned over a finite number of consecutive rounds following the pull. This setting, unexplored so far to the best of our knowledge, is a natural extension of delayed-feedback bandits to the case in which rewards may be dilated over a finite-time span after the pull instead of being fully disclosed in a single, potentially delayed round. We provide two algorithms to address TP-MAB problems, namely, TP-UCB-FR and TP-UCB-EW, which exploit the partial information disclosed by the reward collected over time. We show that our algorithms provide better asymptotical regret upper bounds than delayed-feedback bandit algorithms when a property characterizing a broad set of reward structures of practical interest, namely α-smoothness, holds. We also empirically evaluate their performance across a wide range of settings, both synthetically generated and from a real-world media recommendation problem.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Public Signaling in Bayesian Ad Auctions

Francesco Bacchiocchi
Matteo Castiglioni
Alberto Marchesi
Giulia Romano
Nicola Gatti

We study signaling in Bayesian ad auctions, in which bidders' valuations depend on a random, unknown state of nature. The auction mechanism has complete knowledge of the actual state of nature, and it can send signals to bidders so as to disclose information about the state and increase revenue. For instance, a state may collectively encode some features of the user that are known to the mechanism only, since the latter has access to data sources unaccessible to the bidders. We study the problem of computing how the mechanism should send signals to bidders in order to maximize revenue. While this problem has already been addressed in the easier setting of second-price auctions, to the best of our knowledge, our work is the first to explore ad auctions with more than one slot. In this paper, we focus on public signaling and VCG mechanisms, under which bidders truthfully report their valuations. We start with a negative result, showing that, in general, the problem does not admit a PTAS unless P = NP, even when bidders' valuations are known to the mechanism. The rest of the paper is devoted to settings in which such negative result can be circumvented. First, we prove that, with known valuations, the problem can indeed be solved in polynomial time when either the number of states d or the number of slots m is fixed. Moreover, in the same setting, we provide an FPTAS for the case in which bidders are single minded, but d and m can be arbitrary. Then, we switch to the random valuations setting, in which these are randomly drawn according to some probability distribution. In this case, we show that the problem admits an FPTAS, a PTAS, and a QPTAS, when, respectively, d is fixed, m is fixed, and bidders' valuations are bounded away from zero.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Signaling in Posted Price Auctions

Matteo Castiglioni
Giulia Romano
Alberto Marchesi
Nicola Gatti

We study single-item single-unit Bayesian posted price auctions, where buyers arrive sequentially and their valuations for the item being sold depend on a random, unknown state of nature. The seller has complete knowledge of the actual state and can send signals to the buyers so as to disclose information about it. For instance, the state of nature may reflect the condition and/or some particular features of the item, which are known to the seller only. The problem faced by the seller is about how to partially disclose information about the state so as to maximize revenue. Unlike classical signaling problems, in this setting, the seller must also correlate the signals being sent to the buyers with some price proposals for them. This introduces additional challenges compared to standard settings. We consider two cases: the one where the seller can only send signals publicly visible to all buyers, and the case in which the seller can privately send a different signal to each buyer. As a first step, we prove that, in both settings, the problem of maximizing the seller’s revenue does not admit an FPTAS unless P = NP, even for basic instances with a single buyer. As a result, in the rest of the paper, we focus on designing PTASs. In order to do so, we first introduce a unifying framework encompassing both public and private signaling, whose core result is a decomposition lemma that allows focusing on a finite set of possible buyers’ posteriors. This forms the basis on which our PTASs are developed. In particular, in the public signaling setting, our PTAS employs some ad hoc techniques based on linear programming, while our PTAS for the private setting relies on the ellipsoid method to solve an exponentially-sized LP in polynomial time. In the latter case, we need a custom approximate separation oracle, which we implement with a dynamic programming approach.

PDF Details

IJCAI Conference 2022 Conference Paper

The Power of Media Agencies in Ad Auctions: Improving Utility through Coordinated Bidding

Giulia Romano
Matteo Castiglioni
Alberto Marchesi
Nicola Gatti

The increasing competition in digital advertising induced a proliferation of media agencies playing the role of intermediaries between advertisers and platforms selling ad slots. When a group of competing advertisers is managed by a common agency, many forms of collusion, such as bid rigging, can be implemented by coordinating bidding strategies, dramatically increasing advertisers' value. We study the problem of finding bids and monetary transfers maximizing the utility of a group of colluders, under GSP and VCG mechanisms. First, we introduce an abstract bid optimization problem---called weighted utility problem (WUP)---, which is useful in proving our results. We show that the utilities of bidding strategies are related to the length of paths in a directed acyclic weighted graph, whose structure and weights depend on the mechanism under study. This allows us to solve WUP in polynomial time by finding a shortest path of the graph. Next, we switch to our original problem, focusing on two settings that differ for the incentives they allow for. Incentive constraints ensure that colluders do not leave the agency, and they can be enforced by implementing monetary transfers between the agency and the advertisers. In particular, we study the arbitrary transfers setting, where any kind of monetary transfer to and from the advertisers is allowed, and the more realistic limited liability setting, in which no advertiser can be paid by the agency. In the former, we cast the problem as a WUP instance and solve it by our graph-based algorithm, while, in the latter, we formulate it as a linear program with exponentially-many variables efficiently solvable by applying the ellipsoid algorithm to its dual. This requires to solve a suitable separation problem in polynomial time, which can be done by reducing it to the weighted utility problem a WUP instance.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Online Posted Pricing with Unknown Time-Discounted Valuations

Giulia Romano
Gianluca Tartaglia
Alberto Marchesi
Nicola Gatti

We study the problem of designing posted-price mechanisms in order to sell a single unit of a single item within a finite period of time. Motivated by real-world problems, such as, e. g. , long-term rental of rooms and apartments, we assume that customers arrive online according to a Poisson process, and their valuations are drawn from an unknown distribution and discounted over time. We evaluate our mechanisms in terms of competitive ratio, measuring the worst-case ratio between their revenue and that of an optimal mechanism that knows the distribution of valuations. First, we focus on the identical valuation setting, where all the customers value the item for the same amount. In this setting, we provide a mechanism MC that achieves the best possible competitive ratio, discussing its dependency on the parameters in the case of linear discount. Then, we switch to the random valuation setting. We show that, if we restrict the attention to distributions of valuations with a monotone hazard rate, then the competitive ratio of MC is lower bounded by a strictly positive constant that does not depend on the distribution. Moreover, we provide another mechanism, called MPC, which is defined by a piecewise constant pricing strategy and reaches performances comparable to those obtained with MC. This mechanism is useful when the seller cannot change the posted price too often. Finally, we empirically evaluate the performances of our mechanisms in a number of experimental settings.

PDF Details

AAMAS Conference 2019 Conference Paper

Personality-Based Representations of Imperfect-Recall Games

Andrea Celli
Giulia Romano
Nicola Gatti

Games with imperfect recall are a powerful model of strategic interactions that allows agents to forget less important details of the past. Nevertheless, the computational treatment of imperfectrecall games is largely unexplored so far, and no efficient strategy representation for this setting is known. In this paper, we focus on general imperfect-recall games without absentmindedness, and we study how to produce a perfect-recall representation of these games using personalities. In particular, a valid personality assignment is a decomposition of an imperfect-recall player such that she does not exhibit memory losses within the same personality. Given a valid personality assignment, we can build an auxiliary team game where a team of perfect-recall players—sharing the same objectives— replaces a player with imperfect recall. Our primary goal is the construction of a compact representation in terms of number of personalities. We study the (iterated) inflation operation as a way to simplify the information structure of a game with imperfect recall. We show that the complete (i. e. , maximal) inflation of a game can be found in polynomial time. We also show that finding the valid personality assignment minimizing the number of personalities is NP-hard, and also hard to approximate, unless P = NP, even in a completely inflated game.

PDF