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

Diodato Ferraioli

Diodato Ferraioli 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 TheoryData Structures and AlgorithmsSocial and Information NetworksMultiagent SystemsDiscrete MathematicsArtificial IntelligenceComputational Complexity

Catalog footprint

What is connected

13works
7topics
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

13 published item(s)

preprint2022arXiv

Efficiency of Ad Auctions with Price Displaying

Most of the economic reports forecast that almost half of the worldwide market value unlocked by AI over the next decade (up to 6 trillion USD per year) will be in marketing&sales. In particular, AI will enable the optimization of more and more intricate economic settings, in which multiple different activities need to be jointly automated. This is the case of, e.g., Google Hotel Ads and Tripadvisor, where auctions are used to display ads of similar products or services together with their prices. As in classical ad auctions, the ads are ranked depending on the advertisers' bids, whereas, differently from classical settings, ads are displayed together with their prices, so as to provide a direct comparison among them. This dramatically affects users' behavior, as well as the properties of ad auctions. We show that, in such settings, social welfare maximization can be achieved by means of a direct-revelation mechanism that jointly optimizes, in polynomial time, the ads allocation and the advertisers' prices to be displayed with them. However, in practice it is unlikely that advertisers allow the mechanism to choose prices on their behalf. Indeed, in commonly-adopted mechanisms, ads allocation and price optimization are decoupled, so that the advertisers optimize prices and bids, while the mechanism does so for the allocation, once prices and bids are given. We investigate how this decoupling affects the efficiency of mechanisms. In particular, we study the Price of Anarchy (PoA) and the Price of Stability (PoS) of indirect-revelation mechanisms with both VCG and GSP payments, showing that the PoS for the revenue may be unbounded even with two slots, and the PoA for the social welfare may be as large as the number of slots. Nevertheless, we show that, under some assumptions, simple modifications to the indirect-revelation mechanism with VCG payments achieve a PoS of 1 for the revenue.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Impact of Social Media Recommendations on Opinion Consensus

We consider a discrete opinion formation problem in a setting where agents are influenced by both information diffused by their social relations and from recommendations received directly from the social media manager. We study how the "strength" of the influence of the social media and the homophily ratio affect the probability of the agents of reaching a consensus and how these factors can determine the type of consensus reached. In a simple 2-symmetric block model we prove that agents converge either to a consensus or to a persistent disagreement. In particular, we show that when the homophily ratio is large, the social media has a very low capacity of determining the outcome of the opinion dynamics. On the other hand, when the homophily ratio is low, the social media influence can have an important role on the dynamics, either by making harder to reach a consensus or inducing it on extreme opinions. Finally, in order to extend our analysis to more general and realistic settings we give some experimental evidences that our results still hold on general networks.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Election Manipulation on Social Networks: Seeding, Edge Removal, Edge Addition

We focus on the election manipulation problem through social influence, where a manipulator exploits a social network to make her most preferred candidate win an election. Influence is due to information in favor of and/or against one or multiple candidates, sent by seeds and spreading through the network according to the independent cascade model. We provide a comprehensive study of the election control problem, investigating two forms of manipulations: seeding to buy influencers given a social network, and removing or adding edges in the social network given the seeds and the information sent. In particular, we study a wide range of cases distinguishing for the number of candidates or the kind of information spread over the network. Our main result is positive for democracy, and it shows that the election manipulation problem is not affordable in the worst-case except for trivial classes of instances, even when one accepts to approximate the margin of victory. In the case of seeding, we also show that the manipulation is hard even if the graph is a line and that a large class of algorithms, including most of the approaches recently adopted for social-influence problems, fail to compute a bounded approximation even on elementary networks, as undirected graphs with every node having a degree at most two or directed trees. In the case of edge removal or addition, our hardness results also apply to the basic case of social influence maximization/minimization. In contrast, the hardness of election manipulation holds even when the manipulator has an unlimited budget, being allowed to remove or add an arbitrary number of edges.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Two-way Greedy: Algorithms for Imperfect Rationality

The realization that selfish interests need to be accounted for in the design of algorithms has produced many contributions in computer science under the umbrella of algorithmic mechanism design. Novel algorithmic properties and paradigms have been identified and studied. Our work stems from the observation that selfishness is different from rationality; agents will attempt to strategize whenever they perceive it to be convenient according to their imperfect rationality. Recent work has focused on a particular notion of imperfect rationality, namely absence of contingent reasoning skills, and defined obvious strategyproofness (OSP) as a way to deal with the selfishness of these agents. Essentially, this definition states that to care for the incentives of these agents, we need not only pay attention about the relationship between input and output, but also about the way the algorithm is run. However, it is not clear what algorithmic approaches must be used for OSP. In this paper, we show that, for binary allocation problems, OSP is fully captured by a combination of two well-known algorithmic techniques: forward and reverse greedy. We call two-way greedy this algorithmic design paradigm. Our main technical contribution establishes the connection between OSP and two-way greedy. We build upon the recently introduced cycle monotonicity technique for OSP. By means of novel structural properties of cycles and queries of OSP mechanisms, we fully characterize these mechanisms in terms of extremal implementations. These are protocols that ask each agent to consistently separate one extreme of their domain at the current history from the rest. Through the connection with the greedy paradigm, we are able to import a host of approximation bounds to OSP and strengthen the strategic properties of this family of algorithms. Finally, we begin exploring the power of two-way greedy for set systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Discrete Preference Games in Heterogeneous Social Networks: Subverted Majorities and the Swing Player

