We address the challenge of aggregating the preferences of multiple agents
over LLM-generated replies to user queries, where agents might modify or
exaggerate their preferences. New agents may participate for each new query,
making fine-tuning LLMs on these preferences impractical. To overcome these
challenges, we propose an auction mechanism that operates without fine-tuning
or access to model weights. This mechanism is designed to provably converge to
the ouput of the optimally fine-tuned LLM as computational resources are
increased. The mechanism can also incorporate contextual information about the
agents when avaiable, which significantly accelerates its convergence. A
well-designed payment rule ensures that truthful reporting is the optimal
strategy for all agents, while also promoting an equity property by aligning
each agent's utility with her contribution to social welfare - an essential
feature for the mechanism's long-term viability. While our approach can be
applied whenever monetary transactions are permissible, our flagship
application is in online advertising. In this context, advertisers try to steer
LLM-generated responses towards their brand interests, while the platform aims
to maximize advertiser value and ensure user satisfaction. Experimental results
confirm that our mechanism not only converges efficiently to the optimally
fine-tuned LLM but also significantly boosts advertiser value and platform
revenue, all with minimal computational overhead.

我们提出一种无需微调或访问模型权重的拍卖机制，能有效聚合多个参与者对 LLM 生成的用户查询回复的偏好，并能加入可用的上下文信息，实现快速收敛，从而提高广告主价值和平台收入。

在线广告中基于 LLMs 的真实聚合

Truthful Aggregation of LLMs with an Application to Online Advertising

This paper studies the design and analysis of approximation algorithms for
aggregating preferences over combinatorial domains, represented using
Conditional Preference Networks (CP-nets). Its focus is on aggregating
preferences over so-called \emph{swaps}, for which optimal solutions in general
are already known to be of exponential size. We first analyze a trivial
2-approximation algorithm that simply outputs the best of the given input
preferences, and establish a structural condition under which the approximation
ratio of this algorithm is improved to $4/3$. We then propose a polynomial-time
approximation algorithm whose outputs are provably no worse than those of the
trivial algorithm, but often substantially better. A family of problem
instances is presented for which our improved algorithm produces optimal
solutions, while, for any $\varepsilon$, the trivial algorithm can\emph{not}\/
attain a $(2-\varepsilon)$-approximation. These results may lead to the first
polynomial-time approximation algorithm that solves the CP-net aggregation
problem for swaps with an approximation ratio substantially better than $2$.

该论文研究了设计和分析适用于将组合领域中使用条件偏好网络（CP-nets）表示的偏好进行聚合的近似算法。它侧重于对所谓的 “交换” 进行偏好聚合，其中已知的最优解通常具有指数规模。我们分析了一个简单的 2 近似算法，该算法仅输出给定输入偏好中的最佳解，并确定了一种结构条件，在此条件下改进了该算法的近似比率为 4/3。然后，我们提出了一种多项式时间逼近算法，其输出的解证明不会比简单算法差，但通常更好。我们提出了一族问题实例，对于这些问题实例，我们改进的算法产生最优解，而对于任何 ε 值，简单算法都不能获得（2-ε）近似解。这些结果可能导致首个在多项式时间内解决 CP-net 聚合问题的近似算法，其近似比率明显优于 2。

使用 CP-Nets 进行偏好聚合的近似算法

Approximation Algorithms for Preference Aggregation Using CP-Nets

We address the question of aggregating the preferences of voters in the
context of participatory budgeting. We scrutinize the voting method currently
used in practice, underline its drawbacks, and introduce a novel scheme
tailored to this setting, which we call "Knapsack Voting". We study its
strategic properties - we show that it is strategy-proof under a natural model
of utility (a dis-utility given by the $\ell_1$ distance between the outcome
and the true preference of the voter), and "partially" strategy-proof under
general additive utilities. We extend Knapsack Voting to more general settings
with revenues, deficits or surpluses, and prove a similar strategy-proofness
result. To further demonstrate the applicability of our scheme, we discuss its
implementation on the digital voting platform that we have deployed in
partnership with the local government bodies in many cities across the nation.
From voting data thus collected, we present empirical evidence that Knapsack
Voting works well in practice.

本文介绍了一种新的投票方案 Knapsack Voting，用于在参与预算的背景下对选民的偏好进行聚合。经过实证研究，该方案在实践中效果良好，并且在自然模型和一般加性效用下具有一定的策略证明性。