跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1112新增论文
+875其中 AI 相关
+133已有论文修订
+97新增 AI 导读

arXiv 最近完成扫描:2026-11-20 05:42 · 全站最近入库:2026-11-19 19:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-19 06:33 — 2026-11-20 06:33(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-20 05:42最近发现新增版本:2026-11-19 19:09库内论文最新更新时间:2026-11-19 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

27,982 已收录论文23,249 AI 相关8,559 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 3 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 05:40(北京时间)
版本更新 · v5arXiv:2509.05956

Pandora's Knapsack via Simple Policies

Zohar Barak, Asnat Berlin, Ilan Reuven Cohen, Alon Eden, Omri Porat, Inbal Talgam-Cohen

原文摘要

We introduce Pandora's Knapsack: a hybrid of the classic stochastic knapsack [Dean, Goemans, and Vondr'ak, 2008] and Pandora's box [Weitzman, 1979]. As in stochastic knapsack, items have sizes drawn from known distributions, and items that fit within a knapsack contribute to the total value. As in Pandora, every item $i$ comes in a box that costs $c_i$ to open. What distinguishes our problem is that the size is revealed only after opening the box and paying the cost. A motivating application from contract design is knapsack contracts, where a principal sequentially delegates jobs with stochastic processing times to agents before a deadline, and must pay each agent to incentivize effort, even if the job ends up not completing in time. We study the power of simple decision-making policies to approximate Pandora's Knapsack, along two complexity axes: (i)~knowledge of size distributions, and (ii)~adaptivity. We show that, compared to the classic stochastic knapsack and Pandora's box, policies in our model must be significantly more complex along both axes to be approximately optimal. Conversely, we show that with full distributional information and by allowing adaptive skipping of items, a constant approximation can be recovered. Our analysis reveals an economic quantity, namely ROI (return-on-investment, defined as the jobs' minimum utility over cost), which smoothly characterizes the performance of simple policies. Across a hierarchy of increasingly adaptive policies, we establish tight adaptivity gaps all governed by ROI. To demonstrate the importance of the ROI parameter in characterizing simple policies, we revisit Pandora's box, and show that return-on-investment exactly captures the adaptivity gap in this classic problem as well.

cs.GT

新论文 · v1arXiv:2611.07494

Transparency in Team Contracts

Paul Dütting, Yingkai Li, Inbal Talgam-Cohen, Jinzhao Wu

原文摘要

In contract design, the principal is often better informed about the project's chances of succeeding than the agents. To incentivize effort, the principal has two main tools: first, to design a contract, sharing part of the project's success among the agents; second, to design a (Bayesian) persuasion scheme, selectively sharing information with the agents. In this work we are interested in the optimal combination of both these tools. We tackle the joint problem through the prism of simplicity vs. optimality, and establish a stark dichotomy: The simple disclosure scheme of full transparency achieves a tight $4/3$-approximation to the optimal combination of information disclosure and team contract, when the team's production function is submodular. In contrast, full transparency can be arbitrarily far from optimal when production is supermodular. The techniques that we develop to bound the gap for submodular functions, also yield a new deterministic polynomial-time approximation algorithm for pure multi-agent contract design, with a significantly improved approximation ratio of $2.311$, and thus a $3.081$-approximation algorithm for the joint information and contracting problem.

cs.GT · econ.TH

版本更新 · v3arXiv:2606.30776

Optimal Auction Design for Constrained Buyers

Batya Berzack, Rotem Oshman, Inbal Talgam-Cohen

原文摘要

We study single-parameter, multi-buyer auctions in which buyers are subject to constraints that affect their bidding strategy. Such constraints arise in many real-world auction settings and fundamentally alter the auction design space: the revelation principle, envelope theorem, and Myerson's lemma no longer hold. Our focus is on a large family of constraints where the buyers do not have a hard budget-cap, but are restricted in how they can bid or spend their budget --- including no-overbidding, ex-post individual rationality (IR), and stagewise IR. We ask whether the seller can leverage the buyers' constraints to obtain improved payoff. We separate between \emph{revenue-aligned} seller objectives (revenue, welfare, or any linear combination), and \emph{consumer-aligned} seller objectives (e.g.\ consumer surplus). For the former, we establish a unified theory for all constraints in the family, which parallels Myerson's theory of optimal auctions for unconstrained buyers. We develop a new measure-theoretic technique to show that Myerson-style auctions remain optimal, despite the altered design space and failure of the classical theory's central tenets. In contrast, we show a consumer-aligned seller can leverage the buyers' strategic limitations to strictly outperform mechanisms that are classically incentive compatible. We also design an auction arbitrarily close to optimal for buyers who cannot tolerate temporary debt.

cs.GT