Top

Social Choice and Welfare

Published in:

01-10-2013 | Original Paper

Strategy-proof rules for two public goods: double median rules

Author: Eun Jeong Heo

Published in: Social Choice and Welfare | Issue 4/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the problem of selecting the locations of two (identical) public goods on an interval. Each agent has preferences over pairs of locations, which are induced from single-peaked rankings over single locations: each agent compares pairs of locations by comparing the location he ranks higher in each pair. We introduce a class of “double median rules” and characterize it by means of continuity, anonymity, strategy-proofness, and users only. To each pair of parameter sets, each set in the pair consisting of \((n+1)\) parameters, is associated a rule in the class. It is the rule that selects, for each preference profile, the medians of the peaks and the parameters belonging to each set in the pair. We identify the subclasses of the double median rules satisfying group strategy-proofness, weak efficiency, and double unanimity (or efficiency), respectively. We also discuss the classes of “multiple median rules” and “non-anonymous double median rules”.

previous article Process manipulation in unique implementation

next article Existence of efficient envy-free allocations of a heterogeneous divisible commodity with nonadditive utilities

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Replacement domination requires that if the preference of an agent changes, then all of the other agents’ welfare should be affected in the same direction.

If each agent has the same peak, then both locations are chosen to be the common peak.

In a generalized model where two public facilities are to be built on a “tree network”, instead of an interval, no rule satisfies efficiency and replacement domination (Umezawa 2012).

For a full survey on strategy-proofness in various models including ours, see Thomson (2011) and Barberà (2010).

If there are more than one agent with the smallest peak, then we choose any two of them for the first group. If there are one agent with the smallest peak and more than one agent with the second smallest peak, then we choose the agent with the smallest peak and any one of the agents with the second smallest peak for the first group.

If each group consists of even number of agents, say \(m\) agents, then the rule chooses the \(\frac{m}{2}\)-th smallest peak for this group. This rule belongs to the class of double median rules that will be formally defined in Sect. 2.

If there are more than one agent with the same peak, we count their peaks as many time as the number of such agents. For example, if all agents have the same peak, then the third largest peak and the seventh largest peak are the same as the common peak.

A rule should only take into account the profile of peaks.

The names of agents should not matter.

Such median rules are often referred to as “generalized median rules”. For the details of the connection between the class of generalized median rules and the class of minmax rules, see Weymark (2011).

For details about separability, see Moulin (1987) and Chun (2006).

In Barberà and Beviá (2002), a rule determines where the facilities should be built and which facility each agent should use. We, instead, define a rule to determine the locations only. Then, each agent chooses the facility that he prefers. If a rule as in Barberà and Beviá (2002) is efficient and strategy-proof, then each agent should be assigned a facility he prefers, as in this paper.

Given a profile and a pair of locations, if an agent is indifferent between the two locations, we cannot tell which facility he chooses. That is why we choose an arbitrary subset of the agents who are indifferent between the two facilities and classify them as the users of the first facility.

Note that the users of each facility are endogenously determined. This statement holds only when the set of users of each facility remains the same. For the “lexicographic” extension of preferences that we discuss in Section 4, however, this might not be the case.

Separability is introduced by Moulin (1987) in a study of surplus sharing. This axiom requires that given assignments for a pair of problems with the same set of agents, if (i) there is a subset of agents whose preferences are the same and (ii) the sum of those agents’ assignments in the two problems remains the same, then the assignment to each agent in this subset should be the same. In resource allocation problems on the domain of single-peaked preferences, Chun (2006) also studies this property. In one public-good problems, this property is vacuous since the assignment is common to all agents. However, in multiple public-good problems, there are subsets of agents whose assignments differ and thus, the idea of separability becomes applicable.

If \(x_1^{\prime }<x_1\), then agent \(i\), with true preference \(R_i\), is better off reporting \(R_i^{\prime }\). If \(x_1^{\prime }>x_1\), then agent \(i\), with true preference \(R_i^{\prime }\), is better off reporting \(R_i\). Note that the argument used to show that \(x_1=x_1^{\prime }\) can also be used to show that for each \(R_i^{\prime \prime }\in \mathcal R \) with \(p(R_i)=p(R_i^{\prime \prime })\), \(x_1=\varphi _1(R_i^{\prime \prime },R_{-\{i\}})\).

I thank the anonymous referee whose comment helped simplifying this proof.

If \(x_1^\mu >x_1\), then agent \(i\), with true preference \(R_i^\mu \), is better off reporting \(R_i\). If \(x_1^\mu <p(R_i^\mu )\), let \(\tilde{R}_i^\mu \in \mathcal R \) be such that \(p(\tilde{R}_i^\mu )=p(R_i^\mu )\) and \(M \tilde{P}_i^\mu x_1^\mu \). By peak only, \(\varphi (\tilde{R}_i^\mu ,R_{-\{i\}})=x^\mu \). Agent \(i\), with true preference \(\tilde{R}_i^\mu \), is better off reporting \(R_i\), in violation of strategy-proofness.

Such a rule is associated with \((\alpha ,\beta )\) such that \(\alpha _n=\cdots =\alpha _0\) and \(\beta _n=\cdots =\beta _0\). Then, for each \(R\in \mathcal R ^N\), \(\varphi (R)=(\alpha _0,\beta _0)\).

Such a rule is associated with \((\alpha ,\beta )\) such that for each \(k\in \{0,\ldots ,n\}\), \(\alpha _k=\beta _k\). Then, for each \(R\in \mathcal R ^N\), \(\varphi _1(R)=\varphi _2(R)\).

The pair of \((\delta _1,\delta _2,\delta _3)\) and \((\delta _1^{\prime },\delta _2^{\prime },\delta _3^{\prime })\) corresponds to \((\alpha _n,\alpha _1,\alpha _0)\) and \((\beta _n,\beta _1,\beta _0)\) in Condition (2) of Theorem 2.

It is easy to check the equivalence of (a) and (a)\(^{\prime }\). (a)\(\rightarrow \)(a)\(^{\prime }\): let \(k^*\in \{1,\ldots ,n\}\) be the largest number such that \(\alpha _{k^*}<\beta _{k^*}\). Then, \(\alpha _n=\beta _n\le \cdots \le \alpha _{k^*+1}=\beta _{k^*+1}\) and \(\alpha _{k^*}=\cdots =\alpha _1<\beta _{k^*}\). The case with \(k^*=n\) corresponds to (a.1)\(^{\prime }\). The case with no such \(k^*\) corresponds to (a.2)\(^{\prime }\). The remaining cases correspond to (a.3)\(^{\prime }\). (a)\(^{\prime }\rightarrow \)(a): suppose otherwise. Then, there is \(k\in \{1,\ldots ,n\}\) such that \(\alpha _k<\beta _k\) and \(\alpha _k<\alpha _1\). It is easy to verify that there is no such \(k\) under condition (a)\(^{\prime }\). Similar arguments are used to show the equivalence of (b) and (b)\(^{\prime }\).

Conditions (a.1)\(^{\prime }\) and (b.2)\(^{\prime }\), conditions (a.2)\(^{\prime }\) and (b.1)\(^{\prime }\), and conditions (a.3)\(^{\prime }\) and (b.2)\(^{\prime }\) are incompatible, respectively.

Miyagawa (1998) characterize the extreme-peaks rule without users only.

To see this, the double median rules discussed in Theorem 3, other than the extreme-peaks rule, are weakly efficient but none is doubly unanimous. Next, consider a rule such that (i) if the peak profile consists of two distinct locations, then the rule selects these two locations, and (ii) otherwise, the rule selects \((0,M)\). This rule is doubly unanimous but not weakly efficient.

Recall that \(l(x,R)=|\mathrm{Left}(x_1,R)|\).

For a survey, see Thomson (2009).

Bochet and Gordon 2012 also study solidarity requirements pertaining to variable populations and variable numbers of facilities.

Since we mainly consider the problem of locating two facilities, throughout the paper, we denote a generic rule for two-facility problems by \(\varphi \), instead of \(\phi ^2\).

Ehlers and Gordon (2011) identifies the class of rules satisfying these three requirements based on the lexicographic extension of preferences. The class of rules that they identify is larger than ours, but there is no direct relation between the two.

Barberà S (2010) Strategy-proof social choice: Arrow KJ, Sen AK, Suzumura K (eds) Handbook of soc choice and welf, vol 2. North-Holland, Amsterdam

Barberà S, Beviá C (2002) Self-selection consistent functions. J Econ Theory 105:263–277CrossRef

Bochet O, Gordon S (2012) Priorities in the location of multiple public facilities. Games Econ Behav 74:52–67CrossRef

Ching S (1997) Strategy-proofness and “median voters”. Int J Game Theory 26:473–490CrossRef

Chun Y (2006) The separability principle in economies with single-peaked preferences. Soc Choice Welf 26:239–253CrossRef

Ehlers L (2002) Multiple public goods and lexicographic preferences: replacement principle. J Math Econ 37:1–15CrossRef

Ehlers L (2003) Multiple public goods, lexicographic preferences, and single-plateaued preference rules. Games Econ Behav 43:1–27CrossRef

Ehlers L, Gordon S (2011) Multiple public goods: strategy-proofness and the lexmax extension. University of Montreal, Mimeo

Ju B (2008) Efficiency and consistency for locating multiple public facilities. J Econ Theory 138:165–183CrossRef

Miyagawa E (1998) Mechanisms for providing a menu of public goods. Dissertation, University of Rochester, Rochester

Miyagawa E (2001) Locating libraries on a street. Soc Choice Welf 18:527–541CrossRef

Moulin H (1980) On strategy-proofness and single peakedness. Pub Choice 35:437–455CrossRef

Moulin H (1987) Equal or proportional division of a surplus, and other methods. Int J Game Theory 16:161–186CrossRef

Thomson W (2009) Consistent allocation rules. University of Rochester, Mimeo

Thomson W (2011) Strategy-proof allocation rules. University of Rochester, Mimeo

Umezawa M (2012) The replacement principle for the provision of multiple public goods on tree networks. Soc Choice Welf 38:211–235CrossRef

Weymark J (2011) Unified appproach to strategy-proofness for single-peaked preferences. Vanderbilt University, Mimeo

Title: Strategy-proof rules for two public goods: double median rules
Author: Eun Jeong Heo
Publication date: 01-10-2013
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 4/2013
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-012-0713-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2013

Measuring the cohesiveness of preferences: an axiomatic analysis

On the generalization and decomposition of the Bonferroni index

Dynamic contests with resource constraints

Welfare, labor supply and heterogeneous preferences: evidence for Europe and the US

A complete and strongly anonymous leximin relation on infinite streams

Process manipulation in unique implementation

Premium Partner