Grant Schoenebeck

ICLR Conference 2025 Conference Paper

Benchmarking LLMs' Judgments with No Gold Standard

• Shengwei Xu
• Yuxuan Lu 0001
• Grant Schoenebeck
• Yuqing Kong

We introduce the GEM (Generative Estimator for Mutual Information), an evaluation metric for assessing language generation by large language models (LLMs), particularly in generating informative judgments, without the need for a gold standard reference. GEM broadens the scenarios where we can benchmark LLM generation performance-from traditional ones, like machine translation and summarization, where gold standard references are readily available, to subjective tasks without clear gold standards, such as academic peer review. GEM uses a generative model to estimate mutual information between candidate and reference responses, without requiring the reference to be a gold standard. In experiments on two human-annotated datasets, GEM demonstrates competitive correlations with human scores compared to the state-of-the-art GPT-4o Examiner, and outperforms all other baselines. Additionally, GEM is more robust against strategic manipulation, such as rephrasing or elongation, which can artificially inflate scores under a GPT-4o Examiner. We also present GRE-bench (Generating Review Evaluation Benchmark) which evaluates LLMs based on how well they can generate high-quality peer reviews for academic research papers. Because GRE-bench is based upon GEM, it inherits its robustness properties. Additionally, GRE-bench circumvents data contamination problems (or data leakage) by using the continuous influx of new open-access research papers and peer reviews each year. We show GRE-bench results of various popular LLMs on their peer review capabilities using the ICLR2023 dataset.

NeurIPS Conference 2025 Conference Paper

Stochastically Dominant Peer Prediction

• Yichi Zhang
• Shengwei Xu
• Grant Schoenebeck
• David Pennock

Eliciting reliable human feedback is essential for many machine learning tasks, such as learning from noisy labels and aligning AI systems with human preferences. Peer prediction mechanisms incentivize truthful reporting without ground truth verification by scoring agents based on correlations with peers. Traditional mechanisms, which ensure that truth-telling maximizes the \textbf{expected scores} in equilibrium, can elicit honest information while assuming agents' utilities are \textbf{linear functions} of their scores. However, in practice, non-linear payment rules are usually preferred, or agents' utilities are inherently non-linear. We propose \emph{stochastically dominant truthfulness (SD-truthfulness)} as a stronger guarantee: the score distribution of truth-telling stochastically dominates all other strategies, incentivizing truthful reporting for a wide range of monotone utility functions. Our first observation is that no existing peer prediction mechanism naturally satisfies this criterion without strong assumptions. A simple solution - rounding scores into binary lotteries — can enforce SD-truthfulness, but often degrades \emph{sensitivity}, a key property related to fairness and statistical efficiency. We demonstrate how a more careful application of rounding can better preserve sensitivity. Furthermore, we introduce a new enforced agreement (EA) mechanism that is theoretically guaranteed to be SD-truthful in binary-signal settings and, under mild assumptions, empirically achieves the highest sensitivity among all known SD-truthful mechanisms.

AAAI Conference 2024 Conference Paper

Eliciting Honest Information from Authors Using Sequential Review

• Yichi Zhang
• Grant Schoenebeck
• Weijie Su

In the setting of conference peer review, the conference aims to accept high-quality papers and reject low-quality papers based on noisy review scores. A recent work proposes the isotonic mechanism, which can elicit the ranking of paper qualities from an author with multiple submissions to help improve the conference's decisions. However, the isotonic mechanism relies on the assumption that the author's utility is both an increasing and a convex function with respect to the review score, which is often violated in realistic settings (e.g.~when authors aim to maximize the number of accepted papers). In this paper, we propose a sequential review mechanism that can truthfully elicit the ranking information from authors while only assuming the agent's utility is increasing with respect to the true quality of her accepted papers. The key idea is to review the papers of an author in a sequence based on the provided ranking and conditioning the review of the next paper on the review scores of the previous papers. Advantages of the sequential review mechanism include: 1) eliciting truthful ranking information in a more realistic setting than prior work; 2) reducing the reviewing workload and increasing the average quality of papers being reviewed; 3) incentivizing authors to write fewer papers of higher quality.

