LIVIVO - Search results -

Search results

Result 1 - 10 of total 23

Search options

Book ; Online: Bayesian Conversations

Leme, Renato Paes / Schneider, Jon / Zheng, Shuran

2023

Abstract: We initiate the study of Bayesian conversations, which model interactive communication between two strategic agents without a mediator. We compare this to communication through a mediator and investigate the settings in which mediation can expand the ... ...

Abstract	We initiate the study of Bayesian conversations, which model interactive communication between two strategic agents without a mediator. We compare this to communication through a mediator and investigate the settings in which mediation can expand the range of implementable outcomes. In the first part of the paper, we ask whether the distributions of posterior beliefs that can be induced by a mediator protocol can also be induced by a (unmediated) Bayesian conversation. We show this is not possible -- mediator protocols can ``correlate'' the posteriors in a way that unmediated conversations cannot. Additionally, we provide characterizations of which distributions over posteriors are achievable via mediator protocols and Bayesian conversations. In the second part of the paper, we delve deeper into the eventual outcome of two-player games after interactive communication. We focus on games where only one agent has a non-trivial action and examine the performance of communication protocols that are individually rational (IR) for both parties. We consider different levels of IR including ex-ante, interim, and ex-post; and we impose different restrictions on how Alice and Bob can deviate from the protocol: the players are committed/non-committed. Our key findings reveal that, in the cases of ex-ante and interim IR, the expected utilities achievable through a mediator are equivalent to those achievable through unmediated Bayesian conversations. However, in the models of ex-post IR and non-committed interim IR, we observe a separation in the achievable outcomes.
Keywords	Computer Science - Computer Science and Game Theory
Publishing date	2023-07-17
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Description Complexity of Regular Distributions

Leme, Renato Paes / Sivan, Balasubramanian / Teng, Yifeng / Worah, Pratik

2023

Abstract: Myerson's regularity condition of a distribution is a standard assumption in economics. In this paper, we study the complexity of describing a regular distribution within a small statistical distance. Our main result is that $\tilde{\Theta}{(\epsilon^{-0. ...

Abstract	Myerson's regularity condition of a distribution is a standard assumption in economics. In this paper, we study the complexity of describing a regular distribution within a small statistical distance. Our main result is that $\tilde{\Theta}{(\epsilon^{-0.5})}$ bits are necessary and sufficient to describe a regular distribution with support $[0,1]$ within $\epsilon$ Levy distance. We prove this by showing that we can learn the regular distribution approximately with $\tilde{O}(\epsilon^{-0.5})$ queries to the cumulative density function. As a corollary, we show that the pricing query complexity to learn the class of regular distribution with support $[0,1]$ within $\epsilon$ Levy distance is $\tilde{\Theta}{(\epsilon^{-2.5})}$. To learn the mixture of two regular distributions, $\tilde{\Theta}(\epsilon^{-3})$ pricing queries are required.
Keywords	Computer Science - Computer Science and Game Theory ; Economics - Theoretical Economics
Publishing date	2023-05-09
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: U-Calibration

Kleinberg, Robert / Leme, Renato Paes / Schneider, Jon / Teng, Yifeng

Forecasting for an Unknown Agent

2023

Abstract: We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility is unknown to the forecaster. We show that optimizing forecasts for a ... ...

Abstract	We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility is unknown to the forecaster. We show that optimizing forecasts for a single scoring rule (e.g., the Brier score) cannot guarantee low regret for all possible agents. In contrast, forecasts that are well-calibrated guarantee that all agents incur sublinear regret. However, calibration is not a necessary criterion here (it is possible for miscalibrated forecasts to provide good regret guarantees for all possible agents), and calibrated forecasting procedures have provably worse convergence rates than forecasting procedures targeting a single scoring rule. Motivated by this, we present a new metric for evaluating forecasts that we call U-calibration, equal to the maximal regret of the sequence of forecasts when evaluated under any bounded scoring rule. We show that sublinear U-calibration error is a necessary and sufficient condition for all agents to achieve sublinear regret guarantees. We additionally demonstrate how to compute the U-calibration error efficiently and provide an online algorithm that achieves $O(\sqrt{T})$ U-calibration error (on par with optimal rates for optimizing for a single scoring rule, and bypassing lower bounds for the traditionally calibrated learning procedures). Finally, we discuss generalizations to the multiclass prediction setting. Comment: Accepted for presentation at the Conference on Learning Theory (COLT) 2023
Keywords	Computer Science - Machine Learning ; Computer Science - Computer Science and Game Theory
Subject code	006
Publishing date	2023-06-30
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Ex-post Individually Rational Bayesian Persuasion

