Source author record

Riccardo Colini-Baldeschi

Riccardo Colini-Baldeschi appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Artificial Intelligence Machine Learning

Catalog footprint

What is connected

4works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2023arXiv

Fully Dynamic Online Selection through Online Contention Resolution Schemes

We study fully dynamic online selection problems in an adversarial/stochastic setting that includes Bayesian online selection, prophet inequalities, posted price mechanisms, and stochastic probing problems subject to combinatorial constraints. In the classical ``incremental'' version of the problem, selected elements remain active until the end of the input sequence. On the other hand, in the fully dynamic version of the problem, elements stay active for a limited time interval, and then leave. This models, for example, the online matching of tasks to workers with task/worker-dependent working times, and sequential posted pricing of perishable goods. A successful approach to online selection problems in the adversarial setting is given by the notion of Online Contention Resolution Scheme (OCRS), that uses a priori information to formulate a linear relaxation of the underlying optimization problem, whose optimal fractional solution is rounded online for any adversarial order of the input sequence. Our main contribution is providing a general method for constructing an OCRS for fully dynamic online selection problems. Then, we show how to employ such OCRS to construct no-regret algorithms in a partial information model with semi-bandit feedback and adversarial inputs.

preprint2021arXiv

Approximately Efficient Two-Sided Combinatorial Auctions

Mechanism design for one-sided markets has been investigated for several decades in economics and in computer science. More recently, there has been an increased attention on mechanisms for two-sided markets, in which buyers and sellers act strategically. For two-sided markets, an impossibility result of Myerson and Satterthwaite states that no mechanism can simultaneously satisfy individual rationality (IR), incentive compatibility (IC), strong budget-balance (SBB), and be efficient. On the other hand, important applications to web advertisement, stock exchange, and frequency spectrum allocation, require us to consider two-sided combinatorial auctions in which buyers have preferences on subsets of items, and sellers may offer multiple heterogeneous items. No efficient mechanism was known so far for such two-sided combinatorial markets. This work provides the first IR, IC and SBB mechanisms that provides an O(1)-approximation to the optimal social welfare for two-sided markets. An initial construction yields such a mechanism, but exposes a conceptual problem in the traditional SBB notion. This leads us to define the stronger notion of direct trade strong budget balance (DSBB). We then proceed to design mechanisms that are IR, IC, DSBB, and again provide an O(1)-approximation to the optimal social welfare. Our mechanisms work for any number of buyers with XOS valuations - a class in between submodular and subadditive functions - and any number of sellers. We provide a mechanism that is dominant strategy incentive compatible (DSIC) if the sellers each have one item for sale, and one that is bayesian incentive compatible (BIC) if sellers hold multiple items and have additive valuations over them. Finally, we present a DSIC mechanism for the case that the valuation functions of all buyers and sellers are additive.

preprint2016arXiv

Revenue Maximizing Envy-Free Pricing in Matching Markets with Budgets

We study envy-free pricing mechanisms in matching markets with $m$ items and $n$ budget constrained buyers. Each buyer is interested in a subset of the items on sale, and she appraises at some single-value every item in her preference-set. Moreover, each buyer has a budget that constraints the maximum affordable payment, while she aims to obtain as many items as possible of her preference-set. Our goal is to compute an envy-free pricing allocation that maximizes the revenue, i.e., the total payment charged to the buyers. This pricing problem is hard to approximate better than $Ω({\rm min} \{n,m\}^{1/2-ε})$ for any $ε>0$, unless $P=NP$. The hardness result is due to the presence of the matching constraints given that the simpler multi-unit case can be approximated up to a constant factor of $2$. The goal of this paper is to circumvent the hardness result by restricting ourselves to specific settings of valuations and budgets. Two particularly significant scenarios are: each buyer has a budget that is greater than her single-value valuation, and each buyer has a budget that is lower than her single-value valuation. Surprisingly, in both scenarios we are able to achieve a $1/4$-approximation to the optimal envy-free revenue. The algorithms utilize a novel version of the Ausebel ascending price auction. These results may suggest that, although it is difficult to approximate the optimal revenue in general, ascending price auctions could achieve relatively good revenue in most of the practical settings.

preprint2011arXiv

On Multiple Round Sponsored Search Auctions with Budgets

In a sponsored search auction the advertisement slots on a search result page are generally ordered by click-through rate. Bidders have a valuation, which is usually assumed to be linear in the click-through rate, a budget constraint, and receive at most one slot per search result page (round). We study multi-round sponsored search auctions, where the different rounds are linked through the budget constraints of the bidders and the valuation of a bidder for all rounds is the sum of the valuations for the individual rounds. All mechanisms published so far either study one-round sponsored search auctions or the setting where every round has only one slot and all slots have the same click-through rate, which is identical to a multi-item auction. This paper contains the following three results: (1) We give the first mechanism for the multi-round sponsored search problem where different slots have different click-through rates. Our mechanism is incentive compatible in expectation, individually rational in expectation, Pareto optimal in expectation, and also ex-post Pareto optimal for each realized outcome. (2) Additionally we study the combinatorial setting, where each bidder is only interested in a subset of the rounds. We give a deterministic, incentive compatible, individually rational, and Pareto optimal mechanism for the setting where all slots have the same click-through rate. (3) We present an impossibility result for auctions where bidders have diminishing marginal valuations. Specifically, we show that even for the multi-unit (one slot per round) setting there is no incentive compatible, individually rational, and Pareto optimal mechanism for private diminishing marginal valuations and public budgets.