UAI Conference 2023 Conference Paper

Testing conventional wisdom (of the crowd)

• Noah Burrell
• Grant Schoenebeck

Do common assumptions about the way that crowd workers make mistakes in microtask (labeling) applications manifest in real crowdsourcing data? Prior work only addresses this question indirectly. Instead, it primarily focuses on designing new label aggregation algorithms, seeming to imply that better performance justifies any additional assumptions. However, empirical evidence in past instances has raised significant challenges to common assumptions. We continue this line of work, using crowdsourcing data itself as directly as possible to interrogate several basic assumptions about workers and tasks. We find strong evidence that the assumption that workers respond correctly to each task with a constant probability, which is common in theoretical work, is implausible in real data. We also illustrate how heterogeneity among tasks and workers can take different forms, which have different implications for the design and evaluation of label aggregation algorithms.

JAIR Journal 2022 Journal Article

Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization

• Wei Chen
• Binghui Peng
• Grant Schoenebeck
• Biaoshuai Tao

We consider the adaptive influence maximization problem: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the full-adoption feedback model, after selecting each seed, the seed-picker observes all the resulting adoptions. In the myopic feedback model, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of greedy adaptivity gap, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a (1 − 1/e)-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a (1−1/e) fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the independent cascade model and the linear threshold model. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a (1 − 1/e)-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular diffusion model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.

AAMAS Conference 2022 Conference Paper

Optimal Local Bayesian Differential Privacy over Markov Chains

• Darshan Chakrabarti
• Jie Gao
• Aditya Saraf
• Grant Schoenebeck
• Fang-Yi Yu

In this paper, we focus on data generated from a Markov chain and provide optimal mechanisms for local Bayesian differential privacy (BDP) guarantees. Our main theoretical contribution is to provide a mechanism for achieving BDP when data is drawn from a binary Markov chain. We improve on the state-of-the-art BDP mechanism and show that our mechanism provides the optimal noise-privacy tradeoffs for any local mechanism up to negligible factors. We perform experiments on synthetic data to show that a correlation aware adversary can launch successful attacks on data that satisfies only the vanilla differential privacy guarantees. Finally, we perform experiments on real data to show that our privacy guarantees are robust to underlying distributions that are not simple Markov chains.

I&C Journal 2022 Journal Article

Think globally, act locally: On the optimal seeding for nonsubmodular influence maximization

• Grant Schoenebeck
• Biaoshuai Tao
• Fang-Yi Yu

In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. We study this problem with the r-complex contagion model, where each uninfected vertex in the network becomes infected if it has at least r infected neighbors. We focus on a random graph model called the stochastic hierarchical blockmodel. When the graph is not exceptionally sparse, under certain mild assumptions, we prove the optimal seeding strategy puts all the seeds in a single community. This matches the intuition that, in a nonsubmodular cascade model, placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e. g. , the independent cascade model) in which nearby seeds tend to erode each others' effects. We use this observation to design a polynomial-time dynamic programming algorithm for a slightly more general setting.

IJCAI Conference 2021 Conference Paper

SURPRISE! and When to Schedule It.

• Zhihuan Huang
• Shengwei Xu
• You Shan
• Yuxuan Lu
• Yuqing Kong
• Tracy Xiao Liu
• Grant Schoenebeck

Information flow measures, over the duration of a game, the audience’s belief of who will win, and thus can reflect the amount of surprise in a game. To quantify the relationship between information flow and audiences' perceived quality, we conduct a case study where subjects watch one of the world’s biggest esports events, LOL S10. In addition to eliciting information flow, we also ask subjects to report their rating for each game. We find that the amount of surprise in the end of the game plays a dominant role in predicting the rating. This suggests the importance of incorporating when the surprise occurs, in addition to the amount of surprise, in perceived quality models. For content providers, it implies that everything else being equal, it is better for twists to be more likely to happen toward the end of a show rather than uniformly throughout.

AAMAS Conference 2021 Conference Paper

Timely Information from Prediction Markets

• Grant Schoenebeck
• Chenkai Yu
• Fang-Yi Yu

