Michal Feldman, Tel Aviv University
Title: Ambiguous Contracts
Abstract: In this work we explore the deliberate infusion of ambiguity into the design of contracts. We show that when the agent is ambiguity-averse and chooses an action that maximizes their max-min utility, then the principal can strictly gain from using an ambiguous contract. We provide insights into the structure of optimal contracts, and establish that optimal ambiguous contracts are composed of simple contracts. We also provide a characterization of ambiguity-proof classes of contracts. Finally, we show that when the agent considers mixed strategies, then there is no advantage in using an ambiguous contract.
Joint work with Paul Duetting, Daniel Peretz and Larry Samuelson.
Vincenzo Bonifaci, Roma Tre University
Title: On a Voter Model with Context-Dependent Opinion Adoption
Abstract: Opinion diffusion is a crucial phenomenon in social networks, shaping the way in which, if at all, collectives of agents achieve consensus on decisions of common interest. The voter model is a well-known theoretical model of opinion spreading in social networks and structured populations. Its simplest version assumes that an agent revising its opinion will adopt the opinion of a neighbor chosen at random. Despite its simplicity, this model often affords characterization of quantities of interest, such as the probability that a certain opinion will fixate into a consensus opinion, or the expected time it takes for consensus to emerge.
Standard voter models are oblivious to the opinions held by the agents involved in the process. In this study, we investigate a context-dependent opinion spreading process on a social graph, in which the probability that an agent abandons opinion A in favor of opinion B depends on both A and B. We discuss the relations of this model with existing voter models and we derive theoretical results for both the fixation probability and the expected consensus time for two opinions, both when opinion updates occur synchronously and when they occur asynchronously. Experimental results and a non rigorous, mean-field approach provide further insights into cases that seem impervious to a rigorous analysis, also shedding light on general, potential instabilities of the dynamics in the case of more than two opinions.
Mathieu Molina, CREST-INRIA
Title: Prophet Inequalities: Competing with the Top ℓ Items is Easy
Abstract: We explore a prophet inequality problem, where the values of a sequence of items are drawn i.i.d. from some distribution, and an online decision maker must select one item irrevocably. We establish that CRℓ the worst-case competitive ratio between the expected optimal performance of an online decision maker compared to that of a prophet who uses the average of the top ℓ items is exactly the solution to an integral equation. This quantity CRℓ is larger than 1−e−ℓ. This implies that the bound converges exponentially fast to 1 as ℓ grows. In particular for ℓ=2, CR2≈0.966 which is much closer to 1 than the classical bound of 0.745 for ℓ=1. Additionally, we prove asymptotic lower bounds for the competitive ratio of a more general scenario, where the decision maker is permitted to select k items. This subsumes the k multi-unit i.i.d. prophet problem and provides the current best asymptotic guarantees, as well as enables broader understanding in the more general framework. Finally, we prove a tight asymptotic competitive ratio when only static threshold policies are allowed.
Matteo Russo, Sapienza University of Rome
Title: . Online Learning with Sublinear Best-Action Queries
Abstract: In online learning, a decision maker repeatedly selects one of a set of actions, with the goal of minimizing the overall loss incurred. Following the recent line of research on algorithms endowed with additional predictive features, we revisit this problem by allowing the decision maker to acquire additional information on the actions to be selected. In particular, we study the power of \emph{best-action queries}, which reveal beforehand the identity of the best action at a given time step. In practice, predictive features may be expensive, so we allow the decision maker to issue at most $k$ such queries. We establish tight bounds on the performance any algorithm can achieve when given access to $k$ best-action queries for different types of feedback models. In particular, we prove that in the full feedback model, $k$ queries are enough to achieve an optimal regret of $\Theta(\min\{\sqrt T, \frac Tk\})$. This finding highlights the significant multiplicative advantage in the regret rate achievable with even a modest (sublinear) number $k \in \Omega(\sqrt{T})$ of queries. Additionally, we study the challenging setting in which the only available feedback is obtained during the time steps corresponding to the $k$ best-action queries. There, we provide a tight regret rate of $\Theta(\min\{\frac{T}{\sqrt k},\frac{T^2}{k^2}\})$, which improves over the standard $\Theta(\frac{T}{\sqrt k})$ regret rate for label efficient prediction for $k \in \Omega(T^{2/3})$.
This work has been accepted for publication at NeurIPS 2024 and is joint work with Andrea Celli, Riccardo Colini-Baldeschi, Federico Fusco, Daniel Haimovich, Dima Karamshuk, Stefano Leonardi and Niek Tax.
Michele Salvi, University of Rome Tor Vergata
Title: Random Spanning Trees in Random Environment
Abstract: A spanning tree of a graph G is a connected subset of G without cycles. The Uniform Spanning Tree (UST) is obtained by choosing one of the possible spanning trees of G at random. The Minimum Spanning Tree (MST) is realised instead by putting random weights on the edges of G and then selecting the spanning tree with the smallest weight. These two models exhibit markedly different behaviours: for example, their diameter on the complete graph with n nodes transitions from n^1/2 for the UST to n^1/3 for the MST. What lies in between?
We introduce a model of Random Spanning Trees in Random Environment (RSTRE) designed to interpolate between UST and MST. In particular, when the environment disorder is sufficiently low, the RSTRE on the complete graph has a diameter of n^1/2 as the UST. Conversely, when the disorder is high, the diameter behaves like n^1/3 as for the MST. We conjecture a smooth transition between these two values for intermediate levels of disorder.
This talk is based on joint work with Rongfeng Sun and Luca Makowiec (NUS Singapore).