Hello, my name is Krzysztof Rogowski. I will present the paper "Improved Approximation Ratio for Strategyproof Facility Location on a Cycle", which is joint work with Marcin Dziubiński.

Let's start with the motivation for studying facility location from a mechanism design perspective. This framework can model various real-world scenarios, but we will stick with the highlighted example. Imagine a group of international friends who want to agree on a time to watch a movie together. Each friend has their own preferred time, and they want to find a way to select a time that minimizes overall dissatisfaction. Question is how to choose the time based on agents' reported preferences.

I will present you now how election process could be modeled. We have a cycle graph $G$ and a set of agents $N$.

Observing graph and agents social planner propose a mechanism. Mechanism is a function that maps agents' votes to a lottery over the vertices of $G$, where a lottery means a probability distribution.

Each agent has their ideal vertex which is also their type (depicted by dot) The agents' types collectively constitute the state of the world.

Each agent has preferences over the vertices of $G$, determined by their cost, Cost incurred for agent from vertex is its distance from their ideal vertex.

Agents observe the mechanism and then submit their votes. For the sake of example, assume that they vote truthfully.

The mechanism selects a resulting lottery based solely on the agents' votes.

We depict the resulting lottery with clock hands—the longer the hand, the higher the probability of that vertex being selected.

Agents and the social planner evaluate the mechanism by looking at the resulting lottery.

As a side note, the final result of the election is sampled from the lottery returned by the mechanism and depicted as a yellow circle.

We are not interested in random sampling aspect here.

Back to main example and scoring.

Let be nice for agents and select opt mechanism which for every situation returns socially optimal outcome (according to agents' votes).

Let be nice for agents and select opt mechanism which for every situation returns socially optimal outcome (according to agents' votes).

Agents' costs are extended to lotteries with expected values. Social cost is the sum of individual costs. When designing mechanisms, our goal is to minimize social cost. Let's look at the costs incurred by individual agents in our example. We can observe that the red agent has a cost of 3, which is not ideal for them.

Red agent can misreport their vote (make it not point to their true ideal location).

Here we see the outcome the mechanism would return for a message profile that includes a misreported vote by the red agent.

After recalculating costs, we observe that the red agent can benefit from misreporting. This is an undesirable situation.

We call a mechanism strategyproof if no situation like the one presented before occurs—that is, regardless of others' votes, an agent cannot benefit from misreporting their vote. The term "in expectation" refers to how agents evaluate the mechanism in our model—using expected values.

Further we restrict ourselves to SP mechanisms only. However, this restriction comes with a cost: As shown in our example, a mechanism that always returns the socially optimal result is not SP in some settings. This leads to an interesting question, which we tackle for the cycle graph: What is the best possible strategyproof mechanism in such setting?

To answer that question, we need a way to compare the quality of mechanisms. We use the well-established notion of approximation ratio. It is defined as the minimal constant $\phi$ such that, for all states of the world, the social cost of the mechanism's result is at most $\phi$ times worse than the optimal social cost. Equipped with this tool to compare mechanisms, we proceed to introduce some facility location mechanisms known from the literature.

Let's start with the random dictator mechanism. It returns lottery where the probability of selecting a vertex is proportional to the number of votes for that vertex. Below are some examples depicting how RD works. You can notice that in the second example, a vertex chosen by two agents is selected twice as often (visually, it has a clock hand twice as long). This mechanism is strategyproof (SP), neutral, and anonymous, where: - neutrality means the mechanism doesn't distinguish between similar graph vertices, - anonymity means it doesn't distinguish between agents. Quite interestingly, despite its simplicity, for many settings—especially the circle—the RD mechanism is the best performing mechanism known to date, with an approximation ratio bound of $2-2/n$.

Let's now introduce the PCD mechanism, proposed by Meir in 2019. It works for cycles and an odd number of agents. It selects each agent's vote with probability proportional to the length of the opposing arc, which for three agents corresponds to the arc between the other two agents. You can see an example of the PCD mechanism in action in the figure below. We won't delve further into its workings, as those details are not needed for our presentation. Nevertheless, to advertise this mechanism a bit more, I will mention that it can be seen as a generalization of the median mechanism for graphs with cycles. The PCD mechanism, like RD, is strategyproof, anonymous, and neutral. Moreover, it can be shown that it has an approximation ratio bound of 2.

So far, we've discussed known mechanisms. Now we move to new territory introduced in our paper. We start with simple idea. Let's take the mechanisms we already have and mix them. More precisely, consider the RD+PCD mechanism, which for a given state of the world returns the average lottery of RD and PCD. Because costs for agents are defined via expected value, it is easy to show that this construction preserves strategyproofness. Moreover, it does not refer specifically to any vertices or agents, so it also preserves neutrality and anonymity.

Most importantly, mixing interacts well with the approximation ratio. Let me briefly explain why. First, let's establish a key observation: For every state of the world, the performance of the RD+PCD mechanism is the average performance of RD and PCD. Because of this, we can expect the approximation ratio bound for RD+PCD to be somewhere between 1.5 and 2, depending on whether the bad states of the world for RD and PCD overlap. Try to see it from the perspective of single state. Consider state $s$ for which RD performs bad that is almost twice as poorly as the optimal solution. Such a state exists due to the approximation ratio bound of 2 for RD. Depending on how PCD performs for $s$, the performance of RD+PCD is somewhere between $2$ and $1.5$. If PCD also performs poorly for $s$, then RD+PCD would have approximation ratio around $2$ for $s$ (upper row). But if $s$ is a good state for PCD, then RD+PCD would have approximation ratio around $1.5$ for $s$ (bottom row).

We ran experiments to see how RD+PCD mechanism perform. They involved calculating the approximation ratio of the RD+PCD mechanism for various states of the world across different sets of agents and cycle graphs with varying numbers of vertices. In the presented plot, each color corresponds to a different cardinality of the agent set. The x-axis ranges over number of vertices in the cycle graph. The approximation ratio of the RD+PCD mechanism for each set of states can be read from the y-axis. Note that some dots on the plot would correspond to set with over one million states of the world. The first immediate observation is that we have not found any state of the world where RD+PCD performs more than 1.5 times worse than the optimal solution. Moreover, a quick look at the value trends across different colors and the x-axis suggests that the approximation ratio of RD+PCD is indeed be bounded by 1.5. This is quite a finding, because as previously argued, it requires RD and PCD mechanisms to perfectly complement each other (have their bad states disjoined). The main technical contribution of our paper is proving the bound of 1.75 for the approximation ratio of the RD+PCD mechanism, which is halfway between the experimental bound of 1.5 and the trivial, worst-case bound of 2. This result positively answers the open question of whether there is any mechanism that beats the RD mechanism and the bound of 2.

Here goes the main theorem. It concerns strategyproof mechanisms for facility location on a cycle. For any odd number of agents $n$, there exists a strategyproof mechanism with approximation ratio at most $\phi=1.75$.

Here is a table comparing our result with bounds for the approximation ratio of optimal strategyproof mechanisms from the literature. You can see that our result narrows the gap between the known upper and lower bounds by about 25%. Furthermore, our experimental results reduce the gap even further, achieving an approximation ratio bound of $1.5$.

Obvious directions for further research are: - Closing the gap between the experimental and proven bounds for the approximation ratio of RD+PCD. - Experimenting with different types of mixing and generalizing results to other graphs beyond cycles.

As a parting slide, I leave you with an overview of the proof for the 1.75 bound for RD+PCD. I won't delve into any details, and for further discussion, I invite you to join me in the poster session. Thank you for your attention!