Prediction markets are powerful tools to elicit and aggregate beliefs from strategic agents. However, in current prediction markets, agents may exhaust the social welfare by competing to be the first to update the market. We initiate the study of the trade-off between how quickly information is aggregated by the market, and how much this information costs. We design markets to aggregate timely information from strategic agents to maximize social welfare. To this end, the market must incentivize agents to invest the correct amount of effort to acquire information: quickly enough to be useful, but not faster (and more expensively) than necessary. The market also must ensure that agents report their information truthfully and on time. We consider two settings: in the first, information is only valuable before a deadline; in the second, the value of information decreases as time passes. We use both theorems and simulations to demonstrate the mechanisms.

NeurIPS Conference 2021 Conference Paper

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

• Grant Schoenebeck
• Biaoshuai Tao

We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. As a special case, our model captures the common scenario where voters can be categorized into three types: those who always prefer one alternative, those who always prefer the other, and those contingent voters whose preferences depends on the state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased. We present a mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).

AAAI Conference 2020 Conference Paper

Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization

• Wei Chen
• Binghui Peng
• Grant Schoenebeck
• Biaoshuai Tao

We consider the adaptive influence maximization problem: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the full-adoption feedback model, after selecting each seed, the seed-picker observes all the resulting adoptions. In the myopic feedback model, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of greedy adaptivity gap, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a (1 − 1/e)-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a (1 − 1/e) fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the independent cascade model and the linear threshold model. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a (1 − 1/e)-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular cascade model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.

AAAI Conference 2020 Conference Paper

Information Elicitation Mechanisms for Statistical Estimation

• Yuqing Kong
• Grant Schoenebeck
• Biaoshuai Tao
• Fang-Yi Yu

We study learning statistical properties from strategic agents with private information. In this problem, agents must be incentivized to truthfully reveal their information even when it cannot be directly verified. Moreover, the information reported by the agents must be aggregated into a statistical estimate. We study two fundamental statistical properties: estimating the mean of an unknown Gaussian, and linear regression with Gaussian error. The information of each agent is one point in a Euclidean space. Our main results are two mechanisms for each of these problems which optimally aggregate the information of agents in the truth-telling equilibrium: • A minimal (non-revelation) mechanism for large populations — agents only need to report one value, but that value need not be their point. • A mechanism for small populations that is non-minimal — agents need to answer more than one question. These mechanisms are “informed truthful” mechanisms where reporting unaltered data (truth-telling) 1) forms a strict Bayesian Nash equilibrium and 2) has strictly higher welfare than any oblivious equilibrium where agents’ strategies are independent of their private signals. We also show a minimal revelation mechanism (each agent only reports her signal) for a restricted setting and use an impossibility result to prove the necessity of this restriction. We build upon the peer prediction literature in the singlequestion setting; however, most previous work in this area focuses on discrete signals, whereas our setting is inherently continuous, and we further simplify the agents’ reports.

AAMAS Conference 2019 Conference Paper

The Volatility of Weak Ties: Co-evolution of Selection and Influence in Social Networks

• Jie Gao
• Grant Schoenebeck
• Fang-Yi Yu

In this work we look at opinion formation and the effects of two phenomena both of which promote consensus between agents connected by ties: influence, agents changing their opinions to match their neighbors; and selection, agents re-wiring to connect to new agents when the existing neighbor has a different opinion. In our agent-based model, we assume that only weak ties can be rewired and strong ties do not change. The network structure as well as the opinion landscape thus co-evolve with two important parameters: the probability of influence versus selection; and the fraction of strong ties versus weak ties. Using empirical and theoretical methodologies we discovered that on a two-dimensional spatial network: • With no/low selection the presence of weak ties enables fast consensus. This conforms with the classical theory that weak ties are helpful for quickly mixing and spreading information, and strong ties alone act much more slowly. • With high selection, too many weak ties inhibit any consensus at all—the graph partitions. The weak ties reinforce the differing opinions rather than mixing them. However, sufficiently many strong ties promote convergence, though at a slower pace. We additionally test the aforementioned results using a real network. Our study relates two theoretical ideas: the strength of weak ties— that weak ties are useful for spreading information; and the idea of echo chambers or filter bubbles, that people are typically bombarded by the opinions of like-minded individuals. The difference is in how (much) selection operates.