We study discrete preference games in heterogeneous social networks. These games model the interplay between a player's private belief and his/her publicly stated opinion (which could be different from the player's belief) as a strategic game in which the players' strategies are the opinions and the cost of an opinion in a state is a convex combination through a parameter $α\in[0,1]$ of two factors: the disagreement between the player's opinion and his/her internal belief and the number of neighbors whose opinions differ from the one of the player. The parameter $α$ models how stubborn a player is: players with large $α$ change their opinion only if many neighbors disagree with his/her belief. We consider social networks that are heterogeneous in the sense that the parameter $α$ can vary from player to player. We ask if it is possible that the belief shared by the majority of the players does not coincide with the opinion that is publicly announced by the majority of the players in an equilibrium state. Our main result is a characterization of the social networks that admit an initial belief assignment for which there exists a sequence of best response moves that reach an equilibrium in which the initial majority is subverted. Our characterization is effective in the sense that can be tested efficiently and the initial belief assignment that can be subverted can be computed in time polynomial in the number of players. Our result is actually stronger as we show that in each initial belief assignment that can be subverted, subversion is actually obtained in a very strong way: it only takes one move of a single player, the swing player, to lead the social network to a point of no return in which any rational move from any player leads to a subverted majority.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Minority Becomes Majority in Social Networks

It is often observed that agents tend to imitate the behavior of their neighbors in a social network. This imitating behavior might lead to the strategic decision of adopting a public behavior that differs from what the agent believes is the right one and this can subvert the behavior of the population as a whole. In this paper, we consider the case in which agents express preferences over two alternatives and model social pressure with the majority dynamics: at each step an agent is selected and its preference is replaced by the majority of the preferences of her neighbors. In case of a tie, the agent does not change her current preference. A profile of the agents' preferences is stable if the preference of each agent coincides with the preference of at least half of the neighbors (thus, the system is in equilibrium). We ask whether there are network topologies that are robust to social pressure. That is, we ask if there are graphs in which the majority of preferences in an initial profile always coincides with the majority of the preference in all stable profiles reachable from that profile. We completely characterize the graphs with this robustness property by showing that this is possible only if the graph has no edge or is a clique or very close to a clique. In other words, except for this handful of graphs, every graph admits at least one initial profile of preferences in which the majority dynamics can subvert the initial majority. We also show that deciding whether a graph admits a minority that becomes majority is NP-hard when the minority size is at most 1/4-th of the social network size.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sequential Posted Price Mechanisms with Correlated Valuations

We study the revenue performance of sequential posted price mechanisms and some natural extensions, for a general setting where the valuations of the buyers are drawn from a correlated distribution. Sequential posted price mechanisms are conceptually simple mechanisms that work by proposing a take-it-or-leave-it offer to each buyer. We apply sequential posted price mechanisms to single-parameter multi-unit settings in which each buyer demands only one item and the mechanism can assign the service to at most k of the buyers. For standard sequential posted price mechanisms, we prove that with the valuation distribution having finite support, no sequential posted price mechanism can extract a constant fraction of the optimal expected revenue, even with unlimited supply. We extend this result to the the case of a continuous valuation distribution when various standard assumptions hold simultaneously. In fact, it turns out that the best fraction of the optimal revenue that is extractable by a sequential posted price mechanism is proportional to ratio of the highest and lowest possible valuation. We prove that for two simple generalizations of these mechanisms, a better revenue performance can be achieved: if the sequential posted price mechanism has for each buyer the option of either proposing an offer or asking the buyer for its valuation, then a Omega(1/max{1,d}) fraction of the optimal revenue can be extracted, where d denotes the degree of dependence of the valuations, ranging from complete independence (d=0) to arbitrary dependence (d=n-1). Moreover, when we generalize the sequential posted price mechanisms further, such that the mechanism has the ability to make a take-it-or-leave-it offer to the i-th buyer that depends on the valuations of all buyers except i's, we prove that a constant fraction (2-sqrt{e})/4~0.088 of the optimal revenue can be always be extracted.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Imperfect best-response mechanisms

Best-response mechanisms (Nisan, Schapira, Valiant, Zohar, 2011) provide a unifying framework for studying various distributed protocols in which the participants are instructed to repeatedly best respond to each others' strategies. Two fundamental features of these mechanisms are convergence and incentive compatibility. This work investigates convergence and incentive compatibility conditions of such mechanisms when players are not guaranteed to always best respond but they rather play an imperfect best-response strategy. That is, at every time step every player deviates from the prescribed best-response strategy according to some probability parameter. The results explain to what extent convergence and incentive compatibility depend on the assumption that players never make mistakes, and how robust such protocols are to "noise" or "mistakes".

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Metastability of Asymptotically Well-Behaved Potential Games

