BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Biaoshuai Tao

Biaoshuai Tao appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheorySocial and Information NetworksData Structures and AlgorithmsComputational ComplexityCryptography and SecurityDiscrete Mathematicsecon.THMultiagent Systems

Catalog footprint

What is connected

8works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2026arXiv

It's Not All Black and White: Degree of Truthfulness for Risk-Avoiding Agents

The classic notion of \emph{truthfulness} requires that no agent has a profitable manipulation -- an untruthful report that, for \emph{some} combination of reports of the other agents, increases her utility. This strong notion implicitly assumes that the manipulating agent either knows what all other agents are going to report, or is willing to take the risk and act as-if she knows their reports. Without knowledge of the others' reports, most manipulations are \emph{risky} -- they might decrease the manipulator's utility for some other combinations of reports by the other agents. Accordingly, a recent paper (Bu, Song and Tao, ``On the existence of truthful fair cake cutting mechanisms'', Artificial Intelligence 319 (2023), 103904) suggests a relaxed notion, which we refer to as \emph{risk-avoiding truthfulness (RAT)}, which requires only that no agent can gain from a \emph{safe} manipulation -- one that is sometimes beneficial and never harmful. Truthfulness and RAT are two extremes: the former considers manipulators with complete knowledge of others, whereas the latter considers manipulators with no knowledge at all. In reality, agents often know about some -- but not all -- of the other agents. This paper introduces the \emph{RAT-degree} of a mechanism, defined as the smallest number of agents whose reports, if known, may allow another agent to safely manipulate, or $n$ if there is no such number. This notion interpolates between classic truthfulness (degree $n$) and RAT (degree at least $1$): a mechanism with a higher RAT-degree is harder to manipulate safely. To illustrate the generality and applicability of this concept, we analyze the RAT-degree of prominent mechanisms across various social choice settings, including auctions, indivisible goods allocations, cake-cutting, voting, and two-sided matching.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

A Complete Landscape for the Price of Envy-Freeness

We study the efficiency of fair allocations using the well-studied price of fairness concept, which quantitatively measures the worst-case efficiency loss when imposing fairness constraints. Previous works provided partial results on the price of fairness with well-known fairness notions such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). In this paper, we give a complete characterization for the price of envy-freeness in various settings. In particular, we first consider the two-agent case under the indivisible-goods setting and present tight ratios for the price of EF1 (for scaled utility) and EFX (for unscaled utility), which resolve questions left open in the literature. Next, we consider the mixed goods setting which concerns a mixture of both divisible and indivisible goods. We focus on envy-freeness for mixed goods (EFM), which generalizes both envy-freeness and EF1, as well as its strengthening called envy-freeness up to any good for mixed goods (EFXM), which generalizes envy-freeness and EFX. To this end, we settle the price of EFM and EFXM by providing a complete picture of tight bounds for two agents and asymptotically tight bounds for $n$ agents, for both scaled and unscaled utilities.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization

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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

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

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. Voters may be "contingent" with different preferences in different states; or predetermined with the same preference in every 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 an easy-to-deploy 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).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Limitations of Greed: Influence Maximization in Undirected Networks Re-visited

We consider the influence maximization problem (selecting $k$ seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a $(1 - (1 - 1/k)^k + Ω(1/k^3))$-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic $(1- (1 - 1/k)^k)$ bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a $(1- (1 - 1/k)^k + O(1/k^{0.2}))$ approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a $(1-(1-1/k)^k)$-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a $(1-(1-1/k)^k + c)$ approximation for constant $c > 0$. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio $(1 - (1 - 1/k)^k)$ is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a $(1 - (1 - 1/k)^k + f(k))$-approximation for any positive function $f(k)$. The result in setting 2) is again in a sharp contrast to Khanna and Lucier's $(1 - (1 - 1/k)^k + c)$-approximation result for the independent cascade model, where the $(1 - (1 - 1/k)^k + c)$ approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization

We study the $r$-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the $r$-complex contagion model, each uninfected vertex in the network becomes infected if it has at least $r$ infected neighbors. In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the well-studied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability $ω(n^{-(1+1/r)})$, under certain mild assumptions, we prove that the optimal seeding strategy is to put 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 and the linear threshold model) in which nearby seeds tend to erode each others' effects. Our key technique is a novel time-asynchronized coupling of four cascade processes. Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in $ω(n^{-(1+1/r)})$ or in $o(n^{-2})$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as the influence maximization problem. It admits a $(1-1/e)$-factor approximation algorithm if the influence function is submodular. Otherwise, in the worst case, the problem is NP-hard to approximate to within a factor of $N^{1-\varepsilon}$. This paper studies whether this worst-case hardness result can be circumvented by making assumptions about either the underlying network topology or the cascade model. All of our assumptions are motivated by many real life social network cascades. First, we present strong inapproximability results for a very restricted class of networks called the (stochastic) hierarchical blockmodel, a special case of the well-studied (stochastic) blockmodel in which relationships between blocks admit a tree structure. We also provide a dynamic-program based polynomial time algorithm which optimally computes a directed variant of the influence maximization problem on hierarchical blockmodel networks. Our algorithm indicates that the inapproximability result is due to the bidirectionality of influence between agent-blocks. Second, we present strong inapproximability results for a class of influence functions that are "almost" submodular, called 2-quasi-submodular. Our inapproximability results hold even for any 2-quasi-submodular $f$ fixed in advance. This result also indicates that the "threshold" between submodularity and nonsubmodularity is sharp, regarding the approximability of influence maximization.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Outsourcing Computation: the Minimal Refereed Mechanism

We consider a setting where a verifier with limited computation power delegates a resource intensive computation task---which requires a $T\times S$ computation tableau---to two provers where the provers are rational in that each prover maximizes their own payoff---taking into account losses incurred by the cost of computation. We design a mechanism called the Minimal Refereed Mechanism (MRM) such that if the verifier has $O(\log S + \log T)$ time and $O(\log S + \log T)$ space computation power, then both provers will provide a honest result without the verifier putting any effort to verify the results. The amount of computation required for the provers (and thus the cost) is a multiplicative $\log S$-factor more than the computation itself, making this schema efficient especially for low-space computations.

0 citations0 reviewsNo code linkedOpen access