ICLR Conference 2018 Conference Paper

Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality

• Xingjun Ma
• Bo Li 0026
• Yisen Wang 0001
• Sarah Monazam Erfani
• Sudanthi N. R. Wijewickrema
• Grant Schoenebeck
• Dawn Song
• Michael E. Houle

Deep Neural Networks (DNNs) have recently been shown to be vulnerable against adversarial examples, which are carefully crafted instances that can mislead DNNs to make errors during prediction. To better understand such attacks, a characterization is needed of the properties of regions (the so-called `adversarial subspaces') in which adversarial examples lie. We tackle this challenge by characterizing the dimensional properties of adversarial regions, via the use of Local Intrinsic Dimensionality (LID). LID assesses the space-filling capability of the region surrounding a reference example, based on the distance distribution of the example to its neighbors. We first provide explanations about how adversarial perturbation can affect the LID characteristic of adversarial regions, and then show empirically that LID characteristics can facilitate the distinction of adversarial examples generated using state-of-the-art attacks. As a proof-of-concept, we show that a potential application of LID is to distinguish adversarial examples, and the preliminary results show that it can outperform several state-of-the-art detection measures by large margins for five attack strategies considered in this paper across three benchmark datasets. Our analysis of the LID characteristic for adversarial regions not only motivates new directions of effective adversarial defense, but also opens up more challenges for developing new attacks to better understand the vulnerabilities of DNNs.

SODA Conference 2018 Conference Paper

Consensus of Interacting Particle Systems on Erdös-Rényi Graphs

• Grant Schoenebeck
• Fang-Yi Yu

Interacting Particle Systems—exemplified by the voter model, iterative majority, and iterative k —majority processes—have found use in many disciplines including distributed systems, statistical physics, social networks, and Markov chain theory. In these processes, nodes update their “opinion” according to the frequency of opinions amongst their neighbors. We propose a family of models parameterized by an update function that we call Node Dynamics: every node initially has a binary opinion. At each round a node is uniformly chosen and randomly updates its opinion with the probability distribution specified by the value of the update function applied to the frequencies of its neighbors’ opinions. In this work, we prove that the Node Dynamics converge to consensus in time Θ( n log n ) in complete graphs and dense Erdös-Rényi random graphs when the update function is from a large family of “majority-like” functions. Our technical contribution is a general framework that upper bounds the consensus time. In contrast to previous work that relies on handcrafted potential functions, our framework systematically constructs a potential function based on the state space structure.

AAAI Conference 2017 Conference Paper

Engineering Agreement: The Naming Game with Asymmetric and Heterogeneous Agents

• Jie Gao
• Bo Li
• Grant Schoenebeck
• Fang-Yi Yu

Being popular in language evolution, cognitive science, and culture dynamics, the Naming Game has been widely used to analyze how agents reach global consensus via communications in multi-agent systems. Most prior work considered networks that are symmetric and homogeneous (e. g. , vertex transitive). In this paper we consider asymmetric or heterogeneous settings that complement the current literature: 1) we show that increasing asymmetry in network topology can improve convergence rates. The star graph empirically converges faster than all previously studied graphs; 2) we consider graph topologies that are particularly challenging for naming game such as disjoint cliques or multi-level trees and ask how much extra homogeneity (random edges) is required to allow convergence or fast convergence. We provided theoretical analysis which was confirmed by simulations; 3) we analyze how consensus can be manipulated when stubborn nodes are introduced at different points of the process. Early introduction of stubborn nodes can easily influence the outcome in certain family of networks while late introduction of stubborn nodes has much less power.

SODA Conference 2014 Conference Paper

Better Approximation Algorithms for the Graph Diameter

• Shiri Chechik
• Daniel H. Larkin
• Liam Roditty
• Grant Schoenebeck
• Robert Endre Tarjan
• Virginia Vassilevska Williams

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in time an estimate for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D ⌋ – ( M – 1) ≤ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to. Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no ( n 2− ∊ ) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than. Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine -approximation for the diameter, one running in time, and one running in time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – ∊ )-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c -approximation for the diameter, i. e. an estimate such that D – c ≤ ≤ D. An extremely simple time algorithm achieves an additive n ∊ -approximation; no better results are known. We show that for any ∊ > 0, getting an additive n ∊ -approximation algorithm for the diameter running in ( n 2− δ ) time for any δ > 2 ∊ would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c -approximation for any constant c is unlikely. Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i. e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in time, one can compute for each v ∊ V in an undirected graph, an estimate ∊( v ) for the eccentricity ∊( v ) such that max { R, · ∊( v )} ≤ ∊( v ) ≤ min { D, · ∊( v )} where R = min v ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊ ′ ( v ) with · ∊( v ) ≤ ∊′ ( v ) ≤ ∊( v ).

FOCS Conference 2010 Conference Paper

Optimal Testing of Reed-Muller Codes

• Arnab Bhattacharyya 0001
• Swastik Kopparty
• Grant Schoenebeck
• Madhu Sudan 0001
• David Zuckerman

We consider the problem of testing if a given function f: F 2 n → F 2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [1] proposed and analyzed a natural 2 d+1 -query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Ω(1)-far with probability Ω(1/(d2 d )). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Ω(2 -d )-far with Ω(1)probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1) st -Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by induction on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F 2 n to F 2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every function q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

SODA Conference 2009 Conference Paper

On the complexity of Nash equilibria of action-graph games

• Constantinos Daskalakis
• Grant Schoenebeck
• Gregory Valiant
• Paul Valiant

FOCS Conference 2008 Conference Paper

Linear Level Lasserre Lower Bounds for Certain k-CSPs

• Grant Schoenebeck

We show that for kges3 even the Omega(n) level of the Lasserre hierarchy cannot disprove a random k-CSP instance over any predicate type implied by k-XOR constraints, for example k-SAT or k-XOR. (One constant is said to imply another if the latter is true whenever the former is. For example k-XOR constraints imply k-CNF constraints.) As a result the Omega(n) level Lasserre relaxation fails to approximate such CSPs betterthan the trivial, random algorithm. As corollaries, we obtain Omega(n) level integrality gaps for the Lasserre hierarchy of 7/6-epsiv for VERTEXCOVER, 2-epsiv for k-UNIFORMHYPERGRAPHVERTEXCOVER, and any constant for k-UNIFORMHYPERGRAPHINDEPENDENTSET. This is the first construction of a Lasserre integrality gap. Our construction is notable for its simplicity. It simplifies, strengthens, and helps to explain several previous results.

STOC Conference 2007 Conference Paper

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut

• Grant Schoenebeck
• Luca Trevisan 0001
• Madhur Tulsiani

We study linear programming relaxations of Vertex Cover and Max Cutarising from repeated applications of the "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove thatthe integrality gap remains at least 2-ε after Ω ε (log n) rounds, where n is the number ofvertices, and Tourlakis proves that integrality gap remains at least 1.5-ε after Ω((log n) 2 ) rounds. Fernandez de laVega and Kenyon prove that the integrality gap of Max Cut is at most 12 + ε after any constant number of rounds. (Theirresult also applies to the more powerful Sherali-Adams method. We prove that the integrality gap of Vertex Cover remains at least 2-ε after Ω ε (n) rounds, and that theintegrality gap of Max Cut remains at most 1/2 +ε after Ω ε (n) rounds.

AAAI Conference 2004 Conference Paper

GROWRANGE: Anytime VCG-Based Mechanisms

• David C. Parkes
• Grant Schoenebeck

We introduce anytime mechanisms for distributed optimization with self-interested agents. Anytime mechanisms retain good incentive properties even when interrupted before the optimal solution is computed, and provide better quality solutions when given additional time. Anytime mechanisms can solve easy instances of a hard problem quickly and optimally, while providing approximate solutions on very hard instances. In a particular instantiation, GROWRANGE, we successively expand the range of outcomes considered, computing the optimal solution for each range. Truth-revelation remains a dominant strategy equilibrium with a stage-based interruption, and is a best-response with high probability when the interruption is time-based.