One of the main criticisms to game theory concerns the assumption of full rationality. Logit dynamics is a decentralized algorithm in which a level of irrationality (a.k.a. "noise") is introduced in players' behavior. In this context, the solution concept of interest becomes the logit equilibrium, as opposed to Nash equilibria. Logit equilibria are distributions over strategy profiles that possess several nice properties, including existence and uniqueness. However, there are games in which their computation may take time exponential in the number of players. We therefore look at an approximate version of logit equilibria, called metastable distributions, introduced by Auletta et al. [SODA 2012]. These are distributions that remain stable (i.e., players do not go too far from it) for a super-polynomial number of steps (rather than forever, as for logit equilibria). The hope is that these distributions exist and can be reached quickly by logit dynamics. We identify a class of potential games, called asymptotically well-behaved, for which the behavior of the logit dynamics is not chaotic as the number of players increases so to guarantee meaningful asymptotic results. We prove that any such game admits distributions which are metastable no matter the level of noise present in the system, and the starting profile of the dynamics. These distributions can be quickly reached if the rationality level is not too big when compared to the inverse of the maximum difference in potential. Our proofs build on results which may be of independent interest, including some spectral characterizations of the transition matrix defined by logit dynamics for generic games and the relationship of several convergence measures for Markov chains.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Decentralized Dynamics for Finite Opinion Games

Game theory studies situations in which strategic players can modify the state of a given system, due to the absence of a central authority. Solution concepts, such as Nash equilibrium, are defined to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to improve their own utility and the hope is that the system reaches an "equilibrium" quickly. We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [Bindel et al., FOCS2011]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Logit Dynamics with Concurrent Updates for Local-Interaction Games

Logit choice dynamics are a family of randomized best response dynamics based on the logit choice function [McFadden, 1974], used for modeling players with limited rationality and knowledge. In this paper we study the all-logit dynamics, where at each time step all players concurrently update their strategies according to the logit choice function. In the well studied one-logit dynamics [Blume, 1993] instead at each step only one randomly chosen player is allowed to update. We study properties of the all-logit dynamics in the context of local interaction games, a class of games that has been used to model complex social phenomena and physical systems. In a local interaction game, players are the vertices of a social graph whose edges are two-player potential games. Each player picks one strategy to be played for all the games she is involved in and the payoff of the player is the sum of the payoffs from each of the games. We prove that local interaction games characterize the class of games for which the all-logit dynamics is reversible. We then compare the stationary behavior of one-logit and all-logit dynamics. Specifically, we look at the expected value of a notable class of observables, that we call decomposable observables. We prove that the difference between the expected values of the observables at stationarity for the two dynamics depends only on the rationality level beta and on the distance of the social graph from a bipartite graph. In particular, if the social graph is bipartite then decomposable observables have the same expected value. Finally, we show that the mixing time of the all-logit dynamics has the same twofold behavior that has been highlighted in the case of the one-logit: for some games it exponentially depends on the rationality level beta, whereas for other games it can be upper bounded by a function independent from beta.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Convergence to Equilibrium of Logit Dynamics for Strategic Games

We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise beta describes the behavior of a complex system whose individual components act selfishly and keep responding according to some partial ("noisy") knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by the inverse of the parameter beta. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that, for potential games, the mixing time is upper and lower bounded by an exponential in the inverse of the noise and in the maximum potential difference. Instead, for games with dominant strategies, the mixing time cannot grow arbitrarily with the inverse of the noise. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, a class of games that have been previously studied in Physics and, more recently, in Computer Science in the context of diffusion of new technologies. We give evidence that the mixing time of the logit dynamics for these games strongly depends on the structure of the underlying graph. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in the inverse of noise. Moreover, we consider two specific and popular network topologies, the clique and the ring. For games played on a clique we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in the inverse of the noise and in the maximum potential difference, while for games played on a ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Mixing Time and Stationary Expected Social Welfare of Logit Dynamics

We study "logit dynamics" [Blume, Games and Economic Behavior, 1993] for strategic games. This dynamics works as follows: at every stage of the game a player is selected uniformly at random and she plays according to a "noisy" best-response where the noise level is tuned by a parameter $β$. Such a dynamics defines a family of ergodic Markov chains, indexed by $β$, over the set of strategy profiles. We believe that the stationary distribution of these Markov chains gives a meaningful description of the long-term behavior for systems whose agents are not completely rational. Our aim is twofold: On the one hand, we are interested in evaluating the performance of the game at equilibrium, i.e. the expected social welfare when the strategy profiles are random according to the stationary distribution. On the other hand, we want to estimate how long it takes, for a system starting at an arbitrary profile and running the logit dynamics, to get close to its stationary distribution; i.e., the "mixing time" of the chain. In this paper we study the stationary expected social welfare for the 3-player CK game, for 2-player coordination games, and for two simple $n$-player games. For all these games, we also give almost tight upper and lower bounds on the mixing time of logit dynamics. Our results show two different behaviors: in some games the mixing time depends exponentially on $β$, while for other games it can be upper bounded by a function independent of $β$.

0 citations0 reviewsNo code linkedOpen access