Strategy proof location mechanisms on graphs with a cycle

Facility location problem

Environment:

• graph ,
• set of agents ,
• state of world , that is preferences of agents from regarding vertices of graph represented by their ideal locations.

Facility location problem (cont.)

Agent: Prefers vertices of graph , which are near their ideal locations.

Social planner: Wants to select a vertex of graph , which is "good" for all agents - induces small social choice.

Social cost associated with any point of the graph is defined as the sum of its distances from the ideal locations of agents:

Mechanism design

Question: What happens when preferences of agents are their private information?

Solution: Social planner has to organize election in order to obtain agents preferences and based on those select graph's vertex.

Election process

Schedule:

1. Social planner declares a rule for deciding the election by selecting a mechanism (function which maps agents messages into election's result).
2. Agents who know the mechanism submit their preferences forming messages profile .
3. Mechanism is applied to messages profile in order to obtain election's final result.

Problem with the cycle

For any let be a cycle of length with equally spaced vertices.

Environment specialization: Graph is the .

Problem: There is a state of the world in which it is beneficial for an agent to lie.

Strategyproofness (SP)

Definition: no one benefits from lying, i.e.:

where:

1. preferences of agents,
2. agents,
3. alternative submissions of agent .

Dictatorial mechanism

Dictatorial mechanism with respect to agent is a function defined as:

Known facts: dictatorial mechanism is SP, but for many states of the world it works suboptimally (sometimes it is impossible to do better).

Randomization

Mechanism returns a probability distribution over the set of graph's vertices.

At the end election process one of the points is selected according to the probability distribution returned by the mechanism.

Agents' utility and social cost are extended for probability distributions by using expected values.

RD (Random Dictator)

RD mechanism:

• randomly selects one of the agents with equal probability,
• returns the submission of agent (i.e. works as ).

Known fact: mechanism RD is SP, because it is a mixture of dictatorial mechanisms which are SP.

Approximation ratio

Definition: for the state of the world and the mechanism the approximation ratio is defined as:

For the set of states of the world the definition is extended by taking the maximum:

Intuition: measures the quality of the mechanism in comparison to the optimal solution (in the worst case).

How well do SP mechanisms work?

Lower bound: there are instances of the facility location problem for which the best SP mechanism has an approximation ratio at least .

Upper bound:

• dictatorial mechanism has an approximation ratio equal to ,
• RD mechanism has an approximation ratio equal to and in general is the best performing known SP mechanism.

PCD mechanism (Proportional Circle Distance)

PCD mechanism (cont.)

Bounds for PCD obtained in the master thesis

Upper bound with respect to the number of agents

Theorem: The approximation ratio of the PCD mechanism is bounded from above by:

Implication: Improvement of the known upper bound on the approximation ratio of the optimal SP mechanism on the for any and .

Upper bound with respect to the minimal distance between agents' reports

Let denote the minimal distance between different agents' reports.

Theorem: The approximation ratio of the PCD mechanism is bounded from above by:

Implication: Establishment of upper bound strictly lower than in case when graph is fixed.

Mechanisms with lower approximation ratio

Main idea: Mix different SP mechanisms in order to obtain a new SP mechanism which might work better as worst cases might not overlap.

Approximation ratio of mixed mechanisms:
Let be SP mechanisms. Let be mechanism which operates according to and with equal probability. Then the approximation ratio of is equal to:

RD+PCD Mechanism

Definition: with probability works as RD, with probability works as PCD.

Hypothesis: the approximation ratio of RD+PCD is bounded by .

Experiments

Methodology:

• numerical calculation of RD+PCD approximation ratio for the sets of states of the world (for different ),
• observation of subsets of states of the world for which mechanisms work poorly, and further experiments for them.

Graph dissection

Problem: Distances between vertices of the cycle graph are somewhat more complicated than in the case of a line graph making calculations hard.
Solution:

• Calculate approximation ratio of studied mechanisms substituting costs associated with vertexes as if the graph was a dissected line graph.
• This bounds from above the approximation ratio of the mechanism on the cycle graph.
• Such estimation seems to be good enough and has another good properties.

Dissected line graph: graph obtained by cutting the cycle graph in the point antipodal to some vertex with the minimal social cost.

RD on dissected line graph

Facts:

• RD works on dissected line graph as on the line graph,
• therefore has approximation ratio:

Current work

Working hypothesis: the approximation ratio of RD+PCD with costs as in dissected line graph is bounded by .

Note: Above function has nice derivatives with respect to movements of points which preserves the optimal cost.

Future topics

• R3PCD: mechanism which randomly selects agents and applies PCD to them. Experimental results show that its approximation ratio is bounded by .
• Studies of generalization of PCD to general graphs obtained by application of more random cuts.
• Lift of obtained bounds for PCD and RD+PCD to general graphs.

Thank you, and I welcome any questions.