Zhang, Jiahao / Zheng, Shuran / Leme, Renato Paes / Wu, Zhiwei Steven

2023

Abstract: The success of Bayesian persuasion relies on the key assumption that the sender will commit to a predetermined information disclosure policy (signaling scheme). However, in practice, it is usually difficult for the receiver to monitor whether the sender ... ...

Abstract	The success of Bayesian persuasion relies on the key assumption that the sender will commit to a predetermined information disclosure policy (signaling scheme). However, in practice, it is usually difficult for the receiver to monitor whether the sender sticks to the disclosure policy, which makes the credibility of the sender's disclosure policy questionable. The sender's credibility is particularly tenuous when there are obvious deviations that benefit the sender. In this work, we identify such a deviation: the sender may be unwilling to send a signal that will lead to a less desirable outcome compared to no information disclosure. We thus propose the notion of ex-post individually rational (ex-post IR) Bayesian persuasion: after observing the state, the sender is never required to send a signal that will make the outcome worse off (compared to no information disclosure). An ex-post IR Bayesian persuasion policy is more likely to be truthfully followed by the sender, and thus more credible for the receiver. Our contribution is threefold. Firstly, we demonstrate that the optimal ex-post IR Bayesian persuasion policy can be efficiently computed through a linear program, while also offering geometric characterizations of this optimal policy. Second, we show that surprisingly, for non-trivial classes of games, the imposition of ex-post IR constraints does not affect the sender's expected utility. Finally, we compare ex-post IR Bayesian persuasion to other information disclosure models that ensure different notions of credibility. Comment: 21 pages
Keywords	Computer Science - Computer Science and Game Theory
Subject code	360
Publishing date	2023-12-08
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Corruption-Robust Contextual Search through Density Updates

Leme, Renato Paes / Podimata, Chara / Schneider, Jon

2022

Abstract: We study the problem of contextual search in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of noise in the system. For the $\eps$-ball loss, we give a tight regret bound of $O(C + ...

Abstract	We study the problem of contextual search in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of noise in the system. For the $\eps$-ball loss, we give a tight regret bound of $O(C + d \log(1/\eps))$ improving over the $O(d^3 \log(1/\eps)) \log^2(T) + C \log(T) \log(1/\eps))$ bound of Krishnamurthy et al (STOC21). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. Our techniques are a significant departure from prior approaches. Specifically, we keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained. Comment: Extended abstract accepted at COLT22
Keywords	Computer Science - Machine Learning ; Computer Science - Computer Science and Game Theory
Publishing date	2022-06-15
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Bernoulli Factories for Flow-Based Polytopes

Niazadeh, Rad / Leme, Renato Paes / Schneider, Jon

2022

Abstract: We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit ... ...

Abstract	We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and $k$-flows. In the process, we uncover new connections to algebraic combinatorics.
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Mathematics - Combinatorics ; Mathematics - Probability
Publishing date	2022-07-18
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Mechanism Design for Large Language Models

Duetting, Paul / Mirrokni, Vahab / Leme, Renato Paes / Xu, Haifeng / Zuo, Song

2023

Abstract: We investigate auction mechanisms to support the emerging format of AI-generated content. We in particular study how to aggregate several LLMs in an incentive compatible manner. In this problem, the preferences of each agent over stochastically generated ...

Abstract	We investigate auction mechanisms to support the emerging format of AI-generated content. We in particular study how to aggregate several LLMs in an incentive compatible manner. In this problem, the preferences of each agent over stochastically generated contents are described/encoded as an LLM. A key motivation is to design an auction format for AI-generated ad creatives to combine inputs from different advertisers. We argue that this problem, while generally falling under the umbrella of mechanism design, has several unique features. We propose a general formalism -- the token auction model -- for studying this problem. A key feature of this model is that it acts on a token-by-token basis and lets LLM agents influence generated contents through single dimensional bids. We first explore a robust auction design approach, in which all we assume is that agent preferences entail partial orders over outcome distributions. We formulate two natural incentive properties, and show that these are equivalent to a monotonicity condition on distribution aggregation. We also show that for such aggregation functions, it is possible to design a second-price auction, despite the absence of bidder valuation functions. We then move to designing concrete aggregation functions by focusing on specific valuation forms based on KL-divergence, a commonly used loss function in LLM. The welfare-maximizing aggregation rules turn out to be the weighted (log-space) convex combination of the target distributions from all participants. We conclude with experimental results in support of the token auction formulation.
Keywords	Computer Science - Computer Science and Game Theory ; Economics - Theoretical Economics
Subject code	005
Publishing date	2023-10-16
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Optimal Contextual Pricing and Extensions

