1,720,992 research outputs found
Mechanism Design: (Ir)Rationality and Obvious Strategyproofness
No full textMulti-agent systems (MAS) are comprised by autonomous agents, each with a potentially specific goal that may be different from the objective of the system designer. MAS represent the perfect environment for the work in Algorithmic Mechanism Design (AMD), which seeks to design incentive-compatible mechanisms, the core idea being to maximise the profit of the agents when they behave honestly, thus preventing misbehaviour and allowing the designer to optimise her goal. AMD often assumes full rationality of agents who are expected to know their full preferences (however complex they are) and to strategise optimally so that the mechanism is guided towards outcomes they prefer. However, in real MAS, this is too strong an assumption. Humans could interact with software agents and irrationally choose suboptimal strategies due to their cognitive biases and/or limitations [1]. Software agents themselves could be “irrational” since they could have been “badly” programmed either because the programmer misunderstood the incentive structure in place or due to computational barriers [2]. Much work has been done in the last years to relax full rationality and set an agenda to design AMD mechanisms for real MAS, where we seek to incentivise honest behaviour when agents have some form of imperfect rationality. This paper will survey some recent works focusing on mechanism design when agents have imperfect rationality
Approximation Guarantee of OSP Mechanisms: The Case of Machine Scheduling and Facility Location
Full text linkObvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, i.e., those who struggle with contingent reasoning (Li in Am Econ Rev 107(11):3257–3287, 2017). However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski in J Econ Theory 177:405–425, 2018). We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i.e., machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a significant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring—a novel mechanism design paradigm that introduces a mild level of scrutiny on agents’ declarations (Kovács et al. in WINE 9470:398–412, 2015)
Obvious Strategyproofness, Bounded Rationality and Approximation
Full text linkObvious strategyproofness (OSP) has recently emerged as the solution concept of interest to study incentive compatibility in presence of agents with a specific form of bounded rationality, i.e., those who have no contingent reasoning skill whatsoever. We here want to study the relationship between the approximation guarantee of incentive-compatible mechanisms and the degree of rationality of the agents, intuitively measured in terms of the number of contingencies that they can handle in their reasoning. We weaken the definition of OSP to accommodate for cleverer agents and study the trade-off between approximation and agents’ rationality for two paradigmatic problems: machine scheduling and facility location. We prove that, for both problems, “good” approximations are possible if and only if the agents’ rationality allows for a significant number of contingencies to be considered, thus showing that OSP is not too restrictive a notion of bounded rationality from the point of view of approximation
Explicit Payments for Obviously Strategyproof Mechanisms
No full textThe design of mechanisms where incentives are simple to understand for the agents has attracted a lot of attention recently. One particularly relevant concept in this direction has been Obvious Strategyproofness (OSP), a class of mechanisms that are so simple to be recognized as incentive compatible even by agents with a limited form of rationality. It is known that there exist payments that lead to an OSP mechanism whenever the algorithm they augment is either greedy or reverse greedy (a.k.a., deferred acceptance). However, to date, their explicit definition is unknown. In this work we provide payments for OSP mechanisms based on greedy or reverse greedy algorithms. Interestingly, our results show an asymmetry between these two classes of algorithms: while for reverse greedy the usual strategyproof payments work well also for OSP, the payments for greedy algorithms may break individual rationality or budget balancedness. Thus, the designer needs to subsidize the market in order to simultaneously guarantee these properties and simple incentives. We apply this result to analyze the amount of subsidies needed by a well-known greedy algorithm for combinatorial auctions with single-minded bidders
On the Connection between Greedy Algorithms and Imperfect Rationality
No full textThe design of algorithms or protocols that are able to align the goals of the planner with the selfish interests of the agents involved in these protocols is of paramount importance in almost every decentralized setting (such as, computer networks, markets, etc.) as shown by the rich literature in Mechanism Design. Recently, huge interest has been devoted to the design of mechanisms for imperfectly rational agents, i.e., mechanisms for which agents are able to easily grasp that there is no action different from following the protocol that would satisfy their interests better. This work has culminated in the definition of Obviously Strategyproof (OSP) Mechanisms, that have been shown to capture the incentives of agents without contingent reasoning skills.Without an understanding of the algorithmic nature of OSP mechanisms, it is hard to assess how well these mechanisms can satisfy the goals of the planner. For the case of binary allocation problems and agents whose private type is a single number, recent work has shown that a generalization of greedy completely characterizes OSP. In this work, we strengthen the connection between greedy and OSP by providing a characterization of OSP mechanisms for all optimization problems involving these single-parameter agents. Specifically, we prove that OSP mechanisms must essentially work as follows: they either greedily look for agents with "better"types and allocate them larger outcomes; or reverse greedily look for agents with "worse"types and allocate them smaller outcomes; or, finally, split the domain of agents in "good"and "bad"types, and subsequently proceed in a reverse greedy fashion for the former and greedily for the latter. We further demonstrate how to use this characterization to give bounds on the approximation guarantee of OSP mechanisms for the well known scheduling related machines problem
Social pressure in opinion dynamics
Full text linkMotivated by privacy and security concerns in online social networks, we study the role of social pressure in opinion dynamics. These are dynamics, introduced in economics and sociology literature, that model the formation of opinions in a social network. We enrich one of the most classical opinion dynamics, by introducing the pressure, increasing with time, to reach an agreement.
We prove that for clique social networks, the dynamics always converges to consensus (no matter the level of noise) if the social pressure is high enough. Moreover, we provide (tight) bounds on the speed of convergence; these bounds are polynomial in the number of nodes in the network provided that the pressure grows sufficiently fast. We finally look beyond cliques: we characterize the graphs for which consensus is guaranteed, and make some considerations on the computational complexity of checking whether a graph satisfies such a condition
New Constructions of Obviously Strategyproof Mechanisms
No full textCatering to the incentives of people with limited rationality is a challenging research direction that requires novel paradigms to design mechanisms. Obviously strategy-proof (OSP) mechanisms have recently emerged as the concept of interest to this research agenda. However, the majority of the literature in the area has either highlighted the shortcomings of OSP or focused on the “right” definition rather than on the construction of these mechanisms. Here, we give the first set of tight results on the approximation guarantee of OSP mechanisms for scheduling related machines and a characterization of set system instances for which OSP mechanisms that return optimal solutions exist. By extending the well-known cycle monotonicity technique, we are able to concentrate on the algorithmic component of OSP mechanisms and provide some novel paradigms for their design, when private types belong to a set with few values. In essence, we prove that OSP encompasses careful interleaving of ascending and descending auctions
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
