Source author record

Panagiotis Kanellopoulos

Panagiotis Kanellopoulos 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 Theory Artificial Intelligence Computational Complexity Multiagent Systems

Catalog footprint

What is connected

5works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2024arXiv

Truthful Two-Facility Location with Candidate Locations

We study a truthful two-facility location problem in which a set of agents have private positions on the line of real numbers and known approval preferences over two different facilities. Given the locations of the two facilities, the cost of an agent is the total distance from the facilities she approves. The goal is to decide where to place the facilities from a given finite set of candidate locations so as to (a) approximately optimize desired social objectives, and (b) incentivize the agents to truthfully report their private positions. We focus on the class of deterministic strategyproof mechanisms and show bounds on their approximation ratio in terms of the social cost (i.e., the total cost of the agents) and the max cost for several classes of instances depending on the preferences of the agents over the facilities.

preprint2023arXiv

Settling the Distortion of Distributed Facility Location

We study the distributed facility location problem, where a set of agents with positions on the line of real numbers are partitioned into disjoint districts, and the goal is to choose a point to satisfy certain criteria, such as optimize an objective function or avoid strategic behavior. A mechanism in our distributed setting works in two steps: For each district it chooses a point that is representative of the positions reported by the agents in the district, and then decides one of these representative points as the final output. We consider two classes of mechanisms: Unrestricted mechanisms which assume that the agents directly provide their true positions as input, and strategyproof mechanisms which deal with strategic agents and aim to incentivize them to truthfully report their positions. For both classes, we show tight bounds on the best possible approximation in terms of several minimization social objectives, including the well-known social cost (total distance of agents from chosen point) and max cost (maximum distance among all agents from chosen point), as well as other fairness-inspired objectives that are tailor-made for the distributed setting.

preprint2020arXiv

Modified Schelling Games

We introduce the class of modified Schelling games in which there are different types of agents who occupy the nodes of a location graph; agents of the same type are friends, and agents of different types are enemies. Every agent is strategic and jumps to empty nodes of the graph aiming to maximize her utility, defined as the ratio of her friends in her neighborhood over the neighborhood size including herself. This is in contrast to the related literature on Schelling games which typically assumes that an agent is excluded from her neighborhood whilst computing its size. Our model enables the utility function to capture likely cases where agents would rather be around a lot of friends instead of just a few, an aspect that was partially ignored in previous work. We provide a thorough analysis of the (in)efficiency of equilibria that arise in such modified Schelling games, by bounding the price of anarchy and price of stability for both general graphs and interesting special cases. Most of our results are tight and exploit the structure of equilibria as well as sophisticated constructions.

preprint2018arXiv

How game complexity affects the playing behavior of synthetic agents

Agent based simulation of social organizations, via the investigation of agents' training and learning tactics and strategies, has been inspired by the ability of humans to learn from social environments which are rich in agents, interactions and partial or hidden information. Such richness is a source of complexity that an effective learner has to be able to navigate. This paper focuses on the investigation of the impact of the environmental complexity on the game playing-and-learning behavior of synthetic agents. We demonstrate our approach using two independent turn-based zero-sum games as the basis of forming social events which are characterized both by competition and cooperation. The paper's key highlight is that as the complexity of a social environment changes, an effective player has to adapt its learning and playing profile to maintain a given performance profile

preprint2014arXiv

Bounding the inefficiency of outcomes in generalized second price auctions

The Generalized Second Price (GSP) auction is the primary auction used for monetizing the use of the Internet. It is well-known that truthtelling is not a dominant strategy in this auction and that inefficient equilibria can arise. In this paper we study the space of equilibria in GSP, and quantify the efficiency loss that can arise in equilibria under a wide range of sources of uncertainty, as well as in the full information setting. The traditional Bayesian game models uncertainty in the valuations (types) of the participants. The Generalized Second Price (GSP) auction gives rise to a further form of uncertainty: the selection of quality factors resulting in uncertainty about the behavior of the underlying ad allocation algorithm. The bounds we obtain apply to both forms of uncertainty, and are robust in the sense that they apply under various perturbations of the solution concept, extending to models with information asymmetries and bounded rationality in the form of learning strategies. We present a constant bound (2.927) on the factor of the efficiency loss (\emph{price of anarchy}) of the corresponding game for the Bayesian model of partial information about other participants and about ad quality factors. For the full information setting, we prove a surprisingly low upper bound of 1.282 on the price of anarchy over pure Nash equilibria, nearly matching a lower bound of 1.259 for the case of three advertisers. Further, we do not require that the system reaches equilibrium, and give similarly low bounds also on the quality degradation for any no-regret learning outcome. Our conclusion is that the number of advertisers in the auction has almost no impact on the price of anarchy, and that the efficiency of GSP is very robust with respect to the belief and rationality assumptions imposed on the participants.