Liu, Allen / Leme, Renato Paes / Schneider, Jon

2020

Abstract: In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\mathbb{R}^d$ and only observes the purchasing decisions of a buyer with a fixed but unknown linear valuation over the products. ...

Abstract	In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in $\mathbb{R}^d$ and only observes the purchasing decisions of a buyer with a fixed but unknown linear valuation over the products. The regret measures the difference between the revenue the seller could have obtained knowing the buyer valuation and what can be obtained by the learning algorithm. We give a poly-time algorithm for contextual pricing with $O(d \log \log T + d \log d)$ regret which matches the $\Omega(d \log \log T)$ lower bound up to the $d \log d$ additive factor. If we replace pricing loss by the symmetric loss, we obtain an algorithm with nearly optimal regret of $O(d \log d)$ matching the $\Omega(d)$ lower bound up to $\log d$. These algorithms are based on a novel technique of bounding the value of the Steiner polynomial of a convex region at various scales. The Steiner polynomial is a degree $d$ polynomial with intrinsic volumes as the coefficients. We also study a generalized version of contextual search where the hidden linear function over the Euclidean space is replaced by a hidden function $f : \mathcal{X} \rightarrow \mathcal{Y}$ in a certain hypothesis class $\mathcal{H}$. We provide a generic algorithm with $O(d^2)$ regret where $d$ is the covering dimension of this class. This leads in particular to a $\tilde{O}(s^2)$ regret algorithm for linear contextual search if the linear function is guaranteed to be $s$-sparse. Finally we also extend our results to the noisy feedback model, where each round our feedback is flipped with a fixed probability $p < 1/2$. Comment: Updated title to "Optimal Contextual Pricing and Extensions"
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Machine Learning
Subject code	005
Publishing date	2020-03-03
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Bandits with adversarial scaling

Lykouris, Thodoris / Mirrokni, Vahab / Leme, Renato Paes

2020

Abstract: We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a (fixed across time) arm-quality ... ...

Abstract	We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest. Comment: Appeared in ICML 2020
Keywords	Computer Science - Machine Learning ; Computer Science - Computer Science and Game Theory ; Statistics - Machine Learning
Publishing date	2020-03-04
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Combinatorial Bernoulli Factories

Niazadeh, Rad / Leme, Renato Paes / Schneider, Jon

Matchings, Flows and Other Polytopes

2020

Abstract: A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means the algorithm does not know $p$, but has sample access to ...

Abstract	A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p \in [0,1]$ means the algorithm does not know $p$, but has sample access to independent draws of a Bernoulli random variable with mean equal to $p$. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector $x\in \mathcal{P}$ for a given polytope $\mathcal{P}\subset [0,1]^n$, output a randomized vertex such that the expected value of the $i$-th coordinate is \emph{exactly} equal to $x_i$. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix $[x_{ij}]$ and asked to sample a matching such that the probability of each edge $(i,j)$ be present in the matching is exactly equal to $x_{ij}$. We show that a polytope $\mathcal{P}$ admits a Bernoulli factory if and and only if $\mathcal{P}$ is the intersection of $[0,1]^n$ with an affine subspace. Our construction is based on an algebraic formulation of the problem, involving identifying a family of Bernstein polynomials (one per vertex) that satisfy a certain algebraic identity on $\mathcal{P}$. The main technical tool behind our construction is a connection between these polynomials and the geometry of zonotope tilings. We apply these results to construct an explicit factory for the perfect matching polytope. The resulting factory is deeply connected to the combinatorial enumeration of arborescences and may be of independent interest. For the $k$-uniform matroid polytope, we recover a sampling procedure known in statistics as Sampford sampling. Comment: 41 pages, 9 figures
Keywords	Computer Science - Data Structures and Algorithms ; Computer Science - Discrete Mathematics ; Computer Science - Computer Science and Game Theory ; Mathematics - Combinatorics ; Mathematics - Probability
Subject code	000
Publishing date	2020-11-07
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED